On the role and controllability of persistent clients in traffic aggregates

ABSTRACT

Flash crowd events (FCEs) present a real threat to the stability of routers and end-servers. Such events are characterized by a large and sustained spike in client arrival rates, usually to the point of service failure. Traditional rate-based drop policies, such as Random Early Drop (RED), become ineffective in such situations since clients tend to be persistent, in the sense that they make multiple retransmission attempts before aborting their connection. As it is built into TCP's congestion control, this persistence is very widespread, making it a major stumbling block to providing responsive aggregate traffic controls. This paper focuses on analyzing and modeling the effects of client persistence on the controllability of aggregate traffic. Based on this model, we propose a new drop strategy called persistent dropping to regulate the arrival of SYN packets and achieves three important goals: 1) it allows routers and end-servers to quickly converge to their control targets without sacrificing fairness; 2) it minimizes the portion of client delay that is attributed to the applied controls; and 3) it is both easily implementable and computationally tractable. Using a real implementation of this controller in the Linux kernel, we demonstrate its efficacy, up to 60% delay reduction for drop probabilities less than 0.5.

REFERENCES

• 1: [1] H. Balakrishnan, V. N. Padmanabhan, S. Seshan, M. Stemm, and R. Katz, "TCP behavior of a busy Internet server: analysis and improvements," in Proc. IEEE INFOCOM, Mar. 1998, pp. 252-262.
• 2: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 3: Norman L. Biggs, Discrete mathematics, Oxford University Press, Inc., New York, NY, 1986
• 4: B. Braden , D. Clark , J. Crowcroft , B. Davie , S. Deering , D. Estrin , S. Floyd , V. Jacobson , G. Minshall , C. Partridge , L. Peterson , K. Ramakrishnan , S. Shenker , J. Wroclawski , L. Zhang, Recommendations on Queue Management and Congestion Avoidance in the Internet, RFC Editor, 1998
• 5: [5] N. Cardwell, S. Savage, and T. Anderson, "Modeling TCP latency," in Proc. IEEE INFOCOM, 2000, pp. 1742-1751.
• 6: Wu-chang Feng , Kang G. Shin , Dilip D. Kandlur , Debanjan Saha, The BLUE active queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.513-528, August 2002 [doi>10.1109/TNET.2002.801399]
• 7: [7] S. D. Committee, SPECweb Tech. Rep., Apr. 1999. [Online]. Available: http://www.specbench.org/osg/web/
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: [9] A. Feldmann, Characteristics of TCP Connection Arrivals, ser. Self-Similar Network Traffic and Performance Evaluation. New York: Wiley, 2000, ch. 15, pp. 367-399.
• 10: A. Feldmann , A. C. Gilbert , W. Willinger , T. G. Kurtz, The changing nature of network traffic: scaling phenomena, ACM SIGCOMM Computer Communication Review, v.28 n.2, p.5-29, Apr. 1998 [doi>10.1145/279345.279346]
• 11: Anja Feldmann , Anna C. Gilbert , Polly Huang , Walter Willinger, Dynamics of IP traffic: a study of the role of variability and the impact of control, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.301-313, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: 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]
• 13: 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]
• 14: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 15: Sally Floyd , Mark Handley , Jitendra Padhye , Jörg Widmer, Equation-based congestion control for unicast applications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.43-56, August 28-September 01, 2000, Stockholm, Sweden
• 16: [16] C. Hollot, V. Misra, D. Towsley, and W. Gong, "A control theoretic analysis of RED," in Proc. IEEE INFOCOM, 2001, vol. 3, pp. 1510-1519.
• 17: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 18: Hani Jamjoom , Padmanabhan Pillai , Kang G. Shin, Resynchronization and controllability of bursty service requests, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.582-594, August 2004 [doi>10.1109/TNET.2004.833147]
• 19: Hani Jamjoom , Kang G. Shin, Persistent dropping: an efficient control of traffic aggregates, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863988]
• 20: Jaeyeon Jung , Balachander Krishnamurthy , Michael Rabinovich, Flash crowds and denial of service attacks: characterization and implications for CDNs and web sites, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511485]
• 21: Jonathan Lemon, Resisting SYN Flood DoS Attacks with a SYN Cache, Proceedings of the BSDCon 2002, p.89-97, February 11-14, 2002
• 22: Ratul Mahajan , Steven M. Bellovin , Sally Floyd , John Ioannidis , Vern Paxson , Scott Shenker, Controlling high bandwidth aggregates in the network, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.62-73, July 2002 [doi>10.1145/571697.571724]
• 23: [23] F. Marie, Netfilter Extensions HOWTO. [Online]. Available: http:// www.netfilter.org.
• 24: [24] R. Morris and D. Lin, "Variance of aggregated web traffic," in Proc. IEEE INFOCOM, 2000, vol. 1, pp. 360-366.
• 25: David Mosberger , Tai Jin, httperf—a tool for measuring web server performance, ACM SIGMETRICS Performance Evaluation Review, v.26 n.3, p.31-37, Dec. 1998 [doi>10.1145/306225.306235]
• 26: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 27: Jitendra Pahdye , Sally Floyd, On inferring TCP behavior, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.287-298, August 2001, San Diego, California, United States
• 28: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 29: [29] J. Reumann, H. Jamjoom, and K. Shin, "Adaptive packet filters," in Proc. IEEE GLOBECOM, Nov. 2001, pp. 2331-2335.
• 30: Sambit Sahu , Philippe Nain , Christophe Diot , Victor Firoiu , Don Towsley , Don Iowsley, On achievable service differentiation with token bucket marking for TCP, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.23-33, June 18-21, 2000, Santa Clara, California, United States
• 31: Shriram Sarvotham , Rudolf Riedi , Richard Baraniuk, Connection-level analysis and modeling of network traffic, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505215]
• 32: [32] H. Zhang and D. Ferrari, "Rate-controlled static priority queueing," in Proc. IEEE INFOCOM, San Francisco, CA, 1993, pp. 227-236.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Management, Performance

Keywords:
active queue management, aggregate traffic control, flash crowds, persistent dropping