Reorder engine with error recovery

A computer readable storage medium comprising computer executable instructions, which when executed perform a computer-implemented method of ordering data items comprising:

• receiving the data items at a network device, the received data items being associated with a sequence number chosen from a sequence number space, the sequence number indicating a relative order of the data items;
• classifying the received data items, using a computer-implemented reorder engine, into one of a plurality of possible regions based on the sequence number of the data items and a value that defines a position of a reorder buffer in the sequence number space, the regions including a first region when the sequence number of the data items fall within a sequence number range encompassed by the reorder buffer and a second region when the sequence number of the data items fall within a sequence number range extending from a head of the reorder buffer to a predetermined range beyond the head of the reorder buffer;
• and
• processing the data items based on the classified regions.

A network device comprising:

• a data transmission component;
• and
• a plurality of processing elements connected by the data transmission component, the processing elements communicating with one another by transmitting data items over the data transmission component, the processing elements each including a reorder component to arrange received data items into an order corresponding to an order in which the data items were transmitted, each of the reorder components including:
• a reorder buffer to store the data items, each of the data items including a sequence number chosen from a sequence number space that includes three possible regions, where processing of each of the data items, by the reorder engine, depends on which of the three possible regions is associated with each of the data items, the sequence number indicating the order of the data items, and
• a reorder engine to classify the data items based on the sequence number of the data items and based on a position of the reorder buffer relative to the sequence number space into one of the three regions, the reorder engine determining whether to store the data items in the reorder buffer based on the classified region of the data items.

A reordering device comprising:

• a reorder buffer to store information relating to data items, each of the data items being associated with a sequence number chosen from a sequence number space that includes three possible regions, where processing of each of the data items, by the reorder engine, of each of the data items depends on which of the three possible regions is associated with each of the data items, the sequence number indicating a relative order of the data items;
• a reorder buffer pointer to store a value indicating a rearmost active entry of the reorder buffer relative to the sequence number space;
• and
• a reorder engine to receive the data items, the reorder engine classifying each of the received data items into one of the three possible—regions based on the sequence number of the data item and the value of the reorder buffer pointer, the reorder engine determining whether to store the information relating to the received data items in the reorder buffer based on the region into which each of the received data items is classified, and
• where when the data items are classified into a second region of the three possible regions, the reorder engine is further to:
• shift the sequence number range encompassed by the reorder buffer to create a shifted version of the reorder buffer, and
• invalidate the data items that are no longer in the shifted version of the reorder buffer.