Maintaining packet sequence using cell flow control

• US 7,688,816 B2
• Filed: 12/03/2004
• Issued: 03/30/2010
• Est. Priority Date: 03/15/2004
• Status: Active Grant

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Park, Jinsoo, Chao, Hung-Hsiang Jonathan
• Primary Examiner(s): Cho; Hong
• Assistant Examiner(s): Scheibel; Robert C
• Application Number:
  US11/004,260
• Publication Number:
  US 20050201400A1
• Time in Patent Office: 1,943 Days
• Field of Search: None
• US Class Current: 370/389
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue

Abstract

Packets out-of-sequence problem can be solved by using a window flow control scheme that can dispatch traffic at the cell level, in a round robin fashion, as evenly as possible. Each VOQ at the input port has a sequence head pointer that is used to assign sequence numbers (SN) to the cells. Also a sequence tail pointer is available at each VOQ that is used to acknowledge and limit the amount of cells that can be sent to the output ports based on the window size of the scheme. Each VIQ at the output port has a sequence pointer or sequence number (SN) pointer that indicates to the VIQ which cell to wait for. Once the VIQ receives the cell that the SN pointer indicated, the output port sends an ACK packet back to the input port. By using sequence numbers and the relevant pointers, the packet out-of-sequence problem is solved.

Claims

1. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, a method comprising:

tracking, for each of the virtual output queues, an available cell count;

if the available cell count for a selected non-empty virtual output queue is greater than a predetermined value,

sending a cell from the selected non-empty virtual output queue, and

updating, in a first way, the available cell count corresponding to the selected non-empty virtual output queue;

if a message is received from the egress traffic manager that indicates that an output port corresponding to the selected non-empty virtual output queue has moved in order a cell received out of order by the non-empty virtual input queue from the corresponding virtual input queue to a reassembly queue, updating, in a second way, the available cell count corresponding to the virtual output queue;

identifying a link fault;

sending a flush packet to the egress traffic manager component that received packets by the link that had a fault; and

flushing associated virtual input queues associated with the ingress traffic manager component.

2. The method of claim 1 wherein the act of updating the available cell count corresponding to the selected non-empty virtual output queue in the first way includes decreasing the available cell count, and

wherein the act of updating the available cell count corresponding to the virtual output queue in the second way includes increasing the available cell count.

3. The method of claim 1 further comprising:

examining virtual output queues in a fair manner to find a non-empty virtual output queue.

4. The method of claim 1 further comprising:

receiving a cell at the egress traffic component;

determining whether or not the cell was received in order; and

if it is determined that the cell was received in order, then

generating the message,

sending the message to the ingress traffic component, and

moving the cell from the virtual input queue to the reassembly queue.

21. The method of claim 3 wherein the examining of the virtual output queues in a fair manner comprises a round robin fashion.

5. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, a method comprising:

receiving a cell at a virtual input queue of the egress traffic manager component;

determining whether or not the cell was received in order;

if it is determined that the cell was received in order, then

generating a message indicative of a cell received in order,

sending the message indicative of the cell received in order to the ingress traffic manager component, and

moving the cell from the virtual input queue to the reassembly queue;

if it is determined that the cell was not received in order, then holding the cell in the virtual input queue until all prior cells are received;

accepting the message indicative of the cell received in order in a virtual output queue;

updating an available cell count corresponding to the virtual output queue;

identifying a link fault;

sending a flush packet to the egress traffic manager component that received packets by the link that had a fault; and

flushing associated virtual input queues associated with the ingress traffic manager component.

6. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, a method of reducing a potential number of out-of-sequence cells sent from a first virtual output queue, the method comprising:

maintaining an available cell count for the first virtual output queue, and sending a cell from the first virtual output queue only if the cell count is greater than a predetermined value;

re-sequencing any out-of-sequence cells at the egress traffic manager component by storing cells received out of order in a location in the virtual input queue corresponding to the order of the cell and moving cells from the virtual input queue to the reassembly queue after all prior cells are received;

identifying a link fault;

sending a flush packet to the egress traffic manager component that received packets by the link that had a fault; and

flushing associated virtual input queues associated with the ingress traffic manager component.

7. The method of claim 6 wherein the act of maintaining an available cell count includes:

increasing the cell count when an output port corresponding to the first virtual output queue moves one or more in-sequence cells from a virtual input queue to a reassembly queue, and,

decreasing the cell count when the first virtual output queue sends one or more cells.

8. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, a method comprising:

tracking, for each of the virtual output queues, an available cell count using a first variable and a second variable;

for a non-empty virtual output queue, if a difference between the first variable and the second variable is less than a predetermined window value,

inserting the first variable, corresponding to the non-empty virtual output queue, into a cell as a sent sequence number;

sending the cell from the non-empty virtual output queue wherein the sent sequence number is used to determine where to store cells at a location in the virtual input queue, and

incrementing the first variable corresponding to the non-empty virtual output queue; and

for the non-empty virtual output queue, if a message including an acknowledge sequence number is received from the egress traffic manager component that an output port corresponding to the non-empty virtual output queue has moved a cell from its virtual input queue to a reassembly queue, then setting the second variable, corresponding to the non-empty virtual output queue, to a value of the acknowledge sequence number; and

,

receiving a cell at the egress traffic manager component;

determining whether or not the cell was received in order; and

if it is determined that the cell was received in order, then

generating the message including the sent sequence number of the cell as an acknowledge sequence number,

sending the message to the ingress traffic manager component,

moving the cell from the virtual input queue to the reassembly queue along with cells with intervening sequence numbers that were received out of order;

identifying a link fault;

sending a flush packet to the egress traffic manager component that received packets by the link that had a fault; and

flushing associated virtual input queues associated with the ingress traffic manager component.

9. The method of claim 8 further comprising:

examining virtual output queues in a fair manner to find a non-empty virtual output queue.

22. The method of claim 9 wherein the examining of the virtual output queues in a fair manner comprises a round robin fashion.

10. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, a method comprising:

maintaining, for each of the virtual input queues, a pointer variable;

receiving a cell, including a sent sequence number, at the egress traffic component;

storing the cell in one virtual input queues as a function of the sent sequence number and not on the basis of the order that the cell was received;

determining whether or not the cell was received in order; and

if it is determined that the cell was received in order, then

generating a cell received in order message including the sent sequence number as an acknowledge sequence number,

sending the cell received in order message to the ingress traffic component, and

moving the cell from the virtual input queue to the reassembly queue;

for a virtual output queue, accepting the cell received in order message;

updating an available cell count corresponding to the virtual output queue;

identifying a link fault;

sending a flush packet to the egress traffic manager component that received packets by the link that had a fault; and

flushing associated virtual input queues associated with the ingress traffic manager component.

11. The method of claim 10 wherein the act of determining whether or not the cell was received in order uses the pointer variable for the virtual input queue in which the cell was received in order and the sent sequence number of the cell.

12. The method of claim 11 wherein the cell is determined to be received in order if the pointer variable for the virtual input queue equals the sent sequence number of the cell.

13. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, an apparatus comprising:

for each of the virtual output queues, at least one component configured for tracking an available cell count;

wherein for each of the virtual output queues that are not empty, the component is further configured to

send a cell from the virtual output queue, and

update, in a first way, the available cell count corresponding to the virtual

output queue, if the available cell count is greater than a predetermined value; and

wherein for each of the virtual output queues, the at least one component is further configured for updating, in a second way, the available cell count corresponding to the virtual output queue if a message is received from the egress traffic manager component that an output port corresponding to the virtual output queue has moved a cell received out of order in the virtual input queue from its virtual input queue to a reassembly queue, wherein the at least one component is further configured to reorder into the reassembly queue cells received out of order in the virtual input port; and

a component for identifying a link fault;

a component for sending a flush packet to an egress traffic manager component that received packets by the link that had a fault; and

a component for flushing associated virtual input queues associated with the ingress traffic manager component.

14. The apparatus of claim 13 wherein the component for updating the available cell count corresponding to each of the virtual output queues in the first way includes a component for decreasing the available cell count, and

wherein the component for updating the available cell count corresponding to each of the virtual output queues in the second way is further configured for increasing the available cell count.

15. The apparatus of claim 13 further comprising:

a component for examining virtual output queues in a fair manner to find a non-empty virtual output queue.

16. The apparatus of claim 13 further comprising:

a cell receiving component for receiving a cell at the egress traffic component;

a determining component for determining whether or not the cell was received in order; and

at least another component for

generating the message,

sending the message to the ingress traffic component, and

moving the cell from the virtual input queue to the reassembly queue, if it is

determined that the cell was received in order.

23. The apparatus of claim 15 wherein the component examining the virtual output queues in a fair manner uses a round robin technique.

17. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, an apparatus comprising:

means for sending cells front a virtual output queue in such a way that limits a potential number of out-of-sequence cells, wherein the potential number of out-of-sequence cells is limited by;

means for maintaining an available cell count for the virtual output queue, and

means for determining when the cell count is greater than a predetermined

value and sending a cell from the virtual output queue only when the cell

count is greater than the predetermined value; and

means for re-sequencing any out-of-sequence cells at the egress traffic manager component by storing the cell received in one of the virtual input queues in a location based on the order that the cell was sent and not the order that the cell was received;

means for identifying a link fault;

means for sending a flush packet to an egress traffic manager component that received packets by the link that had a fault; and

means for flushing associated virtual input queues associated with the ingress traffic manager component.

18. For use in a system having an ingress traffic manager component having a plurality of virtual output queues, and an egress traffic manager component having a plurality of virtual input queues and a plurality of reassembly queues, apparatus comprising:

means for tracking, for at least one of the virtual output queues, an available cell count using a first variable and a second variable;

means for determining that the at least one virtual output queue is non-empty and;

inserting the first variable, corresponding to the non-empty virtual output queue, into a cell as a sent sequence number;

sending the cell from the non-empty virtual output queue, and

incrementing the first variable corresponding to the non-empty virtual output queue,

wherein the means inserts, sends and increments if a difference between the first variable and the second variable is less than a predetermined window value;

means, for the at least one virtual output queue, far setting the second variable, corresponding to the at least one virtual output queue, to a value of the acknowledge sequence number if a message including an acknowledge sequence number is received from the egress traffic manager component that an output port corresponding to the at least one virtual output queue has moved a cell from its virtual input queue to a reassembly queue;

means for storing a cell as a function of the sequence number in the virtual input queue so that cells can be received out of order and reordered when moving the cells to the reassembly queue;

means for identifying a link fault;

means for sending a flush packet to the egress traffic manager component that receive packets by the link that had a fault; and

means for flushing associated virtual input queues associated wit the ingress traffic manager component.

19. The apparatus of claim 18 further comprising:

means for examining virtual output queues in a fair manner to find a non-empty virtual output queue.

20. The apparatus of claim 18 further comprising:

means for receiving a cell at the egress traffic manager component;

means for determining whether or not the cell was received in order; and

means for,

generating the message including the sent sequence number of the cell as an acknowledge sequence number,

sending the message to the ingress traffic component, and

moving the cell from the virtual input queue to the reassembly queue when it is determined that the cell was received in order.