Achieving 100% throughput in TCP/AQM under aggressive packet marking with small buffer

ABSTRACT

We consider a TCP/AQM system with large link capacity (NC) shared by many flows. The traditional rule-of-thumb suggests that the buffer size be chosen in proportion to the number of flows (N) for full link utilization, while recent research outcomes show that O(√N) buffer sizing is sufficient for high utilization and O(1) buffer sizing makes the system stable at the cost of reduced link utilization. In this paper, we consider a system where the Active Queue Management (AQM) is scaled as O(N^α) with a buffer of size O(N^β) (0 < α < β < 0.5). By capturing randomness both in packet arrivals and in packet markings, we develop a doubly-stochastic model for a TCP/AQM system with many flows. We prove that, under such a scale, the system always performs well in the sense that the link utilization goes to 100% and the loss ratio decreases to zero as the system size N increases. Our results assert that the system enjoys benefit of largeness with no tradeoff between full link utilization, zero packet loss, and small buffer size, at least asymptotically. This is in stark contrast to existing results showing that there always exists a tradeoff between full link utilization and the required buffer size. Extensive ns-2 simulation results under various configurations also confirm our theoretical findings. Our study illustrates that blind application of fluid modeling may result in strange results and exemplifies the importance of choosing a right modeling approach for different scaling regimes.

REFERENCES

• 1: Sally Floyd, TCP and explicit congestion notification, ACM SIGCOMM Computer Communication Review, v.24 n.5, p.8-23, Oct. 1994 [doi>10.1145/205511.205512]
• 2: Guido Appenzeller , Isaac Keslassy , Nick McKeown, Sizing router buffers, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: J. Sun, M. Zukerman, K. Ko, G. Chen, and S. Chan, "Effect of large buffers on TCP Queueing behavior," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004.
• 4: A. Dhamdhere, H. Jiang, and C. Dovrolis, "Buffer sizing for congested Internet links," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005.
• 5: G. Raina and D. Wischik, "Buffer sizes for large multiplexers: TCP queueing theory and instability," in EuroNGI, Rome, Italy, Apr. 2005.
• 6: Damon Wischik , Nick McKeown, Part I: buffer sizes for core routers, ACM SIGCOMM Computer Communication Review, v.35 n.3, July 2005 [doi>10.1145/1070873.1070884]
• 7: Gaurav Raina , Don Towsley , Damon Wischik, Part II: control theory for buffer sizing, ACM SIGCOMM Computer Communication Review, v.35 n.3, July 2005 [doi>10.1145/1070873.1070885]
• 8: M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, "Routers with very small buffers," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 9: Curtis Villamizar , Cheng Song, High performance TCP in ANSNET, ACM SIGCOMM Computer Communication Review, v.24 n.5, p.45-60, Oct. 1994 [doi>10.1145/205511.205520]
• 10: Steven H. Low , Fernando Paganini , Jiantao Wang , John C. Doyle, Linear stability of TCP/RED and a scalable control, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.5, p.633-647, 5 December 2003 [doi>10.1016/S1389-1286(03)00304-9]
• 11: Supratim Deb , R. Srikant, Rate-based versus queue-based models of congestion control, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 12: D. Hong and D. Lebedev, "Many TCP user asymptotic analysis of the AIMD model," INRIA Tech. Rep. RR-42292001.
• 13: P. Tinnakornsrisuphap and A. M. Makowski, "Limit behavior of ECN/RED gateways under a large number of TCP flows," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003.
• 14: S. Deb and R. Srikant, "Global stability of congestion controllers for the Internet," IEEE Trans. Autom. Contr., vol. 48, no. 6, pp. 1055-1060, Jun. 2003.
• 15: S. Shakkottai and R. Srikant, "Mean FDE models for Internet congestion control under a many-flows regime," IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1050-1072, Jun. 2004.
• 16: F. P. Kelly, "Models for a self-managed Internet," Philos. Trans. Roy. Soc. A358, pp. 2335-2348, 2000.
• 17: Pasi E. Lassila , Jorma T. Virtamo, Modeling the Dynamics of the RED Algorithm, Proceedings of the First COST 263 International Workshop on Quality of Future Internet Services, p.28-42, September 25-26, 2000
• 18: S. Deb, S. Shakkottai, and R. Srikant, "Stability and convergence of TCP-like congestion controllers in a many-flows regime," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003.
• 19: Peerapol Tinnakornsrisuphap , Richard J. La, Characterization of queue fluctuations in probabilistic AQM mechanisms, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 20: F. Baccelli , D. R. McDonald , J. Reynier, A mean-field model for multiple TCP connections through a buffer implementing RED, Performance Evaluation, v.49 n.1-4, p.77-97, September 2002 [doi>10.1016/S0166-5316(02)00136-0]
• 21: D. R. McDonald and J. Reynier, "Mean field convergence of a rate model of multiple TCP connections throughput a buffer implementing red," Ann. Appl. Probab., vol. 16, no. 1, pp. 244-294, 2006.
• 22: P. Kuusela, P. E. Lassila, and J. T. Virtamo, "Modeling RED with idealized TCP source," in Proc. IFIP ATM & IP, 2001.
• 23: V. Sharma , J. Virtamo , P. Lassila, PERFORMANCE ANALYSIS OF THE RANDOM EARLY DETECTION ALGORITHM, Probability in the Engineering and Informational Sciences, v.16 n.3, p.367-388, July 2002 [doi>10.1017.S0269964802163078]
• 24: S. M. Ross, Stochastic Processes, 2nd ed. New York: Wiley, 1996.
• 25: P. Brémaud, Point Processes and Queues: Martingale Dynamics. New York: Springer-Verlag, 1981.
• 26: D. J. Daley and D. Vere-Jones, An Introduction to the Theory of Point Processes. New York: Springer-Verlag, 1988.
• 27: J. Cao and K. Ramanan, "A Poisson limit for buffer overflow probabilities," in Proc. IEEE INFOCOM, New York, NY, 2002.
• 28: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]
• 29: Hao Jiang , Constantinos Dovrolis, Why is the internet traffic bursty in short time scales?, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 30: R. Morris and D. Lin, "Variance of aggregated web traffic," in Proc. IEEE INFOCOM, Tel-Aviv, Israel, Apr. 2000.
• 31: T. Karagiannis, M. Molle, M. Faloutsos, and A. Broido, "A nonstationary Poisson view of Internet traffic," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004.
• 32: P. Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. New York: Springer-Verlag, 1999.
• 33: T. Lindvall, Lectures on the cOupling Method. New York: Dover, 2002.
• 34: D. Y. Eun and X. Wang, "Achieving 100% throughput in TCP/AQM under aggressive packet marking with small buffer," North Carolina State Univ., Raleigh, NC, Tech. Rep., Aug. 2006 [Online]. Available: http://www4.ncsu.edu~dyeun/pub/techrep06-smallbuffer.pdf
• 35: ns-2 - The Network Simulator. ISI, 2004 [Online]. Available: http:// www.isi.edunsnamns

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks
      C.2.2 Network Protocols

          Nouns: TCP/IP
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Management, Performance

Keywords:
router buffer sizing, small buffer, stochastic modeling, transmission control protocol