Prioritization and preemption of data frames over a switching fabric

• US 8,379,524 B1
• Filed: 12/08/2008
• Issued: 02/19/2013
• Est. Priority Date: 10/16/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Jacobs, Mick R., Benning, Michael A.
• Primary Examiner(s): Divecha, Nishant B
• Application Number:
  US12/330,117
• Time in Patent Office: 1,534 Days
• Field of Search: None
• US Class Current: 370/235.1
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3018 Input queuing

Abstract

Network switching and/or routing devices can use multiple priority data streams and queues to support prioritized serial transmission of data from line cards (or the like) through a fabric switch to other line cards (or the like). Preemption logic is used to insert within a data stream commands indicating a switch from one priority level data to another. Delimiter commands and combination switch/delimiter commands can also be used. Multiple crossbars are implemented in the fabric switch to support the various data stream priority levels.

Claims

1. A method comprising:

receiving a data stream, wherein

the data stream comprises data having a first priority level and data having a second priority level;

detecting a priority level of data from the data stream;

storing data having the first priority level in a first input queue;

storing data having the second priority level in a second input queue; and

simultaneously transmitting data from the first and second input queues to first and second crossbars, respectively, wherein

the simultaneously transmitting data comprises

transmitting data having the first priority level through the first crossbar coupled to the first input queue, and

transmitting data having the second priority level through the second crossbar coupled to the second input queue,

the first crossbar only switches data having the first priority level,

the first crossbar is not configured to switch data having the second priority level,

the second crossbar only switches data having the second priority level, and

the second crossbar is not configured to switch data having the first priority level.

2. The method of claim 1 wherein the first input queue and the second input queue are formed from a memory logically organized into the first input queue and the second input queue.

3. The method of claim 1 wherein the first priority level is greater than the second priority level.

4. The method of claim 1 wherein the data stream includes data having at least one additional priority level, the method further comprising:

transmitting data having the at least one additional priority level through at least one additional crossbar.

5. The method of claim 1 further comprising:

receiving the data having the first priority level and transmitted through the first crossbar;

storing the data having the first priority level and transmitted through the first crossbar in a first output queue;

receiving the data having the second priority level and transmitted through the second crossbar; and

storing the data having the second priority level and transmitted through the second crossbar in a second output queue.

6. The method of claim 5 wherein the first output queue and the second output queue are formed from a memory logically organized into the first output queue and the second output queue.

7. The method of claim 5 further comprising:

transmitting data stored in the first output queue; and

transmitting data stored in the second output queue.

8. The method of claim 7 wherein the transmitting data stored in the first output queue and the transmitting data stored in the second output queue are performed based on the priority levels of the respective data.

9. The method of claim 5 further comprising:

determining at least one priority level control code; and

selectively transmitting data having the first priority level and data having the second priority level along with the at least one priority level control code.

10. The method of claim 1, wherein

the transmitting data having the first priority level through the first crossbar is performed based on priority level of the data having the first priority level.

11. An apparatus comprising:

at least one input means for receiving and storing data, wherein

the data comprises data having a first priority level and data having a second priority level;

a first data path coupled between the at least one input means and a first switching means;

a second data path coupled between the at least one input means and a second switching means;

wherein the at least one input means is configured to simultaneously transmit data having the first priority level and data having the second priority level to the first and second switching means, respectively, via the first and second data paths, respectively;

wherein the first switching means is configured to transfer only data having the first priority level from the at least one input means, wherein the first switching means is not configured to transfer data having the second priority level;

wherein the second switching means is configured to transfer only data having the second priority level from the at least one input means, wherein the second switching means is not configured to transfer data having the first priority level; and

at least one output means for receiving and storing the data having the first priority level from the first switching means and the data having the second priority level from the second switching means, the at least one output means being coupled to the first and second switching means.

12. The apparatus of claim 11 wherein the at least one input means further comprises:

a plurality of means for queuing data, each of the plurality of means for queuing means storing data having a particular priority.

13. The apparatus of claim 11 further comprising a means for storing data, wherein the means for storing data is logically organized into a first means for queuing data and a second means for queuing data.

14. The apparatus of claim 11 wherein the at least one input means includes a detection means for distinguishing between data having the first priority level and data having the second priority level.

15. An apparatus comprising:

first and second input buffers each configured to receive first and second data, respectively, wherein

the first data comprises data having a first priority level and data having a second priority level, and

the second data includes data having the first priority level and data having the second priority level;

a first crossbar coupled to the first and second input buffers, the first crossbar configured

to receive only data from the first and second input buffers having the first priority level, wherein

the first crossbar is not configured to receive data having the second priority level from the first and second input buffers;

a second crossbar coupled to the first and second input buffers, the second crossbar configured to receive only data from the first and second input buffers having the second priority level, wherein

the second crossbar is not configured to receive data having the first priority level from the first and second input buffers;

a first data path coupled between the first input buffer and the first crossbar;

a second data path coupled between the first input buffer and the second crossbar;

wherein the first input buffer is configured to simultaneously transmit data having the first priority level and data having the second priority level to the first and second crossbars, respectively, via the first and second data paths, respectively;

a first circuit configured to read only data having the first priority level from the first input buffer for subsequent transmission to the first crossbar;

a second circuit configured to read only data having the second priority level from the first input buffer for subsequent transmission to the second crossbar;

first and second output buffers coupled to the first crossbar and second crossbars, wherein

the first output buffer is configured to receive data having the first priority level from the first crossbar and data having the second priority level from the second crossbar, and

the second output buffer is configured to receive data having the first priority level from the first crossbar and data having the second priority level from the second crossbar.

16. The apparatus of claim 15 wherein the first input buffer further comprises:

a plurality of data queues, each of the plurality of data queues storing data having a respective priority.

17. The apparatus of claim 15 further comprising:

first and second line cards, each of which being coupleable to a respective network device and configured to transmit/receive data thereto/therefrom;

wherein the first and second line cards are coupled to the first and second input buffers, respectively; and

wherein the first and second line cards are coupled to the first and second output buffers, respectively.

18. The apparatus of claim 17 wherein the first line card includes a priority selection circuit, the priority selection circuit configured to generate priority level control codes and to selectively transmit data having the first priority level and data having the second priority level.

19. The apparatus of claim 18 wherein data having the first priority level is preferentially transferred from the first line card to the first input buffer before data having the second priority level is transferred.

20. The apparatus of claim 15 wherein first output buffer further comprises:

a plurality of data queues, each of the plurality of data queues storing data having a particular priority.

21. The apparatus of claim 15 wherein the first output buffer includes a priority selection circuit, the priority selection circuit configured to generate priority level control codes and to selectively transmit data having the first priority level and data having the second priority level.