Trunking inter-switch links

• US 6,532,212 B1
• Filed: 09/25/2001
• Issued: 03/11/2003
• Est. Priority Date: 09/25/2001
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Mcdata Corporation (Broadcom, Inc.)
• Inventors: Beal, David D., Yang, Henry S., Soloway, Stuart R.
• Primary Examiner(s): Hsu, Alphus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US09/964,184
• Time in Patent Office: 532 Days
• Field of Search: 370/252, 370/253, 370/236, 370/232, 370/230, 370/235, 370/237, 370/239, 370/389, 370/400, 370/412, 370/414, 370/238, 359/115, 359/117, 359/128, 709/230
• US Class Current: 370/230
• 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/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/357 Fibre channel switches
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method and apparatus for routing frames through a fibre channel fabric to make the most efficient possible use of redundant inter-switch links between neighboring switches. The inter-switch links may have different bandwidths. The flow between adjacent switches is monitored to determine various local usage statistics and periodically adjust routing tables to move data flows from congested links to lightly loaded links.

Claims

1. A method of routing a flow through a switch in a fibre channel fabric comprising:

receiving traffic at a port coupled to said switch;

identifying said flow from said traffic using header information;

determining at least one path operative for routing said flow through said fibre channel fabric; and

rerouting said flow from a first link in said at least one path to a second link in said at least one path based upon operating performance information in addition to topology information, wherein said operating performance information comprises a congested link condition comprising a first condition resulting from an additional flow on said first link resulting in said first link exceeding a first congestion threshold, wherein said first congestion threshold defines a percentage of bandwidth on said first link in relation to the total available amount of bandwidth on said first, and wherein said congested link condition comprises a second condition resulting from the data rate of said flow plus a data rate on said second link resulting in said second link not exceeding a second congestion threshold, wherein said second congestion threshold defines a percentage of bandwidth on said second link in relation to the total available amount of bandwidth on said second link.

2. A method of routing a flow through a switch in a fibre channel fabric comprising:

receiving traffic at a port coupled to said switch;

identifying said flow from said traffic using header information;

determining at least one path operative for routing said flow through said fibre channel fabric; and

rerouting said flow from a first link in said at least one path to a second link in said at least one path based upon operating performance information in addition to topology information, wherein said operating performance information comprises comparing a projected change in a first cost function on said first link with a projected change in a second cost function on said second link, and wherein said projected change in said first cost function is determined from an initial cost function of said first link and a cost function of said first link minus said flow and said projected change in said second cost function is determined from an initial cost function of said second link and a cost function of said second link plus said flow.

3. The method of claim 2 wherein said act of rerouting said flow from a first link in said at least one path to a second link in said at least one path is performed if the second cost function multiplied by a stability factor is less than the first cost function.

4. A method of routing a flow on at least one path in a fiber channel fabric, said at least one path comprising a source switch and a destination switch, wherein at least one switch pair in said at least one path is coupled by a plurality of links, said method comprising:

determining said at least one path between said source switch and said destination switch;

routing said flow over a first link coupling said at least one switch pair in said at least one path, said at least one switch pair having the same originating switch; and

rerouting said flow to a second link coupling said at least one switch pair based upon operating performance information and topology information,

Wherein said performance information comprises a condition where said flow cannot be rerouted to said second link if said flow has been recently rerouted within a period of time, wherein said period of time is one minute.

5. A method of routing a flow through a switch in a fibre channel fabric comprising:

receiving traffic at a port coupled to said switch;

identifying said flow from said traffic using header information;

determining at least one path operative for routing said flow through said fibre channel fabric;

rerouting said flow from a first link in said at least one path to a second link in said at least one path based upon operating performance information in addition to topology information;

assigning a flow value for said portion of a destination identification; and

entering said flow value and associated plurality of operating performance information into a data structure resident on said first switch, wherein said operating performance information comprises a transmit port of the flow, a plurality of statistics used to compute a short-term and long-term filtered value for a frame rate and a time the flow was last rerouted.

6. A method of routing a flow on at least one path in a fiber channel fabric, said at least one path comprising a source switch and a destination switch, wherein at least one switch pair in said at least one path is coupled by a plurality of links, said method comprising:

determining said at least one path between said source switch and said destination switch;

routing said flow over a first link coupling said at least one switch pair in said at least one path, said at least one switch pair having the same originating switch; and

rerouting said flow to a second link coupling said at least one switch pair based upon operating performance information and topology information,

wherein said operating performance information comprises a congested link condition, said congested link condition comprises a first condition resulting in said first link exceeding a first congestion threshold, wherein said first congestion threshold defines a percentage of bandwidth on said first link in relation to the total available amount of bandwidth on said first link and, wherein said congested link condition comprises a second condition resulting from an additional flow on said second link resulting in said second link not exceeding a second congestion threshold, wherein said second congestion threshold defines a percentage of bandwidth on said second link in relation to the total available amount of bandwidth on said second link.

7. A method of routing traffic through a switch in a fibre channel fabric, wherein said switch is coupled to a plurality of links for routing said traffic, said method comprising:

at a receive port of said switch, receiving traffic comprising a plurality of frames, each frame comprising a destination identification specifying at least a specific destination of a plurality of destinations;

grouping said traffic into a plurality of flows based upon header information;

scanning said plurality of flows for one or more flows that satisfy operating performance information; and

rerouting at least one flow from a first link to a second link based upon operating performance information in addition to topology information.

8. The method of claim 7 wherein said flow is further defined by the values of specified bits in a source ID field and a destination ID field of the frames and by the receive port, wherein eight bits of the domain part of the D_ID are included in said specified bits.

9. The method of claim 7 wherein said flow is further defined by a sequence frames identified by a domain portion of a destination ID field and a receive port to H1+H2, D1 is approximately equal to D2 and D<

D1.

10. The method of claim 7 wherein said flow is further defined by a number of received frames that meet selection criteria applied to header information and receive port of each received frame.

11. The method of claim 7 wherein said flow is further identified by values of specified bits in a source field and a destination field and by the receive port of said sequence of frames, wherein a set of transmit links allowed by said act of rerouting is identical for all frames in said flow.

12. The method of claim 7, wherein said act of grouping said traffic into a plurality of flows further comprises grouping said traffic into a plurality of flows based upon receive port information.

13. A fibre channel switch comprising:

a plurality of ports for transmitting and receiving frames;

a first port operative for receiving a frame;

a first protocol for selecting a second port for transmitting a frame received from said first port; and

a second protocol for dynamically switching said selection from said second port to a third port based upon operating performance information in addition to topology information.

14. The fibre channel switch of claim 13 further comprising a processor for enabling said first and second protocols.

15. The fibre channel switch of claim 13 further comprising memory coupled to said first port for storing received frames.

16. The fibre channel switch of claim 13 further comprising a data structure for grouping a plurality of frames received at said first port into a flow, said plurality of frames destined for a same group of destinations.

17. The fibre channel switch of claim 13 wherein said data structure further comprises a flow table for entering a flow identification and associated operating performance information.

18. The fibre channel switch of claim 17 wherein said operating performance information further comprises a transmit port of the flow, a plurality of statistics used to compute a short-term and long-term filtered value for a frame rate and a time the flow was last rerouted.

19. The fibre channel switch of claim 13 wherein said flow is determined from the destination identification in a frame.

20. The fibre channel switch of claim 13 further comprising a routing table for routing said frames wherein said routing table is modified by said second protocol.

21. A fibre channel fabric comprising:

a first switch;

at least one switch coupled to said first switch by a plurality of links, said links operable for routing traffic;

a first protocol implemented in said first switch for selecting a first of said plurality of links and thereafter routing said traffic over said first link; and

a second protocol implemented in said first switch for rerouting said traffic to a second of said plurality of links based upon operating performance information in addition to topology information.