BALANCING LOAD IN A NETWORK, SUCH AS A DATA CENTER NETWORK, USING FLOW BASED ROUTING

• US 20120287791A1
• Filed: 05/13/2011
• Published: 11/15/2012
• Est. Priority Date: 05/13/2011
• Status: Active Grant

• Current Assignee: Polytechnic Institute Of New York University (New York University)
• Original Assignee: Polytechnic Institute Of New York University (New York University)
• Inventors: CHAO, H. Jonathan, Xi, Kang
• Granted Patent: US 8,879,397 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 61/2517 using port numbers

Abstract

Load balancing is performed in a network using flow-based routing. For example, upon detection of a big flow, one or more alternative paths from a source host to a destination host in the network may be discovered by probing the network and generating, for each of the one or more alternative paths, an association of the packet header information of the big flow to an alternative path discovered using results of probing the network. Upon congestion in a path currently being used by the big flow, an alternative path that is not congested is selected from the one or more discovered alternative paths. The packet header information of the big flow is altered using the generated association of the packet header information to the selected alternative path such that the big flow will be transmitted using the selected alternative path.

Claims

1. A computer-implemented method comprising:

detecting, with a computer system including one or more computers in a network, a flow of packets;

identifying the detected flow as a big flow, the big flow having packet header information identifying a source host and a destination host of the big flow;

probing, with the computer system and responsive to detection of the big flow, the network by altering the packet header information to discover one or more alternative paths from the source host to the destination host in the network;

generating, with the computer system and for each of the one or more alternative paths, an association of the packet header information to an alternative path discovered using results of probing the network and identified by at least one of an alternative source port and an alternative destination port;

determining if congestion exists on a path currently being used by the big flow in the network;

selecting, with the computer system and responsive to a determination of the existence of congestion on the path currently being used, an alternative path that is from the one or more alternative paths and that is not congested; and

altering, with the computer system, the packet header information of the big flow using the generated association of the packet header information to the selected alternative path such that the big flow will be transmitted from the source host to the destination host using the selected alternative path.

2. The computer-implemented method of claim 1, wherein probing the network comprises:

creating one or more probe packets, wherein each of the one or more probe packets has header information similar to the packet header information by

(i) setting values of a source Internet Protocol (IP) address, a destination IP address, and a protocol field in the header information of each of the one or more probe packets to values of corresponding fields in the packet header information, and

(ii) setting at least one of a source port number and a destination port number in the header information of each of the one or more probe packets to a port number that is different from the corresponding port number in the packet header information;

setting values of a time-to-live field in each of the one or more probe packets such that the probe packets will be sent into the network at different points along an alternative path; and

transmitting the one or more probe packets in the network.

3. The computer-implemented method of claim 2, further comprising:

receiving the result of each of the one or more probe packets, wherein the results collectively indicate a path taken by the one or more probe packets from the source host towards the destination host; and

reconstructing an alternative path from the source host to the destination host using the result of each of the one or more probe packets.

4. The computer-implemented method of claim 2, wherein the one or more probe packets are transmitted such that the one or more probe packets traverse multiple hops of the same alternative path and multiple alternative paths in parallel.

5. The computer-implemented method of claim 1, wherein each of the altered packet header information associated with each of the one or more alternative paths differs from the packet header information in at least one of a source port number and a destination port number.

6. The computer-implemented method of claim 1, wherein the flow has characteristics of a big flow when it lasts longer than a pre-determined duration threshold.

7. The computer-implemented method of claim 1, wherein the flow has characteristics of a big flow when it has a bit rate higher than a pre-determined rate threshold.

8. The computer-implemented method of claim 1, wherein the flow has characteristics of a big flow when it both lasts longer than a pre-determined duration threshold and has a bit rate higher than a pre-determined rate threshold.

9. The computer-implemented method of claim 1, wherein the packet header information includes a source Internet Protocol (IP) address field, a destination IP address field, a protocol field, a source port number field and a destination port number field.

10. The computer-implemented method of claim 1, wherein each of the one or more associations of the packet header information to an alternative path is generated by associating at least one of a source port number and a destination port number of the packet header information to at least one of a source port number and a destination port number corresponding to the alternative path.

11. The computer-implemented method of claim 1 further comprising:

transmitting the association of the packet header information to the selected alternative path to the destination host.

12. The computer-implemented method of claim 11 further comprising:

storing the association of the packet header information to the selected alternative path at the destination host.

13. The computer-implemented method of claim 12, wherein the association is stored as an association of at least one of a source port number and destination port number of the selected alternative path to at least one of a source port number and destination port number of the packet header information.

14. The computer-implemented method of claim 1, wherein altering the packet header information using the generated association comprises altering a value of at least one of a source port number and a destination port number in the packet header information to a value of corresponding fields of the selected alternative path.

15. The computer-implemented method of claim 1 further comprising:

replacing, upon receipt of the big flow at the destination host, at least one of a value of source port number or destination port number in the altered packet header information with a value of corresponding fields of original packet header information of the big flow.

16. The computer-implemented method of claim 15, wherein replacing the at least one of the value of source port number or destination port number in the altered packet header information is performed using the association of at least one of a source port number and a destination port number of the selected alternative path to at least one of a source port number and destination port number of the packet header information stored at the destination host.

17. The computer-implemented method of claim 1, wherein the big flow is transmitted to the destination host using an equal cost multi path (ECMP) routing protocol.

18. The computer-implemented method of claim 1, wherein the act of selecting the alternative path is performed by the source host.

19. The computer-implemented method of claim 1, wherein the act of selecting the alternative path is performed by a controller in the network that monitors traffic in the network.

20. A computer-implemented method comprising:

detecting, with a computer system including one or more computers in a network, a flow of packets;

identifying the detected flow as a big flow, the big flow having packet header information identifying a source host and a destination host of the big flow;

probing, with the computer system and responsive to detection of the big flow, the network by altering the packet header information to discover one or more alternative paths from the source host to the destination host in the network;

generating, with the computer system and for each of the one or more alternative paths, an association of the packet header information to an alternative path using results of probing the network and identified by at least one of an alternative source port and an alternative destination port;

notifying, with the computer system, to a controller in the network that is monitoring traffic in the network, the big flow and the one or more alternative paths;

determining, with the controller, that congestion exists on a path currently being used by the big flow in the network;

selecting, with the controller and responsive to a determination of the existence of congestion on the path currently being used by the big flow, an alternative path from the one or more alternative paths that is not congested;

sending, with the controller, a re-route notification including a path identification of the selected alternative path to the source host; and

altering, upon a receipt of the re-route notification, the packet header information of the big flow using the generated association such that the big flow will be transmitted from the source host to the destination host using the selected alternative path.

21. Apparatus comprising:

a) at least one processor;

b) at least one input device; and

c) at least one storage device storing program instructions which, when executed by the at least one processor, performs a method including;

detecting, with a computer system including one or more computers in a network, a flow of packets,

identifying the detected flow as a big flow, the big flow having packet header information identifying a source host and a destination host of the big flow,

probing, with the computer system and responsive to detection of the big flow, the network by altering the packet header information to discover one or more alternative paths from the source host to the destination host in the network,

generating, with the computer system and for each of the one or more alternative paths, an association of the packet header information to an alternative path discovered using results of probing the network and identified by at least one of an alternative source port and an alternative destination port,

determining if congestion exists on a path currently being used by the big flow in the network,

selecting, with the computer system and responsive to a determination of the existence of congestion on the path currently being used by the big flow, an alternative path that is from the one or more alternative paths and that is not congested, and

altering, with the computer system, the packet header information of the big flow using the generated association of the packet header information to the selected alternative path such that the big flow will be transmitted from the source host to the destination host using the selected alternative path.

22. An article of manufacture comprising:

a machine-readable medium having instructions which, when executed by a machine, performs a method including;

detecting, with a computer system including one or more computers in a network, a flow of packets,

identifying the detected flow as a big flow, the big flow having packet header information identifying a source host and a destination host of the big flow,

probing, with the computer system and responsive to detection of the big flow, the network by altering the packet header information to discover one or more alternative paths from the source host to the destination host in the network,

generating, with the computer system and for each of the one or more alternative paths, an association of the packet header information to an alternative path discovered using results of probing the network and identified by at least one of an alternative source port and an alternative destination port,

determining if congestion exists on a path currently being used by the big flow in the network,

selecting, with the computer system and responsive to a determination of the existence of congestion on the path currently being used by the big flow, an alternative path that is from the one or more alternative paths and that is not congested, and

altering, with the computer system, the packet header information of the big flow using the generated association of the packet header information to the selected alternative path such that the big flow will be transmitted from the source host to the destination host using the selected alternative path.