Sequencing packets from multiple threads

Abstract

A device may reserve a slot for a received packet in a packet ordering queue (POQ), convey the packet to one of a plurality of threads for processing, obtain the packet from the one of the plurality of threads after the packet has been processed, organize the packet in the POQ in accordance with a position of the reserved slot, and release the packet from the POQ if the reserved slot is a head of the POQ.

1 - 20 . (canceled) 
     
     
         21 . A method comprising:
 receiving, at a device, a packet;   identifying, by the device, an address holder for the received packet, the address holder indicating a queue associated with the packet;   identifying, by the device and based on the address holder, the queue associated with the packet;   reserving, by the device, a slot for the packet in the queue,
 the slot being selected based on an order in which the packet was received by a component of the device in relation to other received packets; and 
   placing, by the device, the packet in the reserved slot.   
     
     
         22 . The method of  claim 21 , where identifying the address holder for the received packet includes:
 locating a record for a flow associated with the packet, the address holder being associated with the flow.   
     
     
         23 . The method of  claim 22 , where locating the record includes:
 extracting header information from the packet; and   locating the record associated with the flow using the header information.   
     
     
         24 . The method of  claim 21 , where reserving the slot for the packet includes writing an arrival position in the packet. 
     
     
         25 . The method of  claim 24 , where writing the arrival position includes writing an index to a tail of the queue in the packet. 
     
     
         26 . The method of  claim 21 , where placing the packet in the reserved slot includes writing a reference to the packet in the slot. 
     
     
         27 . The method of  claim 21 , where identifying the queue associated with the packet includes:
 locking the address holder to prevent a different component of the device from modifying contents of the address holder.   
     
     
         28 . A system comprising:
 one or more processors to:
 receive a packet; 
 identify an address holder for the received packet,
 the address holder indicating a queue associated with the packet; 
 
 identify, based on the address holder, the queue associated with the packet; 
 reserve a slot for the packet in the queue,
 the slot being selected based on an order in which the packet was received by a component of the system in relation to other received packets; and 
 
 place the packet in the reserved slot. 
   
     
     
         29 . The system of  claim 28 , where, when identifying the address holder for the received packet, the one or more processors are further to:
 locate a record for a flow associated with the packet, the address holder being associated with the flow.   
     
     
         30 . The system of  claim 29 , where, when locating the record, the one or more processors are further to:
 extract header information from the packet; and   locate the record associated with the flow using the header information.   
     
     
         31 . The system of  claim 28 , where, when reserving the slot for the packet, the one or more processors are further to write an arrival position in the packet. 
     
     
         32 . The system of  claim 31 , where, when writing the arrival position, the one or more processors are further to write an index to a tail of the queue in the packet. 
     
     
         33 . The system of  claim 28 , where, when placing the packet in the reserved slot, the one or more processors are further to write a reference to the packet in the slot. 
     
     
         34 . The system of  claim 28 , where, when identifying the queue associated with the packet, the one or more processors are to:
 lock the address holder to prevent a different component of the system from modifying contents of the address holder.   
     
     
         35 . A non-transitory computer-readable medium including instructions, the instructions comprising:
 one or more instructions that, when executed by one or more processors of a device, cause the one or more processors to:
 receive a packet; 
 identify an address holder for the received packet,
 the address holder indicating a queue associated with the packet; 
 
 identify, based on the address holder, the queue associated with the packet; 
 reserve a slot for the packet in the queue,
 the slot being selected based on an order in which the packet was received by a component, associated with the device, in relation to other received packets; and 
 
 place the packet in the reserved slot. 
   
     
     
         36 . The computer-readable medium of  claim 35 , where the one or more instructions that cause the one or more processors to identify the address holder for the received packet include:
 one or more instructions that cause the one or more processors to locate a record for a flow associated with the packet, the address holder being associated with the flow.   
     
     
         37 . The computer-readable medium of  claim 36 , where the one or more instructions that cause the one or more processors to locate the record include:
 one or more instructions that cause the one or more processors to extract header information from the packet; and   one or more instructions to locate the record associated with the flow using the header information.   
     
     
         38 . The computer-readable medium of  claim 35 , where the one or more instructions that cause the one or more processors to reserve the slot for the packet include:
 one or more instructions that cause the one or more processors to write an arrival position in the packet.   
     
     
         39 . The computer-readable medium of  claim 38 , where the one or more instructions that cause the one or more processors to write the arrival position include:
 one or more instructions that cause the one or more processors to write an index to a tail of the queue in the packet.   
     
     
         40 . The computer-readable medium of  claim 35 , where the one or more instructions that cause the one or more processors to place the packet in the reserved slot include:
 one or more instructions that cause the one or more processors to write a reference to the packet in the slot.