Techniques for selecting paths and/or trunk ports for forwarding traffic flows

• US 8,509,236 B2
• Filed: 08/26/2008
• Issued: 08/13/2013
• Est. Priority Date: 09/26/2007
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Zhang, Hui, Wong, Yuen, Naraghi, Vahid
• Primary Examiner(s): Elliott, IV, Benjamin H
• Application Number:
  US12/198,710
• Publication Number:
  US 20120163389A1
• Time in Patent Office: 1,813 Days
• Field of Search: 370/392, 370/401
• US Class Current: 370/392
• 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

Techniques that offer enhanced diversity in the selection of paths (e.g., ECMP paths) and/or ports from ports associated with trunks for forwarding data traffic. In one embodiment, one or more functions are used to generate a result. A first portion of the generated result may be used as an index (e.g., ECMP index) for selecting a path (e.g., an ECMP path) from multiple possible paths for forwarding a packet. A second portion of the generated result, different from the first portion, may be used as an index (trunk index) for selecting an output port from multiple output ports associated with a trunk for forwarding a packet. In this manner, selected portions of the generated result may be used as indices, one for selecting a path and another for selecting a trunk port for forwarding packets such that the two indices are not the same and are not dependent upon one another.

Claims

1. A method comprising:

applying, by a network device, one or more mathematical functions to one or more sections of a packet to generate a result value;

using, by the network device, a first portion of the result value to select an equal-cost-multipath (ECMP) path from a plurality of ECMP paths for forwarding the packet from the network device; and

when the selected ECMP path is a trunk comprising a plurality of trunk ports, using, by the network device, a second portion of the result value to select a trunk port from the plurality of trunk ports, wherein the second portion is different from the first portion, and wherein the first portion and the second portion are non-overlapping portions of the result value.

2. The method of claim 1 wherein:

the one or more mathematical functions comprise a cyclic redundancy check (CRC) function; and

generating the result value comprises using the CRC function to generate the result value.

3. The method of claim 1 wherein:

the one or more mathematical functions comprise a cyclic redundancy check (CRC) function and a rotate function, wherein an amount of rotation performed by the rotate function is preconfigured for the network device; and

generating the result value comprises using the CRC function and the rotate function to generate the result value.

4. The method of claim 1 wherein applying the one or more mathematical functions comprises:

applying a first mathematical function to the one or more sections of the packet to generate a first result value; and

applying a second mathematical function to the first result value to generate the result value.

5. The method of claim 4 wherein the first mathematical function is a rotate function and the second mathematical function is a CRC function.

6. The method of claim 4 wherein the first mathematical function is a CRC function and the second mathematical function is a rotate function.

7. The method of claim 1 wherein applying the one or more mathematical functions comprises:

applying a first mathematical function to the one or more sections of the packet to generate a first result value;

applying a second mathematical function to the first result value to generate a second result value; and

applying a third mathematical function to the second result value to generate the result value.

8. The method of claim 7 where at least the first mathematical function or the third mathematical function is a rotate function and the second mathematical function is a CRC function.

9. The method of claim 1 further comprising:

communicating the packet from the network device to a second network device using the selected ECMP path;

wherein a result value generated by the second network device using the one or more sections of the packet and the one or more mathematical functions is different from the result value generated by the network device from which the packet was communicated to the second network device.

10. The method of claim 1 wherein the first portion and the second portion are each less than the result value.

11. The method of claim 1 wherein the first portion or the second portion is made of up non-contiguous sections of the result value.

12. A network device comprising:

a plurality of ports; and

a packet processor configurable to;

apply one or more mathematical functions to one or more sections of a packet to generate a result value;

use a first portion of the result value to select an equal-cost-multipath (ECMP) path from a plurality of ECMP paths for forwarding the packet from the network device; and

when the selected ECMP path is a trunk comprising a plurality of trunk ports, use a second portion of the result value to select a trunk port from the plurality of trunk ports, wherein the second portion is different from the first portion, and wherein the first portion and the second portion are non-overlapping portions of the result value.

13. The network device of claim 12 wherein the one or more mathematical functions comprise a cyclic redundancy check (CRC) function and the packet processor is configured to use the CRC function to generate the result value.

14. The network device of claim 12 wherein the one or more mathematical functions comprise a cyclic redundancy check (CRC) function and a rotate function and the packet processor is configured to use the CRC function and the rotate function to generate the result value, wherein the amount of rotation performed by the rotate function is preconfigured for the network device.

15. The network device of claim 12 wherein applying the one or more mathematical functions comprises:

applying a first mathematical function to the one or more sections of the packet to generate a first result value; and

applying a second mathematical function to the first result value to generate the result value.

16. The network device of claim 15 wherein the first mathematical function is a rotate function and the second mathematical function is a CRC function.

17. The network device of claim 15 wherein the first mathematical function is a CRC function and the second mathematical function is a rotate function.

18. The network device of claim 12 wherein applying the one or more mathematical functions comprises:

applying a first mathematical function to the one or more sections of the packet to generate a first result value;

applying a second mathematical function to the first result value to generate a second result value; and

applying a third mathematical function to the second result value to generate the result value.

19. The network device of claim 18 where at least the first mathematical function or the third mathematical function is a rotate function and the second mathematical function is a CRC function.

20. A network device comprising:

means for applying one or more mathematical functions to one or more sections of a packet to generate a result value;

means for using a first portion of the result value to select an equal-cost-multipath (ECMP) path from a plurality of ECMP paths for forwarding the packet from the network device; and

means for, when the selected ECMP path is a trunk comprising a plurality of trunk ports, using a second portion of the result value to select a trunk port from the plurality of trunk ports, wherein the second portion is different from the first portion, and wherein the first portion and the second portion are non-overlapping portions of the result value.