Granular differentiated queueing services for QoS: structure and cost model

ABSTRACT

One weakness of DiffServ is the lack of granularity for QoS guaranteed services, which makes it difficult to cost-effectively support end-to-end (e2e) QoS according to the e2e situation (e.g., path lengths) of applications. With the conventional packet-level QoS mechanisms for the regulated traffic, i.e., buffer admission control plus output schedulers in general, increasing service granularity may inevitably complicate implementation and/or impact scalability since sophisticated output schedulers seem necessary in this case. In this paper, a new structure, Differentiated Queueing Services (DQS), is discussed to handle the above issue. DQS tries to provide granular and scalable QoS guaranteed services to be selected by users according to their QoS requirements and e2e situation. Its basic idea is to convert packet delay guarantee into packet loss ratio guarantee with either dropping or marking the packets whose e2e delays are perceived unable to be guaranteed. Packets are queued according to their e2e delay requirements so that various delay bounds can be guaranteed without using sophisticated output schedulers while different packet loss ratios are mainly controlled by call admission control (CAC). To this end, the e2e QoS requirement is carried by each packet to avoid storing such information in network units for scalability. On the other hand, differentiated services should also be accomplished with a differentiated cost model for pricing, not only for the profits of both the service provider and the user, but also to prevent good services from being abused. So, a cost model for differentiated QoS services provided by DQS is also discussed with a possible CAC based on the exponentially bounded burstiness traffic.

REFERENCES

• 1: E.W. Knightly and N.B. Shroff, "Admission control for statistical QoS: theory and practice," IEEE Network Mag., pp. 20--29, Mar./Apr. 1999.
• 2: H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. The IEEE, vol. 83, no. 10, pp. 1374--1396, Oct. 1995.
• 3: V. Jacobson, K. Nichols, and K. Poduri, "An expedited forwarding PHB," IETF RFC 2598, Jun. 1999.
• 4: B. Davie, A. Charny, J.C.R. Bennett, K. Benson, J.Y. Le Boudec, W. Courtney, S. Davari, V. Firoiu, and D. Stiliadis, "An expedited forwarding (PHB) per-hop behavior," IETF RFC 3246, Mar. 2002.
• 5: A. Charny, J.C.R. Bennett, K. Benson, J.Y. Le Boudec, A. Chiu, W. Courtney, S. Davari, V. Firoiu, C. Kalmanek, and K.K. Ramakr-ishnan, "Supplemental information for the new definition of the EF PHB (expedited forwarding per-hop behavior)," IETF RFC 3247, Mar. 2002.
• 6: J. Heinanen, F. Baker, W. Weiss, and J. Wroclawaski, "Assured forwarding PHB group," IETF RFC 2597, Jun. 1999.
• 7: N. Benameur , S. Ben Fredj , S. Oueslati-Boulahia , J. W. Roberts, Quality of service and flow level admission control in the internet, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.1, p.57-71, 16 September 2002 [doi>10.1016/S1389-1286(02)00266-9]
• 8: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 9: S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An architecture for differentiated dervices," IETF RFC 2475, Dec. 1998.
• 10: 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
• 11: Zhi-Li Zhang , Zhenhai Duan , Lixin Gao , Yiwei Thomas Hou, Decoupling QoS control from core routers: a novel bandwidth broker architecture for scalable support of guaranteed services, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.71-83, August 28-September 01, 2000, Stockholm, Sweden
• 12: Y.M. Jiang, "LBFA: a stateless approach to scalable support of end-to-end per-flow service guarantees," in submission of INFOCOM'04, Jul. 2003.
• 13: R. Guérin, S. Kamat, V. Peris, and R. Rajan, "Scalable QoS provision through buffer management," in Proc. ACM SIGCOMM, Vancouver, Canada, Sep. 1998.
• 14: 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
• 15: J. Roberts and S. Oueslati-Boulahia, "Quality of service by flow-aware networking," Phil Trans. R. Soc. Lond, vol. A (2000) 358, no. 1773, pp. 2197--2207, 2000.
• 16: V. Firoiu, X.H. Zhang, and Y. Gao, "Best effort differentiated services: trade-off service differentiation for elastic applications," in Proc. IEEE Int. Conf. Telecom., Zagreb, Croatia, Jun. 2001.
• 17: P. Hurley, K. Mourad, J.Y. Le Boudec, and P. Thiran, "ABE: providing a low-delay service within best effort," IEEE Network Mag., vol. 15, no. 3, pp. 60--69, May 2001.
• 18: Y.N.-E. Liu and W. Wong, "Deadline based channel scheduling," in Proc. IEEE Globecom, San Antonio TX, USA, Nov. 2001, vol. 4, pp. 2358--2362.
• 19: Fundamental Trade-offs in Aggregate Packet Scheduling, Proceedings of the Ninth International Conference on Network Protocols, p.129, November 11-14, 2001
• 20: B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K.K. Ramakrishnan, S. Shenker, J. Wroclawski, and L.X. Zhang, "Rec- ommendations on queue management and congestion avoidance in the Internet," IETF RFC 2309, Apr. 1998.
• 21: Mark Allen Weiss, Data structures and algorithm analysis in C, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 22: Jorg Liebeherr , Dallas E. Wrege, Design and Analysis of a High-Performance Packet Multiplexer for Multiservice Networks with Delay Guarantees, University of Virginia, Charlottesville, VA, 1994
• 23: L. Kleinrock, Queueing Systems, volume II: Computer Applications, John Wiley & Sons, 1975.
• 24: Leonidas Georgiadis , Roch Guérin , Vinod Peris , Kumar N. Sivarajan, Efficient network QoS provisioning based on per node traffic shaping, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.482-501, Aug. 1996 [doi>10.1109/90.532860]
• 25: R. Guérin , V. Peris, Quality-of-service in packet networks: basic mechanisms and directions, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.3, p.169-189, Feb. 11, 1999 [doi>10.1016/S0169-7552(98)00261-X]
• 26: A.W. Berger and W. Whitt, "Extending the effective bandwidth concept to networks with priority classes," IEEE Commun. Mag., vol. 36, no. 8, pp. 78--83, Aug. 1998.
• 27: Arthur W. Berger , Ward Whitt, Effective bandwidths with priorities, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.447-460, Aug. 1998 [doi>10.1109/90.720887]
• 28: A. Elwalid , D. Mitra, Analysis, approximations and admission control of a multi-service multiplexing system with priorities, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 2)-Volume, p.463, April 02-06, 1995
• 29: H.L. Vu and M. Zukerman, "Blocking probability for priorityclasses in optical burst switching networks," IEEE Commun. Let., vol. 6, no. 5, pp. 214--216, May 2002.
• 30: P.B. Key, "Resource pricing for differentiated services," http://research.microsoft.com/~peterkey/Papers/KIVSpbkey.pdf, Feb. 2001.
• 31: P. Marbach, "Pricing differentiated services networks: bursty traffic," in Proc. IEEE INFOCOM, Anchorage Alaska, USA, Apr. 2001, vol. 2, pp. 650--658.
• 32: C.A. Courcoubetis and A. Dimakis, "Providing bandwidth guarantees over a best-effort network: call-admission and pricing," in Proc. IEEE INFOCOM, Anchorage Alaska, USA, Apr. 2001, vol. 1, pp. 459--467.
• 33: D. Mitra, K.G. Ramakrishnan, and Q. Wang, "Combined economic modeling and traffic engineering: joint optimization of pricing and routing in multi-service networks," in Proc. ITC-17, Salvador da Bahia, Brazil, Dec. 2002.
• 34: S. Jordan and H. Jiang, "Connection establishment in high speed networks," IEEE J. Selected Areas Commun., vol. 13, no. 7, pp. 1150--1161, Sep. 1995.
• 35: H. Jiang and S. Jordan, "A pricing model for high speed networks with guaranteed quality of service," in Proc. IEEE INFOCOM, San Fransisco, USA, Mar. 1996, vol. 2, pp. 888--895.
• 36: X. Wang and H. Schulzrinne, "Pricing network resoruce for adaptive applications in a differentiated services network," in Proc. IEEE INFOCOM, Anchorage Alaska, USA, Apr. 2001, vol. 2, pp. 943--952.
• 37: L.A. DaSilva, "Pricing for QoS-enabled networks: a survey," IEEE Commun. Surveys & Tutorials (online), Jan. 2000, DaSilva.pdf.
• 38: Opher Yaron , Moshe Sidi, Performance and stability of communication networks via robust exponential bounds, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.372-385, June 1993 [doi>10.1109/90.234858]
• 39: H. Michiel and K. Laevens, "Teletraffic engineering in a broadband era," Proc. The IEEE, vol. 85, no. 12, pp. 2007--2033, Dec. 1997.
• 40: E. Biton and A. Orda, "QoS provision with EDF scheduling, stochastic burtiness and stochastic guarantees," in Proc. ITC-18, Berlin, Germany, Aug./Sep. 2003, vol. 5b, pp. 1061--1070.
• 41: E. Biton and A. Orda, "QoS provision with EDF scheduling, stochastic burtiness and stochastic guarantees (extented version)," http://comnet.technion.ac.il/~berez/BO03.pdf.
• 42: D. Anick, D. Mitra, and M.M. Sondhi, "Stochastic theory of a data-handling system with multiple sources," Bell Syst. Tech. J., vol. 16, no. 8, pp. 1871--1894, Oct. 1982.

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.2 Network Protocols
          Subjects: Protocol architecture (OSI model)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Algorithms, Performance

Keywords:
differentiated queueing services (DQS), end-to-end QoS, service granularity