Prioritization and preemption of data frames over a switching fabric

• US 9,094,327 B2
• Filed: 12/28/2012
• Issued: 07/28/2015
• 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): Mesfin, Yemane
• Assistant Examiner(s): Elmejjarmi, Abdelillah
• Application Number:
  US13/729,867
• Publication Number:
  US 20130182704A1
• Time in Patent Office: 942 Days
• Field of Search: 370/357, 370/352, 370/356, 370/419, 370/463
• US Class Current: 1/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 first data stream, wherein

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

receiving a second data stream, wherein

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

generating a combined data stream, wherein

the generating is based on the first data stream and on the second data stream, and

the combined data stream comprises

portions of the first data stream,

portions of the second data stream,

one or more first delimiters, and

one or more second delimiters, wherein

each of the one or more first delimiters comprises a first switch code,

wherein

the first switch code indicates a change in priority from the first priority level to the second priority level,

each of the one or more second delimiters comprises a second switch code, wherein

the second switch code indicates a change in priority from the second priority level to the first priority level, and

the portions of the first data stream and the portions of the second data stream are separated using the one or more first delimiters and the one or more second delimiters.

2. The method of claim 1, wherein

the portions of the first data stream comprise a plurality of first data frames,

the portions of the second data stream comprise a plurality of second data frames, and

the generating the combined data stream comprises

generating the plurality of first data frames, and

generating the plurality of second data frames,

in the combined data stream.

3. The method of claim 2, wherein

the generating the combined data stream comprises

determining whether a next second data frame of the plurality of second data frames is available for transmission, and

in response to a determination that the next second data frame is available, pre-empting the generating of the plurality of first data frames in the combined data stream.

4. The method of claim 3, wherein

the pre-empting the generating of the plurality of first data frames comprises

inserting one of the one or more first delimiters in the combined data stream, and

pausing the generating of the plurality of first data frames.

5. The method of claim 3, wherein

the pre-empting is configured to be performed during generation of a first data frame of the plurality of first data frames, and

the generating the combined data stream further comprises

determining whether to resume the generation of the first data frame in the combined data stream,

in response to a determination to resume the generation of the first data frame, inserting one of the one or more second delimiters into the combined data stream, and

resuming the generation of the first data frame in the combined data stream.

6. The method of claim 2, wherein the generating the combined data stream further comprises

determining whether a first data frame of the plurality of first data frames is available for transmission,

in response to a determination that the first data frame is available, determining whether the first data frame is to be transmitted in the combined data stream, and

in response to a determination that the first data frame is to be transmitted, inserting the first data frame in the combined data stream.

7. The method of claim 2, wherein

at least one of the one or more first delimiters further indicates a next second data frame of the second data frames, and

at least one of the one or more second delimiters further indicates a next first data frame of the first data frames.

8. The method of claim 1, wherein

the combined data stream is configured to be received by an input module, and

the input module is configured to

process the combined data stream, and

transmit data having the first priority level and data having the second priority level to the first and second switching devices, respectively, via first and second data paths, respectively.

21. The method of claim 1, further comprising:

analyzing at least a portion of a frame of the first data stream; and

classifying a priority level of the first data stream in response to the analyzing.

9. An apparatus comprising:

a line card comprising

a forwarding module configured to

receive a first data stream, wherein

the first data stream comprises data having a first priority level,

receive a second data stream, wherein

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

a multiplexer module configured to

receive the first data stream and the second data stream from the forwarding module, and

generate a combined data stream, wherein

the multiplexer module is configured to perform the generating based on the first data stream and on the second data stream, and

the combined data stream further comprises

 

portions of the first data stream,

 

portions of the second data stream,

 

the first delimiters, and

 

the second delimiters, wherein

each of the one or more first delimiters comprises a first switch code, wherein

 

the first switch code indicates a change in priority from the first priority level to the second priority level,

each of the one or more second delimiters comprises a second switch code, wherein

 

the second switch code indicates a change in priority from the second priority level to the first priority level, and

the portions of the first data stream and the portions of the second data stream are separated by the one or more first delimiters and the one or more second delimiters.

10. The apparatus of claim 9, wherein

the portions of the first data stream comprise a plurality of first data frames,

the portions of the second data stream comprise a plurality of second data frames, and

the generating the combined data stream comprises

generating the plurality of first data frames, and

generating the plurality of second data frames,

in the combined data stream.

11. The apparatus of claim 10, wherein

the multiplexer module is configured to generate the combined data stream by

determining whether a next second data frame of the plurality of second data frames is available for transmission, and

in response to a determination that the next second data frame is available, pre-empting the generating of the plurality of first data frames in the combined data stream.

12. The apparatus of claim 10, wherein

the multiplexer module is configured to pre-empt the generation of the first data frames by

inserting one of the one or more first delimiters in the combined data stream, and

pausing the generating of the plurality of first data frames.

13. The apparatus of claim 10, wherein

the pre-empting the generating of the plurality of first data frames in the combined data stream pre-empts generation of a first data frame of the first data frames, and

at least one of the one or more second delimiters indicates resuming generation of the first data frame.

14. The apparatus of claim 10, wherein

at least one of the one or more first delimiters further indicates a next second data frame of the second data frames, and

at least one of the one or more second delimiters further indicates a next first data frame of the first data frames.

15. The apparatus of claim 10, wherein

the combined data stream is configured to be received by an input module,

the input module is configured to

process the combined data stream, and

transmit data having the first priority level and data having the second priority level to the first and second switching devices, respectively, via first and second data paths, respectively.

16. An apparatus comprising

first receiving means for receiving a first data stream, wherein

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

second receiving means for receiving a second data stream, wherein

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

generating means for generating a combined data stream, wherein

the generating is based on the first data stream and on the second data stream, and

the combined data stream comprises

portions of the first data stream,

portions of the second data stream,

one or more first delimiters, and

one or more second delimiters, wherein

each of the one or more first delimiters comprises a first switch code,

wherein

the first switch code indicates a change in priority from the first priority level to the second priority level,

each of the one or more second delimiters comprises a second switch code, wherein

the second switch code indicates a change in priority from the second priority level to the first priority level, and

the portions of the first data stream and the portions of the second data stream are separated by the one or more first delimiters and the one or more second delimiters.

17. The apparatus of claim 16, wherein

the portions of the first data stream comprise a plurality of first data frames,

the portions of the second data stream comprise a plurality of second data frames, and

the generating the combined data stream comprises

generating the plurality of first data frames, and

generating the plurality of second data frames,

in the combined data stream.

18. The apparatus of claim 16, wherein

the generating comprises

determining whether a next second data frame of the plurality of second data frames is available for transmission, and

in response to a determination that the next second data frame is available, pre-empting the generating of the plurality of first data frames in the combined data stream.

19. The apparatus of claim 16, wherein

at least one of the one or more first delimiters further indicates a next second data frame of the second data frames, and

at least one of the one or more second delimiters further indicates a next first data frame of the first data frames.

20. The apparatus of claim 16, wherein

the combined data stream is configured to be received by an input module,

the input module is configured to

process the combined data stream, and

transmit data having the first priority level and data having the second priority level to the first and second switching devices, respectively, via first and second data paths, respectively.