Weighted load balancing in a multistage network

Patent metadata

Field	Value
Publication number	US-9608913-B1
Application number	US-201414223645-A
Country	US
Kind code	B1
Filing date	Mar 24, 2014
Priority date	Feb 24, 2014
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

A method for weighted data traffic routing can include generating an integer hash value based on a header of a data packet and encoding the integer hash value to generate a search key for a content addressable memory included in the data switch. The method can also include performing a lookup in the content addressable memory to match the search key with one of a plurality of prefixes stored in the content addressable memory, the plurality of prefixes including an encoded set of routing weights associated with a plurality of egress ports of the data switch. The method can further include forwarding the data packet on an egress port of the plurality of egress ports associated with the one of the plurality of prefixes in the content addressable memory.

First claim

What is claimed is:

1. A method comprising:
generating, by a data switch, an integer hash value based on a header of a data packet;
encoding the integer hash value to generate a search key for a content addressable memory included in the data switch;
performing a lookup in the content addressable memory to identify a prefix that matches the search key, wherein the content addressable memory stores a plurality of prefixes, each of the plurality of prefixes is a prefix of an encoded contiguous integer range associated with a routing weight, and each prefix is associated with a respective egress port of a plurality of egress ports of the data switch; and
forwarding the data packet on an egress port associated with the one of the plurality of prefixes in the content addressable memory identified by the lookup.

2. The method of claim 1 , further comprising, prior to generating the integer hash value:
receiving, at the data switch, the data packet for transmission to a destination address; and
determining, based on the destination address, a routing table for routing the packet, the routing table being implemented in the content addressable memory.

3. The method of claim 1 , wherein the encoding the integer hash value includes encoding the integer hash value using one of naive range encoding, fence encoding and database independent pre-encoding (DIRPE).

4. The method of claim 1 , wherein the encoded contiguous integer ranges and the search key are encoded using a same encoding algorithm.

5. 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 an integer hash value based on a header of a data packet;
encode the integer hash value to generate a search key for a content addressable memory that is included in the data switch;
perform a lookup in the content addressable memory to identify a prefix that matches the search key, wherein the content addressable memory stores a plurality of prefixes, each of the plurality of prefixes is a prefix of an encoded contiguous integer range associated with a routing weight, and each prefix is associated with a respective egress port of a plurality of egress ports of the data switch; and
forward the data packet on an egress port associated with the one of the plurality of prefixes in the content addressable memory identified by the lookup.

6. The data switch of claim 5 , wherein the instructions, when executed by the processor, further cause the data switch, prior to generating the integer hash value, to:
receive, at the data switch, the data packet for transmission to a destination address; and
determine, based on the destination address, a routing table for routing the packet, the routing table being implemented in the content addressable memory.

7. The data switch of claim 5 , wherein the encoded contiguous integer ranges and the search key are encoded using a same encoding algorithm.

8. The data switch of claim 5 , wherein the content addressable memory includes a ternary content addressable memory.

9. A method comprising:
receiving, at a data switch, a set of routing weights for a plurality of egress ports of the data switch;
converting the set of routing weights to a set of contiguous integer ranges;
generating a set of ternary content addressable memory (TCAM) prefixes by encoding the set of contiguous integer ranges and identifying prefixes of the respective encoded contiguous integer ranges; and
storing the set of TCAM prefixes with corresponding respective egress ports of the plurality of egress ports in a TCAM of the data switch, the TCAM implementing a weighted cost multi-path (WCMP) routing table for the plurality of egress ports; and
forwarding a data packet, received at the data switch, on an egress port of the plurality of egress ports based on a header of the received data packet and the WCMP routing table.

10. The method of claim 9 , wherein the encoding the set of contiguous integer ranges includes encoding the set of contiguous integer ranges using one of naive range encoding, fence encoding and database independent pre-encoding (DIRPE).

11. The method of claim 9 , wherein the converting the set of routing weights to the set of contiguous integer ranges includes performing summation on the set of routing weights.

12. The method of claim 9 , wherein the set of routing weights includes a set of integer routing weights.

13. The method of claim 9 , wherein the set of routing weights is a first set of routing weights, the set of contiguous integer ranges is a first set of contiguous integer ranges and the set of TCAM prefixes is a first set of TCAM prefixes, the method further comprising:
receiving, at the data switch, a second set of routing weights for the plurality of egress ports of the data switch, the second set of routing weights being different than the first set of routing weights;
converting the second set of routing weights to a second set of contiguous integer ranges;
generating a second set of TCAM prefixes by encoding the second set of contiguous integer ranges and identifying prefixes of the respective encoded contiguous integer ranges generated based on the second set of contiguous integer ranges; and
storing the second set of TCAM prefixes with corresponding respective egress ports of the plurality of egress ports in the TCAM of the data switch.

14. 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:
convert a set of routing weights for a plurality of egress ports of the data switch to a set of contiguous integer ranges;
generate a set of ternary content addressable memory (TCAM) prefixes by encoding the set of contiguous integer ranges and identifying prefixes of the respective encoded contiguous integer ranges; and
store the set of TCAM prefixes with corresponding respective egress ports of the plurality of egress ports in a TCAM of the data switch, the TCAM implementing a weighted cost multi-path (WCMP) routing table for the plurality of egress ports.

15. The data switch of claim 14 , wherein the set of contiguous integer ranges are encoded using one of naive range encoding, fence encoding and database independent pre-encoding (DIRPE).

16. The data switch of claim 14 , wherein the set of routing weights are converted to the set of contiguous integer ranges by performing summation on the set of routing weights.

17. The data switch of claim 14 , wherein the set of routing weights is a first set of routing weights, the set of contiguous integer ranges is a first set of contiguous integer ranges and the set of TCAM prefixes is a first set of TCAM prefixes, the instructions, when executed by the at least one processor, cause the data switch to:
receive, at the data switch, a second set of routing weights for the plurality of egress ports of the data switch, the second set of routing weights being different than the first set of routing weights;
convert the second set of routing weights to a second set of contiguous integer ranges;
generate a second set of TCAM prefixes by encoding the second set of contiguous integer ranges and identifying prefixes of the respective encoded contiguous integer ranges generated based on the second set of contiguous integer ranges; and
store the second set of TCA

Assignees

• Google Inc

Inventors

• Kabbani Abdul
• Hasan Jahangir
• Vahdat Amin

Classifications

• H04L47/125 Primary

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

• H04L45/7457

  Electricity · mapped topic

• H04L45/74591

  using content-addressable memories [CAM] · CPC title