System and method for load balancing in a data network

Patent metadata

Field	Value
Publication number	US-10454830-B2
Application number	US-201615147073-A
Country	US
Kind code	B2
Filing date	May 5, 2016
Priority date	May 5, 2016
Publication date	Oct 22, 2019
Grant date	Oct 22, 2019

Abstract

A method for load balancing in a data network including a plurality of network switches includes receiving a data flow, initiating a path selection process to determine a path between a source network switch and a destination network switch, the path selection process selecting an optimal path based on congestion information of the first network switch and the congestion information of the second network switch, the optimal path corresponding to a path of minimal congestion, and transmitting the data flow along the selected path.

First claim

The invention claimed is:

1. A method for load balancing in a data network comprising a plurality of network switches, the method comprising:
receiving a data flow,
initiating a two-stage path selection process to determine a path between a source network switch and a destination network switch, wherein each path between a source switch and a destination switch comprises:
at least a first hop, a last hop and one or more intermediate hops,
wherein each hop is a portion of the path between the source switch and the destination switch;
a first stage of the two stage path selection process identifying the first and final hops of the path via which to transmit the data flow to the destination switch,
a second stage of the two stage selection process identifying the one or more intermediate hops of the path via which to transmit the data flow to the destination switch;
wherein the first stage of the two stage path selection process identifies an aggregation switch ID, a first hop that corresponds to the path between a source ToR switch and a source aggregation switch in a first pod, and further identifies a second hop that corresponds to a path between a destination ToR switch and a destination aggregation switch in a second pod;
wherein the source aggregation switch and the destination aggregation switch being associated with each other via a pairwise connectivity property, the pairwise connectivity property being such that the source aggregation switch and the destination aggregation switch having the same switch ID and being associated with each other;
the path selection process selecting an optimal path based on congestion information of a first network switch and congestion information of a second network switch, the optimal path corresponding to a path of minimal congestion, and
transmitting the data flow along the selected path.

2. The method for load balancing in a data network in accordance with claim 1 , wherein the first hop and final hop of the path connecting to one or more aggregation switches having the same switch ID.

3. The method for load balancing in a data network in accordance with claim 1 , wherein the first hop being associated with one or more uplinks of the source ToR switch and the final hop being associated with one or more uplinks of the destination ToR switch.

4. The method for load balancing in a data network in accordance with claim 1 , wherein the second stage of the two stage path selection process identifies a second hop and third hop of the path, the second hop being associated with uplinks of a source aggregation switch and the third hop being associated with the uplinks of the destination aggregation switch.

5. The method for load balancing in a data network in accordance with claim 1 , wherein the second stage of the two stage path selection process identifies a hop between the source aggregation switch and a core switch, and wherein the second stage of the two stage path selection process identifies a hop between the destination aggregation switch and the core switch.

6. The method for load balancing in a data network in accordance with claim 5 , wherein the source aggregation switch and the destination aggregation switch connecting to the same core switch.

7. A method for load balancing in a data network in accordance with claim 1 , wherein the congestion information of the first network switch and the congestion information is determined by applying a congestion monitoring process at each switch within the network to determine the congestion information of all uplinks associated with the network switch in an egress or ingress direction.

8. A method for load balancing in a data network in accordance with claim 7 , wherein the congestion information of the first network switch is the congestion information of all uplinks to the first switch in the egress direction, and the congestion information of the second network switch is the congestion information for all uplinks to the second network switch in the ingress direction.

9. A method for load balancing in a data network in accordance with claim 1 , wherein the congestion information is the local congestion information associated with the uplinks of a network switch.

10. A method for load balancing in a data network in accordance with claim 7 , wherein the congestion monitoring process comprises determining the local congestion information for one or more network switches in both the ingress and egress directions.

11. A method for load balancing in a data network in accordance with claim 7 , wherein the congestion monitoring process further comprises, at each ToR switch, updating the local congestion information in the ingress direction based on the number of packets or bytes entering the ToR switch, and updating the local congestion information in the egress direction based on the number of packets or bytes exiting the ToR switch.

12. A method for load balancing in a data network in accordance with claim 1 , wherein the method comprises the additional step of encapsulating the first packet of each data flow with a dedicated header, the header comprising at least the congestion information associated with all uplinks of at least one network switch, the dedicated header being generated by a source network switch.

13. A method for load balancing in a data network in accordance with claim 1 , wherein the method comprises the additional steps of:
transmitting the packet with the dedicated header to a destination network switch,
the destination network switch processing the dedicated header to extract the congestion information,
the destination network switch processing the congestion information to identify an intermediate network switch that corresponds to least congestion.

14. A method for load balancing in a data network in accordance with claim 1 , wherein the method comprises the additional steps of:
encapsulating the first packet of each new data flow with a dedicated header, the source ToR switch encapsulating the first packet with the dedicated header to create a request packet, and
transmitting the request packet and dedicated header to a destination ToR switch.

15. A method for load balancing in a data network in accordance with claim 1 , wherein the method comprises the additional steps of:
receiving the request packet by the destination ToR switch,
processing the request packet to determine a maximum level of congestion of the first and final hops of each path,
selecting an aggregation switch ID that corresponds to the least congestion in the first and final hops, and
generating a response packet and transmitting the response packet to an aggregation switch matching the aggregation switch ID.

16. A method for load balancing in a data network in accordance with claim 14 , wherein the request packet comprises a first tag identifying to identify the packet as a path selection request packet, a second tag identifying a stage of the path selection process, a third tag identifying the number of congestion metrics and a congestion data field comprising the congestion information associated with all the uplinks in the egress direction of the source ToR switch.

17. A method for load balancing in a data network in accordance with claim 14 , wherein the step of generating the response packet comprises the additional steps of:
copying the request packet,
swapping the source and destination IP addresses,
setting the second tag in the dedicated header to identify a second stage of path selection, and
clearing the third tag and clearing the congestion data.

18

Assignees

• Univ City Hong Kong

Inventors

• Xu Hong
• Wang Peng

Classifications

• H04L45/245

  Link aggregation, e.g. trunking · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L47/11

  Identifying congestion · CPC title

• H04L12/4633

  Interconnection of networks using encapsulation techniques, e.g. tunneling · CPC title