Detecting shared congestion of flows via end-to-end measurement

ABSTRACT

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. In this paper, we present techniques based on loss or delay observations at end hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. Our novel result is that such detection can be achieved for unicast flows, but the techniques can also be applied to multicast flows. We validate these techniques via queueing analysis, simulation, and experimentation within the Internet. In addition, we demonstrate preliminary simulation results that show that the delay-based technique can determine whether two TCP flows are congested at the same set of resources. We also propose metrics that can be used as a measure of the amount of congestion sharing between two flows.

REFERENCES

• 1: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 2: V. Padmanabhan, "Coordinated congestion management and bandwidth sharing for heterogeneous data streams," in Proc. NOSSDAV'99, Basking Ridge, NJ, June 1999, pp. 187-190.
• 3: L. Gautier, C. Diot, and J. Kurose, "End-to-end transmission control mechanisms for multiparty interactive applications in the internet," in Proc. IEEE INFOCOM'99, vol. 3, New York, NY, Mar. 1999, pp. 1470-1479.
• 4: J. Byers, M. Luby, and M. Mitzenmacher, "Accessing multiple mirror sites in parallel: Using Tornado codes to speed up downloads," in Proc. IEEE INFOCOM'99, vol. 1, New York, NY, Mar. 1999, pp. 275-283.
• 5: P. Rodriguez and E. Biersack, "Parallel-access for mirror sites in the internet," in Proc. IEEE INFOCOM'00, vol. 2, Tel-Aviv, Israel, Mar. 2000, pp. 864-873.
• 6: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 7: K. Harfoush , A. Bestavros , J. Byers, Robust identification of shared losses using end-to-end unicast probes, Proceedings of the 2000 International Conference on Network Protocols, p.22, November 14-17, 2000
• 8: Y. Tsang, M. Coates, and R. Nowak, "Passive unicast network tomography using EM algorithms," in IEEE Int. Conf. Acoustics, Speech, and Signal Processing, vol. 3, Salt Lake City, UT, May 2001, pp. 1469-1472.
• 9: M. Coates and R. Nowak, "Network tomography for internal delay estimation," in IEEE Int. Conf. Acoustics, Speech, and Signal Processing, vol. 6, Salt Lake City, UT, May 2001, pp. 3409-3412.
• 10: S. Seshan, M. Stemm, and R. Katz, "SPAND: Shared passive network performance discovery," in Proc. USITS'97, Monterey, CA, Dec. 1997.
• 11: Stefan Savage , Neal Cardwell , Tom Anderson, The Case for Informed Transport Protocols, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.58, March 28-30, 1999
• 12: V. Padmanabhan, "Optimizing data dissemination and transport in the internet," presented at the BU/NSF Workshop Internet Measurement, Instrumentation and Characterization, Sept. 1999, slides.
• 13: D. Katabi, I. Bazzi, and X. Yang, "An information theoretic approach for shared bottleneck inference based on end-to-end measurements," M.I.T. Lab. for Computer Science, Cambridge, MA, Class project, 1999.
• 14: S. Ratnasamy and S. McCanne, "Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements," in Proc. IEEE INFOCOM'99, vol. 1, New York, NY, Mar. 1999, pp. 353-360.
• 15: R. Caceres, N. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal characteristics: Accuracy of packet loss estimation," IEEE Trans. Inform. Theory, pp. 2462-2480, Nov. 1999.
• 16: N. Duffield, F. Lo Presti, V. Paxson, and D. Towsley, "Inferring link loss using striped unicast probes," in Proc. IEEE INFOCOM'01, vol. 1, Anchorage, AK, Apr. 2001, pp. 915-923.
• 17: M. Yajnik, S. B. Moon, J. Kurose, and D. Towsley, "Measurement and modeling of the temporal dependence in packet loss," in Proc. IEEE INFOCOM'99, vol. 1, New York, NY, Mar. 1999, pp. 345-352.
• 18: S. B. Moon , J. Kurose , P. Skelly , D. Towsley, Correlation of Packet Delay and Loss in the Internet TITLE2:, University of Massachusetts, Amherst, MA, 1998
• 19: S. Moon, P. Skelly, and D. Towsley, "Estimation and removal of clock skew from network delay measurements," in Proc. IEEE INFOCOM'99, vol. 1, New York, NY, Mar. 1999, pp. 227-234.
• 20: Vern Paxson, On calibrating measurements of packet transit times, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.11-21, June 22-26, 1998, Madison, Wisconsin, United States
• 21: D. Rubenstein , J. Kurose , D. Towsley, Detecting Shared Congestion of Flows Via End-to-End Measurement, University of Massachusetts, Amherst, MA, 1999
• 22: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.145-155, June 18-21, 2000, Santa Clara, California, United States
• 23: G. Folland, Real Analysis: Modern Techniques and Their Applications. New York: Wiley, 1984.
• 24: S. Ross, Stochastic Processes. New York: Wiley, 1983.
• 25: S. McCanne and S. Floyd. (1997) ns-LBL network simulator. {Online}. Available: http://www-nrg.ee.1bnl.gov/ns/
• 26: A. Veres , Kenesi S. Molnár , G. Vattay, On the propagation of long-range dependence in the Internet, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.243-254, August 28-September 01, 2000, Stockholm, Sweden

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Internet

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: TCP/IP

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory, Verification

Keywords:
hypothesis testing, inference, network congestion, queueing analysis