Deterministic packet marking for time-varying congestion price estimation

ABSTRACT

The addition of the two-bit Explicit Congestion Notification (ECN) field to the IP header provides routers with a mechanism for conveying link price information necessary for the successful operation of a number of congestion control schemes. Two recent proposals for probabilistic packet marking at the routers allow receivers to estimate path price from the fraction of marked packets. In this paper we introduce an alternative deterministic marking scheme for encoding path price. Each router quantizes the price of its outgoing link to a fixed number of bits. Every data packet sent along the path encodes a partial sum of the quantized link prices in its ECN field, allowing the receiver to estimate the path price. We evaluate the performance of our algorithm in terms of its error in representing prices, and compare it to probabilistic marking. We show that based on empirical Internet traffic characteristics, our algorithm performs better when estimating time-varying prices and static path price using small blocks of packets.

REFERENCES

• 1: [1] S. Athuraliya and S. H. Low, Optimization flow control II: Implementation Netlab, California Inst. Technol., Pasadena, CA, 2000, Tech. Rep.
• 2: [2] S. Athuraliya, V. H. Li, S. H. Low, and Q. Yin, "REM: active queue management," IEEE Network, vol. 15, no. 3, pp. 48-53, May 2001.
• 3: [3] R. J. Gibbens and F. P. Kelly, "Resource pricing and the evolution of congestion control," Automatica, vol. 35, pp. 1969-1985, 1999.
• 4: Dina Katabi , Mark Handley , Charlie Rohrs, Congestion control for high bandwidth-delay product networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: [5] S. Kunniyur and R. Srikant, "A time scale decomposition approach to adaptive ECN marking," in Proc. IEEE INFOCOM, Anchorage, AK, 2001, pp. 1330-1339.
• 6: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 7: [7] F. Paganini, Z. Wang, S. H. Low, and J. C. Doyle, "A new TCP/AQM for stable operation in fast networks," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 96-105.
• 8: [8] R. W. Thommes and M. J. Coates, "Deterministic packet marking for congestion price estimation," presented at the IEEE INFOCOM, Hong Kong, Mar. 2004.
• 9: K. Ramakrishnan , S. Floyd , D. Black, The Addition of Explicit Congestion Notification (ECN) to IP, RFC Editor, 2001
• 10: [10] M. Adler, J.-Y. Cai, J. K. Shapiro, and D. Towsley, "Estimation of congestion price using probabilistic packet marking," in Proc. IEEE INFOCOM , San Francisco, CA, Apr. 2003, pp. 2068-2078.
• 11: [11] F. Begtasevic and P. V. Mieghen, "Measurements of the hopcount in the Internet," presented at the Passive and Active Measurement (PAM2001) Conf., Amsterdam, The Netherlands, Apr. 2001.
• 12: [12] J. Postel, "Internet Protocol," IETF RFC 791, Sep. 1981.
• 13: Steven M. Bellovin, A technique for counting natted hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637243]
• 14: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 15: [15] N. L. Johnson and S. Kotz, Urn Models and Their Applications. New York: Wiley, 1977.
• 16: [16] V. F. Kolchin, B. A. Sevastyanov, and V. P. Chistyakov, Random Allocations . New York: Wiley, 1978.
• 17: Anil Kamath , Rajeev Motwani , Paul Spirakis , Krishna Palem, Tail bounds for occupancy and the satisfiability threshold conjecture, Random Structures & Algorithms, v.7 n.1, p.59-80, Aug. 1995 [doi>10.1002/rsa.3240070105]
• 18: Robust Congestion Signaling, Proceedings of the Ninth International Conference on Network Protocols, p.332, November 11-14, 2001

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Performance attributes; Measurement techniques

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
congestion control, network measurements, packet marking, statistics