Method and system for switch fabric flow control

• US 6,654,343 B1
• Filed: 03/19/2001
• Issued: 11/25/2003
• Est. Priority Date: 03/19/2001
• Status: Expired due to Term

• Current Assignee: Force10 Networks, Inc. (Dell Technologies Inc.)
• Original Assignee: Turin Networks, Inc. (Dell Technologies Inc.)
• Inventors: Zhang, Hui, West, Stephen John, Reissfelder, Bob, Zhu, Shuangxia Sarah, Jia, Yantao, Brandis, Dirk Kurt, Jin, Lei, Ali, Shahzad
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/812,985
• Time in Patent Office: 981 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/235, 370/236, 370/252, 370/253, 370/260, 370/258, 370/363, 370/395, 370/395.42, 370/395.43
• US Class Current: 370/229
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An ingress is coupled with the switch fabric to send flows of data across the switch fabric. Each of the flows of data is associated with a flow identification information and a priority level. An egress is coupled with the switch fabric to receive the flows of data from the ingress. The egress is configured to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows of data to the egress. Each of the flow control messages includes one or more of a flow identification information, an egress space availability information and a new priority level for a flow.

Claims

1. A system, comprising:

a switch fabric;

an ingress coupled with the switch fabric to send flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress coupled with the switch fabric to receive the flows from the ingress and to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows to the egress, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow.

2. The system of claim 1, wherein the ingress comprises ingress flow queues, wherein in response to receiving a flow control message associated with one flow, the ingress locates the one flow in one of the ingress flow queues using the flow identification information.

3. The system of claim 2, wherein the ingress sends data from the one flow to the egress based on the egress space availability information in the flow control message associated with the one flow.

4. The system of claim 3, wherein the data from the one flow comprises one or more cells, and wherein at least one cell from the one flow has been received by the egress when the egress sends the flow control message associated with the one flow.

5. The system of claim 2, wherein when the flow control message associated with the one flow includes the new priority level, the ingress updates the one flow with the new priority level.

6. A system, comprising:

a switch fabric;

an ingress coupled with the switch fabric to send flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress coupled with the switch fabric to receive the flows from the ingress and to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows to the egress, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein the ingress comprises ingress flow queues, wherein in response to receiving a flow control message associated with one flow, the ingress locates the one flow in one of the ingress flow queues using the flow identification information,

wherein the ingress flow queues comprises;

a first set of one or more ingress flow queues having flows that are selected in a first-in-first-out order such that flow selection by the ingress occurs when flow position is at a head of the ingress flow queue, and

a second set of one or more ingress flow queues having flows that are selected in any order such that flow selection by the ingress occurs regardless of flow position in the ingress flow queue.

7. The system of claim 6, wherein one ingress flow queue in the second set is associated with a lowest priority level.

8. The system of claim 6, wherein the ingress selects a flow having a highest priority level from the first set of one or more ingress flow queues.

9. The system of claim 6, wherein a new flow arriving at the ingress is placed in any of the ingress flow queues in the first set of ingress flow queues.

10. A system, comprising:

a switch fabric;

an ingress coupled with the switch fabric to send flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress coupled with the switch fabric to receive the flows from the ingress and to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows to the egress, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein the ingress comprises ingress flow queues, wherein in response to receiving a flow control message associated with one flow, the ingress locates the one flow in one of the ingress flow queues using the flow identification information,

wherein when the flow control message associated with the one flow includes the new priority level, the ingress updates the one flow with the new priority level, and

wherein the one flow having the new priority level is moved to a position in an ingress flow queue associated with a priority level similar to the new priority level of the one flow.

11. A system, comprising:

a switch fabric;

an ingress coupled with the switch fabric to send flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress coupled with the switch fabric to receive the flows from the ingress and to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows to the egress, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein the egress space availability information and the new priority level for an individual flow are calculated based on current and previous occupancy by the individual flow and current and previous occupancy of an aggregate of all flows in an egress queue.

12. A system, comprising:

a switch fabric;

an ingress coupled with the switch fabric to send flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress coupled with the switch fabric to receive the flows from the ingress and to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows to the egress, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein the egress space availability information and the new priority level for the flow are calculated using hysteresis to reduce egress space allocation changes, priority level changes and a number of flow control messages between the egress and the ingress.

13. A system, comprising:

a switch fabric;

an ingress coupled with the switch fabric to send flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress coupled with the switch fabric to receive the flows from the ingress and to send one or more flow control messages to the ingress to control a pace that the ingress sends the flows to the egress, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein one of the flow control messages further comprises an importance bit to enable the ingress to decide if the one flow control message can be dropped.

14. The system of claim 13, further comprising a flow control message queue to store the flow control messages, and wherein the ingress drops non-important flow control messages when the flow control message queue reaches a threshold.

15. A system, comprising:

a switch fabric;

an ingress means for sending flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress means for receiving the flows from the ingress means and sending one or more flow control messages to the ingress means to control a pace that the ingress means sends the flows to the egress means, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow.

16. The system of claim 15, wherein the ingress means comprises ingress flow queues, wherein in response to receiving a flow control message associated with one flow, the ingress means locates the one flow in one of the ingress flow queues using the flow identification information.

17. The system of claim 16, wherein the ingress means sends data from the one flow to the egress means based on the egress space availability information in the flow control message associated with the one flow.

18. The system of claim 17, wherein the data from the one flow comprises one or more cells, and wherein at least one cell from the one flow has been received by the egress means when the egress means sends the flow control message associated with the one flow.

19. A system, comprising:

a switch fabric;

an ingress means for sending flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress means for receiving the flows from the ingress means and sending one or more flow control messages to the ingress means to control a pace that the ingress means sends the flows to the egress means, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein the egress space availability information and the new priority level for an individual flow are calculated based on current and previous occupancy by the individual flow and current and previous occupancy of an aggregate of all flows in an egress queue.

20. A system, comprising:

a switch fabric;

an ingress means for sending flows of data across the switch fabric, each of the flows is associated with flow identification information; and

an egress means for receiving the flows from the ingress means and sending one or more flow control messages to the ingress means to control a pace that the ingress means sends the flows to the egress means, each of the flow control messages including one or more of a flow identification information, an egress space availability information and a new priority level for a flow,

wherein the egress space availability information and the new priority level for an individual flow are calculated using hysteresis to reduce egress space allocation changes, priority level changes and a number of flow control messages between the egress and the ingress.

21. A method, comprising:

receiving a first flow data for a flow from an ingress, the first flow data stored in an egress queue storing one or more flows, the flow associated with flow identification information;

determining space availability information in the egress queue for the flow;

an

sending a flow control message to the ingress to control a pace that the ingress sends a second flow data for the flow, the flow control message comprising the flow identification information; and

determining a new priority level for the flow, wherein when the new priority level of the flow is lower than a current priority level of the flow, the ingress sends the second flow data at a slower pace than a current pace.

22. The method of claim 21, wherein the flow control message comprises the new priority level for the flow.

23. A method, comprising:

receiving a first flow data for a flow from an ingress, the first flow data stored in an egress queue storing one or more flows, the flow associated with flow identification information;

determining space availability information in the egress queue for the flow;

sending a flow control message to the ingress to control a pace that the ingress sends a second flow data for the flow, the flow control message comprising the flow identification information; and

determining a new priority level for the flow, wherein when the new priority level of the flow is lower than a current priority level of the flow, the ingress sends the second flow data at a slower pace than a current pace,

wherein the space availability information and the new priority level for the flow are calculated based on current and previous occupancy by the flow and current and previous occupancy of an aggregate of the one or more flows in the egress queue.

24. A method, comprising:

receiving a first flow data for a flow from an ingress, the first flow data stored in an egress queue storing one or more flows, the flow associated with flow identification information;

determining space availability information in the egress queue for the flow;

sending a flow control message to the ingress to control a pace that the ingress sends a second flow data for the flow, the flow control message comprising the flow identification information; and

determining a new priority level for the flow, wherein when the new priority level of the flow is lower than a current priority level of the flow, the ingress sends the second flow data at a slower pace than a current pace,

wherein the space availability information and the new priority level for the flow are calculated using hysteresis to reduce egress space allocation changes, priority level changes and a number of flow control messages sent to the ingress.

25. A method, comprising:

receiving a flow control message associated with a flow from an egress to determine a pace to send flow data from the flow to the egress, the flow control message comprising flow identification information and a priority level;

in response to receiving the flow control message, locating the flow in one

of multiple ingress flow queues using the flow identification information; and

sending the flow data from the flow to the egress based on information in the flow control message,

wherein the flow control message comprises space availability information for the flow and the flow data is sent to the egress based on the priority level in the flow control message associated with the flow.

26. The method of claim 25, wherein the flow data is sent to the egress based on the space availability information in the flow control message associated with the flow.

27. A method, comprising:

receiving a flow control message associated with a flow from an egress to determine a pace to send flow data from the flow to the egress, the flow control message comprising flow identification information and a priority level;

in response to receiving the flow control message, locating the flow in one of multiple ingress flow queues using the flow identification information; and

sending the flow data from the flow to the egress based on information in the flow control message,

wherein the multiple ingress flow queues comprises;

a first set of one or more ingress flow queues having flows that are selected in a first-in-first-out order such that flow selection occurs when flow position is at a head of the ingress flow queue, and

a second set of one or more ingress flow queues having flows that are selected in any order such that flow selection occurs regardless of flow position in the ingress flow queue.

28. The method of claim 27, wherein an arriving flow is placed in any of the ingress flow queues in the first set of ingress flow queues.

29. The method of claim 27, wherein each of the ingress flow queues in the first set is associated with a priority level, wherein flow data from a flow in an ingress flow queue in the first set of ingress flow queues having a highest priority level is processed first, and wherein the one ingress flow queue in the second set is associated with a lowest priority level.

30. The method of claim 29, wherein flow data for an individual flow is not sent to the egress when the individual flow is placed in the one ingress flow queue in the second set of ingress flow queues.

31. The method of claim 30, wherein the individual flow is placed in the one ingress flow queue in the second set of ingress flow queues when the priority level in the flow control message associated with the individual flow is the same as the priority level associated with the one ingress flow queue in the second set of flow queues.

32. The method of claim 31, wherein an individual flow is removed from the one ingress flow queue in the second set of ingress flow queues when the priority level in the flow control message associated with the individual flow is higher than the priority level associated with the one ingress flow queue in the second set of flow queues, wherein the individual flow is placed in an ingress flow queue in the first set of ingress flow queues.

33. The method of claim 32, wherein the individual flow is placed in the ingress flow queue associated with the same priority level included in the flow control message for the individual flow.

34. A method, comprising:

receiving a flow control message associated with a flow from an egress to determine a pace to send flow data from the flow to the egress, the flow control message comprising flow identification information and a priority level;

in response to receiving the flow control message, locating the flow in one of multiple ingress flow queues using the flow identification information; and

sending the flow data from the flow to the egress based on information in the flow control message,

wherein the flow control message further comprises an importance bit such that when set as non-important, the flow control message can be dropped.