System and method for ECMP load sharing

• US 7,903,654 B2
• Filed: 12/22/2006
• Issued: 03/08/2011
• Est. Priority Date: 08/22/2006
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Bansal, Deepak, Wong, Yuen
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): RANDHAWA, MANDISH K
• Application Number:
  US11/615,769
• Publication Number:
  US 20080049742A1
• Time in Patent Office: 1,537 Days
• Field of Search: 370/392, 370/401, 370/397, 370/230, 370/360, 370/389, 370/386, 370/388, 370/396, 370419-421, 709/238
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service

Abstract

A packet classifier and a method for routing a data packet are provided. The packet classifier includes a content addressable memory, a translation table and a parameter memory. The method includes looking up a content addressable memory for a base address into a parameter memory using a header of the data packet. The base address is related to the routes under ECMP for forwarding the data packet. From among these addresses, using multiple headers of the data packet, an adjustment to the base address is computed. The adjustment specifies an actual address to the parameter memory corresponding to a selected route for forwarding the data packet. The parameter memory is then accessed using the actual address to obtain parameter values relevant to the selected route. The data packet is then forwarded according to the parameter values thus obtained.

Claims

1. A method comprising:

retrieving, by a network device from a first memory, an index for a second memory, the retrieving from the first memory using information from a first portion of a data packet;

retrieving, by the network device from the second memory, a base index for a third memory and a value encoding a number of equal cost paths available for forwarding the data packet, the retrieving from the second memory using the index for the second memory; and

determining, by the network device, an adjusted index for the third memory based on the base index, the value encoding the number of equal cost paths, and a second portion of the data packet.

2. The method of claim 1 wherein the first memory comprises a content addressable memory (CAM) and wherein the third memory comprises a parameter random access memory (PRAM).

3. The method of claim 1 wherein determining the adjusted index for the third memory comprises applying a hash function on selected fields of the second portion of the data packet.

4. The method of claim 3 wherein the hash function also takes as input a random number.

5. The method of claim 1 wherein the second portion of the data packet includes a MAC header, an IP header, or a TCP header.

11. The method of claim 1 further comprising retrieving, by the network device from the third memory, one or more parameters values associated with an equal cost path.

12. The method of claim 11 further comprising forwarding, by the network device, the data packet based on the one or more parameter values.

15. The method of claim 3 wherein determining the adjusted index for the third memory further comprises applying a modulo function on a result of the hash function using the value encoding the number of equal cost paths as a divisor.

6. A network device comprising:

at least one port capable of receiving data packets; and

a first memory, a second memory, and a third memory,

wherein the network device is configured to;

retrieve from the first memory an index for the second memory, the retrieving from the first memory using information from a first portion of a data packet;

retrieve from the second memory a base index for the third memory and a value encoding a number of equal cost paths available for forwarding the data packet, the retrieving from the second memory using the index for the second memory; and

determine an adjusted index for the third memory based on the base index, the value encoding the number of equal cost paths, and a second portion of the data packet.

7. The network device of claim 6 wherein the first memory comprises a content addressable memory (CAM) and wherein the third memory comprises a parameter random access memory (PRAM).

8. The network device of claim 6 wherein determining the adjusted index for the third memory comprises applying a hash function on selected fields of the second portion of the data packet.

9. The network device of claim 8 wherein the hash function also takes as input a random number.

10. The network device of claim 6 wherein the second portion of the data packet includes a MAC header, an IP header, or a TCP header.

13. The network device of claim 6 wherein the network device is further configured to retrieve from the third memory one or more parameters values associated with an equal cost path.

14. The network device of claim 13 where the network device is further configured to forward the data packet based on the one or more parameter values.

16. The network device of claim 8 wherein determining the adjusted index for the third memory further comprises applying a modulo function on a result of the hash function using the value encoding the number of equal cost paths as a divisor.