Method and system for global routing and bandwidth sharing

• US 7,376,121 B2
• Filed: 06/06/2003
• Issued: 05/20/2008
• Est. Priority Date: 06/06/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dunagan, John David, Wang, Jiahe
• Primary Examiner(s): Levitan; Dmitry
• Application Number:
  US10/455,877
• Publication Number:
  US 20040246905A1
• Time in Patent Office: 1,810 Days
• Field of Search: 370/229, 370231-235, 370/351, 370/357, 370/386, 370/388, 370/389, 370/392, 370/400, 370/422, 370/402, 370/229.H
• US Class Current: 370/351
• 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;

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, wherein computing routing information comprises applying a max-fair algorithm to the received topology information and to the received inter-node communications information using a multi-commodity flow implementation, wherein applying the max-fair algorithm comprises first satisfying demand in a fair manner and then satisfying remaining demand by maximizing a sum of allocated flow rates;

computing, at the control unit, 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, wherein computing bandwidth allocation information comprises applying the max-fair algorithm to the received topology information and to the received inter-node communications information using the multi-commodity flow implementation; and

sending the bandwidth allocation information to the at least one router network node.

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 1 wherein computing routing information comprises constructing a map of the network communications environment from the received topology information.

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

15. The method of claim 1 wherein receiving inter-node communications information comprises receiving a pair of data flow demands, a first member of the pair being a data flow demand from a first network node to a second network node, and a second member of the pair being a data flow demand from the second network node to the first network node, and wherein computing routing information comprises using only the smaller data flow demand of the pair.

16. 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.

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

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

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

20. The method of claim 19 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.

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

22. 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.

23. 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.

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

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

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

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

28. The method of claim 1 wherein receiving inter-node communications information comprises receiving a pair of data flow demands, a first member of the pair being a data flow demand from a first network node to a second network node, and a second member of the pair being a data flow demand from the second network node to the first network node, and wherein computing bandwidth allocation information comprises using only the smaller data flow demand of the pair.

29. The method of claim 1 wherein applying a max-fair algorithm comprises computing data flow demand for a pair of network nodes.

30. The method of claim 29 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 data flow demands.

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

32. The method of claim 1 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.

33. The method of claim 1 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.

34. 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 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.

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

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

37. The method of claim 1 further comprising:

receiving priority information about a data flow of a network node;

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

38. The method of claim 1 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.

39. A computer-readable medium encoded with 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;

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, wherein computing routing information comprises applying a max-fair algorithm to the received topology information and to the received inter-node communications information using a multi-commodity flow implementation, wherein applying the max-fair algorithm comprises first satisfying demand in a fair manner and then satisfying remaining demand by maximizing a sum of allocated flow rates;

computing, at the control unit, 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, wherein computing bandwidth allocation information comprises applying the max-fair algorithm to the received topology information and to the received inter-node communications information using the multi-commodity flow implementation; and

sending the bandwidth allocation information to the at least one router network node.