Packet reassembly and deadlock avoidance for use in a packet switch

• US 20050025141A1
• Filed: 06/18/2004
• Published: 02/03/2005
• Est. Priority Date: 06/19/2003
• Status: Active Grant

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Park, Jinsoo, Chao, Hung-Hsiang Jonathan
• Granted Patent: US 7,852,829 B2
• Time in Patent Office: Days
• US Class Current: 370/386
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections

Abstract

Practical packet reassembly in large, multi-plane, multi-stage switches is possible by using a scheduling technique called dynamic packet interleaving. With dynamic packet interleaving scheduling, if more than one packet is contending for the same output link in a switch module, an arbiter in the switch module gives priority to a partial packet (i.e., to a packet that has had at least one cell sent to the queue). The number of reassembly queues required to ensure reassembly is dramatically reduced (e.g., to the number of paths multiplied by the number of scheduling priorities). Deadlock may be avoided by guaranteeing (e.g., reserving) at least one cell space for all partial packets.

Claims

1. For use in a system having a source module with a plurality of source queues, each of the source queues for storing one or more cells of one or more packets, a destination module with a plurality of destination queues, each of the destination queues for storing one or more cells of one or more packets, and a link between the source module and the destination module, a method for scheduling the communication of cells over the link comprising:

a) determining, in a substantially fair manner, a non-empty source queue to grant access to the link at a given time;

b) determining whether or not to transmit a head-of-line cell of the determined non-empty source queue such that the transmission of cells of packets destined for different destination queues can be interleaved, but the transmission of cells of different packets destined for the same destination queue cannot be interleaved;

c) if it is determined to transmit the head-of-line cell of the determined non-empty source queue, then transmitting the-head-of line cell; and

d) if it is determined not to transmit the head-of-line cell of the determined non-empty source queue, then determining a next, non-empty source queue to grant access to the link in a substantially fair manner.

2. The method of claim 1 wherein the act of determining, in a substantially fair manner, a non-empty source queue to grant access to the.link at a given time, uses a round-robin discipline.

3. The method of claim 2 wherein the act of determining a next, non-empty source queue to grant access to the link in a substantially fair manner uses a round-robin discipline.

4. The method of claim 1 wherein if the head-of-line cell is transmitted, then a next non-empty source queue to grant access to the link is determined in a substantially fair manner.

5. The method of claim 1 wherein if the head-of-line cell is transmitted and the head-of-line cell is an end-of-packet cell, then a next non-empty source queue to grant access to the link is determined in a substantially fair manner.

6. The method of claim 1 wherein if the head-of-line cell is transmitted and the head-of-line cell is a single-cell-packet cell, then a next non-empty source queue to grant access to the link is determined in a substantially fair manner.

7. The method of claim 1 wherein if the head-of-line cell is transmitted and the head-of-line cell is either an end-of-packet cell or a single-cell-packet cell, then a next non-empty source queue to grant access to the link is determined in a substantially fair manner, but otherwise, the same source queue will continue to have access to the link.

8. The method of claim 1 wherein the act of determining whether or not to transmit a head-of-line cell of the determined non-empty source queue includes determining whether or not the head-of-line cell is eligible, wherein if the head-of-line cell is determined to be eligible, then transmitting the head-of-line cell, and wherein if the head-of-line cell is not determined to be eligible, then not transmitting the head-of-line cell.

9. The method of claim 1 wherein the source module and the destination module are provided in a multi-plane, multistage switch having p planes, m central modules, and supporting q priorities, and wherein an egress traffic manager module needs only p*m*q reassembly queues to ensure packet reassembly.

10. The method of claim 1 wherein the source module and the destination module are provided in a multi-plane, multistage switch having p planes and m central modules and wherein an egress traffic manager module needs only p*m reassembly queues to ensure packet reassembly.

11. The method of claim 8 wherein the act of determining whether or not the head-of-line cell is eligible is used to reserve memory space in a buffer in which the destination queue is defined, for one or more partial packets stored in the destination queues.

12. The method of claim 8 wherein the head-of-line cell is determined to be eligible if (1) the head-of-line cell is a beginning-of-packet cell, (2) the destination queue is not storing cells of another packet, (3) a sum of a buffer outstanding cell count, a buffer reserved cell count and a maximum reserved cell constant is not greater than a size of a buffer in which the destination queue is defined, and (4) a sum of a queue outstanding cell counter and the maximum reserved cell constant is not greater than a size of the destination queue.

13. The method of claim 8 wherein the head-of-line cell is determined to be eligible if (1) the head-of-linecell is one of a continue-of-packet cell and an end-of-packet cell, and (2) a queue reserved cell count is greater than zero.

14. The method of claim 8 wherein the head-of-line cell is determined to be eligible if (1) the head-of-line cell is one of a continue-of-packet cell and an end-of-packet cell, (2) a sum of a buffer outstanding cell count and a buffer reserved cell count is less than a size of a buffer in which the destination queue is defined, and (3) a queue outstanding cell count is less than a size of the destination queue.

15. The method of claim 8 wherein the head-of-line cell is determined to be eligible if (1) the head-of-line cell is a single-cell-packet cell, (2) the destination queue is not storing cells of another packet, (3) a sum of a buffer outstanding cell count and a buffer reserved cell count is less than a size of a buffer in which the destination queue is defined, and (4) a queue outstanding cell count is less than a size of the destination queue.

16. For use in a system having a source module with a plurality of source queues, each of the source queues for storing one or more cells of one or more packets, a destination module with a plurality of destination queues, each of the destination queues for storing one or more cells of one or more packets, and a link between the source module and the destination module, a scheduler comprising:

a) means for determining, in a substantially fair manner, a non-empty source queue to grant access to the link at a given time;

b) means for determining whether or not to transmit a head-of-line cell of the determined non-empty source queue such that the transmission of cells of packets destined for different destination queues can be interleaved, but the transmission of cells of different packets destined for the same destination queue cannot be interleaved; and

c)means for transmitting the-head-of line cell only if it is determined to transmit the head-of-line cell of the determined non-empty source queue,

wherein the means for determining a non-empty source queue determines a next, non-empty source queue to grant access to the link in a substantially fair manner if it is determined not to transmit the head-of-line cell of the determined non-empty source queue.

17. The apparatus of claim 16 wherein the means for determining, in a substantially fair manner, a non-empty source queue to grant access to the link at a given time, use a round-robin discipline.

18. The apparatus of claim 17 wherein the means for determining a next, non-empty source queue to grant access to the link in a substantially fair manner use a round-robin discipline.

19. The apparatus of claim 16 wherein the means for determining a non-empty source queue determines a next non-empty source queue to grant access to the link in a substantially fair manner if the head-of-line cell is transmitted.

20. The apparatus of claim 16 wherein the means for determining a non-empty source queue determines a next non-empty source queue to grant access to the link in a substantially fair manner if the head-of-line cell is transmitted and the head-of-line cell is an end-of-packet cell.

21. The apparatus of claim 16 wherein the means for determining a non-empty source queue determines a next non-empty source queue to grant access to the link in a substantially fair manner if the head-of-line cell is transmitted and the head-of-line cell is a single-cell-packet cell.

22. The apparatus of claim 16 wherein the means for determining a non-empty source queue determines a next non-empty source queue to grant access to the link in a substantially fair manner if the head-of-line cell is transmitted and the head-of-line cell is either an end-of-packet cell or a single-cell-packet cell, but otherwise, the same source queue will continue to have access to the link.

23. The apparatus of claim 16 wherein the means for determining whether or not to transmit a head-of-line cell of the determined non-empty source queue includes means for determining whether or not the head-of-line cell is eligible, wherein if the head-of-line cell is determined to be eligible, then transmitting the head-of-line cell, and wherein if the head-of-line cell is not determined to be eligible, then not transmitting the head-of-line cell.

24. The apparatus of claim 16 wherein the source module and the destination module are provided in a multi-plane, multistage switch having p planes, m central modules, and supporting q priorities, and wherein an egress traffic manager module needs only p*m*q reassembly queues to ensure packet reassembly.

25. The apparatus of claim 16 wherein the source module and the destination module are provided in a multi-plane, multistage switch having p planes and m central modules and wherein an egress traffic manager module needs only p*m reassembly queues to ensure packet reassembly.

26. The apparatus of claim 23 wherein the means for determining whether or not the head-of-line cell is eligible is used to reserve memory space in a buffer in which the destination queue is defined, for one or more partial packets stored in the destination queues.

27. The apparatus of claim 23 wherein the head-of-line cell is determined to be eligible if (1) the head-of-line cell is a beginning-of-packet cell, (2) the destination queue is not storing cells of another packet, (3) a sum of a buffer outstanding cell count, a buffer reserved cell count and a maximum reserved cell constant is not greater than a size of a buffer in which the destination queue is defined, and (4) a sum of a queue outstanding cell counter and the maximum reserved cell constant is not greater than a size of the destination queue.

28. The apparatus of claim 23 wherein the head-of-line cell is determined to be eligible if (1) the head-of-linecell is one of a continue-of-packet cell and an end-of-packet cell, and (2) a queue reserved cell count is greater than zero.

29. The apparatus of claim 23 wherein the head-of-line cell is determined to be eligible if (1) the head-of-line cell is one of a continue-of-packet cell and an end-of-packet cell, (2) a sum of a buffer outstanding cell count and a buffer reserved cell count is less than a size of a buffer in which the destination queue is defined, and (3) a queue outstanding cell count is less than a size of the destination queue.

30. The apparatus of claim 23 wherein the head-of-line cell is determined to be eligible if (1) the head-of-line cell is a single-cell-packet cell, (2) the destination queue is not storing cells of another packet, (3) a sum of a buffer outstanding cell count and a buffer reserved cell count is less than a size of a buffer in which the destination queue is defined, and (4) a queue outstanding cell count is less than a size of the destination queue.

31. For use in a system having a source module with a plurality of source queues, each of the source queues for storing one or more cells of one or more packets, a destination module with a plurality of destination queues, each of the destination queues for storing one or more cells of one or more packets, and a link between the source module and the destination module, a method for scheduling the communication of cells over the link comprising:

a)performing cell scheduling to determine which of a plurality of head-of-line cells to transmit over a link at any given time; and

b)sending head-of-line cells in the source queues in accordance with the cell scheduling determinations,

wherein the cell scheduling determinations are made such that cells of different packets destined for different destination queues can be interleaved but cells of different packets destined for the same destination queue cannot be interleaved.

32. For use in a system having a source module with a plurality of source queues, each of the source queues for storing one or more cells of one or more packets, a destination module with a plurality of destination queues, each of the destination queues for storing one or more cells of one or more packets, and a link between the source module and the destination module, a method for scheduling the communication of cells over the link comprising:

a) performing cell scheduling to determine which of a plurality of head-of-line cells to transmit over a link at any given time; and

b) sending head-of-line cells in the source queues in accordance with the cell scheduling determinations,

wherein at least one destination queue is provided in a buffer, and

wherein if a part of a packet has been sent, but not the entire packet, at least one cell space is reserved in the buffer for the partially sent packet.