article

Free access

Fast simulation of networks of queues with effective and decoupling bandwidths

Editor: David M. Nicol Authors:

Matthias Falkner,

Michael Devetsikiotis,

Ioannis LambadarisAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 9, Issue 1

Pages 45 - 58

https://doi.org/10.1145/301677.301684

Published: 01 January 1999 Publication History

PDF eReader

Abstract

A significant difficulty when using Monte Carlo simulation for the performance analysis of communication networks is the long runtime required to obtain accurate statistical estimates. Under the proper conditions, importance sampling (IS) is a technique that can speed up simulations involving rare events in network (queuing) systems. Large speed-up factors in simulation runtime can be obtained with IS if the modification or bias of the underlying probability measures of certain random processes is carefully chosen. Fast simulation methods based on large deviation theory (LTD) have been successfully applied in many cases.

In this paper, we set up an IS-based simulation of various elementary network topologies. These configurations are frequenly encountered in broadband ATM-based network components such as switches and multiplexers. Our objective in this study is to obtain the optimal or near-optimal biasing parameter values of the arrival processes for the importance sampling simulation. For this purpose we appropriately apply a technique presented by Chang et al. for certain portions of the networks (intree) while we develop a new algorithm, inspired by the work of De Veciana et al. on decoupling bandwidths, for the non-intree portion of the network.

References

[1]

AL-QAQ, W. A., DEVETSIKIOTIS, M., AND TOWNSEND, J. K. 1993. Importance Sampling Methodologies for Simulation of Communication systems with time-varying channels and adaptive equalizers. IEEE J. Sel. Areas Commun. 11, 3 (Apr.), 317-327.

Google Scholar

[2]

CHANG, C.-S., HEIDELBERGER, P., JUNEJA, S., AND SHAHABUDDIN, P. 1994. Effective bandwidth and fast simulation of ATM intree networks. Perform. Eval. 20, 1-3 (May 1994), 45-65.

Crossref

Google Scholar

[3]

CRANE, M. A. AND LEMOINE, A. J. 1977. An Introduction to the Regenerative Method for Simulation Analysis. Springer-Verlag, Vienna, Austria.

Crossref

Google Scholar

[4]

DE VECIANA, G., COURCOUBETIS, C., AND WALRAND, J. 1994. Decoupling bandwidths for networks: A decomposition approach to resource management. In Proceedings of the IEEE Conference on Computer Communication (INFOCOM, Toronto, Ont.). IEEE Computer Society Press, Los Alamitos, CA.

Google Scholar

[5]

DEVETSIKIOTIS, M. AND TOWNSEND, J. K. 1993. Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks. IEEE/ACM Trans. Netw. 1, 3 (June 1993), 293-305.

Crossref

Google Scholar

[6]

GLYNN, P W. AND IGLEHART, D. L. 1989. Importance sampling for stochastic simulations. Manage. Sci. 35, 11 (Nov. 1989), 1367-1392.

Crossref

Google Scholar

[7]

GOYAL, A., SHAHABUDDIN, P., HEIDELBERGER, P., NICOLA, V. F., AND GLYNN, P.W. 1992. A unified framework for simulating Markovian models of highly dependable systems. IEEE Trans. Comput. 41, 1 (Jan. 1992), 36-51.

Crossref

Google Scholar

[8]

HEIDELBERGER, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul. 5, 1 (Jan. 1995), 43-85.

Crossref

Google Scholar

[9]

KESIDIS, G., WALRAND, J., AND CHANG, C.-S. 1993. Effective bandwidths for multiclass Markov fluids and other ATM sources. IEEE/ACM Trans. Netw. 1, 4 (Aug. 1993), 424-428.

Crossref

Google Scholar

[10]

L'ECUYER, P. AND CHAMPOUX, Y. 1996. Importance sampling for large ATM-type queueing networks. In Proceedings of the 1996 Winter Simulation Conference. ACM Press, New York, NY.

Crossref

Google Scholar

[11]

PAREKH, S. AND WALRAND, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Automat. Contr. AC-34, 1, 54-66.

Google Scholar

[12]

SADOWSKY, g. S. AND BUCKLEW, g.A. 1990. On large deviation theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theor. IT-36, 3 (May), 579-588.

Google Scholar

[13]

WANG, Q. AND FROST, V. S. 1993. Efficient estimation of cell blocking probability for ATM systems. IEEE/ACM Trans. Netw. 1, 2 (Apr. 1993), 230-235.

Crossref

Google Scholar

Cited By

View all

Kuznetsov IShumska A(2024)APPLYING FAST SIMULATION TO THE EVALUATION OF CUSTOMERS BLOCKING PROBABILITY IN THE MULTICHANNEL QUEUING SYSTEM WITH MULTICAST ACCESSKIBERNETYKA TA SYSTEMNYI ANALIZ10.34229/KCA2522-9664.24.2.5(51-63)Online publication date: 2024
https://doi.org/10.34229/KCA2522-9664.24.2.5
Kuznetsov IShumska A(2024)Applying Fast Simulation to the Evaluation of Customer Blocking Probability in the Multichannel Queuing System with Multicast AccessCybernetics and Systems Analysis10.1007/s10559-024-00662-x60:2(209-219)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10559-024-00662-x
Kuznetsov MKuznetsov IShumska A(2022)Comparative Analysis of Two Modified Fast Simulation Methods for Evaluation of the Failure Probability of a Rank Structure SystemCybernetics and Systems Analysis10.1007/s10559-022-00502-w58:5(691-701)Online publication date: 1-Dec-2022
https://doi.org/10.1007/s10559-022-00502-w
Show More Cited By

Index Terms

Fast simulation of networks of queues with effective and decoupling bandwidths

Recommendations

Fast simulation of a voice-data multiplexer
INFOCOM '95: Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume - Volume 1

This paper considers the problem of estimating, via simulation, extremely low packet loss rates in a voice-data multiplexer. The multiplexer gives priority to voice packets, unless the data queue length exceeds a threshold. To efficiently simulate such ...
Analysis of an importance sampling estimator for tandem queues

We analyze the performance of an importance sampling estimator for a rare-event probability in tandem Jackson networks. The rare event we consider corresponds to the network population reaching K before returning to ø, starting from ø, with K large. The ...
Importance sampling in rate-sharing networks
Simutools '08: Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops

We consider a network supporting elastic traffic, where the service capacity is shared among the various classes according to an alpha-fair sharing policy. Assuming Poisson arrivals and exponentially distributed service requirements for each class, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 9, Issue 1

Jan. 1999

80 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/301677

Editor:
David M. Nicol
Dartmouth College, Hanover, NH

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1999

Published in TOMACS Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
446
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)14

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kuznetsov IShumska A(2024)APPLYING FAST SIMULATION TO THE EVALUATION OF CUSTOMERS BLOCKING PROBABILITY IN THE MULTICHANNEL QUEUING SYSTEM WITH MULTICAST ACCESSKIBERNETYKA TA SYSTEMNYI ANALIZ10.34229/KCA2522-9664.24.2.5(51-63)Online publication date: 2024
https://doi.org/10.34229/KCA2522-9664.24.2.5
Kuznetsov IShumska A(2024)Applying Fast Simulation to the Evaluation of Customer Blocking Probability in the Multichannel Queuing System with Multicast AccessCybernetics and Systems Analysis10.1007/s10559-024-00662-x60:2(209-219)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10559-024-00662-x
Kuznetsov MKuznetsov IShumska A(2022)Comparative Analysis of Two Modified Fast Simulation Methods for Evaluation of the Failure Probability of a Rank Structure SystemCybernetics and Systems Analysis10.1007/s10559-022-00502-w58:5(691-701)Online publication date: 1-Dec-2022
https://doi.org/10.1007/s10559-022-00502-w
Kuznetsov NKuznetsov I(2021)Fast Simulation of the Customer Blocking Probability in Queueing Networks with Multicast AccessCybernetics and Systems Analysis10.1007/s10559-021-00378-2Online publication date: 24-Jul-2021
https://doi.org/10.1007/s10559-021-00378-2
Feng BHuang CDevetsikiotis M(2009)FISTEACM Transactions on Modeling and Computer Simulation10.1145/1596519.159652119:4(1-39)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1596519.1596521
Giordano SPagano MTartarelli S(2008)An importance sampling algorithm for the simulation of a GPS schedulerEuropean Transactions on Telecommunications10.1002/ett.446013040713:4(351-361)Online publication date: 12-Sep-2008
https://doi.org/10.1002/ett.4460130407
Hsu CDevetsikiotis M(2007)An adaptive approach to accelerated evaluation of highly available servicesACM Transactions on Modeling and Computer Simulation10.1145/1315575.131557618:1(1-26)Online publication date: 12-Dec-2007
https://dl.acm.org/doi/10.1145/1315575.1315576
Hsu CDevetsikiotis M(2004)An adaptive approach to fast simulation of traffic groomed optical networksProceedings of the 36th conference on Winter simulation10.5555/1161734.1161847(612-620)Online publication date: 5-Dec-2004
https://dl.acm.org/doi/10.5555/1161734.1161847
Chih-Chieh Hsu Devetsikiotis M(2004)An Adaptive Approach to Fast Simulation of Traffic Groomed Optical NetworksProceedings of the 2004 Winter Simulation Conference, 2004.10.1109/WSC.2004.1371368(600-608)Online publication date: 2004
https://doi.org/10.1109/WSC.2004.1371368
Andrew L(2004)Fast simulation of wavelength continuous WDM networksIEEE/ACM Transactions on Networking10.1109/TNET.2004.83315912:4(759-765)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1109/TNET.2004.833159
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Fast simulation of a voice-data multiplexer

Analysis of an importance sampling estimator for tandem queues

Importance sampling in rate-sharing networks

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations