skip to main content
article

Statistical admission control using delay distribution measurements

Published: 01 November 2006 Publication History

Abstract

Growth of performance sensitive applications, such as voice and multimedia, has led to widespread adoption of resource virtualization by a variety of service providers (xSPs). For instance, Internet Service Providers (ISPs) increasingly differentiate their offerings by means of customized services, such as virtual private networks (VPN) with Quality of Service (QoS) guarantees or QVPNs. Similarly Storage Service Providers (SSPs) use storage area networks (SAN)/network attached storage (NAS) technology to provision virtual disks with QoS guarantees or QVDs. The key challenge faced by these xSPs is to maximize the number of virtual resource units they can support by exploiting the statistical multiplexing nature of the customers' input request load.While a number of measurement-based admission control algorithms utilize statistical multiplexing along the bandwidth dimension, they do not satisfactorily exploit statistical multiplexing along the delay dimension to guarantee distinct per-virtual-unit delay bounds. This article presents Delay Distribution Measurement (DDM) based admission control algorithm, the first measurement-based approach that effectively exploits statistical multiplexing along the delay dimension. In other words, DDM exploits the well-known fact that the actual delay experienced by most service requests (packets or disk I/O requests) for a virtual unit is usually far smaller than its worst-case delay bound requirement because multiple virtual units rarely send request bursts at the same time. Additionally, DDM supports virtual units with distinct probabilistic delay guarantees---virtual units that can tolerate more delay violations can reserve fewer resources than those that tolerate less, even though they require the same delay bound. Comprehensive trace-driven performance evaluation of QVPNs (using Voice over IP traces) and QVDs (using video stream, TPC-C, and Web search I/O traces) shows that, when compared to deterministic admission control, DDM can potentially increase the number of admitted virtual units (and resource utilization) by up to a factor of 3.

References

[1]
Andrews, M. 2000. Probabilistic end-to-end delay bounds for earliest deadline first scheduling. In Proceedings of IEEE INFOCOM (March).
[2]
Boorstyn, R., Burchard, A., Leibeherr, J., and Oottamakorn, C. 2000. Statistical service assurances for traffic scheduling algorithms. IEEE J. Select. Areas Comm. 18, 13, 2651--2664.
[3]
Boudec, J.-Y. L. and Vojnovic, M. 2002. Stochastic analysis of some expedited forwarding networks. In IEEE Infocom (June).
[4]
Breslau, L., Jamin, S., and Shenker, S. 2000. Comments on performance of measurement-based admission control algorithms. In Proceedings of IEEE INFOCOM (March).
[5]
C-S. Chang, Chiu, Y., and Song, W. 2001. On the performance of multiplexing independent regulated inputs. In ACM Sigmetrics 2001/Performance 2001. 184--193.
[6]
Crosby, S., Leslie, I., McGurk, B., Lewis, J., Russell, R., and Toomey, F. June 1997. Statistical properties of a near-optimal measurement-based admission CAC algorithm. In Proceedings of IEEE ATM.
[7]
Cruz, R. 1991. A calculus for network delay, Part I: Network elements in isolation. IEEE Trans. Inform. Theory 37, 1, 114--131.
[8]
Elwalid, A. and Mitra, D. 1999. Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes. In Proceedings of IEEE INFOCOM (March). 1220--1230.
[9]
Floyd, S. 1996. Comments on measurement-based admission control for controlled load services. Tech. rep., Lawrence Berkeley Laboratory (July).
[10]
Gibbens, R. and Kelly, F. 1997. Measurement-based connection admission control. In Proceedings of 15th International Teletraffic Conference (June).
[11]
Gopalan, K. and Chiueh, T. 2001. Real-time disk scheduling using deadline sensitive scan. Tech. rep. ECSL-TR-92, Experimental Computer Systems Lab, Stony Brook University.
[12]
Gopalan, K., Chiueh, T., and Lin, Y. 2004. Probabilistic delay guarantees using delay distribution measurements. In Proceedings of ACM Multimedia, New York, NY.
[13]
Guillemin, F. M., Likhanov, N., Mazumdar, R. R., and Rosenberg, C. 2002. Extremal traffic and bounds for the mean delay of multiplexed regulated traffic streams. In Proceedings of IEEE INFOCOM, New York, NY. (June).
[14]
Huang, L., Peng, G., and Chiueh, T. 2004. Multi-dimensional storage virtualization. In Proceedings of ACM Sigmetrics/Performance, New York, NY.
[15]
Jamin, S., Danzig, P., Shenker, S., and Zhang, L. 1997. A measurement-based admission control algorithm for integrated services packet networks. IEEE/ACM Trans. Network. 5, 1, 56--70.
[16]
Jiang, W. and Schulzrinne, H. 1996. Analysis of On-Off patterns in VoIP and their effect on voice traffic aggregation. In Proceedings of ICCCN (March).
[17]
Kelly, F. 1996. Notes on effective bandwidths. In Stochastic Networks: Theory and Applications 4, 141--168.
[18]
Kesidis, G. and Konstantopoulos, T. 2000. Worst-case performance of a buffer with independent shaped arrival processes. IEEE Comm. Lett. 4, 1, 26--28.
[19]
Knightly, E. and Shroff, N. B. 1999. Admission control for statistical QoS. IEEE Network 13, 2, 20--29.
[20]
Kurose, J. 1992. On computing per-session performance bounds in high-speed multi-hop computer networks. In Proceedings of ACM Sigmetrics. 128--139.
[21]
Lumb, C. R., Merchant, A., and Alvarez, G. A. 2003. Façade: Virtual storage devices with performance guarantees. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies, San Francisco, CA.
[22]
Parekh, A. and Gallager, R. 1993. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Trans. Network. 1, 3, 344--357.
[23]
Qiu, J. and Knightly, E. 2001. Measurement-based admission control with aggregate traffic envelopes. IEEE/ACM Trans. Network. 9, 2, 199--210.
[24]
Reisslein, M., Ross, K., and Rajagopal, S. 2002. A framework for guaranteeing statistical QoS. IEEE/ACM Trans. Network. 10, 1, 27--42.
[25]
Sivaraman, V. and Chiussi, F. 2000. Providing end-to-end statistical delay guarantees with earliest deadline first scheduling and per-hop traffic shaping. In Proceedings of IEEE INFOCOM (March).
[26]
Urgaonkar, B., Shenoy, P., and Roscoe, T. 2002. Resource overbooking and application profiling in shared hosting platforms. In Proceedings of Symposium on Operating Systems Design and Implementation (Dec.) Boston, MA.
[27]
Vernick, M., Venkatramani, C., and Chiueh, T. 1996. Adventures in building the stony brook video server. In Proceedings of ACM Multimedia.
[28]
Vin, H. M., Goyal, P., and Goyal, A. 1994. A statistical admission control algorithm for multimedia servers. In Proceedings of ACM Multimedia.
[29]
Wang, Y. and Zhu, Q. 1998. Error control and concealment for video communication: A review. Proceedings of IEEE 86, 5, 974--997.
[30]
Zhang, L. 1991. Virtual Clock: A new traffic control algorithm for packet-switched networks. ACM Trans. Comput. Syst. 9, 2, 101--124.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Multimedia Computing, Communications, and Applications
ACM Transactions on Multimedia Computing, Communications, and Applications  Volume 2, Issue 4
November 2006
148 pages
ISSN:1551-6857
EISSN:1551-6865
DOI:10.1145/1201730
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2006
Published in TOMM Volume 2, Issue 4

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Admission control algorithm for visible light communication random access network under delay and jitter constraintsThe Computer Journal10.1093/comjnl/bxae125Online publication date: 7-Dec-2024
  • (2022)Service Function Chaining in MEC: A Mean-Field Game and Reinforcement Learning ApproachIEEE Systems Journal10.1109/JSYST.2022.317123216:4(5357-5368)Online publication date: Dec-2022
  • (2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
  • (2022)Disk drive data placement and schedulingStorage Systems10.1016/B978-0-32-390796-5.00012-7(197-222)Online publication date: 2022
  • (2020)A scalable system for the monitoring of video transmission components in delay-sensitive networked applicationsMultimedia Tools and Applications10.1007/s11042-020-08743-779:25-26(18727-18745)Online publication date: 11-Mar-2020
  • (2013)Combining quality of services path first routing and admission control to support VoIP trafficFuture Generation Computer Systems10.1016/j.future.2012.03.02629:7(1742-1750)Online publication date: 1-Sep-2013
  • (2011)On Achieving Robustness and Fairness in Call Admission Control for Voice Services within NGN EnvironmentProceedings of the 2011 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery10.1109/CyberC.2011.25(96-99)Online publication date: 10-Oct-2011
  • (2010)Support for enterprise consolidation of I/O bound servicesSoftware: Practice and Experience10.1002/spe.99040:12(1035-1051)Online publication date: 2-Nov-2010
  • (2009)A new VoIP call admission control based on blocking probability calculation2009 Fourth International Conference on Communications and Networking in China10.1109/CHINACOM.2009.5339917(1-6)Online publication date: Aug-2009
  • (2009)Incremental PID-like algorithm based trust model in peer-to-peer networks2009 Fourth International Conference on Communications and Networking in China10.1109/CHINACOM.2009.5339708(1-5)Online publication date: Aug-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media