Selection of trunk ports and paths using rotation

• US 8,149,839 B1
• Filed: 08/26/2008
• Issued: 04/03/2012
• Est. Priority Date: 09/26/2007
• Status: Expired due to Fees

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Hsu, Ivy Pei-Shan, Bansal, Deepak, Hui, Lok Yan, Wong, Yuen, Naraghi, Vahid
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Bokhari, Syed M
• Application Number:
  US12/198,697
• Time in Patent Office: 1,316 Days
• Field of Search: 370/386, 370/389, 370/238, 370/392, 370/230, 455/445
• 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 network data traffic. In one embodiment, a network device uses a rotate function to generate a rotated index (path index) that is used to select a path (e.g., an ECMP) path from multiple paths (e.g., multiple ECMP paths) for forwarding a packet. A network device may also generate a rotated index (trunk index) that is used to select an output port from multiple output ports associated with a trunk for forwarding the packet.

Claims

1. A method comprising:

generating, at a first network device, a first value based upon one or more sections of a first packet;

bit rotating, at the first network device, the first value by a first amount to generate a first rotated index, wherein the first amount is specified by a first control variable that is configured for the first network device, and wherein the first rotated index is used to select a path from a plurality of paths for forwarding the first packet from the first network device;

generating, at the first network device, a second value based upon one or more sections of a second packet; and

bit rotating, at the first network device, the second value by a second amount to generate a second rotated index, wherein the second amount is specified by a second control variable that is configured for the network device and is distinct from the first control variable, and wherein the second rotated index is used to select a port from a plurality of ports associated with a trunk for forwarding the second packet from the first network device.

2. The method of claim 1 wherein generating the first value comprises:

hashing the one or more sections of the first packet to generate a hash value; and

generating the first value using the hash value.

3. The method of claim 1 further comprising:

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

generating, at the second network device, a third value based upon the one or more sections of the first packet;

bit rotating, at the second network device, the third value by a third amount to generate a third rotated index, wherein the third amount is specified by a third control variable configured for the second network device, and wherein the third amount specified by the third control variable is different from the first amount specified by the first control variable; and

selecting, at the second network device, a path from a plurality of paths for forwarding the first packet from the second network device based upon the third rotated index.

4. The method of claim 1 wherein the control variable is configurable by a user.

5. A network device comprising:

a plurality of ports; and

a packet processor configured to

generate a first value based upon one or more sections of a first packet to be forwarded from the network device,

bit rotate the first value by a first amount to generate a first rotated index, wherein the first amount is specified by a first control variable that is configured for the network device, and wherein the first rotated index is used to select a path from a plurality of paths for forwarding the first packet from the first network device;

generate a second value based upon one or more sections of a second packet to be forwarded from the network device; and

bit rotate the second value by a second amount to generate a second rotated index, wherein the second amount is specified by a second control variable that is configured for the network device and is distinct from the first control variable, and wherein the second rotated index is used to select a port from a plurality of ports associated with a trunk for forwarding the second packet from the first network device.

6. The network device of claim 5 wherein the packet processor is configured to:

hash the one or more sections of the first packet to generate a hash value; and

generate the first value using the hash value.

7. The network device of claim 5 further configured to:

communicate the first packet from the network device to a second network device using the selected path;

wherein the second network device is configured to apply a different amount of rotation from the first amount for generating a third rotated index that is used to select a path for forwarding the first packet from the second network device.

8. The network device of claim 5 wherein the control variable is configurable by a user.

9. A network device comprising:

means for generating a first value based upon one or more sections of a first packet;

means for bit rotating the first value by a first amount to generate a first rotated index, wherein the first amount is specified by a first control variable that is configured for the first network device, and wherein the first rotated index is used to select a path from a plurality of paths for forwarding the first packet from the network device;

means for generating a second value based upon one or more sections of a second packet; and

means for bit rotating the second value by a second amount to generate a second rotated index, wherein the second amount is specified by a second control variable that is configured for the network device and is distinct from the first control variable, and wherein the second rotated index is used to select a port from a plurality of ports associated with a trunk for forwarding the second packet from the network device.

10. The network device of claim 9 further comprising:

means for hashing the one or more sections of the first packet to generate a hash value; and

means for generating the first value using the hash value.

11. The network device of claim 9 further comprising:

means for communicating the first packet from the network device to a second network device using the selected path;

wherein the second network device is configured to apply a different amount of rotation from the first amount for generating a third rotated index that is used to select a path for forwarding the first packet from the second network device.