Ion Stoica
Hui Zhang
Skip Abstract Section
Abstract
Existing approaches for providing guaranteed services require routers to manage per flow states and perform per flow operations [9, 21]. Such a stateful network architecture is less scalable and robust than stateless network architectures like the original IP and the recently proposed Diffserv [3]. However, services provided with current stateless solutions, Diffserv included, have lower flexibility, utilization, and/or assurance level as compared to the services that can be provided with per flow mechanisms.In this paper, we propose techniques that do not require per flow management (either control or data planes) at core routers, but can implement guaranteed services with levels of flexibility, utilization, and assurance similar to those that can be provided with per flow mechanisms. In this way we can simultaneously achieve high quality of service, high scalability and robustness. The key technique we use is called Dynamic Packet State (DPS), which provides a lightweight and robust mechanism for routers to coordinate actions and implement distributed algorithms. We present an implementation of the proposed algorithms that has minimum incompatibility with IPv4.
- 1 Ozalp Babao~lu and Sam Toueg. Non-Blocking Atomic Commitment. Distributed Systems, S. Mullender (ed.), pages 147-168, 1993.]] Google Scholar
Digital Library
- 2 F. Baker, C. Iturralde, F. Le Faucheur, and B. Davie. Aggregation of RSVP for IP4 and IP6 Reservations. Internet Draft, draft-baker-rsvp-aggregation-00.txt.]] Google ScholarDigital Library
- 3 Y. Bernet et. al. A framework for differentiated services, November 1998. Internet Draft, draft-ietf-diffservframework-01 .txt.]]Google Scholar
- 4 R. Gallon, P. Doolan, N. Feldman, A. Fredette, G. Swallow, and A. Viswanathan. A framework for multiprotocol label switching, November 1997. Internet Draft, draft-ietf-mplsframework-02.txt.]]Google Scholar
- 5 D. Clark. The design philosophy of the DARPA internet protocols. In Proceedings oJ A CM SIGCOMM'88, pages 106- 114, Stanford, CA, August 1988.]] Google ScholarDigital Library
- 6 D. Clark. Internet cost allocation and pricing, lnternet Economics, L. W. JtlcKnight and J. P. Bailey (eds.), pages 215- 252, 1997.]] Google ScholarDigital Library
- 7 D. Clark and J. Wroclawski. An approach to service allocation in the Internet, July 1997'. Internet Draft.]]Google Scholar
- 8 A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In Journal o.f Internetworking Research and Experience, pages 3-26, October 1990. Also in Proceedings of ACM SIGCOMM'89, pp 3-12.]] Google ScholarDigital Library
- 9 D. Ferrari and D. Verma. A scheme for real-time channel establishment in wide-area networks. IEEE Journal on Selected Areas in Communications, 8(3):368-379, April 1990.]]Google ScholarDigital Library
- 10 N. Figueiraand J. Pasquale. An upper bound on delay for the VirtualClock service discipline. IEEE/A CM Transactions on .Networking, 3(4), April 1995.]] Google ScholarDigital Library
- 11 S. Floyd and V. Jacobson. Random early detection for congestion avoidance. IEEE/A CM Transactions on Networking, 1(4):397-413, July 1993.]] Google ScholarDigital Library
- 12 L. Georgiadis, R. Guerin, V. Peris, and K. Sivarajan. Efficient network QoS provisioning based on per node traffic shaping. IEEE/ACM Transactions on Networking, 4(4):482-501, August 1996.]] Google ScholarDigital Library
- 13 P. Goyal, S. Lam, and H. Vin. Determining end-to-end delay bounds in heterogeneous networks. In Proceedings of NOSS- DAV'95, pages 287-298, Durham, New Hampshire, April 1995.]] Google ScholarDigital Library
- 14 R. Guerin, S. Blake, and S. Herzog. Aggregating RSVP- based QoS Requests. Internet Draft, draft-guerin-aggregrsvp-00.txt.]]Google Scholar
- 15 S. Jamin, P. Danzig, S. Shenker, and L. Zhang. A measurement-based admission control algorithm for integrated services packet networks. In Proceedings of SIG- COMM'95, pages 2-13, Boston, MA, September 1995.]] Google ScholarDigital Library
- 16 S. Keshav. A control-theoretic approach to flow control. In Proceedings of A CM SIGCOMM'91, pages 3-15, Zurich, Switzerland, September 1991.]] Google ScholarDigital Library
- 17 K. Nichols, S. Blake, F. Baker, and D. L. Black. Definition of the Differentiated Services Field (DS Field) in the ipv4 and ipv6 Headers, October 1998. Internet Draft, draf-ietfdiffserv-header-04.txt.]] Google ScholarDigital Library
- 18 K. Nichols, V. Jacobson, and L. Zhang. An approach to service allocation in the Internet, November 1997. Internet Draft.]]Google Scholar
- 19 NLANR: Network Traffic Packet Header Traces. URL: http://moat, nlanr, net/Traces/.]]Google Scholar
- 20 A. Parekh and R. Gallager. A generalized processor sharing approach to flow control- the single node case. In Proceedings of the INFOCOM'92, 1992.]] Google ScholarDigital Library
- 21 S. Shenker R. Braden, D. Clark. Integrated services in the Internet architecture: an overview, June 1994. Internet RFC 1633.]] Google ScholarDigital Library
- 22 S. Shenker. Making greed work in networks: A game theoretical analysis of switch service disciplines. In Proceedings of AU.M SIGG'OMM'9g, pages 47-57, London, UK, August 1994.]] Google ScholarDigital Library
- 23 S. Shenker, G. Partridge, and R. Guerin. Specification of guaranteed quality of service, 1997. Internet RFC 2212.]] Google ScholarDigital Library
- 24 D.C. Stephens, J.C.R. Bennett, and H. Zhang. Implementing scheduling algorithms in high speed networks. To Appear in IEEE JSA C', 1999.]]Google ScholarDigital Library
- 25 D. Stilliadis and A. Verma. Latency-rate servers: A general model for analysis of traffic scheduling algorithms. IEEE/ACM Transactions on Networking, 6(2):164-174, April 1998.]] Google ScholarDigital Library
- 26 I. Stoica, S. Shenker, and H. Zhang. Gore-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks. In Proceedings ACM SIG- COMM'98, pages 118-130, Vancouver, September 1998.]] Google ScholarDigital Library
- 27 I. Stoica and H. Zhang. LIRA: A model for service differentiation in the Internet. In Proceedings o.f NOSSDAV'98, London, UK, July 1998.]]Google Scholar
- 28 I. Stoica and H. Zhang. Providing guranteed services without per flow management, May 1999. Technical Report CMU- CS-99-133.]]Google Scholar
- 29 D. Tse and M. Grosslauser. Measurement-based Call Admission Control: Analysis and Simulation. In Proceedings oJ {NFOCOM'97, pages 981-989, Kobe, Japan, 1997.]] Google ScholarDigital Library
- 30 D. Verma, H. Zhang, and D. Ferrari. Guaranteeing delay jitter bounds in packet switching networks. In Proceedings of Tricomm'91, pages 35-46, Chapel Hill, North Carolina, April 1991.]]Google Scholar
- 31 W. E. Weihl. Transaction-Processing Techniques. Distributed Systems, S. Mullender (ed.), pages 329-352, 1993.]] Google ScholarDigital Library
- 32 D. Wrege, E. Knightly, H. Zhang, and J. Liebeherr. Deterministic delay bounds for vbr video packet-switching networks: Fundmental limits and practical trade-offs. 4(3):352- 362, June 1996.]] Google ScholarDigital Library
- 33 D.E. Wrege and J. Liebeherr. A Near-Optimal Packet Scheduler for QoS Networks.]]Google Scholar
- 34 J. Wroclawski. Specification of controlled-load network element service, 1997. Internet RFG 2211.]] Google ScholarDigital Library
- 35 H. Zhang and D. Ferrari. Rate-controlled static priority queueing. In Proceedings of IEEE INFOCOM'93, pages 227- 236, San Francisco, California, April 1993.]]Google ScholarCross Ref
- 36 H. Zhang and D. Ferrari. Rate-controlled service disciplines. Journal of High Speed Networks, 3(4):389-412, 1994.]]Google ScholarCross Ref
- 37 L. Zhang. Virtual Clock: A new traffic control algorithm for packet switching networks. In Proceedings of A CM SIG- COMM'90, pages 19-29, Philadelphia, PA, September 1990.]] Google ScholarDigital Library
Index Terms
- Providing guaranteed services without per flow management
Recommendations
Providing guaranteed services without per flow management
SIGCOMM '99: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communicationExisting approaches for providing guaranteed services require routers to manage per flow states and perform per flow operations [9, 21]. Such a stateful network architecture is less scalable and robust than stateless network architectures like the ...
Comments