Method and system for global routing and bandwidth sharing

• US 20040246905A1
• Filed: 06/06/2003
• Published: 12/09/2004
• Est. Priority Date: 06/06/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dunagan, John David, Wang, Jiahe
• Granted Patent: US 7,376,121 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 63/029 Firewall traversal, e.g. tunnelling or, creating pinholes

Abstract

Disclosed is a routing and bandwidth allocation system that maximizes network throughput while maintaining global fairness in the sharing of network resources. From gathered global network information (such as inter-node communications patterns and network topology), routing tables and bandwidth allocation policies are computed for routers. In some embodiments, the computations involve applying multi-commodity flow methods to provide a “max-fair” allocation of network resources. While in some embodiments each router collects global network information and then locally produces its own routing and bandwidth allocation tables, it can be simpler and cheaper in terms of both computation and security for a centralized, trusted control unit to perform the calculations and then to distribute the results to the routers. The computed bandwidth policies can leave some bandwidth unallocated to handle unexpected surges in demand. The computed routing tables can include multiple paths leading to greater link utilization and to robustness to link failure.

Claims

1. In a network communications environment comprising a plurality of network nodes, a plurality of communications links among network nodes, and a control unit, the plurality of network nodes comprising a plurality of host network nodes and a plurality of router network nodes, a method for the control unit to produce routing information, the method comprising:

receiving topology information about the network communications environment;

receiving inter-node communications information; and

computing routing information for at least one router network node, the computing based, at least in part, on the received topology information and on the received inter-node communications information.

2. The method of claim 1 wherein the network communications environment comprises a virtual private network and further comprises a communications link to the Internet.

3. The method of claim 1 wherein the network communications environment comprises a neighborhood network and further comprises a communications link to the Internet.

4. The method of claim 1 wherein the network communications environment is a hierarchical communications environment and wherein at least one of the plurality of communications links comprises a virtual communications link among network nodes, the virtual communications link comprising a plurality of physical communications links.

5. The method of claim 4 wherein the network communications environment comprises an Internet Service Provider peering environment.

6. The method of claim 1 wherein at least one of the plurality of communications links is selected from the group consisting of:

a point-to-point link, a broadcast link, a wired link, a wireless link, an electrical link, an optical fiber link, an infrared link, and a radio link.

7. The method of claim 1 wherein at least one of the plurality of communications links is selected from the group consisting of:

a virtual communications link comprising a plurality of physical communications links and a multi-hop communications link comprising a plurality of single-hop communications links.

8. The method of claim 1 wherein the control unit is one of the plurality of network nodes.

9. The method of claim 1 wherein at least one of the plurality of network nodes is both a host network node and a router network node.

10. The method of claim 1 wherein receiving topology information comprises receiving topology information from at least one router network node.

11. The method of claim 10 wherein receiving topology information comprises receiving information selected from the group consisting of:

a capacity of at least one communications link connected to the router network node and an identification of at least one other network node connected to a communications link connected to the router network node.

12. The method of claim 1 wherein receiving inter-node communications information comprises receiving inter-node communications information from at least one host network node.

13. The method of claim 12 wherein receiving inter-node communications information comprises receiving information selected from the group consisting of:

an absolute expected flow rate from the host network node to another network node and a relative expected flow rate from the host network node to another network node, the expected flow rate relative to expected flow rates from the host network node to other network nodes.

14. The method of claim 1 wherein computing routing information comprises constructing a map of the network communications environment from the received topology information.

15. The method of claim 1 wherein computing routing information comprises normalizing the received inter-node communications information.

16. The method of claim 1 wherein receiving inter-node communications information comprises receiving a pair of expected flow rates, a first member of the pair being an expected flow rate from a first network node to a second network node, and a second member of the pair being an expected flow rate from the second network node to the first network node, and wherein computing routing information comprises using only the smaller flow rate of the pair.

17. The method of claim 1 wherein receiving inter-node communications information comprises receiving expected flow rates from source network nodes to destination network nodes, and wherein computing routing information comprises treating a set of expected flow rates having a common destination network node as a single expected flow rate.

18. The method of claim 1 wherein the plurality of communications links comprises a plurality of wireless links, wherein flow on a first wireless communications link interferes with flow on a second wireless communications link, and wherein computing routing information comprises constraining an allocated flow on the second wireless communications link to account for the interference.

19. The method of claim 1 wherein computing routing information comprises constraining a fraction of an allocated flow rate routed across one communications link.

20. The method of claim 1 wherein computing routing information comprises constraining a fraction of an allocated flow rate routed through one router network node.

21. The method of claim 1 wherein computing routing information comprises applying a max-fair algorithm to the received topology information and to the received inter-node communications information.

22. The method of claim 21 wherein applying a max-fair algorithm comprises computing an expected flow rate for a pair of network nodes.

23. The method of claim 22 wherein applying a max-fair algorithm comprises maximizing a sum of allocated flow rates within the network communications environment subject to a constraint of maximizing a minimum of ratios of allocated flow rates to expected flow rates.

24. The method of claim 1 wherein computing routing information for at least one router network node comprises computing routing information for the control unit.

25. The method of claim 1 wherein computing routing information for at least one router network node comprises computing routing information for a router network node distinct from the control unit, the method further comprising:

sending the computed routing information to the router network node.

26. The method of claim 1 wherein computing routing information for at least one router network node comprises computing multipath routing information, the multipath routing information comprising routing probabilities for a plurality of paths from the router network node to a destination network node.

27. The method of claim 1 further comprising:

receiving updated topology information about the network communications environment;

receiving updated inter-node communications information; and

computing updated routing information for at least one router network node, the computing based, at least in part, on the received updated topology information and on the received updated inter-node communications information.

28. The method of claim 27 wherein receiving updated topology information, receiving updated inter-node communications information, and computing updated routing information are performed periodically.

29. The method of claim 27 wherein computing updated routing information comprises removing from consideration a network node that does not provide updated information.

30. The method of claim 1 further comprising:

computing bandwidth allocation information for at least one router network node, the computing based, at least in part, on the received topology information and on the received inter-node communications information.

31. The method of claim 30 wherein computing bandwidth allocation information comprises constructing a map of the network communications environment from the received topology information.

32. The method of claim 30 wherein computing bandwidth allocation information comprises normalizing the received inter-node communications information.

33. The method of claim 30 wherein receiving inter-node communications information comprises receiving a pair of expected flow rates, a first member of the pair being an expected flow rate from a first network node to a second network node, and a second member of the pair being an expected flow rate from the second network node to the first network node, and wherein computing bandwidth allocation information comprises using only the smaller flow rate of the pair.

34. The method of claim 30 wherein receiving inter-node communications information comprises receiving expected flow rates from source network nodes to destination network nodes, and wherein computing bandwidth allocation information comprises treating a set of expected flow rates having a common destination network node as a single expected flow rate.

35. The method of claim 30 wherein computing bandwidth allocation information comprises applying a max-fair algorithm to the received topology information and to the received inter-node communications information.

36. The method of claim 35 wherein applying a max-fair algorithm comprises computing an expected flow rate for a pair of network nodes.

37. The method of claim 36 wherein applying a max-fair algorithm comprises maximizing a sum of allocated flow rates within the network communications environment subject to a constraint of maximizing a minimum of ratios of allocated flow rates to expected flow rates.

38. The method of claim 30 wherein computing bandwidth allocation information for at least one router network node comprises computing bandwidth allocation information for the control unit.

39. The method of claim 30 wherein computing bandwidth allocation information for at least one router network node comprises computing bandwidth allocation information for a router network node distinct from the control unit, the method further comprising:

sending the computed bandwidth allocation information to the router network node.

40. The method of claim 30 wherein computing bandwidth allocation information for at least one router network node comprises, for a communications link outgoing from the router network node, computing allocations of bandwidth received over communications links incoming to the router network node.

41. The method of claim 30 further comprising:

receiving updated topology information about the network communications environment;

receiving updated inter-node communications information; and

computing updated bandwidth allocation information for at least one router network node, the computing based, at least in part, on the received updated topology information and on the received updated inter-node communications information.

42. The method of claim 41 wherein receiving updated topology information, receiving updated inter-node communications information, and computing updated bandwidth allocation information are performed periodically.

43. The method of claim 41 wherein computing updated bandwidth allocation information comprises removing from consideration a network node that does not provide updated information.

44. The method of claim 30 further comprising:

receiving priority information about a network node;

and wherein computing bandwidth allocation information comprises giving priority to bandwidth from that network node.

45. The method of claim 30 further comprising:

receiving a bandwidth reservation factor;

and wherein computing bandwidth allocation information comprises allocating only a fraction of available bandwidth, the fraction determined, at least in part, by the bandwidth reservation factor.

46. A computer-readable medium containing computer-executable instructions for performing a method for a control unit in a network communications environment to produce routing information, the method comprising:

receiving topology information about the network communications environment;

receiving inter-node communications information; and

computing routing information for at least one router network node, the computing based, at least in part, on the received topology information and on the received inter-node communications information.

47. In a network communications environment comprising a plurality of network nodes, a plurality of communications links among network nodes, and a control unit, the plurality of network nodes comprising a plurality of host network nodes and a plurality of router network nodes, a method for a router network node to route information to the router'"'"'s outgoing communications links, the method comprising:

sending to the control unit topology information about the network communications environment;

receiving from the control unit routing information;

receiving from the control unit bandwidth allocation information;

choosing an outgoing communications link for sending information, the choosing based, at least in part, on the received routing information; and

at least when an outgoing communications link is congested, allocating bandwidth of the outgoing communications link among information received over incoming communications links, the allocating based, at least in part, on the received bandwidth allocation information.

48. The method of claim 47 wherein at least one of the router'"'"'s outgoing communications links is selected from the group consisting of:

a point-to-point link, a broadcast link, a wired link, a wireless link, an electrical link, an optical fiber link, an infrared link, and a radio link.

49. The method of claim 47 wherein at least one of the router'"'"'s outgoing communications links is selected from the group consisting of:

a virtual communications link comprising a plurality of physical communications links and a multi-hop communications link comprising a plurality of single-hop communications links.

50. The method of claim 47 wherein the router network node is both a host network node and a router network node.

51. The method of claim 47 wherein sending topology information comprises sending information selected from the group consisting of:

a capacity of at least one communications link connected to the router network node and an identification of at least one other network node connected to a communications link connected to the router network node.

52. The method of claim 47 wherein receiving routing information comprises receiving multipath routing information, the multipath routing information comprising routing probabilities for a plurality of paths from the router network node to a destination network node.

53. The method of claim 47 wherein receiving bandwidth allocation information comprises, for a communications link outgoing from the router network node, receiving allocations of bandwidth received over communications links incoming to the router network node.

54. The method of claim 47 further comprising:

sending to the control unit updated topology information about the network communications environment;

receiving from the control unit updated routing information; and

receiving from the control unit updated bandwidth allocation information.

55. The method of claim 54 wherein sending updated topology information, receiving updated routing information, and receiving updated bandwidth allocation information are performed periodically.

56. The method of claim 47 further comprising:

choosing an outgoing communications link for sending information, the choosing based, at least in part, on an amount of unallocated bandwidth of the outgoing communications link.

57. A computer-readable medium containing computer-executable instructions for performing a method for a router network node in a network communications environment to route information to the router'"'"'s outgoing communications links, the method comprising:

sending to a control unit topology information about the network communications environment;

receiving from the control unit routing information;

receiving from the control unit bandwidth allocation information;

choosing an outgoing communications link for sending information, the choosing based, at least in part, on the received routing information; and

at least when an outgoing communications link is congested, allocating bandwidth of the outgoing communications link among information received over incoming communications links, the allocating based, at least in part, on the received bandwidth allocation information.

58. In a network communications environment comprising a plurality of network nodes, a plurality of communications links among network nodes, and a control unit, the plurality of network nodes comprising a plurality of host network nodes and a plurality of router network nodes, a method for a host network node to provide information to the control unit, the method comprising:

collecting inter-node communications information;

sending to the control unit the collected inter-node communications information;

collecting updated inter-node communications information; and

sending to the control unit the collected updated inter-node communications information.

59. The method of claim 58 wherein the host network node is both a host network node and a router network node.

60. The method of claim 58 wherein collecting inter-node communications information comprises collecting information selected from the group consisting of:

an absolute expected flow rate from the host network node to another network node and a relative expected flow rate from the host network node to another network node, the expected flow rate relative to expected flow rates from the host network node to other network nodes.

61. The method of claim 58 wherein collecting and sending updated inter-node communications information is performed periodically.

62. The method of claim 58 further comprising:

sending to the control unit priority information about the host network node.

63. A computer-readable medium containing computer-executable instructions for performing a method for a host network node in a network communications environment to provide information to a control unit, the method comprising:

collecting inter-node communications information;

sending to the control unit the collected inter-node communications information;

collecting updated inter-node communications information; and

sending to the control unit the collected updated inter-node communications information.

64. A control unit system for producing routing information, the control unit system comprising:

a communications receiver configured for receiving topology information about a network communications environment and for receiving inter-node communications information;

a processor configured for computing routing information for at least one router network node in the network communications environment, the computing based, at least in part, on received topology information and on received inter-node communications information; and

a routing information data structure containing routing information computed by the processor.

65. The control unit system of claim 64 wherein the router network node is distinct from the control unit system, the control unit system further comprising:

a communications sender configured for sending computed routing information to the router network node.

66. The control unit system of claim 64 wherein the processor is further configured for computing bandwidth allocation information for the router network node, the computing based, at least in part, on the received topology information and on the received inter-node communications information;

the control unit system further comprising;

a bandwidth allocation data structure containing bandwidth allocation information computed by the processor.

67. The control unit system of claim 66 wherein the router network node is distinct from the control unit system, the control unit system further comprising:

a communications sender configured for sending computed bandwidth allocation information to the router network node.

68. A router network node system for routing information to the router'"'"'s outgoing communications links, the router network node system comprising:

a plurality of outgoing communications links;

a plurality of incoming communications links;

a communications sender configured for sending topology information about a network communications environment;

a communications receiver configured for receiving routing information and for receiving bandwidth allocation information;

a routing information data structure containing received routing information;

a bandwidth allocation data structure containing received bandwidth allocation information; and

a routing processor configured for choosing an outgoing communications link for sending information, the choosing based, at least in part, on the received routing information and, at least when an outgoing communications link is congested, for allocating bandwidth of the outgoing communications link among information received over incoming communications links, the allocating based, at least in part, on the received bandwidth allocation information.

69. A host network node system for providing information, the host network node system comprising:

a collector configured for collecting inter-node communications information;

an inter-node communications data structure containing collected inter-node communications information; and

a communications sender configured for sending collected inter-node communications information.

70. The host network node system of claim 69 further comprising:

a priority data structure containing priority information about the host network node; and

wherein the communications sender is further configured for sending the priority information.

71. In a network communications environment, a system for producing and using routing information, the system comprising:

a plurality of network nodes, the plurality comprising a plurality of host network nodes and a plurality of router network nodes;

a plurality of communications links among network nodes;

a control unit comprising a communications receiver configured for receiving topology information about the network communications environment and for receiving inter-node communications information, a processor configured for computing routing information for at least one router network node, the computing based, at least in part, on received topology information and on received inter-node communications information, a routing information data structure containing routing information computed by the processor, and a communications sender configured for sending computed routing information;

the router network node comprising a communications sender configured for sending topology information about the network communications environment, a communications receiver configured for receiving routing information, a routing information data structure containing received routing information, and a routing processor configured for choosing an outgoing communications link for sending information, the choosing based, at least in part, on the received routing information; and

a host network node comprising a collector configured for collecting inter-node communications information, an inter-node communications data structure containing collected inter-node communications information, and a communications sender configured for sending collected inter-node communications information.

72. The system of claim 71 wherein the processor of the control unit is further configured for computing bandwidth allocation information for the router network node, the computing based, at least in part, on received topology information and on received inter-node communications information;

wherein the control unit further comprises a bandwidth allocation data structure containing bandwidth allocation information computed by the processor;

wherein the communications receiver of the router network node is further configured for receiving bandwidth allocation information;

wherein the router network node further comprises a bandwidth allocation data structure containing received bandwidth allocation information; and

wherein the routing processor is further configured for, at least when an outgoing communications link is congested, allocating bandwidth of the outgoing communications link among information received over incoming communications links, the allocating based, at least in part, on the received bandwidth allocation information.

73. A computer-readable medium containing an inter-node communications information data structure for a host network node, the inter-node communications information data structure comprising:

a first data field containing data identifying a second network node distinct from the host network node; and

a second data field containing data representing an expected flow rate of communications from the host network node to the second network node.

74. The inter-node communications information data structure of claim 73 wherein the data in the second data field representing an expected flow rate are selected from the group consisting of:

an absolute expected flow rate from the host network node to the second network node and a relative expected flow rate from the host network node to the second network node, the expected flow rate relative to expected flow rates from the host network node to other network nodes.

75. The inter-node communications information data structure of claim 73 further comprising:

a third data field containing data identifying a third network node distinct from the host network node and distinct from the second network node; and

a fourth data field containing data representing an expected flow rate of communications from the host network node to the third network node.

76. The inter-node communications information data structure of claim 73 further comprising:

a third data field containing data representing priority information about the host network node.

77. A computer-readable medium containing a multipath routing information data structure for a router network node, the multipath routing information data structure comprising:

a first data field containing data identifying a destination network node;

a second data field containing data identifying a first path from the router network node to the destination network node;

a third data field containing data representing a routing probability for first path;

a fourth data field containing data representing a second path from the router network node to the destination network node; and

a fifth data field containing data representing a routing probability for the second path.

78. The multipath routing information data structure of claim 77 wherein the data in the second data field identifying a first path comprise an identifier of a next hop on the first path from the router network node to the destination network node.

79. The multipath routing information data structure of claim 77 further comprising:

a sixth data field containing data identifying a second destination network node; and

a seventh data field containing data identifying a path from the router network node to the second destination network node.

80. A computer-readable medium containing a bandwidth allocation information data structure for a router network node, the bandwidth allocation information data structure comprising:

a first data field containing data representing an outgoing communications link of the router network node; and

a second data field containing data representing, for the outgoing communications link, allocations of bandwidth received over incoming communications links of the router network node.

81. The bandwidth allocation information data structure of claim 80 further comprising:

a third data field containing data representing a second outgoing communications link of the router network node; and

a fourth data field containing data representing, for the second outgoing communications link, allocations of bandwidth received over incoming communications links of the router network node.