Patent ID: 8379647

Claim:
A device comprising: a plurality of service threads for processing packets; one or more packet ordering queues (POQs) for ordering the packets after the plurality of service threads process the packets; a packet distribution thread to: receive the packets, determine whether a particular POQ of the one or more POQs is assigned to the packets; allocate the particular POQ to the packets when the particular POQ is not assigned to the packets; and reserve slots in the particular POQ for the packets in an order of their arrival; an ingress queue to: provide the packets from the packet distribution thread to the plurality of service threads; an egress queue to: receive the packets from the plurality of service threads after the plurality of service threads process the packets, and store the received packets in an order that is different from the order of their arrival at the packet distribution thread; and a packet ordering thread to: obtain the packets from the egress queue, place information relating to the packets in the reserved slots in the particular POQ, release the packets from the reserved slots in the order of their arrival at the packet distribution thread, where, when releasing a particular one of the packets, the packet ordering thread is to: identify a particular slot, in the particular POQ, that is currently designated as a head slot, where the particular slot is associated with the particular packet, release the particular packet upon determining that the particular slot, associated with the particular packet, is designated as the head slot, and designate a next slot, that immediately follows the particular slot in the POQ, as the head slot, and remove the particular POQ upon determining that the head slot, in the particular POQ, is not associated with any packets.