Reorder resilient transport

Patent metadata

Field	Value
Publication number	US-9979640-B2
Application number	US-201414580981-A
Country	US
Kind code	B2
Filing date	Dec 23, 2014
Priority date	Dec 23, 2014
Publication date	May 22, 2018
Grant date	May 22, 2018

Abstract

Devices and techniques for reorder resilient transport are described herein. A device may store data packets in sequential positions of a flow queue in an order in which the data packets were received. The device may retrieve a first data packet from a first sequential position and a second data packet from a second sequential position that is next in sequence to the first sequential position in the flow queue. The device may store the first data packet and the second data packet in a buffer and refrain from providing the first data packet and the second data packet to upper layer circuitry if the packet order information for the first data packet and the second data packet indicate that the first data packet and the second data packet were received out of order. Other embodiments are also described.

First claim

What is claimed is:

1. A non-transitory machine-readable medium including instructions that, when executed by a first end station, cause the first end station to:
store a plurality of data packets in sequential positions of a flow queue in an order in which the plurality of data packets were received;
retrieve a first data packet of the plurality of data packets, the first data packet having first packet order information, from a first sequential position in the flow queue;
retrieve a second data packet of the plurality of data packets, the second data packet having second packet order information, from a second sequential position, the second sequential position being a next sequential position after the first sequential position in the flow queue;
store the first data packet and the second data packet in a buffer and refrain from providing the first data packet and the second data packet to upper layer circuitry responsive to the first packet order information and the second packet order information indicate that the first data packet and the second data packet were received out of order, wherein the first packet order information and the second packet order information indicate an order in which the first data packet and the second data packet were sent from a second end station;
maintain a timer based on a value for average round trip travel time for data packets between the first end station and the second end station;
initialize the timer to an initial value responsive to retrieving a data packet of the plurality of data packets; and
responsive to the data packet was received out-of-order, based on packet order information for the data packet, store the data packet in the buffer, otherwise, responsive to the timer has expired, provide the data packets in the buffer to the upper layer circuitry.

2. The non-transitory machine-readable medium of claim 1 , including further instructions that, when executed by the first end station, cause the first end station to:
provide the first data packet and the second data packet to the upper layer circuitry responsive to the buffer is empty and responsive to the first packet order information and the second packet order information indicate that the first data packet and the second data packet were received in order.

3. The non-transitory machine-readable medium of claim 1 , wherein, responsive to the first packet order information and the second packet order information indicate that the first data packet and the second data packet were received out of order, the instructions further cause the first end station to:
initialize a counter;
retrieve a third data packet having third packet order information from a third sequential position that is a next sequential position to the second sequential position in the flow queue;
store the third data packet in the buffer; and
increment the counter responsive to the buffer does not include data packets in sequential order, based on the first packet order information, the second packet order information, and the third packet order information, subsequent to storing the third data packet.

4. The non-transitory machine-readable medium of claim 3 , wherein the instructions further cause the first end station to:
repeat operations of retrieving data packets, incrementing the counter, and storing data packets in the buffer for each of the plurality of data packets, sequentially based on the sequential positions of respective data packets; and
provide a reordered buffer to the upper layer circuitry responsive to the counter being incremented past a counter limit, the reordered buffer being generated by reordering the buffer into a sequential order based on packet order information of each data packet in the buffer.

5. The non-transitory machine-readable medium of claim 4 , wherein the instructions further cause the first end station to:
responsive to detecting, based on packet order information, that a data packet was received in order, provide a reordered buffer to the upper layer circuitry, the reordered buffer being generated by reordering the buffer into a sequential order based on packet order information of each data packet in the buffer.

6. The non-transitory machine-readable medium of claim 1 , wherein the instructions further cause the first end station to: increment a counter for each data packet received out of order.

7. A device comprising:
a network interface to receive a plurality of data packets and to store the plurality of data packets in sequential positions of a flow queue in an order in which the plurality of data packets were received at the network interface; and
an out-of-order module to:
retrieve a first data packet having first packet order information from a first sequential position in the flow queue, retrieve a second data packet having second packet order information from a second sequential position in the flow queue,
store the first data packet and the second data packet in a buffer and refrain from providing the first data packet and the second data packet to upper layer circuitry responsive to the first packet order information and the second packet order information indicate that the first data packet and the second data packet were received out of order,
maintain a timer based on a value for average round trip travel time for data packets between the device and a source end station,
initialize the timer to an initial value responsive to retrieving a data packet of the plurality of data packets, and
responsive to the respective data packet is received within the average round trip travel time, store the data packet in the buffer and reorder the buffer based on the respective packet order information, otherwise, responsive to the timer has expired, provide the data packets in the buffer to the upper layer circuitry.

8. The device of claim 7 , wherein the network interface is to notify the out-of-order module that the plurality of data packets are out of order prior to storing the plurality of data packets in the flow queue.

9. The device of claim 7 , wherein the out-of-order module is further to:
provide the first data packet and the second data packet to the upper layer circuitry responsive to the butler is empty and responsive to the first packet order information and the second packet order information indicate that the first data packet and the second data packet were received in order.

10. The device of claim 7 , wherein, responsive to the first packet information and the second packet order information indicate that the first data packet and the second data packet were received out of order, the out-of-order module is further to:
initialize a counter;
retrieve a third data packet having third packet order information from a third sequential position subsequent to the second sequential position in the flow queue;
store the third data packet in the buffer; and
increment the counter responsive to the buffer does not include data packets in sequential order, based on the first packet order information, the second packet order information, and the third packet order information, subsequent to storing the third data packet.

11. The device of claim 10 , wherein the out-of-order module is further to:
repeat operations of retrieving data packets, incrementing the counter, and storing data packets in the buffer for each of the plurality of data packets, sequentially based on the sequential positions of respective data packets; and
provide a reordered buffer to the upper layer circuitry responsive to the counter being increment past a counter limit, the reordered buffer being generated by reordering the buffer into a sequential order based on packet order inform

Assignees

• Intel Corp

Inventors

• Vasudevan Anil
• Sarangam Parthasarathy
• Mann Eric
• Cohn Daniel

Classifications

• H04L45/38

  Flow based routing · CPC title

• H04L45/74 Primary

  Address processing for routing · CPC title

• H04L47/115

  using a dedicated packet · CPC title

• H04L47/52

  by attributing bandwidth to queues · CPC title

• H04L47/54

  Loss aware scheduling · CPC title