Critical path analysis of TCP transactions

ABSTRACT

Improving the performance of data transfers in the Internet (such as Web transfers) requires a detailed understanding of when and how delays are introduced. Unfortunately, the complexity of data transfers like those using HTTP is great enough that identifying the precise causes of delays is difficult. In this paper we describe a method for pinpointing where delays are introduced into applications like HTTP by using critical path analysis. By constructing and profiling the critical path, it is possible to determine what fraction of total transfer latency is due to packet propagation, network variation (e.g., queuing at touters or route fluctuation), packet losses, and delays at the server and at the client. We have implemented our technique in a tool called tcpeval that automates critical path analysis for Web transactions. We show that our analysis method is robust enough to analyze traces taken for two different TCP implementations (Linux and FreeBSD). To demonstrate the utility of our approach, we present the results of critical path analysis for a set of Web transactions taken over 14 days under a variety of server and network conditions. The results show that critical path analysis can shed considerable light on the causes of delays in Web transfers, and can expose subtleties in the behavior of the entire end-to-end system.

REFERENCES

• 1: M. Allman, S. Floyd, and C. Partridge. Increasing TCP's initial window. IETF RFC 2414, September 1998.
• 2: Jussara M. Almeida , Virgilio Almeida , David J. Yates, Measuring the behavior of a World-Wide Web server, Proceedings of the IFIP TC6 seventh international conference on High performance netwoking VII, p.57-72, May 1997, White Plains, New York, United States
• 3: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 4: M. Aron, D. Sanders, P. Druschel, and W. Zwaenepoel. Scalable content-aware request distribution in cluster-based network servers. In Proceedings of the USENIX 2000 Conference, San Diego, CA, June 2000.
• 5: H. Balakrishnan, V. Padmanabhan, S. Seshan, M. Stemm, and R. Katz. Tcp behavior of a busy internet server: Analysis and improvements. In Proceedings of IEEE INFOCOM '98, San Francisco, CA, March 1998.
• 6: G. Banga and J. Mogul. Scalable kernel performance for internet servers under realistic loads. In Proceedings of the USENIX Annual Technical Conference, New Orleans, LA, June 1998.
• 7: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 8: Paul Barford , Mark Crovella, A performance evaluation of hyper text transfer protocols, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.188-197, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Distributed Packet Rewriting and its Application to Scalable Server Architectures, Proceedings of the Sixth International Conference on Network Protocols, p.290, October 13-16, 1998
• 10: Jean-Chrysotome Bolot, End-to-end packet delay and loss behavior in the internet, Conference proceedings on Communications architectures, protocols and applications, p.289-298, September 13-17, 1993, San Francisco, California, United States
• 11: Lawrence S. Brakmo , Sean W. O'Malley , Larry L. Peterson, TCP Vegas: new techniques for congestion detection and avoidance, Proceedings of the conference on Communications architectures, protocols and applications, p.24-35, August 31-September 02, 1994, London, United Kingdom
• 12: N. Cardwell, S. Savage, and T. Anderson. Modeling TCP latency. In Proceedings of the 2000 IEEE Infocom Conference, Tel-Aviv, Israel, March 2000.
• 13: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 14: P. Druschel, V. Pai, and W. Zwaenepoel. Flash: An efficient and portable web server. In Proceedings of the USENIX 1999 Annual Technical Conference, Monterey, CA, June 1999.
• 15: R. Fielding, J. Gettys, J. Mogul, H, Frystyk, and T. Berners-Lee. Hypertext transfer protocol -- HTTP/1.1. IETF RFC 2068, January 1997.
• 16: Henrik Frystyk Nielsen , James Gettys , Anselm Baird-Smith , Eric Prud'hommeaux , Håkon Wium Lie , Chris Lilley, Network performance effects of HTTP/1.1, CSS1, and PNG, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.155-166, September 14-18, 1997, Cannes, France
• 17: J. K. Hollingsworth , B. P. Miller, Parallel program performance metrics: a comprison and validation, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.4-13, November 16-20, 1992, Minneapolis, Minnesota, United States
• 18: C. Huitema. Internet quality of service assessment. ftp.telcordia.com/pub/huitema/stats/quality_today.html, 2000.
• 19: Keynote Systems Inc. http://www.keynote.com, 1998.
• 20: Lucent NetCare Inc. net.medic. http://www.ins.com/software/medic/datasheet/index.asp, 1997.
• 21: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 22: Balachander Krishnamurthy , Craig E. Wills, Analyzing factors that influence end-to-end Web performance, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.17-32, June 2000, Amsterdam, The Netherlands
• 23: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 24: D. Lin and H. T. Kung. TCP fast recovery strategies: Analysis and improvements. In Proceedings of IEEE INFOCOM '98, San Francisco, CA, March 1998.
• 25: K. G. Lockyer. Introduction to Critical Path Analysis. Pitman Publishing Co., New York, N.Y., 1964.
• 26: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 27: B. P. Miller , M. Clark , J. Hollingsworth , S. Kierstead , S. S. Lim , T. Torzewski, IPS-2: The Second Generation of a Parallel Program Measurement System, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.206-217, April 1990 [doi>10.1109/71.80132]
• 28: D. Mills. Network time protocol (version 3): Specification, implementation and analysis. Technical Report RFC 1305, Network Information Center, SRI International, Menlo Park, CA, 1992.
• 29: J. Mogul. The case for persistent-connection HTTP. Technical Report WRL 95/4, DEC Western Research Laboratory, Palo Alto, CA, 1995.
• 30: Jeffrey C. Mogul , Fred Douglis , Anja Feldmann , Balachander Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.181-194, September 14-18, 1997, Cannes, France
• 31: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 32: V. Padmanabhan and R. Katz. TCP fast start: A technique for speeding up web transfers. In Proceedings of the IEEE GLOBECOM '98, November 1998.
• 33: 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
• 34: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 35: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 36: Apache HTTP Server Project. http://www.apache.org, 1998.
• 37: M. Schroeder , M. Burrows, Performance of Firefly RPC, Proceedings of the twelfth ACM symposium on Operating systems principles, p.83-90, November 1989
• 38: T. Shepard. TCP packet trace analysis. Master's thesis, Massachusetts Institute of Technology, 1990.
• 39: W. Stevens. TCP slow start, congestion avoidance, fast retransmit, and fast recovery algorithms. RFC 2001, January 1997.
• 40: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 41: C.-Q. Yang and B. Miller. Critical path analysis for the execution of parallel and distributed programs. In Proceedings of 8th International Conference on Distributed Computing Systems, San Jose, CA, June 1997.