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. We validate these techniques via queueing analysis, simulation, and experimentation within the Internet.

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 Proceedings of NOSSDAV'99, Basking Ridge, NJ, June 1999.
• 3: L. Gautier, C. Diot, and J. Kurose. End-to-end Transmission Control Mechanisms for Multiparty Interactive Applications in the Intemet. In Proceedings oflEEE INFOCOM'99, New York, NY, March 1999.
• 4: J. Byers, M. Luby, and M. Mitzenmacher. Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads. In Proceedings ofIEEE INFOCOM'99, New York, NY, March 1999.
• 5: D. Rubenstein , J. Kurose , D. Towsley, Detecting Shared Congestion of Flows Via End-to-End Measurement, University of Massachusetts, Amherst, MA, 1999
• 6: S. Seshan, M. Stemm, and R. Katz. SPAND: Shared Passive Network Performance Discovery. In Proceedings of the USITS'97, Monterey, CA, December 1997.
• 7: 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
• 8: V. Padmanabhan. Optimizing Data Dissemination and Transport in the Intemet, September 1999. slides presented at the BU/NSF Workshop on Internet Measurement, Instrumentation and Characterization.
• 9: D. Katabi, I. Ba.~i, and X. Yang. An Information Theoretic Approach for Shared Bottleneck Inference Based on End-to-end Measurements. Class project, MIT Laboratory for Computer Science, contact: [e-mail], 1999.
• 10: S. Ratxmsamy and S. McCanne. Inference of Multicast Routing Trees and Bottleneck Bandwidths using End-to-end Measurements. In Proceedings oflEEE INFOCOM'99, New York, NY, March 1999.
• 11: R. Caceres, N. Dutfield, j. Horowitz, and D. Towsley. Multicast-Based Inference of Network-Internal Characteristics: Accuracy of Packet Loss Estimation. Transactions on Information Theory, November 1999.
• 12: M. Yajnik, S.B. Moon, J. Kurose, and D. Towsley. Measurement and Modeling of the Temporal Dependence in Packet Loss. In Proceedings ofIEEE INFOCOM'99, New York, NY, March 1999.
• 13: 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
• 14: S. Moon, P. Skelly, and D. Towsley. Estimation and Removal of Clock Skew from Network Delay Measurements. In Proceedings of IEEE INFOCOM'99, New York, NY, March 1999.
• 15: 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
• 16: G. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley and Sons, New York, NY, 1984.
• 17: S. Ross. Stochastic Processes. John Wiley and Sons, New York, NY, 1983.
• 18: S. McCanne and S. Floyd. ns-LBL Network Simulator, 1997. Obtain via http://www-nrg.ee.lbnl.gov/ns/.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory, Verification