Dynamic Path Selection

• US 20110216769A1
• Filed: 03/08/2010
• Published: 09/08/2011
• Est. Priority Date: 03/08/2010
• Status: Abandoned Application

• Current Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Ko, Kung-Ling, Balakavi, Venkata Pramod, Gnanasekaran, Sathish, Lakshmanan, Subramanian
• Application Number:
  US12/719,321
• Publication Number:
  US 20110216769A1
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 12/56 Packet switching systems
• 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/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A switch/router dynamically selects a path from multiple available paths between a source destination pair for a frame. A hash function generates a hash value from frame parameters such as source ID, destination ID, exchange ID, etc. The hash value is given as an input to a plurality of range comparators where each range comparator has a range of values associated with it. If the hash value falls within a range associated with a range comparator, that range comparator generates an in-range signal. A path selector module detects which range comparator has generated the in-range signal, and determines a path associated with that range comparator from previously stored information. The frame is transmitted via the selected path. The ranges associated with each range comparator can be non-overlapping and unequal in size. The number of range comparators can be equal to a number of selected multiple paths.

Claims

1. A switch comprising:

a hashing module for determining a hash value associated with one or more parameters of a frame, the hash value being larger than a number of possible paths for the frame;

a plurality of range comparators receiving the hash value as input, each range comparator having an associated range of values, wherein one of the plurality of range comparators generates an in-range signal if the hash value falls within the range of values associated with the one of the plurality of range comparators; and

a path selector for selecting one of the number of possible paths between a source destination pair for the frame, the selected path corresponding to the in-range signal generated by the one of the plurality of range comparators.

2. The switch of claim 1, wherein at least two of the plurality of range comparators have unequal associated ranges of values.

3. The switch of claim 1, wherein a total number of active range comparators of the plurality of range comparators is equal to a total number of plurality of paths between the source and destination pair.

4. The switch of claim 1, wherein the one or more parameters of the frame includes an exchange ID of the frame.

5. The switch of claim 1, wherein each of the plurality of paths between the source and destination pair have equal costs associated with them.

6. The switch of claim 1, wherein the range of values associated with each of the plurality of range comparators is programmable.

7. A method for distributing traffic, the method comprising:

generating a hash value from one or more parameters of a frame, the hash value being larger than a number of possible paths for the frame;

determining one range of values from a plurality of ranges of values, the one range of values including the hash value;

selecting one of the number of paths for the frame, the selected path corresponding to the one range of values that includes the hash value.

8. The method of claim 7, wherein at least two of the plurality of ranges of values have unequal sizes.

9. The method of claim 7, wherein a total number of the plurality of ranges of values is equal to a total number of the plurality of paths between the source and destination pair.

10. The method of claim 7, wherein the one or more parameters of the frame includes an exchange ID of the frame.

11. The method of claim 7, wherein each of the plurality of paths between the source and destination pair have equal costs associated with them.

12. The method of claim 7, further comprising modifying at least one range of values from the plurality of ranges of values from a first range to a second range.