On the correspondency between TCP acknowledgment packet and data packet

ABSTRACT

At the TCP sender side, the arrival of an ack packet always triggers the sender to send data packets, which establishes a correspondency between the arrived ack packet and the sent data packets. In a TCP connection, the correspondency between every ack packet and its corresponding data packets forms a sequence. This sequence characterizes the sender's behavior. In this paper, we propose a method to estimate this correspondency sequence from the dump trace measured at the receiver side. Because many possible correspondency sequences can be constructed based on the trace, the problem here is an estimation problem, which is to select a most possible one from those candidate sequences. The method proposed first eliminates some candidates that violate basic TCP congestion behavior. Then, it chooses the most possible one among the remaining sequences using the statistical characteristics of delays between the acks and their corresponding data packets under maximum-likelihood criterion. The method can work in the condition when the TCP connection experiences various network delay and loss, and it applies to TCP senders of different versions. Simulations and Internet experiments have been performed to validate the method.

REFERENCES

• 1: Allman, M., H. Balakrishnan, and S. Floyd, Enhancing TCP's Loss Recovery Using Limited Transmit. RFC3042, 2001.
• 2: Allman, M., S. Floyd, and C. Partridge, Increasing TCP's Initial Window. RFC2414, 1998.
• 3: Allman, M., V. Paxson, and W. Stevens, TCP Congestion Control. RFC2581, 1999.
• 4: Paul Barford , Mark Crovella, Critical path analysis of TCP transactions, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.127-138, August 28-September 01, 2000, Stockholm, Sweden
• 5: Caceres, R., et al., Multicast-Based Inference of Network Internal Loss Characteristics. IEEE Trans. ON Information Theory, 1999. 45(7): p. 2462--2480.
• 6: Floyd, S. and T. Henderson, the Newreno Modification to TCP's Fast Recovery Algorithm. RFC2582, 1999.
• 7: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 8: Kleinrock, L., Queueing Systems. 1976: Wiley, NY.
• 9: Qiong Li , David L. Mills, Jitter-based delay-boundary prediction of wide-area networks, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.578-590, October 2001 [doi>10.1109/90.958327]
• 10: Ljung, L. and T. Soderstrom, Theory and Practive of Recursive Identification. 1983: The MIT Press.
• 11: Mathis, M., et al., TCP Selective Acknowledgment Options. RFC2018, 1996.
• 12: Jitendra Pahdye , Sally Floyd, On inferring TCP behavior, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.287-298, August 2001, San Diego, California, United States
• 13: Vern Paxson, Automated packet trace analysis of TCP implementations, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-179, September 14-18, 1997, Cannes, France
• 14: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 15: Paxson, V. and M. Allman, Computing TCP's Retransmission Timer. RFC2988, 2000.
• 16: Proakis, J.G., Digital communications(Fourth Edition). 2001: McGraw-Hill Inc.
• 17: Raheli, R., A. Polydoros, and C.-K. Tzou, Per-Survivor Processing: A General Approach to MLSE in Uncertain Environments. IEEE Trans. ON COMMUNICATIONS, 1995. 43(2/3/4): p. 354--364.
• 18: Seshadri, N., Joint Data and Channel estimation Using Blind Trellis Search Techniques. IEEE Trans. ON COMMUNICATIONS, 1994. 42(2/3/4): p. 1000.
• 19: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Measurement

Keywords:
TCP, maximum-likelihood estimation, non-deterministic finite state machine