Method and apparatus for packet ordering in a data processing system
View Patent ↗A method and system for packet ordering in a multi-processor data processing system. The multi-processor system comprises an input queue, packet memory for storing the data packets, a series of packet processors with on-chip memory, an output queue, and an ordering buffer. The ordering buffer is provided to maintain strict packet order in the multi-processor system, where the packets are buffered in on-chip memory, but are not necessarily processed in order. The ordering buffer holds a pointer and completion flag for each packet being processed or already processed but not released to the output queue. The ordering buffer allows the data packets to be read from the on-chip memory in the packet processors regardless of the order in which the data packets are processed. A processed data packet is released to the output queue in order once the processing of earlier packets is completed.
1. A system for processing multiple incoming packets of data and outgoing packets in a multi-processor data processing system, said system comprising:
(a) means for inputting each of said incoming data packets in a specific order and means for assigning an ordering pointer to each of said packets of data, said ordering pointers being stored in an ordering buffer;
(b) means for processing said incoming packets of data;
(c) means for setting a completion flag upon completion of processing of said associated incoming packet, and said completion flag being stored in said ordering buffer with the ordering pointer associated with said incoming packet;
(d) means for outputting said processed data packets after said associated completion flags have been set, said means for outputting being responsive to the ordering pointers associated with said incoming data packets so that said specific order of the incoming packets is maintained;
wherein said means for inputting each of said incoming data packets in a specific order includes means for assigning a plurality of sequence numbers defining a sequential order, said incoming packets being assigned a sequence number in said sequential order according to the order of input from an incoming queue, and each of said sequence numbers providing an index to the location of the associated ordering pointer in said ordering buffer.
2. The system as claimed in claim 1 , wherein said means for outputting said processed data packets includes means for en-queuing the processed data packets on an outgoing queue in order according to said sequence numbers in response to the completion flags being set for the processed data packets.
3. The system as claimed in claim 2 , wherein said means for assigning a plurality of sequence numbers further includes means for recovering sequence numbers previously assigned to said processed data packets en-queued on said outgoing queue, and said recovered sequence numbers being made available for assignment to other incoming data packets.
4. The system as claimed in claim 3 , wherein said sequence numbers and said recovered sequence numbers comprise a pool of sequence numbers defining the locations of the ordering pointers for said ordering buffer.
5. A method for processing multiple incoming packets of data and outgoing packets in a multi-processor data processing system, said method comprising the steps of:
(a) inputting each of said incoming data packets in a specific order and assigning an ordering pointer to each of said incoming data packets;
(b) processing each of said incoming data packets;
(c) setting a completion flag for each of said incoming data packets upon completion of processing of said associated incoming data packet;
(d) outputting said processed incoming data packets after said associated completion flags have been set, said processed incoming data packets being outputted based on the ordering pointers associated with said incoming data packets so that said specific order is maintained;
wherein said step of inputting each of said incoming data packets in a specific order comprises assigning a sequence number to each of said incoming data packets, said sequence numbers defining a sequential order, said incoming packets being assigned a sequence number according to the order of input, and each of said sequence numbers providing an index to the location of the associated ordering pointer in an ordering buffer.
6. The method as claimed in claim 5 , wherein said step for outputting said processed incoming data packets comprises en-queuing the processed data packets on an outgoing queue in the order of said sequence numbers in response to the completion flags being set for the processed incoming data packets.
7. The method as claimed in claim 6 , further including the step of recovering the sequence numbers previously assigned to the processed incoming data packets en-queued on said outgoing queue, and said recovered sequence numbers being made available for assignment to other incoming data packets.
8. A network processor for processing multiple incoming data packets and outgoing data packets in a data processing system, said network processor comprising:
(a) an input component for inputting each of said incoming data packets in a specific order and a component for assigning an ordering pointer to each of said incoming data packets, and said ordering pointers being located in an ordering buffer;
(b) a plurality of packet processor components for processing said inputted incoming data packets;
(c) a component for setting a completion flag for each of said incoming data packets upon completion of processing of said incoming data packet;
(d) an output component for outputting said processed incoming data packets after said associated completion flags have been set, said output component being responsive to the order in said ordering buffer of the ordering pointers associated with said incoming data packets so that said specific order of the incoming data packets is maintained;
wherein said input component for inputting each of said incoming data packets includes a component for assigning a plurality of sequence numbers defining a sequential order, said incoming packets being assigned a sequence number in said sequential order according to the order of input from an incoming queue, and each of said sequence numbers providing an index to the location of the associated ordering pointer in said ordering buffer.
9. The network processor as claimed in claim 8 , wherein said output component includes a component for en-queuing the processed data packets on an outgoing queue in the order of said sequence numbers in response to the completion flags being set for the processed data packets.
10. The network processor as claimed in claim 9 , wherein component for assigning a plurality of sequence numbers further includes a component for recovering sequence number previously assigned to said processed data packets en-queued on said outing queue, and said recovered sequence numbers being made available for assignment to other incoming data packets.
11. The network processor as claimed in claim 10 , wherein said sequence numbers and said recovered sequence numbers comprise a pool of sequence numbers defining the locations of the ordering pointers for said ordering buffer.