More Web Proxy on the site http://driver.im/

Article

Probabilistic delay guarantees using delay distribution measurement

Authors:

Kartik Gopalan,

Tzi-cker Chiueh,

Yow-Jian LinAuthors Info & Claims

MULTIMEDIA '04: Proceedings of the 12th annual ACM international conference on Multimedia

Pages 900 - 907

https://doi.org/10.1145/1027527.1027734

Published: 10 October 2004 Publication History

Abstract

Carriers increasingly differentiate their wide-area connectivity offerings by means of customized services, such as virtual private networks (VPN) with Quality of Service (QoS) guarantees, or QVPNs. The key challenge faced by carriers is to maximize the number of QVPNs admitted by exploiting the statistical multiplexing nature of input traffic. While existing measurement-based admission control algorithms utilize statistical multiplexing along the bandwidth dimension, they do not satisfactorily exploit statistical multiplexing along the <i>delay dimension</i> to guarantee <i>distinct per-QVPN delay bounds</i>. This paper 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 packets of a QVPN is usually far smaller than its worst-case delay bound requirement since multiple QVPNs rarely send traffic bursts at the same time. Additionally, DDM supports QVPNs with distinct probabilistic delay guarantees -- QVPNs that can tolerate more delay violations can reserve fewer resource than those that tolerate less, even though they require the same delay bound. A comprehensive performance evaluation using Voice over IP traces shows that, when compared to deterministic admission control, DDM can potentially increase the number of admitted QVPNs (and link utilization) by up to a factor of 3.0 even when the delay violation probability is as small as 10<sup>-5</sup>.

References

[1]

M. Andrews. Probabilistic end-to-end delay bounds for earliest deadline first scheduling. In Proc. of IEEE INFOCOM 2000, March 2000.

[2]

R. Boorstyn, A. Burchard, J. Leibeherr, and C. Oottamakorn. Statistical service assurances for traffic scheduling algorithms. IEEE Journal on Selected Areas in Communications, 18(13):2651--2664, December 2000.

Digital Library

[3]

L. Breslau, S. Jamin, and S. Shenker. Comments on performance of measurement-based admission control algorithms. In Proc. of IEEE INFOCOM 2000, March 2000.

[4]

C-S. Chang, Y. Chiu, and W. Song. On the performance of multiplexing independent regulated inputs. In ACM Sigmetrics 2001/Performance 2001, pages 184--193, 2001.

Digital Library

[5]

S. Crosby, I. Leslie, B. McGurk, J. Lewis, R. Russell, and F. Toomey. Statistical properties of a near-optimal measurement-based admission CAC algorithm. In Proc. of IEEE ATM'97, June 1997.

[6]

R. Cruz. A calculus for network delay, Part I: Network elements in isolation. IEEE Transactions on Information Theory, 37(1):114--131, Jan. 1991.

Digital Library

[7]

A. Elwalid and D. Mitra. Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes. In Proc. of IEEE INFOCOM'99, pages 1220--1230, March 1999.

[8]

S. Floyd. Comments on measurement-based admission control for controlled load services. Technical Report, Lawrence Berkeley Laboratory, July 1996.

[9]

R. Gibbens and F. Kelly. Measurement-based connection admission control. In Proc. of 15th Intl. Teletraffic Conference, June 1997.

[10]

K. Gopalan, T. Chiueh, and Y. Lin. Delay budget partitioning to maximize network resource usage efficiency. Proc. of IEEE INFOCOM 2004, Hong Kong, China, March 2004.

[11]

F. M. Guillemin, N. Likhanov, R. R. Mazumdar, and C. Rosenberg. Extremal traffic and bounds for the mean delay of multiplexed regulated traffic streams. In Proc. of IEEE INFOCOM'02, New York, NY, June 2002.

[12]

S. Jamin, P. Danzig, S. Shenker, and L. Zhang. A measurement-based admission control algorithm for integrated services packet networks. IEEE/ACM Transactions on Networking, 5(1):56--70, Feb. 1997.

Digital Library

[13]

W. Jiang and H. Schulzrinne. Analysis of On-Off patterns in VoIP and their effect on voice traffic aggregation. In Proc. of ICCCN 2000, March 1996.

[14]

F. Kelly. Notes on effective bandwidths. In Stochastic Networks: Theory and Applications, 4:141--168, 1996.

[15]

G. Kesidis and T. Konstantopoulos. Worst-case performance of a buffer with independent shaped arrival processes. IEEE Communication Letters, 4(1):26--28, Jan. 2000.

[16]

E. Knightly and N. B. Shroff. Admission control for statistical QoS. IEEE Network, 13(2):20--29, March 1999.

Digital Library

[17]

J. Kurose. On computing per-session performance bounds in high-speed multi-hop computer networks. In Proc. of ACM Sigmetrics'92, pages 128--139, 1992.

Digital Library

[18]

J.-Y. L. Boudec and M. Vojnovic. Stochastic analysis of some expedited forwarding networks. In IEEE Infocom'02, New York, NY, June 2002.

[19]

A. Parekh and R. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Transactions on Networking, 1(3):344--357, June 1993.

Digital Library

[20]

J. Qiu and E. Knightly. Measurement-based admission control with aggregate traffic envelopes. IEEE/ACM Transactions on Networking, 9(2):199--210, April 2001.

Digital Library

[21]

M. Reisslein, K. Ross, and S. Rajagopal. A framework for guaranteeing statistical QoS. IEEE/ACM Transactions on Networking, 10(1):27--42, February 2002.

Digital Library

[22]

V. Sivaraman and F. Chiussi. Providing end-to-end statistical delay guarantees with earliest deadline first scheduling and per-hop traffic shaping. In Proc. of IEEE INFOCOM 2000, March 2000.

[23]

B. Urgaonkar, P. Shenoy, and T. Roscoe. Resource overbooking and application profiling in shared hosting platforms. In Proc. of Symposium on Operating Systems Design and Implementation, Boston, MA, Dec. 2002.

Digital Library

[24]

M. Vojnovic and J. Le Boudec. Bounds for independent regulated inputs multiplexed in a service curve network element. IEEE Transactions on Communications, 51(5), Jan. 1991.

Cited By

Raayatpanah MSalehi Fathabadi HKhalaj BKhodayifar SPardalos P(2014)Bounds on end-to-end statistical delay and jitter in multiple multicast coded packet networksJournal of Network and Computer Applications10.1016/j.jnca.2013.12.00441(217-227)Online publication date: May-2014
https://doi.org/10.1016/j.jnca.2013.12.004
Wang YVuran MGoddard S(2012)Cross-Layer Analysis of the End-to-End Delay Distribution in Wireless Sensor NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2011.215984520:1(305-318)Online publication date: Feb-2012
https://doi.org/10.1109/TNET.2011.2159845
Bjurling BSteinert RGillblad D(2011)Translation of probabilistic QoS in hierarchical and decentralized settings2011 13th Asia-Pacific Network Operations and Management Symposium10.1109/APNOMS.2011.6077035(1-8)Online publication date: Sep-2011
https://doi.org/10.1109/APNOMS.2011.6077035
Show More Cited By

Index Terms

Probabilistic delay guarantees using delay distribution measurement
1. Networks
  1. Network architectures

Recommendations

Dynamic resizing of utilization target in measurement-based admission control

A major issue in design of measurement-based admission control (MBAC) algorithms relies on how to maximize link utilization while meeting applications' QoS constraints. Studies have claimed that many proposed MBAC algorithms would give the same ...
An admission control scheme for end-to-end statistical QoS provision in IP networks
Abstract
This paper presents a distributed and scalable admission control scheme to provide end-to-end statistical QoS guarantees in IP network. The basic idea of the scheme is that the ingress routers make admission control decisions according to the ...
Incremental provision of QoS guarantees using only available QoS-aware routers
LANC '07: Proceedings of the 4th international IFIP/ACM Latin American conference on Networking

Most proposals related to QoS provision on the Internet share a common requirement to be deployed: every router within every Autonomous System of the Internet needs to be upgraded to support specific procedures for QoS provision. The main aim of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MULTIMEDIA '04: Proceedings of the 12th annual ACM international conference on Multimedia

October 2004

1028 pages

ISBN:1581138938

DOI:10.1145/1027527

General Chairs:
Henning Schulzrinne
Columbia University
,
Nevenka Dimitrova
Philips Research
,
Program Chairs:
Angela Sasse
UCL
,
Sue Moon
KAIST
,
Rainer Lienhart
U Augsburg

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MM04

Sponsor:

MM04: 2004 12th Annual ACM International Conference on Multimedia

October 10 - 16, 2004

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 2,145 of 8,556 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
410
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Raayatpanah MSalehi Fathabadi HKhalaj BKhodayifar SPardalos P(2014)Bounds on end-to-end statistical delay and jitter in multiple multicast coded packet networksJournal of Network and Computer Applications10.1016/j.jnca.2013.12.00441(217-227)Online publication date: May-2014
https://doi.org/10.1016/j.jnca.2013.12.004
Wang YVuran MGoddard S(2012)Cross-Layer Analysis of the End-to-End Delay Distribution in Wireless Sensor NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2011.215984520:1(305-318)Online publication date: Feb-2012
https://doi.org/10.1109/TNET.2011.2159845
Bjurling BSteinert RGillblad D(2011)Translation of probabilistic QoS in hierarchical and decentralized settings2011 13th Asia-Pacific Network Operations and Management Symposium10.1109/APNOMS.2011.6077035(1-8)Online publication date: Sep-2011
https://doi.org/10.1109/APNOMS.2011.6077035
Plentz PMontez Cde Oliveira R(2011)AS prediction mechanism for distributed threads systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2011.05.00271:10(1367-1376)Online publication date: Oct-2011
https://doi.org/10.1016/j.jpdc.2011.05.002
Wang YVuran MGoddard S(2009)Cross-Layer Analysis of the End-to-End Delay Distribution in Wireless Sensor NetworksProceedings of the 2009 30th IEEE Real-Time Systems Symposium10.1109/RTSS.2009.27(138-147)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/RTSS.2009.27
Harhira HPierre S(2008)Joint routing and admission control problem under statistical delay and jitter constraints in MPLS networksComputer Communications10.1016/j.comcom.2008.07.00231:15(3700-3706)Online publication date: 20-Sep-2008
https://dl.acm.org/doi/10.1016/j.comcom.2008.07.002
Kitatsuji YTsuru MTakine TOie Y(2008)Flow assignment method with traffic characteristics over multiple paths for reducing queuing delayTelecommunications Systems10.1007/s11235-008-9071-737:1-3(97-108)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.1007/s11235-008-9071-7
Bohnert TMonteiro EKoucheryavy YMoltchanov D(2007)Non-parametric and self-tuning measurement-based admission controlProceedings of the 6th international IFIP-TC6 conference on Ad Hoc and sensor networks, wireless networks, next generation internet10.5555/1772322.1772394(664-677)Online publication date: 14-May-2007
https://dl.acm.org/doi/10.5555/1772322.1772394
Gopalan KChiueh TLin Y(2007)Slack allocation techniques for intra-path load balancingJournal of High Speed Networks10.5555/1374545.137454616:3(211-237)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.5555/1374545.1374546
Harhira HPierre SPazzi ROuld-Khaoua MCaminero B(2007)Multi-path dynamic admission control in mpls networks with end-to-end delay guaranteesProceedings of the 2nd ACM workshop on Performance monitoring and measurement of heterogeneous wireless and wired networks10.1145/1298275.1298284(45-49)Online publication date: 22-Oct-2007
https://dl.acm.org/doi/10.1145/1298275.1298284
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents