Reordering of out-of-order packets
View Patent ↗Tasks are assigned to process packets, but the tasks may not process the packets in the order in which the packets were received. Thus, the order of the packets may be lost during processing. The packets, however, should still be transferred in the order in which the packets were received. Therefore, reordering is performed. In particular, the reordering is performed by having tasks write commands for packets into command buffers of a command queue based on a packet sequence number of a packet matching a current sequence number associated with the buffer and by reading commands for consecutive packets in order by passing from one command buffer to another command buffer. With the command buffers in the command queue being written and read in this manner, the packets are “reordered” so that they are transferred in the order in which they were received.
1. A computer readable storage medium encoded with software instructions to perform the following operations when executed by a computer:
(1) receiving packets and assigning sequence numbers to the packets;
(2) using each packet's sequence number to assign a command buffer to the packet so that each two packets with consecutive sequence numbers are assigned different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein the computer is operable to have at least two commands for at least two of the packets to be written to different command buffers simultaneously or not in an order in which the corresponding sequence numbers are assigned to the Rackets in the operation (1);
(4) reading the commands from the command buffers and executing the commands to transfer the packets in an order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(5) wherein if any command buffer C 1 holds commands for at least two packets P 1 and P 2 with the packet P 1 having an earlier assigned sequence number than the packet P 2 , and another command buffer holds a command for another packet P 3 preceding P 2 but not P 1 , then the operation (4) is performed for the packet P 1 , then for the packet P 3 , then for the packet P 2 .
2. A signal embedded in a carrier medium and encoded with software instructions to perform the following operations when executed by a computer:
(1) receiving packets and assigning sequence numbers to the packets;
(2) using each packet's sequence number to assign a command buffer to the packet so that each two packets with consecutive sequence numbers are assigned different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein the computer is operable to have at least two commands for at least two of the packets to be written to different command buffers simultaneously or not in an order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(4) reading the commands from the command buffers and executing the commands to transfer the packets in an order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(5) wherein if any command buffer C 1 holds commands for at least two packets P 1 and P 2 with the packet P 1 having an earlier assigned sequence number than the packet P 2 , and another command buffer holds a command for another packet P 3 preceding P 2 but not P 1 , then the operation (4) is performed for the packet P 1 , then for the packet P 3 , then for the packet P 2 .
3. A method for processing packets, the method comprising:
(1) receiving the packets and assigning sequence numbers to the packets;
(2) using the packets' sequence numbers to assign command buffers to the packets so that each two packets with consecutive sequence numbers are assigned respective two different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein at least two commands for at least two of the packets are written to different command buffers simultaneously or not in an order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(4) reading the commands from the command buffers and executing the commands to transfer the packets in the order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(5) wherein for at least one command buffer C 1 which holds commands for at least two packets P 1 and P 2 with the packet P 1 having an earlier assigned sequence number than the packet P 2 , the operation (4) is performed so as to transfer the packet P 1 , then a packet assigned another command buffer, then the packet P 2 .
4. The method of claim 3 , wherein the command buffer is selected in the operation (2) based on a result of the packet sequence number modulo a number of said command buffers.
5. The method of claim 3 , further comprising:
determining whether the task may write commands into the selected command buffer based on whether a current sequence number of the command buffer matches a packet sequence number of the packet.
6. The method of claim 3 wherein for at least two packets P 1 and P 2 which are assigned a single command buffer C 1 , with the packet P 1 having an earlier assigned sequence number than the packet P 2 , the operation (3) is suspended for the packet P 2 until completion of the operation (3) for the packet P 1 .
7. The method of claim 3 wherein for any two packets P 1 and P 2 which are assigned a single command buffer C 1 , with the packet P 1 having an earlier assigned sequence number than the packet P 2 , the operation (3) is not allowed to proceed for the packet P 2 until completion of the operation (3) for the packet P 1 .
8. The method of claim 3 wherein the operation (4) is performed sequentially for different command buffers taken in an order in which the command buffers are assigned to packets in the operation (2).
9. The method of claim 3 wherein all of said packets are received on a single lane, the method further comprising:
receiving packets for one or more other lanes, wherein each lane is associated with a plurality of command buffers; and
performing the operations (1) through (5) for each lane and its associated plurality of the command buffers.
10. The method of claim 3 further comprising selecting and assigning a task for each packet, wherein the operation (3) is performed for each packet by the packet's assigned task executed by a processor.
11. The system of claim 10 , further comprising a write pointer for each command buffer.
12. The system of claim 10 , further comprising a read pointer for each command buffer.
13. The method of claim 3 wherein at least two of the commands are written to different command buffers simultaneously.
14. A method for processing packets, the method comprising:
(1) sequentially receiving the packets in a first order;
(2) assigning command buffers to the packets so that each two consecutive packets are assigned respective two different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein at least two commands for at least two of the packets are written to different command buffers simultaneously or not in an order in which the packets were received in the operation (1);
(4) reading the commands from the command buffers and executing the commands to transfer the packets in the first order;
(5) wherein for at least one command buffer C 1 which holds commands for two packets P 1 and P 2 with the packet P 1 preceding the packet P 2 in the first order, the operation (4) is performed so as to transfer the packet P 1 , then a packet assigned another command buffer, then the packet P 2 .
15. The method of claim 14 wherein for at least two packets P 1 and P 2 which are assigned a single command buffer C 1 , with the packet P 1 preceding the packet P 2 in the first order, the operation (3) is suspended for the packet P 2 before completion of the operation (3) for the packet P 1 .
16. The method of claim 14 wherein for any two packets P 1 and P 2 which are assigned a single command buffer C 1 , with the packet P 1 preceding the packet P 2 in the first order, the operation (3) is not allowed to proceed for the packet P 2 until completion of the operation (3) for the packet P 1 .
17. The method of claim 14 wherein the operation (4) is performed sequentially on different command buffers taken in an order in which the command buffers are assigned to packets in the operation (2).
18. The method of claim 14 wherein all of said packets are received on a single lane, the method further comprising:
receiving packets for one or more other lanes, wherein each lane is associated with a plurality of command buffers; and
performing the operations (1) through (5) for each lane and its associated plurality of the command buffers.
19. The method of claim 14 further comprising selecting and assigning a task for each packet, wherein the operation (3) is performed for each packet by the packet's assigned task executed by a processor.
20. The method of claim 14 wherein at least two of the commands are written to different command buffers simultaneously.
21. A system comprising:
a plurality of command buffers; and
circuitry for:
(1) receiving packets and assigning sequence numbers to the packets;
(2) using each packet's sequence number to assign a command buffer to the packet so that each two packets with consecutive sequence numbers are assigned different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein the computer is operable to have at least two commands for at least two of the packets to be written to different command buffers simultaneously or not in an order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(4) reading the commands from the command buffers and executing the commands to transfer the packets in an order in which the corresponding sequence numbers are assigned to the packets in the operation (1);
(5) wherein if any command buffer C 1 holds commands for at least two packets P 1 and P 2 with the packet P 1 having an earlier assigned sequence number than the packet P 2 , and another command buffer holds a command for another packet P 3 preceding P 2 but not P 1 , then the operation (4) is performed for the packet P 1 , then for the packet P 3 , then for the packet P 2 .
22. A system comprising:
a plurality of command buffers; and
circuitry for:
(1) sequentially receiving packets in a first order;
(2) assigning command buffers to the packets so that each two consecutive packets are assigned different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein the computer is operable to have at least two commands for at least two of the packets to be written to different command buffers simultaneously or not in an order corresponding to the first order of the at least two packets;
(4) reading the commands from the command buffers and executing the commands to transfer the packets in the first order;
(5) wherein for at least one command buffer C 1 which holds commands for two packets P 1 and P 2 with the packet P 1 preceding the packet P 2 in the first order, and another command buffer holds a command for another packet P 3 preceding P 2 but not P 1, the operation (4) is performed for the packet P 1 , then for the packet P 3 , then for the packet P 2 .
23. A computer readable storage medium encoded with software instructions to perform the following operations when executed by a computer:
(1) sequentially receiving packets in a first order;
(2) assigning command buffers to the packets so that each two consecutive packets are assigned different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein the computer is operable to have at least two commands for at least two of the packets to be written to different command buffers simultaneously or not in an order corresponding to the first order of the at least two packets;
(4) reading the commands from the command buffers and executing the commands to transfer the packets in the first order;
(5) wherein for at least one command buffer C 1 which holds commands for two packets P 1 and P 2 with the packet P 1 preceding the packet P 2 in the first order, and another command buffer holds a command for another packet P 3 preceding P 2 but not P 1 , the operation (4) is performed for the packet P 1 , then for the packet P 3 , then for the packet P 2 .
24. A signal embedded in a carrier medium and encoded with software instructions to perform the following operations when executed by a computer:
(1) sequentially receiving packets in a first order;
(2) assigning command buffers to the packets so that each two consecutive packets are assigned different command buffers;
(3) writing commands for the packets to the packets' assigned command buffers, wherein the computer is operable to have at least two commands for at least two of the packets to be written to different command buffers simultaneously or not in an order corresponding to the first order of the at least two packets;
(4) reading the commands from the command buffers and executing the commands to transfer the packets in the first order;
(5) wherein for at least one command buffer C 1 which holds commands for two packets P 1 and P 2 with the packet P 1 preceding the packet P 2 in the first order, and another command buffer holds a command for another packet P 3 preceding P 2 but not P 1 , the operation (4) is performed for the packet P 1 , then for the packet P 3 , then for the packet P 2 .