Maintaining packet order in network flows over an autonomous network

A method of maintaining packet order in a network flow over an autonomous network, the method comprising:

• establishing a maximum network delay, the maximum network delay being the maximum amount of time taken for a packet to travel across the autonomous network between any two internal endpoints in the autonomous network;
• configuring all switching elements in the autonomous network to perform per-packet multi-path routing by disabling a flow-based deterministic algorithm implemented therein, the per-packet multi-path routing utilizing a round-robin path selection;
• generating, at a first endpoint, a sequence number for a data packet in the network flow between the first endpoint and a second endpoint;
• encapsulating, by the first endpoint, the data packet and the sequence number into an overlay frame;
• sending, by the first endpoint, the overlay frame to the second endpoint over an overlay network implemented upon the autonomous network;
• receiving the overlay frame at the second endpoint;
• determining, by the second endpoint, if the data packet is out-of-order in the network flow based on the sequence number;
• in response to determining that the data packet is out-of-order, buffering the data packet and setting a timer to expire after a specific period of time, the specified period of time being based at least in part on the maximum network delay;
• in response to determining that the data packet is not out-of-order, cancelling any pending timer which was started based upon a previous out-of-order data packet, and delivering the data packet and any buffered packets for the network flow in sequence number order to a program executing on the second endpoint;
• and
• in response to expiration of the timer, delivering the data packet and any buffered packets for the network flow in sequence number order to the program.

A system for maintaining packet order in network flows over an autonomous network comprising a plurality of switching elements configured to perform per-packet multi-path routing, the system comprising:

• a plurality of endpoints connected to the autonomous network, the autonomous network having an established maximum network delay, the maximum network delay being based at least in part on an amount of time for a data packet to travel across the autonomous network between any two internal endpoints in the system, wherein a flow-based deterministic algorithm implemented in each of the plurality of switching elements in the autonomous network is disabled, and wherein each of the plurality of switching elements is configured to perform per-packet multi-path routing, the per-packet multi-path routing utilizing a round-robin path selection;
• and
• network shim modules executing on the plurality of endpoints implementing an overlay network upon the autonomous network, the network shim modules being configured to
• receive a data packet,
• parse flow data and a sequence number from the data packet, wherein the flow data identifies a network flow comprising a plurality of data packets sent from a source endpoint of the plurality of endpoints to a destination endpoint of the plurality of endpoints connected to the autonomous network, and wherein the sequence number indicates a position of the data packet within a sequence of the plurality of data packets in the network flow,
• determine if the data packet is out-of-order in the network flow based on the sequence number,
• upon determining that the data packet is out-of-order, buffer the data packet and set a timer to expire after a specific period of time, the specified period of time being based at least in part on the maximum network delay, and
• upon determining that the data packet is not out-of-order, cancel any pending timer which was started based upon a previous out-of-order data packet, and deliver the data packet and any buffered packets for the network flow in sequence number order to a program executing on the destination endpoint.

A method of maintaining packet order in network flows over an overlay network implemented over an autonomous network comprising switching elements each being configured to perform per-packet, round-robin selection from among multiple best paths to a destination endpoint by disabling a flow-based deterministic algorithm implemented in each of the switching elements, the method comprising executing instructions in the destination endpoint to:

• upon arrival of an out-of-order packet, set a timer for a specific period of time;
• and
• buffer the out-of-order data packet in a network flow on the autonomous network until the first of the specific period of time expires or the next sequential data packet in the network flow arrives, and then delivering the out-of-order data packet and any buffered data packets in order;
• wherein the specific period of time is a maximum network delay established for the autonomous network, the maximum network delay being based at least in part on an amount of time for a data packet to travel across the autonomous network between any two internal switching elements in the autonomous network.