article

Large deviation analysis for multiplexing independent regulated inputs

Authors:

Cheng-Shang Chang,

Yuh-ming Chiu,

Wheyming Tina SongAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 28, Issue 4

Pages 19 - 21

https://doi.org/10.1145/544397.544405

Published: 01 March 2001 Publication History

Get Access

Abstract

In this paper, we consider the performance analysis problem for a work conserving link with a large number of independent regulated inputs. For such a problem, we derive simple stochastic bounds under a general traffic constraint for the inputs. The bound for queue length is shown to be a stochastic extension of the deterministic worst case bound and it is asymptotically tighter than the bound in Kesidis and Konstantopoulos [5]. We also test the bound by considering periodic inputs with independent starting phases. Based on importance sampling, we propose a fast simulation algorithm that achieves significant variance reduction. The simulations results are compared with our stochastic bound and the bound [5].

References

[1]

R. Boorstyn, A. Burchard, J. Liebeherr, and C. Oottamakorn, "Effective Envelopes: Statistical Bounds on Multiplexed Traffic in Packet Networks," Proc. IEEE INFOCOM 2000, Vol. 3, pp. 1223-1232, Tel Aviv, Israel, 2000.

Crossref

Google Scholar

[2]

D. D. Botvich and N. G. Duffield, "Large deviations, the shape of the loss curve, and economies of scale in large multiplexers," Queueing Systems, Vol. 20, pp. 293-320, 1995.

Crossref

Google Scholar

[3]

C. Courcoubetis, F. Kelly and R. Weber, "Measurement-based usage charges in communication networks," preprint, 1998. Available from http://www.statslab.cam.ac.uk/~frank.

Google Scholar

[4]

R. L. Cruz, "A calculus for network delay, Part I: Network elements in isolation," IEEE Trans. Inform. Theory, vol. 37, pp. 114-131, 1991.

Digital Library

Google Scholar

[5]

G. Kesidis and T. Konstantopoulos, "Worst-case performance of a buffer with independent shaped arrival processes," to appear in IEEE Communications Letters. Available from http://cheetah.vlsi.uwaterloo.ca.

Google Scholar

[6]

G. Kesidis and T. Konstantopoulos, "Extremal traffic and worst-case performance for queues with shaped arrivals," to appear in Fields Institute Communications. Available from http://cheetah.vlsi.uwaterloo.ca.

Google Scholar

[7]

E. Knightly, "Enforceable quality of service guarantees for bursty traffic streams," Proc. of IEEE INFOCOM'98, pp. 635-642, San Francisco, March, 1998.

Google Scholar

Index Terms

Large deviation analysis for multiplexing independent regulated inputs
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance

Index terms have been assigned to the content through auto-classification.

Recommendations

On the performance of multiplexing independent regulated inputs
SIGMETRICS '01: Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

In this paper, we consider the performance analysis problem for a work conserving link with a large number of independent regulated inputs. For such a problem, we derive simple stochastic bounds under a general traffic constraint for the inputs. The ...
On the performance of multiplexing independent regulated inputs

In this paper, we consider the performance analysis problem for a work conserving link with a large number of independent regulated inputs. For such a problem, we derive simple stochastic bounds under a general traffic constraint for the inputs. The ...
A Large Deviation Inequality for Functions of Independent, Multi-Way Choices

Often when analysing randomized algorithms, especially parallel or distributed algorithms, one is called upon to show that some function of many independent choices is tightly concentrated about its expected value. For example, the algorithm might ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 28, Issue 4

March 2001

42 pages

ISSN:0163-5999

DOI:10.1145/544397

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2001

Published in SIGMETRICS Volume 28, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
202
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

View Options

Get Access

Login options

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

Index Terms

Recommendations

On the performance of multiplexing independent regulated inputs

On the performance of multiplexing independent regulated inputs

A Large Deviation Inequality for Functions of Independent, Multi-Way Choices

Comments

Published In

Publisher

Publication History

Check for updates

Qualifiers

Other Metrics

Article Metrics

Other Metrics

Login options

Full Access

PDF

eReader

Abstract

References

Index Terms

Recommendations

On the performance of multiplexing independent regulated inputs

On the performance of multiplexing independent regulated inputs

A Large Deviation Inequality for Functions of Independent, Multi-Way Choices

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations