Hash based ECMP load balancing with non-power-of-2 port group sizes
AssigneeGoogle Inc.
InventorMikhail Markine
Life of this patent
Estimating the term…
Abstract
The invention is directed to optimizing load balancing for equal cost multiple path (ECMP) network routing by improving the load balancing of network data traffic across multiple equal cost next hop egress network links that have the same next hop routing cost. At least one of the various embodiments may enable improve load balancing of egress network links by programming network routing tables and conducting diagnostic processes and testing to determine if a programmed network routing table optimally load balances the outgoing the network data traffic among the equal cost next hop egress network links. If an embodiment determines that a programmed network routing table is load balancing less effectively than desired, it may re-program the network routing table(s).
Claims20
A system for load balancing data flow, the system comprising:
- a network device having:
- a plurality of network interfaces for ingress network links and egress network links;
- a plurality of switching chips;
- for each of the plurality of switching chips, a routing table with respective routing table entries to load balance forwarded data;
- and
- an interface through which the routing table entries are remotely programmed by an automated process executing on a remote processor;
- wherein the network device is configured to:
- obtain, from the remote processor via the interface, routing table entries for at least one switching chip within the network device, wherein a first set of routing table entries corresponding to a first switching chip in the plurality of switching chips differs from a second set of routing table entries corresponding to a second switching chip in the plurality of switching chips;
- receive data from an ingress network link;
- determine an identifier value based in part on the received data;
- determine, by one of the plurality of switching chips using the corresponding respective routing table, one of a plurality of egress network links available to the network device with a calculation based on the identifier value;
- and
- forward the received data to a next hop over the determined one of the plurality of egress network links.
A method for load balancing data flow, the method comprising:
- obtaining, by a network device from a remote processor via an interface, for each of a plurality of switching chips within the network device, a routing table with respective routing table entries to load balance forwarded data, wherein a first set of routing table entries corresponding to a first switching chip in the plurality of switching chips differs from a second set of routing table entries corresponding to a second switching chip in the plurality of switching chips;
- receiving, at the network device, data from an ingress network link;
- determining, by the network device, an identifier value based in part on the received data;
- determining, by one of the plurality of switching chips using the corresponding respective routing table remotely programmed via the interface, one of a plurality of egress network links available to the network device with a calculation based on the identifier value;
- and
- forwarding the received data to a next hop over the determined one of the plurality of egress network links.
A system for load balancing data flow, comprising:
- a first processor configured to execute an automated program to determine a plurality of routing table entries for a remote network device;
- and
- the remote network device having a plurality of switching chips and, for each of the plurality of switching chips, a routing table with respective routing table entries;
- wherein the first processor is configured to program the routing table of the remote network device via an interface;
- and
- wherein the remote network device is configured to:
- receive data from an ingress network link;
- determine an identifier value based in part on the received data;
- determine, by one of the plurality of switching chips using the corresponding respective routing table, one of a plurality of egress network links available to the network device with a calculation based on the identifier value, wherein a first set of routing table entries corresponding to a first switching chip in the plurality of switching chips differs from a second set of routing table entries corresponding to a second switching chip in the plurality of switching chips;
- and
- forward the received data to a next hop over the determined one of the plurality of egress network links.
Dependencies are inferred from the claim text.