Ordering traffic captured on a data connection

• US 9,525,642 B2
• Filed: 12/04/2014
• Issued: 12/20/2016
• Est. Priority Date: 01/31/2012
• Status: Active Grant

• Current Assignee: QuantumXchange, Inc.
• Original Assignee: DB Networks Inc.
• Inventors: Varsanyi, Eric
• Primary Examiner(s): Ton, Dang
• Application Number:
  US14/560,295
• Publication Number:
  US 20150156130A1
• Time in Patent Office: 747 Days
• Field of Search: 370/401, 370/389, 370/428, 370/411
• US Class Current: 1/1
• CPC Class Codes: H04L 47/323 Discarding or blocking control packets, e.g. ACK packets

Abstract

Ordering partial network traffic. In an embodiment, data packets are received from a network tap and separated into two queues. For each queue, a push-sequence is maintained to represent a sequence number that must be pushed in order to maintain a consecutive order. When both push-sequences are equal to the sequence number of their first packets, if the acknowledgement number of the first packet on one queue is greater than the push-sequence for the other queue and less than or equal to the push-sequence of the one queue, data is pushed off the other queue. Otherwise, a queue having the earlier timestamp is identified as a first queue, the existence of a next acknowledgement number is determined for the second (other) queue, and data is pushed off the first queue according to the existence of the next acknowledgement number. Gap packets may be generated to force progress.

Claims

1. A system comprising:

at least one hardware processor; and

one or more software modules that, when executed by the at least one hardware processor,

receive a plurality of data packets from a network tap on a network connection between two network agents, wherein each of the plurality of data packets comprise a starting sequence number and an acknowledgement number,

separate the plurality of data packets into two queues based on a direction of communication for each data packet, wherein each of the two queues represents a different direction of communication,

for each of the two queues, maintain a push-sequence value for the queue, wherein each push-sequence value represents a starting sequence number of a packet that must be pushed off its respective queue next in order to maintain a consecutive sequence number order for packets pushed off its respective queue,

when both of the push-sequence values are equal to the starting sequence number of a first data packet on their respective queues,

if the acknowledgement number of the first data packet on one of the two queues is greater than the push-sequence value for the other of the two queues and the acknowledgement number of the first data packet on the other queue is less than or equal to the push-sequence value for the one queue, push, to an output, an amount of data off of the other queue that is equal to a minimum of a length of the first data packet on the other queue and a difference between the acknowledgement number of the first data packet on the one queue and the push-sequence value for the other queue, and,

otherwise,

identify a first one of the two queues whose first data packet has an earlier timestamp than the first data packet on a second one of the two queues,

determine whether or not a next acknowledgement number in a data packet exists on the second queue that is greater than a preceding acknowledgement number in a preceding data packet on the second queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the first queue,

if the next acknowledgement number is determined to exist on the second queue, push, to the output, an amount of data off of the first queue that is equal to the difference between the next acknowledgement number and the push-sequence value for the first queue,

if the next acknowledgement number is not determined to exist on the second queue, push, to the output, the first data packet on the first queue, and

provide the output to an application layer, and

when at least one of the push-sequence values is not equal to the starting sequence number of the first data packet on its respective queue and a forcing condition is met, generate at least one gap packet for at least one of the two queues.

2. The system of claim 1, wherein generating at least one gap packet comprises, when the push-sequence value for a first one of the two queues is equal to the starting sequence number of a first data packet on the first queue and the push-sequence value for a second one of the two queues is not equal to the starting sequence number of a first data packet on the second queue:

if the second queue is not empty and the acknowledgement number of the first data packet on the first queue is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the push-sequence value of the first queue, and a length equal to a minimum of a difference between a starting sequence number of the first data packet on the second queue and the push-sequence value for the second queue and a difference between the acknowledgement number of the first data packet on the first queue and the push-sequence value for the second queue;

if the second queue is not empty and the acknowledgement number of the first data packet on the first queue is not greater than the push-sequence value for the second queue,

determine whether or not a next acknowledgement number in a data packet exists on the first queue that is greater than a preceding acknowledgement number in a preceding data packet on the first queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the second queue,

determine an ending sequence number for a last contiguous data packet on the first queue that comprises the acknowledgement number of the first data packet on the first queue,

if the sequence number of the first data packet on the second queue is within a predetermined range of the push-sequence value for the second queue, the next acknowledgement number is determined to exist on the first queue, the next acknowledgement number is greater than the push-sequence value for the second queue, and the next acknowledgement number is less than the sequence number of the first data packet on the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the first queue,

if the sequence number of the first data packet on the second queue is within a predetermined range of the push-sequence value for the second queue and either the next acknowledgement number is not determined to exist on the first queue, the next acknowledgement number is not greater than the push-sequence value for the second queue, or the next acknowledgement number is not less than the sequence number of the first data packet on the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the sequence number of the first data packet on the second queue and the push-sequence value for the first queue,

if the sequence number of the first data packet on the second queue is not within a predetermined range of the push-sequence value for the second queue, the next acknowledgement number is determined to exist on the first queue, and the next acknowledgement number is greater than the push-sequence value for the second queue,

generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the second queue, and,

if the sequence number of the first data packet on the second queue is not within a predetermined range of the push-sequence value for the second queue and either the next acknowledgement number is not determined to exist on the first queue or the next acknowledgement number is not greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to zero;

if the second queue is empty and the acknowledgement number of the first data packet on the first queue is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-value sequence for the second queue, an acknowledgement number equal to the push-sequence value for the first queue, and a length equal to a difference between the acknowledgement number of the first data packet on the first queue and the push-sequence value for the second queue; and

,

if the second queue is empty and the acknowledgement number of the first data packet on the first queue is not greater than the push-sequence value for the second queue,

determine whether or not a next acknowledgement number in a data packet exists on the first queue that is greater than a preceding acknowledgement number in a preceding data packet on the first queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the second queue,

determine an ending sequence number for a last contiguous data packet on the first queue that comprises the acknowledgement number of the first data packet on the first queue,

if the next acknowledgement number is determined to exist, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the second queue, and,

if the next acknowledgement number is not determined to exist, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to zero.

3. The system of claim 1, wherein maintaining the push-sequence values for the two queues comprises initializing the push-sequence values when the push-sequence value for one queue is outside a predetermined range from the acknowledgement value of a first data packet on the other one of the two queues.

4. The system of claim 3, wherein initializing the push-sequence values comprises:

identifying a first one of the two queues whose first data packet has an earlier timestamp than the first data packet on a second one of the two queues;

setting the push-sequence value for the first queue to the sequence number of the first data packet on the first queue; and

setting the push-sequence value for the second queue to the acknowledgement number of the first data packet on the first queue.

5. The system of claim 1, wherein the forcing condition comprises an elapse of a predetermined time during which no new data packets have been received from the network tap.

6. The system of claim 1, wherein the forcing condition comprises a number of data packets on one or both of the two queues exceeding a predetermined threshold.

7. The system of claim 1, wherein the forcing condition comprises a detection that the network connection between the two network agents has been closed.

8. A method comprising using at least one hardware processor to:

receive a plurality of data packets from a network tap on a network connection between two network agents, wherein each of the plurality of data packets comprise a starting sequence number and an acknowledgement number;

separate the plurality of data packets into two queues based on a direction of communication for each data packet, wherein each of the two queues represents a different direction of communication;

for each of the two queues, maintain a push-sequence value for the queue, wherein each push-sequence value represents a starting sequence number of a packet that must be pushed off its respective queue next in order to maintain a consecutive sequence number order for packets pushed off its respective queue;

when both of the push-sequence values are equal to the starting sequence number of a first data packet on their respective queues,

if the acknowledgement number of the first data packet on one of the two queues is greater than the push-sequence value for the other of the two queues and the acknowledgement number of the first data packet on the other queue is less than or equal to the push-sequence value for the one queue, push, to an output, an amount of data off of the other queue that is equal to a minimum of a length of the first data packet on the other queue and a difference between the acknowledgement number of the first data packet on the one queue and the push-sequence value for the other queue, and,

otherwise,

identify a first one of the two queues whose first data packet has an earlier timestamp than the first data packet on a second one of the two queues,

determine whether or not a next acknowledgement number in a data packet exists on the second queue that is greater than a preceding acknowledgement number in a preceding data packet on the second queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the first queue,

if the next acknowledgement number is determined to exist on the second queue, push, to the output, an amount of data off of the first queue that is equal to the difference between the next acknowledgement number and the push-sequence value for the first queue,

if the next acknowledgement number is not determined to exist on the second queue, push, to the output, the first data packet on the first queue, and

provide the output to an application layer; and

when at least one of the push-sequence values is not equal to the starting sequence number of the first data packet on its respective queue and a forcing condition is met, generate at least one gap packet for at least one of the two queues.

9. The method of claim 8, wherein generating at least one gap packet comprises, when the push-sequence value for a first one of the two queues is equal to the starting sequence number of a first data packet on the first queue and the push-sequence value for a second one of the two queues is not equal to the starting sequence number of a first data packet on the second queue:

if the second queue is not empty and the acknowledgement number of the first data packet on the first queue is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the push-sequence value of the first queue, and a length equal to a minimum of a difference between a starting sequence number of the first data packet on the second queue and the push-sequence value for the second queue and a difference between the acknowledgement number of the first data packet on the first queue and the push-sequence value for the second queue;

if the second queue is not empty and the acknowledgement number of the first data packet on the first queue is not greater than the push-sequence value for the second queue,

determine whether or not a next acknowledgement number in a data packet exists on the first queue that is greater than a preceding acknowledgement number in a preceding data packet on the first queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the second queue,

determine an ending sequence number for a last contiguous data packet on the first queue that comprises the acknowledgement number of the first data packet on the first queue,

if the sequence number of the first data packet on the second queue is within a predetermined range of the push-sequence value for the second queue, the next acknowledgement number is determined to exist on the first queue, the next acknowledgement number is greater than the push-sequence value for the second queue, and the next acknowledgement number is less than the sequence number of the first data packet on the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the first queue,

if the sequence number of the first data packet on the second queue is within a predetermined range of the push-sequence value for the second queue and either the next acknowledgement number is not determined to exist on the first queue, the next acknowledgement number is not greater than the push-sequence value for the second queue, or the next acknowledgement number is not less than the sequence number of the first data packet on the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the sequence number of the first data packet on the second queue and the push-sequence value for the first queue,

if the sequence number of the first data packet on the second queue is not within a predetermined range of the push-sequence value for the second queue, the next acknowledgement number is determined to exist on the first queue, and the next acknowledgement number is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the second queue, and,

if the sequence number of the first data packet on the second queue is not within a predetermined range of the push-sequence value for the second queue and either the next acknowledgement number is not determined to exist on the first queue or the next acknowledgement number is not greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to zero;

if the second queue is empty and the acknowledgement number of the first data packet on the first queue is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-value sequence for the second queue, an acknowledgement number equal to the push-sequence value for the first queue, and a length equal to a difference between the acknowledgement number of the first data packet on the first queue and the push-sequence value for the second queue; and

,

if the second queue is empty and the acknowledgement number of the first data packet on the first queue is not greater than the push-sequence value for the second queue,

determine whether or not a next acknowledgement number in a data packet exists on the first queue that is greater than a preceding acknowledgement number in a preceding data packet on the first queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the second queue,

determine an ending sequence number for a last contiguous data packet on the first queue that comprises the acknowledgement number of the first data packet on the first queue,

if the next acknowledgement number is determined to exist, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the second queue, and,

if the next acknowledgement number is not determined to exist, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to zero.

10. The method of claim 8, wherein maintaining the push-sequence values for the two queues comprises initializing the push-sequence values when the push-sequence value for one queue is outside a predetermined range from the acknowledgement value of a first data packet on the other one of the two queues.

11. The method of claim 10, wherein initializing the push-sequence values comprises:

identifying a first one of the two queues whose first data packet has an earlier timestamp than the first data packet on a second one of the two queues;

setting the push-sequence value for the first queue to the sequence number of the first data packet on the first queue; and

setting the push-sequence value for the second queue to the acknowledgement number of the first data packet on the first queue.

12. The method of claim 8, wherein the forcing condition comprises an elapse of a predetermined time during which no new data packets have been received from the network tap.

13. The method of claim 8, wherein the forcing condition comprises a number of data packets on one or both of the two queues exceeding a predetermined threshold.

14. The method of claim 8, wherein the forcing condition comprises a detection that the network connection between the two network agents has been closed.

15. A non-transitory computer-readable medium having instructions stored thereon, wherein the instructions, when executed by a processor, cause the processor to:

receive a plurality of data packets from a network tap on a network connection between two network agents, wherein each of the plurality of data packets comprise a starting sequence number and an acknowledgement number;

separate the plurality of data packets into two queues based on a direction of communication for each data packet, wherein each of the two queues represents a different direction of communication;

for each of the two queues, maintain a push-sequence value for the queue, wherein each push-sequence value represents a starting sequence number of a packet that must be pushed off its respective queue next in order to maintain a consecutive sequence number order for packets pushed off its respective queue;

when both of the push-sequence values are equal to the starting sequence number of a first data packet on their respective queues,

if the acknowledgement number of the first data packet on one of the two queues is greater than the push-sequence value for the other of the two queues and the acknowledgement number of the first data packet on the other queue is less than or equal to the push-sequence value for the one queue, push, to an output, an amount of data off of the other queue that is equal to a minimum of a length of the first data packet on the other queue and a difference between the acknowledgement number of the first data packet on the one queue and the push-sequence value for the other queue, and,

otherwise,

identify a first one of the two queues whose first data packet has an earlier timestamp than the first data packet on a second one of the two queues,

determine whether or not a next acknowledgement number in a data packet exists on the second queue that is greater than a preceding acknowledgement number in a preceding data packet on the second queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the first queue,

if the next acknowledgement number is determined to exist on the second queue, push, to the output, an amount of data off of the first queue that is equal to the difference between the next acknowledgement number and the push-sequence value for the first queue,

if the next acknowledgement number is not determined to exist on the second queue, push, to the output, the first data packet on the first queue, and

provide the output to an application layer; and

when at least one of the push-sequence values is not equal to the starting sequence number of the first data packet on its respective queue and a forcing condition is met, generate at least one gap packet for at least one of the two queues.

16. The non-transitory computer-readable medium of claim 15, wherein generating at least one gap packet comprises, when the push-sequence value for a first one of the two queues is equal to the starting sequence number of a first data packet on the first queue and the push-sequence value for a second one of the two queues is not equal to the starting sequence number of a first data packet on the second queue:

if the second queue is not empty and the acknowledgement number of the first data packet on the first queue is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the push-sequence value of the first queue, and a length equal to a minimum of a difference between a starting sequence number of the first data packet on the second queue and the push-sequence value for the second queue and a difference between the acknowledgement number of the first data packet on the first queue and the push-sequence value for the second queue;

if the second queue is not empty and the acknowledgement number of the first data packet on the first queue is not greater than the push-sequence value for the second queue,

determine whether or not a next acknowledgement number in a data packet exists on the first queue that is greater than a preceding acknowledgement number in a preceding data packet on the first queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the second queue,

determine an ending sequence number for a last contiguous data packet on the first queue that comprises the acknowledgement number of the first data packet on the first queue,

if the sequence number of the first data packet on the second queue is within a predetermined range of the push-sequence value for the second queue, the next acknowledgement number is determined to exist on the first queue, the next acknowledgement number is greater than the push-sequence value for the second queue, and the next acknowledgement number is less than the sequence number of the first data packet on the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the first queue,

if the sequence number of the first data packet on the second queue is within a predetermined range of the push-sequence value for the second queue and either the next acknowledgement number is not determined to exist on the first queue, the next acknowledgement number is not greater than the push-sequence value for the second queue, or the next acknowledgement number is not less than the sequence number of the first data packet on the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the sequence number of the first data packet on the second queue and the push-sequence value for the first queue,

if the sequence number of the first data packet on the second queue is not within a predetermined range of the push-sequence value for the second queue, the next acknowledgement number is determined to exist on the first queue, and the next acknowledgement number is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the second queue, and,

if the sequence number of the first data packet on the second queue is not within a predetermined range of the push-sequence value for the second queue and either the next acknowledgement number is not determined to exist on the first queue or the next acknowledgement number is not greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to zero;

if the second queue is empty and the acknowledgement number of the first data packet on the first queue is greater than the push-sequence value for the second queue, generate the gap packet to have a starting sequence number equal to the push-value sequence for the second queue, an acknowledgement number equal to the push-sequence value for the first queue, and a length equal to a difference between the acknowledgement number of the first data packet on the first queue and the push-sequence value for the second queue; and

,

if the second queue is empty and the acknowledgement number of the first data packet on the first queue is not greater than the push-sequence value for the second queue,

determine whether or not a next acknowledgement number in a data packet exists on the first queue that is greater than a preceding acknowledgement number in a preceding data packet on the first queue, wherein the preceding acknowledgement number is greater than the push-sequence value for the second queue,

determine an ending sequence number for a last contiguous data packet on the first queue that comprises the acknowledgement number of the first data packet on the first queue,

if the next acknowledgement number is determined to exist, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to a difference between the next acknowledgement number and the push-sequence value for the second queue, and,

if the next acknowledgement number is not determined to exist, generate the gap packet to have a starting sequence number equal to the push-sequence value for the second queue, an acknowledgement number equal to the determined ending sequence number, and a length equal to zero.

17. The non-transitory computer-readable medium of claim 15, wherein maintaining the push-sequence values for the two queues comprises initializing the push-sequence values when the push-sequence value for one queue is outside a predetermined range from the acknowledgement value of a first data packet on the other one of the two queues.

18. The non-transitory computer-readable medium of claim 17, wherein initializing the push-sequence values comprises:

identifying a first one of the two queues whose first data packet has an earlier timestamp than the first data packet on a second one of the two queues;

setting the push-sequence value for the first queue to the sequence number of the first data packet on the first queue; and

setting the push-sequence value for the second queue to the acknowledgement number of the first data packet on the first queue.

19. The non-transitory computer-readable medium of claim 15, wherein the forcing condition comprises an elapse of a predetermined time during which no new data packets have been received from the network tap.

20. The non-transitory computer-readable medium of claim 15, wherein the forcing condition comprises a number of data packets on one or both of the two queues exceeding a predetermined threshold.