Method and system for transport protocol reconstruction and timer synchronization for non-intrusive capturing and analysis of packets on a high-speed distributed network

• US 20040218532A1
• Filed: 04/29/2003
• Published: 11/04/2004
• Est. Priority Date: 04/29/2003
• Status: Active Grant

• Current Assignee: Narus, Inc. (Gen Digital Inc.)
• Original Assignee: Narus, Inc. (Gen Digital Inc.)
• Inventors: Khirman, Stanislav
• Granted Patent: US 7,349,400 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/326 in the transport layer [OSI layer 4] H04L69/16 takes precedence
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A transport protocol data flow reconstruction method delays determination that a missing packet is lost for a period of time. For an evaluated TCP packet in a first direction, the method determines if a TCP packet is missing in a second direction, in which case the method stores the evaluated TCP packet in a list and creates an acknowledgement timer indicating a maximum time to wait until treating the missing TCP packet as lost. Expiration of the acknowledgment timer indicates a missing packet in the second direction. The method determines if a TCP packet is missing in the first direction, in which case the method stores the evaluated TCP packet in the list and creates a retransmission timer indicating a maximum time to wait until treating the missing TCP packet as lost. Expiration of the retransmission timer indicates a missing packet in the first direction.

Claims

1. A method for reconstructing a transport protocol data flow from data packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in a second direction on a second channel, a first part of the data packets captured by a first packet capturing device on the first channel and time stamped by a first timer and a second part of the data packets captured by a second packet capturing device on the second channel and time stamped by a second timer, the method comprising:

selecting a data packet for evaluation captured by the first packet capturing device in the first direction;

determining whether there is a missing data packet in the second direction; and

responsive to determining that there is a missing data packet in the second direction,

storing the data packet for evaluation in a first list; and

creating an acknowledgement timer associated with the data packet stored in the first list, the acknowledgment timer indicating a maximum time to wait until treating the missing data packet as lost.

2. The method of claim 1, wherein the data packet is a Transmission Control Protocol (TCP) packet including an acknowledgment number (Ack) indicating a sequential number of last successfully received continuous data, and determining whether there is a missing data packet in the second direction comprises determining if Ack is larger than BMaxSeq, BMaxSeq being a last seen continuous sequence in the second direction.

3. The method of claim 1, further comprising:

determining whether the missing data packet was previously received in the second direction and stored in a second list; and

responsive to determining that the missing data packet was previously stored in the second list,

extracting the missing packet from the second list, and

canceling the acknowledgement timer associated with the extracted packet.

4. The method of claim 3, wherein the data packet is a TCP packet and determining whether the missing data packet was previously received in the second direction and stored in a second list comprises determining whether the second list includes a packet whose Ack is not more than AMaxSeq, Ack being the acknowledgment number of the packet in the second list and AMaxSeq being the last seen sequential number in the first direction.

5. The method of claim 1, further comprising:

determining whether the acknowledgement timer expired; and

responsive to determining that the acknowledgement timer expired,

extracting the data packet from the first list, and

indicating that at least a packet was lost in the second direction.

6. The method of claim 1, further comprising:

determining whether the data packet is a retransmission of a same packet previously transmitted in the first direction; and

responsive to determining that the data packet is a retransmission, removing the data packet from data packet reconstruction.

7. The method of claim 6, wherein the data packet is a TCP packet and determining whether the data packet is a retransmission comprises determining whether:

Seq+Len<

=AMaxSeq, Seq being the sequential number of the TCP packet, Len being the length of data in the TCP packet and AMaxSeq being the last seen sequential number in the first direction.

8. The method of claim 1, further comprising:

determining whether there is a missing data packet in the first direction; and

responsive to determining that there is a missing data packet in the first direction,

storing the data packet in a first list, and

creating a retransmission timer associated with the data packet stored in the first list, the retransmission timer indicating a maximum time to wait until identifying the missing TCP packet as lost.

9. The method of claim 8, wherein the data packet is a TCP packet and determining whether there is a missing data packet in the first direction comprises determining whether:

Seq<

=AMaxSeq, Seq being the sequential number of the TCP packet and AMaxSeq being the last seen sequential number in the first direction.

10. The method of claim 8, further comprising:

determining whether the retransmission timer expired; and

responsive to determining that the retransmission timer expired,

extracting the data packet from the first list,

indicating that at least a packet was lost in the first direction.

11. The method of claim 8, further comprising:

determining whether the missing data packet was previously received in the first direction and stored in the first list;

responsive to determining that the missing data packet was previously stored in the first list,

extracting the missing data packet from the first list; and

canceling the retransmission timer associated with the extracted packet.

12. The method of claim 11, wherein the data packet is a TCP packet and determining whether the missing data packet was previously received in the first direction and stored in a first list comprises determining whether the first list includes a packet whose Seq is not more than AMaxSeq, Seq being the sequential number of the packet in the first list and AMaxSeq being the last seen sequential number in the first direction.

13. The method of claim 1, wherein the data packet is a TCP packet and the method further comprises optimizing the acknowledgement timer, optimizing the acknowledgement timer comprising:

selecting a packet in the second direction;

extracting a sequential number (bSeq) and a timestamp (Tb) of the packet in the second direction, the sequential number (bSeq) indicating a sequential number in the packet in the second direction and timestamp (Tb) being a timestamp imposed by the second packet capturing device on the packet in the second direction;

determining whether the first list includes a packet whose acknowledgment number (aAck) and timestamp (Ta) satisfies a condition;

aAck<

=bSeq and Ta<

Tb-d-dT, aAck indicating a sequential number of a last successfully received continuous data in the packet in the first list, Ta being a timestamp imposed by the first packet capturing device on the packet in the first list, d being a maximum time between capturing of the packets by the first and second packet capturing devices and analysis of the captured packets, and dT being a maximum time discrepancy between the first and second timers; and

responsive to determining that the first list includes a packet whose aAck satisfies the condition, extracting the packet from the first list and triggering expiration of the acknowledgement timer.

14. The method of claim 1, wherein the data packet is a TCP packet and the method further comprises optimizing the retransmission timer, optimizing the retransmission timer comprising:

selecting a packet in the second direction;

extracting a acknowledgement number (bAck) and a timestamp (Tb) of the packet in the second direction, the sequential number (bAck) indicating a sequential number of a last successfully received continuous data in the packet in the second direction and the timestamp (Tb) being a timestamp imposed by the second packet capturing device on the packet in the second direction;

determining whether the first list includes a packet whose sequential number (aSeq) and timestamp (Ta) satisfies a condition;

aSeq<

=bAck and Ta<

Tb-d-dT, aSeq indicating a sequential number of a first data in the packet in the first list, Ta being a timestamp imposed by the first packet capturing device on the packet in the first list, d being a maximum time between capturing of the packets by the first and second packet devices and analysis of the captured packets, and dT being a maximum time discrepancy between the first and second timers; and

responsive to determining that the first list includes a packet whose aSeq satisfies the condition, extracting the packet from the first list and triggering expiration of the retransmission timer.

15. A method for estimating the actual discrepancy (ddT) between a first timer and a second timer used in a TCP (Transmission Control Protocol) packet reconstruction system for capturing and analyzing TCP packets, the TCP packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in a second direction on a second channel, a first part of the TCP packets captured by a first packet capturing device on the first channel and time stamped by the first timer and a second part of the TCP packets captured by a second packet capturing device on the second channel and time stamped by the second timer, a minimum ddT (min_ddT) initialized as −

dT and a maximum ddT (max_ddT) initialized as dT, dT being a maximum estimated time discrepancy between the first and second timers, the method comprising recursively performing;

selecting a TCP packet from the first part of the TCP packets;

extracting a timestamp (T), a sequential number (Seq), and an acknowledgement number (Ack) from the selected TCP packet, the timestamp (T) being the timestamp imposed by the first timer on the selected packet, the sequential number (Seq) indicating a sequential number of a first data in the selected packet, and Ack indicating a sequential number of a last successfully received continuous data in the selected packet;

setting ALastTime as T, ALastSeq as Seq, and ALastAck as Ack, ALastTime indicating a timestamp of a last seen packet in the first direction, ALastSeq being a sequential number of the last seen packet in the first direction, and ALastAck being an acknowledgement number of the last seen packet in the first direction;

determining whether Seq is not more than BLastAck, BLastAck being an acknowledgement number of a last seen packet in the second direction;

responsive to determining that Seq is not more than BLastAck, modifying max_ddT as;

max_ddT=min (max_ddT, BLastTime−

T+2d);

determining whether Ack is not less than BLastSeq, BLastSeq being a sequential number of a last seen packet in the second direction; and

responsive to determining that Ack is not less than BLastAck, modifying min_ddT as;

min_ddT=max (min_ddT, BLastTime−

T−

2d).

16. The method of 15, further comprising:

generating a modified discrepancy d_ddT between the first timer and the second timer by setting d_ddT as;

d_ddT=(max_ddT−

min_ddT)/2.

17. The method of 15, further comprising:

generating a timer correction value c_ddT for the second timer by setting c_ddT as;

c_ddt=(max_ddT+min_ddt)/2.

18. A computer program product stored on a computer readable medium and adapted to perform a method for reconstructing a transport protocol data flow from data packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in a second direction on a second channel, a first part of the data packets captured by a first packet capturing device on the first channel and time stamped by a first timer and a second part of the data packets captured by a second packet capturing device on the second channel and time stamped by a second timer, the method comprising:

selecting a data packet for evaluation captured by the first packet capturing device in the first direction;

determining whether there is a missing data packet in the second direction; and

responsive to determining that there is a missing data packet in the second direction,

storing the data packet for evaluation in a first list, and

creating an acknowledgement timer associated with the data packet stored in the first list, the acknowledgment timer indicating a maximum time to wait until identifying the missing data packet as lost.

19. The computer program product of claim 18, the method further comprising:

determining whether the missing data packet was previously received in the second direction and stored in a second list; and

responsive to determining that the missing data was previously stored in the second list,

extracting the missing packet from the second list, and

canceling the acknowledgement timer associated with the extracted packet.

20. The computer program product of claim 18, the method further comprising:

determining whether the acknowledgement timer expired; and

responsive to determining that the acknowledgement timer expired,

extracting the data packet from the first list, and

indicating that at least a packet was lost in the second direction.

21. The computer program product of claim 18, the method further comprising:

determining whether the data packet is a retransmission of a same packet previously transmitted in the first direction; and

responsive to determining that the data packet is a retransmission, removing the data packet from data packet reconstruction.

22. The computer program product of claim 18, the method further comprising:

determining whether there is a missing data packet in the first direction; and

responsive to determining that there is a missing data packet in the first direction,

storing the data packet in a first list; and

creating a retransmission timer associated with the data packet stored in the first list, the retransmission timer indicating a maximum time to wait until treating the identifying data packet as lost.

23. The computer program product of claim 22, the method further comprising:

determining whether the retransmission timer expired; and

responsive to determining that the retransmission timer expired, extracting the data packet from the first list, and indicating that at least a packet was lost in the first direction.

24. The computer program product of claim 22, the method further comprising:

determining whether the missing data packet was previously received in the first direction and stored in the first list; and

responsive to determining that the missing data packet was previously stored in the first list,

extracting the missing packet from the first list, and

canceling the retransmission timer associated with the extracted packet.

25. The computer program product of claim 18, wherein the data packet is a TCP packet and the method further comprises optimizing the acknowledgement timer, optimizing the acknowledgement timer comprising:

selecting a packet in the second direction;

extracting a sequential number (bseq) and a timestamp (Tb) of the packet in the second direction, the sequential number (bSeq) indicating a sequential number of a first data in the packet in the second direction and timestamp (Tb) being the timestamp imposed by the second packet capturing device on the packet in the second direction;

determining whether the first list includes a packet whose acknowledgment number (aAck) and timestamp (Ta) satisfies a condition;

aAck<

=bSeq and Ta<

Tb-d-dT, aAck indicating a sequential number of a last successfully received continuous data in the packet in the first list, Ta being a timestamp imposed by the first packet capturing device on the packet in the first list, d being a maximum time between capturing of the packets by the first and second packet devices and analysis of the captured packets, and dT being a maximum time discrepancy between the first and second timers; and

responsive to determining that the first list includes a packet whose aAck satisfies the condition, extracting the packet from the first list and triggering expiration of the acknowledgement timer.

26. The computer program product of claim 18, wherein the data packet is a TCP packet and the method further comprises optimizing the retransmission timer, optimizing the retransmission timer comprising:

selecting a packet in the second direction;

extracting an acknowledgement number (back) and a timestamp(Th) of the packet in the second direction, the acknowledgment number (bAck) indicating a sequential number of a last successfully received continuous data in the packet in the second direction and the timestamp (Tb) being a timestamp imposed by the second packet capturing device on the packet in the second direction;

determining whether the first list includes a packet whose sequential number (aSeq) and timestamp (Ta) satisfies a condition;

aSeq<

=bAck and Ta<

Tb-d-dT, aSeq indicating a sequential number of a first data in the packet in the first list, Ta being a timestamp imposed by the first packet capturing device on the packet in the first list, d being a maximum time between capturing of the packets by the first and second packet devices and analysis of the captured packet, and dT being a maximum time discrepancy between the first and second timers; and

responsive to determining that the first list includes a packet whose aSeq satisfies the condition, extracting the packet from the first list and triggering expiration of the retransmission timer.

27. A computer program product recorded on a computer readable medium and adapted to perform a method for estimating the actual discrepancy ddT between a first timer and a second timer used in a TCP (Transmission Control Protocol) packet reconstruction system for capturing and analyzing TCP packets, the TCP packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in ad second direction on a second channel, a first part of the TCP packets captured by a first packet capturing device on the first channel and time stamped by the first timer and a second part of the TCP packets captured by a second packet capturing device on the second channel and time stamped by the second timer, a minimum ddT (min_ddT ) initialized as −

dT and a maximum ddT (max_ddT) initialized as dT, dT being a maximum estimated time discrepancy between the first and second timers, the method comprising recursively performing;

selecting a TCP packet from the first part of the TCP packets;

extracting a timestamp (T), a sequential number (Seq), and an acknowledgement number (Ack) from the selected TCP packet, the timestamp (T) being a timestamp imposed by the first timer on the selected packet, the sequential number (Seq) indicating a sequential number of a first data in the selected packet, and Ack indicating a sequential number of a last successfully received continuous data in the selected packet;

setting ALastTime as T, ALastSeq as Seq, and ALastAck as Ack, ALastTime being a timestamp of a last seen packet in the first direction, ALastSeq being a sequential number of the last seen packet in the first direction, and ALastAck being an acknowledgement number of the last seen packet in the first direction;

determining whether Seq is not more than BLastAck, BLastAck being an acknowledgement number of a last seen packet in the second direction;

responsive to determining that Seq is not more than BLastAck, modifying max_ddT as;

max_ddT=min (max_ddT, BLastTime−

T+2d);

determining whether Ack is not less than BLastSeq, BLastSeq being a sequential number of a last seen packet in the second direction; and

responsive to determining that Ack is not less than BLastAck, modifying min_ddT as;

min_ddT=max (min_ddT, BLastTime−

T−

2d).

28. The computer program product of 27, further comprising:

generating a modified discrepancy (d ddT) between the first timer and the second timer by setting d-ddT as;

d_—

ddT=(max_—

ddT−

min_—

ddT)/2.

29. The computer program product of 27, further comprising:

generating a timer correction value (c~ddT) for the second timer by setting c_ddT as;

c_ddT=(max_ddT+min_ddT)/2.

30. A system for reconstructing a transport protocol data flow from data packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in a second direction on a second channel, the system coupled to a first packet capturing device for capturing a first part of the data packets on the first channel and to a second packet capturing device for capturing a second part of the data packets on the second channel, the first packet capturing device including a first timer for timestamping the first part of the data packets and the second packet capturing device including a second timer for timestamping the second part of the data packets, the system comprising:

a network interface card coupled to the first and second packet capturing devices for receiving the first and second parts of the data packets; and

a processor adapted to perform;

selecting a data packet for evaluation captured by the first packet capturing device in the first direction;

determining whether there is a missing data packet in the second direction; and

responsive to determining that there is a missing data packet in the second direction,

storing the data packet for evaluation in a first list, and

creating an acknowledgement timer associated with the data packet stored in the first list, the acknowledgment timer indicating a maximum time to wait until identifying the missing data packet as lost.

31. The system of claim 30, wherein the processor is further adapted to perform:

determining whether the missing data packet was previously received in the second direction and stored in a second list; and

responsive to determining that the missing data packet was previously stored in the second list,

extracting the missing packet from the second list, and

canceling the acknowledgement timer associated with the extracted packet.

32. The system of claim 30, wherein the processor is further adapted to perform:

determining whether the acknowledgement timer expired; and

responsive to determining that the acknowledgement timer expired,

extracting the data packet from the first list; and

indicating that at least a packet was lost in the second direction.

33. The system of claim 30, wherein the processor is further adapted to perform:

determining whether the data packet is a retransmission of a same packet previously transmitted in the first direction; and

responsive to determining that the data packet is a retransmission, removing the data packet from data packet reconstruction.

34. The system of claim 30, wherein the processor is further adapted to perform:

determining whether there is a missing data packet in the first direction;

and

responsive to determining that there is a missing data packet in the first direction,

storing the data packet in a first list, and

creating a retransmission timer associated with the data packet stored in the first list, the retransmission timer indicating a maximum time to wait until identifying the missing data packet as lost.

35. The system of claim 34, wherein the processor is further adapted to perform:

determining whether the retransmission timer expired; and

responsive to determining that the acknowledgement timer expired,

extracting the data packet from the first list, and

indicating that at least a packet was lost in the first direction.

36. The system of claim 34, wherein the processor is further adapted to perform:

determining whether the missing data packet was previously received in the first direction and stored in the first list; and

responsive to determining that the missing data packet was previously stored in the first list,

extracting the missing packet from the first list, and

canceling the retransmission timer associated with the extracted packet.

37. The system of claim 30 wherein the data packet is a TCP packet and the processor is further adapted to perform optimizing the acknowledgement timer, optimizing the acknowledgement timer comprising:

selecting a packet in the second direction;

extracting a sequential number (bSeq) and a timestamp (Tb) of the packet in the second direction, the sequential number (bSeq) indicating a first data in the packet in the second direction and the timestamp (Tb) being the a timestamp imposed by the second packet capturing device on the packet in the second direction;

determining whether the first list includes a packet whose acknowledgment number (Ack) and timestamp (Ta) satisfies a condition;

aAck<

=bSeq and Ta<

Tb-d-dT, aAck indicating a sequential number of a last successfully received continuous data in the packet in the first list, Ta being the timestamp imposed by the first packet capturing device on the packet in the first list, d being a maximum time between capturing of the packets by the first and second packet devices and analysis of the captured packets, and dT being a maximum time discrepancy between the first and second timers; and

responsive to determining that the first list includes a packet whose aAck satisfies the condition, extracting the packet from the first list and triggering expiration of the acknowledgement timer.

38. The system of claim 30, wherein the data packet is a TCP packet and the processor is further adapted to perform optimizing the retransmission timer, optimizing the retransmission timer comprising:

selecting a packet in the second direction;

extracting a acknowledgement number (back) and a timestamp (Tb) of the packet in the second direction, the sequential number (bAck) indicating a sequential number of a last successfully received continuous data in the packet in the second direction and the timestamp (Tb) being a timestamp imposed by the second packet capturing device on the packet in the second direction;

determining whether the first list includes a packet whose sequential number (aseq) and timestamp (Ta) satisfies a condition;

aSeq<

=bAck and Ta<

Tb-d-dT, aSeq indicating a sequential number of a first data in the packet in the first list, Ta being a timestamp imposed by the first packet capturing device on the packet in the first list, d being a maximum time between capturing of the packets by the first and second packet devices and analysis of the captured packets, and dT being a maximum time discrepancy between the first and second timers; and

responsive to determining that the first list includes a packet whose aSeq satisfies the condition, extracting the packet from the first list and triggering expiration of the retransmission timer.

39. A system for reconstructing data packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in a second direction on a second channel, a first part of the data packets captured by a first packet capturing device on the first channel and time stamped by a first timer and a second part of the data packets captured by a second packet capturing device on the second channel and time stamped by a second timer, the system comprising:

network interface module coupled to the first and second packet capturing devices for receiving the captured data packets;

data packet reordering module coupled to the network interface module and reordering the captured data packets according to their timestamps imposed by the first and second timers; and

an acknowledgment timer coupled to the data packet reordering module and indicating the maximum time that the data packet reordering module will wait for a missing packet in the second direction in the captured data packets until the data packet reordering module identifies the missing packet as lost.

40. A system for reconstructing data packets transmitted from a first device to a second device in a first direction on a first channel and from the second device to the first device in a second direction on a second channel, a first part of the data packets captured by a first packet capturing device on the first channel and time stamped by a first timer and a second part of the data packets captured by a second packet capturing device on the second channel and time stamped by a second timer, the system comprising:

a network interface module coupled to the first and second packet capturing devices for receiving the captured data packets;

a data packet reordering module coupled to the network interface module and reordering the captured data packets according to their timestamps imposed by the first and second timers; and

a retransmission timer coupled to the data packet reordering module and indicating the maximum time that the data packet reordering module will wait for a missing packet in the first direction in the captured data packets until the data packet reordering module identifies the missing packet as lost.