Rd network services: differentiation through performance incentives

ABSTRACT

With the Internet offering a single best-effort service, there have been numerous proposals of diversified network services that align better with the divergent needs of different distributed applications. The failure of these innovative architectures to gain wide deployment is primarily due to economic and legacy issues, rather than technical shortcomings. We propose a new paradigm for network service differentiation where design principles account explicitly for the multiplicity of Internet service providers and users as well as their economic interests in environments with partly deployed new services. Our key idea is to base the service differentiation on performance itself, rather than price. The proposed RD (Rate-Delay) services enable a user to choose between a higher transmission rate or low queuing delay at a congested network link. An RD router supports the two services by maintaining two queues per output link and achieves the intended rate-delay differentiation through simple link scheduling and dynamic buffer sizing. After analytically deriving specific rules for RD router operation, we conduct extensive simulations that confirm effectiveness of the RD services geared for incremental deployment in the Internet.

REFERENCES

• 1: A. Aggarwal, S. Savage, and T. Anderson. Understanding the Performance of TCP Pacing. In Proceedings IEEE INFOCOM 2000, March 2000.
• 2: J. Bennett and H. Zhang. WF2Q: Worse-case Fair Weighted Fair Queuing. In Proceedings IEEE INFOCOM 1996, March 1996.
• 3: S. Blake , D. Black , M. Carlson , E. Davies , Z. Wang , W. Weiss, An Architecture for Differentiated Service, RFC Editor, 1998
• 4: R. Braden , D. Clark , S. Shenker, Integrated Services in the Internet Architecture: an Overview, RFC Editor, 1994
• 5: J. W. Byers, M. Luby, and M. Mitzenmacher. A Digital Fountain Approach to Asynchronous Reliable Multicast. IEEE Journal on Selected Areas in Communications, 20(8):1528--1540, October 2002.
• 6: David D. Clark , Wenjia Fang, Explicit allocation of best-effort packet delivery service, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.362-373, Aug. 1998 [doi>10.1109/90.720870]
• 7: David D. Clark , John Wroclawski , Karen R. Sollins , Robert Braden, Tussle in cyberspace: defining tomorrow's internet, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 8: D. Wei. A TCP Pacing Implementation for NS2. http://netlab.caltech.edu/projects/ns2tcplinux/ns2pacing/.
• 9: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 10: M. Dertouzos. Control Robotics: The Procedural Control of Physical Processes. In Proceedings IFIP Congress 1974, August 1974.
• 11: Constantinos Dovrolis , Dimitrios Stiliadis , Parameswaran Ramanathan, Proportional differentiated services: delay differentiation and packet scheduling, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.109-120, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: Cristian Estan , George Varghese , Michael Fisk, Bitmap algorithms for counting active flows on high-speed links, IEEE/ACM Transactions on Networking (TON), v.14 n.5, p.925-937, October 2006 [doi>10.1109/TNET.2006.882836]
• 13: V. Firoiu, X. Zhang, and Y. Guo. Best Effort Differentiated Services: Tradeoff Service Differentiation for Elastic Applications. In Proceedings IEEE ICT 2001, June 2001.
• 14: 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
• 15: S. Floyd , T. Henderson, The NewReno Modification to TCP's Fast Recovery Algorithm, RFC Editor, 1999
• 16: 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]
• 17: S. Gorinsky , S. Baruah , T. J. Marlowe , A. D. Stoyenko, Exact and Efficient Analysis of Schedulability in Fixed-Packet Networks: A Generic Approach, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.584, April 09-11, 1997
• 18: S. Gorinsky, M. Georg, M. Podlesny, and C. Jechlitschek. A Theory of Load Adjustments and its Implications for Congestion Control. Journal of Internet Engineering, 1(2):82--93, October 2007.
• 19: Sergey Gorinsky , Sugat Jain , Harrick Vin , Yongguang Zhang, Design of multicast protocols robust against inflated subscription, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.249-262, April 2006 [doi>10.1109./TNET.2006.872573]
• 20: Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.157-168, August 28-30, 1996, Palo Alto, California, United States
• 21: Y. Gu, D. Towsley, C. Hollot, and H. Zhang. Congestion Control for Small Buffer High Speed Networks. In Proceedings IEEE INFOCOM 2007, May 2007.
• 22: R. Guérin , S. Kamat , V. Peris , R. Rajan, Scalable QoS provision through buffer management, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.29-40, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 23: J. Heinanen , F. Baker , W. Weiss , J. Wroclawski, Assured Forwarding PHB Group, RFC Editor, 1999
• 24: P. Hurley, J.-Y. Le Boudec, P. Thiran, and M. Kara. ABE: Providing a Low-Delay Service within Best Effort. IEEE Network, 15(3):60--69, May/June 2001.
• 25: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 26: V. Jacobson , K. Nichols , K. Poduri, An Expedited Forwarding PHB, RFC Editor, 1999
• 27: H.-A. Kim and D. O'Hallaron. Counting Network Flows in Real Time. In Proceedings IEEE GLOBECOM 2003, December 2003.
• 28: Jörg Liebeherr , Dallas E. Wrege , Domenico Ferrari, Exact admission control for networks with a bounded delay service, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.885-901, Dec. 1996 [doi>10.1109/90.556345]
• 29: D. Loguinov and H. Radha. Increase-Decrease Congestion Control for Real-time Streaming: Scalability. In Proceedings IEEE INFOCOM 2002, June 2002.
• 30: S. McCanne and S. Floyd. ns Network Simulator. http://www.isi.edu/nsnam/ns/.
• 31: K. Nichols , S. Blake , F. Baker , D. Black, Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers, RFC Editor, 1998
• 32: J. Postel. Internet Protocol. RFC 791, September 1981.
• 33: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer, Symposium proceedings on Communications architectures and protocols, p.303-313, August 16-18, 1988, Stanford, California, United States
• 34: Stefan Savage , Neal Cardwell , David Wetherall , Tom Anderson, TCP congestion control with a misbehaving receiver, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505704]
• 35: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 36: Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.81-94, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 37: 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]
• 38: D. Wetherall, U. Legedza, and J. Guttag. Introducing New Internet Services: Why and How. IEEE Network, 12(3):12--19, May-June 1998.
• 39: Xiaowei Yang , David Wetherall , Thomas Anderson, A DoS-limiting network architecture, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 40: L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks, Proceedings of the ACM symposium on Communications architectures & protocols, p.19-29, September 26-28, 1990, Philadelphia, Pennsylvania, United States

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Economics, Performance

Keywords:
incremental deployment, legacy infrastructure, legacy traffic, performance incentive, queuing delay, service differentiation, transmission rate