Monarch: a tool to emulate transport protocol flowsover the internet at large

ABSTRACT

This paper proposes Monarch, a novel tool that accurately emulates transport protocol flows from an end host controlled by its user to any other Internet host that responds to simple TCP, UDP, or ICMP packet probes. Since many Internet hosts and routers respond to such probes, Monarch can evaluate transport protocols, such as TCP Reno, TCP Vegas, and TCP Nice, over a large and diverse set of Internet paths. Current approaches to evaluating these protocols need control over both end hosts of an Internet path. Consequently, they are limited to a small number of paths between nodes in testbeds like PlanetLab, RON or NIMI. Monarch's ability to evaluate transport protocols with minimal support from the destination host enables many new measurement studies. We show the feasibility of using Monarch for three example studies: (a) understanding transport protocol behavior over network paths that are less explored by the research community, such as paths to cable and DSL hosts, (b) investigating the relative performance of different transport protocol designs, such as TCP Vegas and TCP Reno, and (c) testing protocol implementations under a wide range of experimental conditions.

References

1. S. Agarwal, J. Sommers, and P. Barford. Scalable network path emulation. In Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), Washington, DC, 2005.]]
2. D. G. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. Experience with an Evolving Overlay Network Testbed. ACM Computer Communication Review, 33(3), July 2003.]]
3. T. Anderson, A. Collins, A. Krishnamurthy, and J. Zahorjan. PCP: Efficient endpoint congestion control. In Proceedings of NSDI'06, May 2006.]]
4. M. Arlitt, B. Krishnamurthy, and J. C. Mogul. Predicting short-transfer latency from TCP Arcana: A trace-based validation. In Proceedings of Internet Measurement Conference, Berkeley, CA, October 2005.]]
5. H. Balakrishnan, V. N. Padmanbhan, S. Seshan, M. Stemm, and R. H. Katz. TCP behavior of a busy Internet server: Analysis and improvements. In Proceedings of IEEE Infocom, San Francisco, CA, USA, March 1998.]]
6. J. Bellardo and S. Savage. Measuring packet reordering. In Proceedings of the 2002 ACM SIGCOMM Internet Measurement Workshop (IMW), Marseille, France, November 2002.]]
7. J.-C. Bolot. Characterizing end-to-end packet delay and loss in the Internet. In Proceedings of ACM SIGCOMM, San Francisco, CA, September 1993.]]
8. L. S. Brakmo and L. Peterson. TCP Vegas: End to end congestion avoidance on a global internet. IEEE Journal on Selected Areas in Communication, 13(8):1465--1480, October 1995.]]
9. M. Carson and D. Santay. NIST Net - a Linux-based network emulation tool. SIGCOMM Computer Communications Review, 33(3):111--126, 2003.]]
10. S. Floyd. RFC 3649 - HighSpeed TCP for large congestion windows, Dec 2003. ftp://ftp.rfc-editor.org/in-notes/rfc3649.txt.]]
11. S. Floyd, M. Handley, J. Padhye, and J. Widmer. Equation-based congestion control for unicast applications. In Proceedings of SIGCOMM'00, Aug 2000.]]
12. S. Floyd, T. Henderson, and A. Gurtov. RFC 3782 - The NewReno modification to TCP's fast recovery algorithm, Apr 2004. ftp://ftp.rfc-editor.org/in-notes/rfc3782.txt.]]
13. R. Govindan and V. Paxson. Estimating router ICMP generation delays. In Proceedings of Passive and Active Measurement (PAM'02), 2002.]]
14. K. P. Gummadi, S. Saroiu, and S. D. Gribble. King: Estimating latency between arbitrary Internet end hosts. In Proceedings of the 2nd ACM SIGCOMM Internet Measurement Workshop (IMW), Marseille, France, November 2002.]]
15. V. Jacobson, R. Braden, and D. Borman. RFC 1323 - TCP extensions for high performance, May 1992. http://www.faqs.org/rfcs/rfc1323.html.]]
16. S. Jaiswal, G. Iannaccone, C. Diot, J. Kurose, and D. Towsley. Inferring TCP connection characteristics through passive measurements. In Proceedings of IEEE Infocom, Hong Kong, March 2004.]]
17. C. Jin, D. X. Wei, and S. H. Low. FAST TCP: Motivation, architecture, algorithms, performance. In Proceedings of IEEE Infocom 2004, Mar 2004.]]
18. D. Katabi, M. Handley, and C. Rohrs. Congestion control for high bandwidth-delay product networks. In Proceedings of SIGCOMM'02, Aug. 2002.]]
19. T. Kelly. Scalable TCP: Improving performance in highspeed wide area networks. ACM Computer Communication Review, 33(2):83--91, Apr 2003.]]
20. K. Lakshminarayanan and V. N. Padmanabhan. Some findings on the network performance of broadband hosts. In Proceedings of the ACMUsenix Internet Measurement Conference (IMC), Miami, FL, USA, October 2003.]]
21. R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. User-level Internet path diagnosis. In Proceedings of the 19th Symposium on Operating Systems Principles (SOSP), Bolton Landing, NY, USA, October 2003.]]
22. S. Mascolo, C. Casetti, M. Gerla, M. Y. Sanadidi, and R. Wang. TCP Westwood: bandwidth estimation for enhanced transport over wireless links. In Proceedings of MOBICOM'01, pages 287--297, Jul 2001.]]
23. M. Mathis and J. Mahdavi. Forward acknowledgment: Refining TCP congestion control. In Proceedings of SIGCOMM 1996, pages 281--291, Aug. 1996.]]
24. M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow. RFC 2018 - TCP selective acknowledgment options, Oct. 1996. http://www.faqs.org/rfcs/rfc2018.html.]]
25. A. Medina, M. Allman, and S. Floyd. Measuring the evolution of transport protocols in the Internet. Computer Communication Review, 35(2):37--52, 2005.]]
26. A. Medina, M. Allman, and S. Floyd. Measuring interactions between transport protocols and middleboxes. In Proceedings of the Internet Measurement Conference, Taormina, Italy, August 2004.]]
27. Monarch web site. http://monarch.mpi-sws.mpg.de/.]]
28. M. Musuvathi and D. R. Engler. Model-checking large network protocol implementations. In Proceedings of NSDI'04, pages 155--168, March 2004.]]
29. Netfilter: Firewalling, NAT, and packet mangling for Linux, 2006. http://www.netfilter.org.]]
30. The network simulator - ns2. http://www.isi.edu/nsnam/ns.]]
31. J. Padhye. Papers on TCP modeling and related topics, 2001. http://research.microsoft.com/~padhye/tcp-model.html.]]
32. J. Padhye and S. Floyd. Identifying the TCP behavior of web servers. In Proceedings of the ACM SIGCOMM Conference, San Diego, CA, USA, June 2001.]]
33. V. Paxson. End-to-end routing behavior in the Internet. IEEEACM Transactions on Networking, 5(5):601--615, October 1997.]]
34. V. Paxson, A. K. Adams, and M. Mathis. Experiences with NIMI. In Proceedings of 2002 Symposium on Applications and the Internet (SAINT), Nara, Japan, February 2002.]]
35. PlanetLab. http://www.planet-lab.org/.]]
36. PlanetLab. Current slices in PlanetLab, 2006. http://www.planet-lab.org/php/slices.php.]]
37. J. Postel. RFC 792 - Internet control message protocol, 1981. http://www.faqs.org/rfcs/rfc792.html.]]
38. K. K. Ramakrishnan, S. Floyd, and D. L. Black. RFC 3168 - The addition of explicit congestion notification (ECN) to IP, Sep 2001. http://www.faqs.org/rfcs/rfc3168.html.]]
39. R. Rejaie, M. Handley, and D. Estrin. RAP: An end-to-end rate-based congestion control mechanism for realtime streams in the Internet. In Proceedings of IEEE Infocom'99, pages 1337--1345, Mar 1999.]]
40. L. Rizzo. Dummynet: A simple approach to the evaluation of network protocols. ACM Computer Communications Review, 1997.]]
41. S. Saroiu, K. P. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of the Multimedia Computing and Networking (MMCN), San Jose, CA, January 2002.]]
42. S. Saroiu, K. P. Gummadi, and S. D. Gribble. SProbe: A fast tool for measuring bottleneck bandwidth in uncooperative environments, 2002. http://sprobe.cs.washington.edu.]]
43. P. Sarolahti and A. Kuznetsov. Congestion control in Linux TCP. In Proceedings of USENIX 2002, June 2002.]]
44. S. Savage. Sting: a TCP-based network measurement tool. In Proceedings of the 1999 USENIX Symposium on Internet Technologies and Systems, Boulder, CO, USA, October 1999.]]
45. University of Southern California, Information Sciences Institute. RFC 793 - Transmission control protocol, 1981. http://www.faqs.org/rfcs/rfc793.html.]]
46. A. Vahdat, K. Yocum, K. Walsh, P. Mahadevan, D. Kostic, and D. Becker. Scalability and accuracy in a large-scale network emulator. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation, Boston, MA, 2002.]]
47. A. Venkataramani, R. Kokku, and M. Dahlin. TCP Nice: a mechanism for background transfers. In Proceedings of OSDI'02, Dec 2002.]]
48. B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An integrated experimental environment for distributed systems and networks. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, pages 255--270, Boston, MA, Dec. 2002. USENIX Association.]]
49. L. Xu, K. Harfoush, and I. Rhee. Binary increase congestion control for fast long-distance networks. In Proceedings of IEEE Infocom, Hong Kong, March 2004.]]

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network performance evaluation

  • Network properties

    • Network range

      • Local area networks

      • Wide area networks

  • Network protocols