Weighted load balancing in a multistage network using hierarchical ECMP

• US 9,571,400 B1
• Filed: 03/18/2014
• Issued: 02/14/2017
• Est. Priority Date: 02/25/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mandal, Subhasree, Kabbani, Abdul
• Primary Examiner(s): Patel, Parth
• Application Number:
  US14/217,937
• Time in Patent Office: 1,064 Days
• Field of Search: 370/235, 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A method for weighted routing of data traffic can include generating a first hash value based on a header of a data packet and performing a lookup in a first equal cost multi-path (ECMP) table using the first hash value to select a secondary ECMP table. The first ECMP table can include a weighted listing of at least two secondary ECMP tables. The method can further include generating a second hash value based on the header of the data packet and performing a lookup in the selected secondary ECMP table based on the second hash value to select an egress port of a plurality of egress ports of the data switch. The method can further include forwarding the data packet on the selected egress port.

Claims

1. A method comprising:

generating, by a data switch, a first hash value based on a header of a data packet;

performing, by the same data switch, a lookup in a first equal cost multi-path (ECMP) table using the first hash value, the first ECMP table including a weighted listing of at least two secondary ECMP tables, the lookup in the first ECMP table selecting a secondary ECMP table of the at least two secondary ECMP tables;

after performing the lookup in the first ECMP table, generating, by the same data switch, a second hash value based on the header of the data packet;

performing, by the same data switch, a lookup in the selected secondary ECMP table based on the second hash value to select an egress port of a plurality of egress ports of the data switch, a first secondary ECMP table of the at least two secondary ECMP tables including a listing of a first set of egress ports of the plurality of egress ports, a second secondary ECMP table of the at least two secondary ECMP tables including a listing of a second set of egress ports of the plurality of egress ports, the listing of the first set of egress ports being different than the listing of the second set of egress ports; and

forwarding, by the same data switch, the data packet on the selected egress port.

2. The method of claim 1, wherein:

generating the first hash value includes generating the first hash value using a first hash function; and

generating the second hash value includes generating the second hash value using a second hash function, the second hash function being different than the first hash function.

3. The method of claim 1, wherein the first hash value and the second hash value are a same hash value.

4. The method of claim 1, wherein:

the first set of egress ports and the second set of egress ports is a same set of egress ports of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a weighted listing; and

the listing of the second set of egress ports in the second secondary ECMP table is an un-weighted listing.

5. The method of claim 1, wherein:

the first set of egress ports and the second set of egress ports are different sets of egress ports, the first set of egress ports being a subset of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a first un-weighted listing; and

the listing of the second set of egress ports in the second secondary ECMP table is a second un-weighted listing.

6. The method of claim 1, wherein weights in the first ECMP table are based on a ratio of at least one routing weight of the first set of egress ports and at least one routing weight of the second set of egress ports.

7. The method of claim 1, wherein a third secondary ECMP table of the at least two secondary ECMP tables includes a listing of a third set of egress ports of the plurality of egress ports, the listing of the third set of egress ports being different than the listing of the first set of egress ports and the listing of the second set of egress ports.

8. The method of claim 7, wherein:

the first set of egress ports, the second set of egress ports and the third set egress ports are different sets of the plurality of egress ports, the first set of egress ports being a first subset of the plurality of egress ports and the second set of egress ports being a second subset of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a first un-weighted listing;

the listing of the second set of egress ports in the second secondary ECMP table is a second un-weighted listing; and

the listing of the third set of egress ports in the third secondary ECMP table is a third un-weighted listing.

9. The method of claim 7, wherein:

the first set of egress ports and the second set of egress ports are different sets of egress ports, the second set of egress ports and the third set of egress ports are a same set of egress ports, the first set of egress ports are a subset of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a first un-weighted listing;

the listing of the second set of egress ports in the second secondary ECMP table is a weighted listing; and

the listing of the third set of egress ports in the third secondary ECMP table is a second un-weighted listing.

10. A data switch, comprising:

at least one memory that is configured to store instructions; and

at least one processor that is operably coupled to the at least one memory and that is configured to process the instructions to cause the data switch to;

generate a first hash value based on a header of a data packet;

perform a lookup in a first equal cost multi-path (ECMP) table using the first hash value, the first ECMP table including a weighted listing of at least two secondary ECMP tables, the lookup in the first ECMP table selecting a secondary ECMP table of the at least two secondary ECMP tables;

after performing the lookup in the first ECMP table, generate a second hash value based on the header of the data packet;

perform a lookup in the selected secondary ECMP table based on the second hash value to select an egress port of a plurality of egress ports of the data switch, a first secondary ECMP table of the at least two secondary ECMP tables including a listing of a first set of egress ports of the plurality of egress ports, a second secondary ECMP table of the at least two secondary ECMP tables including a listing of a second set of egress ports of the plurality of egress ports, the listing of the first set of egress ports being different than the listing of the second set of egress ports; and

forward the data packet on the selected egress port.

11. The data switch of claim 10, wherein:

the first set of egress ports and the second set of egress ports is a same set of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a weighted listing; and

the listing of the second set of egress ports in the second secondary ECMP table is an un-weighted listing.

12. The data switch of claim 10, wherein:

the first set of egress ports and the second set of egress ports are different sets of egress ports, the first set of egress ports being a subset of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a first un-weighted listing; and

the listing of the second set of egress ports in the second secondary ECMP table is a second un-weighted listing.

13. The data switch of claim 10, wherein a third secondary ECMP table of the at least two secondary ECMP tables includes a listing of a third set of egress ports of the plurality of egress ports, the listing of the third set of egress ports being different than the listing of the first set of egress ports and the listing of the second set of egress ports.

14. The data switch of claim 13, wherein:

the first set of egress ports, the second set of egress ports and the third set egress ports are different sets of egress ports, the first set of egress ports being a first subset of the plurality of egress ports and the second set of egress ports being a second subset of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a first un-weighted listing;

the listing of the second set of egress ports in the second secondary ECMP table is a second un-weighted listing; and

the listing of the third set of egress ports in the third secondary ECMP table is a third un-weighted listing.

15. The data switch of claim 13, wherein:

the first set of egress ports and the second set of egress ports are different sets of egress ports, the second set of egress ports and the third set of egress ports are a same set of egress ports, the first set of egress ports are a subset of the plurality of egress ports;

the listing of the first set of egress ports in the first secondary ECMP table is a first un-weighted listing;

the listing of the second set of egress ports in the second secondary ECMP table is a weighted listing; and

the listing of the third set of egress ports in the third secondary ECMP table is a second un-weighted listing.

16. A method comprising:

receiving, at a data switch, a set of routing weights for a plurality of egress ports of the data switch;

converting, at the data switch, the set of routing weights to a two-level hierarchy of equal cost multipath (ECMP) tables, the converting including;

generating a first-level ECMP table;

generating a first second-level ECMP table; and

generating a second second-level ECMP table,

the first-level ECMP table including a weighted listing of the first second-level ECMP table and the second second-level ECMP table, the first second-level ECMP table including a listing of a first set of egress ports of the plurality of egress ports of the data switch, the second second-level ECMP table including a listing of a second set of egress ports of the plurality of egress ports of the same data switch, the listing of the second set of egress ports being different than the listing of the first set of egress ports; and

storing the two-level hierarchy of ECMP tables in the data switch.

17. The method of claim 16, wherein:

the first set of egress ports and the second set of egress ports is a same set of egress ports of the plurality of egress ports;

the listing of the first set of egress ports in the first second-level ECMP table is a weighted listing; and

the listing of the second set of egress ports in the second second-level ECMP table is an un-weighted listing.

18. The method of claim 17, wherein weights in the first second-level ECMP table are based on, at least, a ratio of a first routing weight of the received routing weights and a second routing weight of the received routing weights, the first routing weight being associated with at least a first egress port of the plurality of egress ports, the second routing weight being associated with at least a second egress port of the plurality of egress ports, the second egress port being different than the first egress port.

19. The method of claim 16, wherein:

the first set of egress ports and the second set of egress ports are different sets of egress ports, the first set of egress ports being a subset of the plurality of egress ports;

the listing of the first set of egress ports in the first second-level ECMP table is a first un-weighted listing; and

the listing of the second set of egress ports in the second second-level ECMP table is a second un-weighted listing.

20. The method of claim 16, wherein weights in the first-level ECMP table are based on, at least, a ratio of a first routing weight of the received routing weights and a second routing weight of the received routing weights, the first routing weight being associated with at least a first egress port of the plurality of egress ports, the second routing weight being associated with at least a second egress port of the plurality of egress ports, the second egress port being different than the first egress port.

21. The method of claim 16, wherein the converting the set of routing weights to the two-level hierarchy of ECMP tables further includes generating a third second-level ECMP table that includes a listing of a third set of egress ports of the plurality of egress ports, the listing of the third set of egress ports being different than the listing of the first set of egress ports and the listing of the second set of egress ports.

22. A data switch, comprising:

at least one memory that is configured to store instructions; and

at least one processor that is operably coupled to the at least one memory and that is configured to process the instructions to cause the data switch to;

receive a set of routing weights for a plurality of egress ports of the data switch;

convert the set of routing weights to a two-level hierarchy of equal cost multi-path (ECMP) tables, the converting including;

generating a first-level ECMP table;

generating a first second-level ECMP table; and

generating a second second-level ECMP table,

the first-level ECMP table including a weighted listing of the first second-level ECMP table and the second second-level ECMP table, the first second-level ECMP table including a listing of a first set of egress ports of the plurality of egress ports of the data switch, the second second-level ECMP table including a listing of a second set of egress ports of the plurality of egress ports of the same data switch, the listing of the second set of egress ports being different than the listing of the first set of egress ports; and

store the two-level hierarchy of ECMP tables in the data switch.

23. The data switch of claim 22, wherein:

the first set of egress ports and the second set of egress ports is a same set of egress ports of the plurality of egress ports;

the listing of the first set of egress ports in the first second-level ECMP table is a weighted listing; and

the listing of the second set of egress ports in the second second-level ECMP table is an un-weighted listing.

24. The data switch of claim 23, wherein weights in the first second-level ECMP table are based on, at least, a ratio of a first routing weight of the received routing weights and a second routing weight of the received routing weights, the first routing weight being associated with at least a first egress port of the plurality of egress ports, the second routing weight being associated with at least a second egress port of the plurality of egress ports, the second egress port being different than the first egress port.

25. The data switch of claim 22, wherein weights in the first-level ECMP table are based on, at least, a ratio of a first routing weight of the received routing weights and a second routing weight of the received routing weights, the first routing weight being associated with at least a first egress port of the plurality of egress ports, the second routing weight being associated with at least a second egress port of the plurality of egress ports, the second egress port being different than the first egress port.

26. The data switch of claim 22, wherein the converting the set of routing weights to the two-level hierarchy of ECMP tables further includes generating a third second-level ECMP table that includes a listing of a third set of egress ports of the plurality of egress ports, the listing of the third set of egress ports being different than the listing of the first set of egress ports and the listing of the second set of egress ports.