Load-balancing algorithms for data center networks

Abstract

Multipath load-balancing algorithms, which can be used for data center networks (DCNs), are provided. A multipath load-balancing algorithm can be, for example, a distributed multipath load-balancing algorithm or a centralized multipath load-balancing algorithm. Algorithms of the subject invention can be used for, e.g., hierarchical DCNs and/or fat-tree DCNs. Algorithms of the subject invention are effective and scalable and significantly outperform existing solutions.

What is claimed is: 
     
         1 . A method of load balancing in a network, comprising:
 receiving, by a switch, a packet;   looking up, by the switch, a packet header of the packet to check whether the packet belongs to an existing flow;   if the packet belongs to an existing flow, forwarding the packet based on information in a flow table of the switch, and otherwise, creating a new entry in the flow table for the packet and calculating the next hop;   determining if the next hop is an upstream or downstream layer of the network based on a destination IP address; and   comparing load values of links to the next layer and selecting a worst-fit link.   
     
     
         2 . The method according to  claim 1 , wherein, if no viable link to the next layer exists, the method further comprises sending, by the switch, the packet back to the previous hop for backtracking. 
     
     
         3 . The method according to  claim 1 , wherein each entry in the flow table of the switch includes at least one piece of information selected from the group consisting of: source address; source port number; destination address; destination port number; and outgoing link on which the flow is assigned. 
     
     
         4 . The method according to  claim 1 , wherein each entry in the flow table of the switch includes all of the following pieces of information: source address; source port number; destination address; destination port number; and outgoing link on which the flow is assigned. 
     
     
         5 . The method according to  claim 1 , wherein the network is a fat tree based data center network. 
     
     
         6 . The method according to  claim 1 , wherein the flow table of the switch determines whether the packet is treated as part of a new flow, treated as part of an existing flow, or backtracked. 
     
     
         7 . The method according to  claim 1 , wherein the network is represented by a model, such that the network is modeled as a directed graph G=(H ∪S, L), wherein a node h ∈H is a host, wherein a node s ∈S is a switch, and wherein an edge (n i , n j ) ∈L is a link connecting a switch with another switch or a host. 
     
     
         8 . A method of load balancing in a network, comprising:
 checking which layer of the network a packet should go through based on locations of a source host of the network and a destination host of the network;   determining, by a central controller, a bottleneck link of each potential path corresponding to a different connecting layer switch;   comparing, by the central controller, the available bandwidth of all the potential paths and finding the path with the maximum bandwidth; and   if the maximum bandwidth is greater than a demand of a flow of the network, then selecting the corresponding path for the flow, and otherwise, determining that no viable path exists for the packet.   
     
     
         9 . The method according to  claim 8 , further comprising, after determining the bottleneck link of each potential path corresponding to a different connecting layer switch, determining a path from the source host to the destination host. 
     
     
         10 . The method according to  claim 8 , wherein checking which layer of the network the packet should go through comprises determining which top-layer layer of the network the packet should go through. 
     
     
         11 . The method according to  claim 8 , wherein the network is a fat tree based data center network. 
     
     
         12 . A system for load balancing a network, wherein the system comprises one of the following:
 a) a switch configured to:
 receiving a packet;
 look up a packet header of the packet to check whether the packet belongs to an existing flow; 
 if the packet belongs to an existing flow, forward the packet based on information in a flow table of the switch, and otherwise, create a new entry in the flow table for the packet and calculate the next hop; 
 
 determine if the next hop is an upstream or downstream layer of the network based on a destination IP address; and 
 compare load values of links to the next layer and selecting a worst-fit link; or 
   b) a central controller configured to:
 check which layer of the network a packet should go through based on locations of a source host of the network and a destination host of the network; 
 determine a bottleneck link of each potential path corresponding to a different connecting layer switch; 
 compare the available bandwidth of all the potential paths and find the path with the maximum bandwidth; and 
 if the maximum bandwidth is greater than a demand of a flow of the network, then select the corresponding path for the flow, and otherwise, determine that no viable path exists for the packet. 
   
     
     
         13 . The system according to  claim 12 , wherein the system comprises the switch, and wherein the switch is further configured to send the packet back to the previous hop for backtracking if no viable link to the next layer exists. 
     
     
         14 . The system according to  claim 12 , wherein the system comprises the switch, and wherein each entry in the flow table of the switch includes at least one piece of information selected from the group consisting of: source address; source port number; destination address; destination port number; and outgoing link on which the flow is assigned. 
     
     
         15 . The system according to  claim 12 , wherein the system comprises the switch, and wherein the flow table of the switch determines whether the packet is treated as part of a new flow, treated as part of an existing flow, or backtracked. 
     
     
         16 . The system according to  claim 12 , wherein the system comprises the switch, and wherein the network is represented by a model, such that the network is modeled as a directed graph G=(H ∪S, L), wherein a node h ∈H is a host, wherein a node s ∈S is a switch, and wherein an edge (n i , n j ) ∈L is a link connecting a switch with another switch or a host. 
     
     
         17 . The system according to  claim 12 , wherein the system comprises the central controller, and wherein the central controller is further configured to determine a path from the source host to the destination host after determining the bottleneck link of each potential path corresponding to a different connecting layer switch. 
     
     
         18 . The system according to  claim 12 , wherein the system comprises the central controller, and wherein checking which layer of the network the packet should go through comprises determining which top-layer layer of the network the packet should go through. 
     
     
         19 . The system according to  claim 12 , further comprising a computer-readable medium having the model representing the network stored thereon. 
     
     
         20 . The system according to  claim 12 , further comprising a processor in operable communication with the switch.