SYSTEM AND METHOD FOR ECMP LOAD SHARING

• US 20080049742A1
• Filed: 12/22/2006
• Published: 02/28/2008
• 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
• Granted Patent: US 7,903,654 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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 for routing a data packet, comprising:

using information in header of the data packet, looking up a search memory for a logical address;

using multiple headers of the data packet, obtaining an actual address into a parameter address based on the logical address accessing the parameter memory using the actual address to obtain parameter values relevant to the selected route; and

forwarding the data packet according to the parameter values.

2. A method as in claim 1, wherein looking up the search memory comprises looking up a content addressable memory.

3. A method as in claim 1, wherein the logical address relates to the plurality of routes for forwarding the data packet;

4. A method as in claim 1, wherein computing an adjustment comprises applying a hash function on selected fields of the multiple headers of the data packet.

5. A method as in claim 4, further comprises using the hash function and the logical address to obtain an address of a location in a translation table holding the actual address.

6. A method as in claim 5, wherein the logical address comprises a base address in a memory module holding the translation table.

7. A method as in claim 4, further comprising generating a random number and using the random number in the hash function.

8. A method as in claim 1, wherein the multiple headers comprise two or more of the MAC header, the IP header and the TCP header.

9. An apparatus for routing a data packet, comprising:

a parameter memory holding parameter values relevant to routes for forwarding the data packet;

a search memory providing, based on a header of the data packet, a logical address for obtaining an actual address into the parameter memory; and

a translation table holding the actual address, the location in the translation table holding the actual address being related to the logical address and selected fields in multiple headers of the data packet;

10. An apparatus as in claim 9, wherein the search memory comprises a content addressable memory.

11. An apparatus as in claim 9, wherein the logical address relates to a plurality of routes for forwarding the data packet;

12. An apparatus as in claim 9, wherein the actual address is obtained in part by applying a hash function on selected fields of the multiple headers of the data packet.

13. An apparatus as in claim 12, wherein the hash function and the logical address are used in combination to compute an address for the location in the translation table holding the actual address.

14. An apparatus as in claim 13, wherein the logical address comprises a base address in a memory module holding the translation table.

15. An apparatus as in claim 12, wherein a random number is used in the hash function.

16. An apparatus as in claim 9, wherein the multiple headers comprise two or more of the MAC header, the IP header and the TCP header.