skip to main content
10.1145/1190095.1190168acmotherconferencesArticle/Chapter ViewAbstractPublication PagesvaluetoolsConference Proceedingsconference-collections
Article

Insensitive queueing models for communication networks

Published: 11 October 2006 Publication History

Abstract

A rich class of communication networks can be represented as queueing networks with state-dependent arrival rates and service rates. We provide necessary and sufficient conditions for such queueing networks to be insensitive in the sense that the steady-state distribution depends on the service time distribution at each queue through the mean only. This insensitivity property is key to the development of simple engineering rules that do not require the knowledge of fine traffic statistics.

References

[1]
F. Baskett, K. M. Chandy, R. R. Muntz and F. G. Palacios, Open, closed and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22 (1975) 248--260.
[2]
S. Ben Fredj, T. Bonald, A. Proutière, G. Régnié and J. W. Roberts, Statistical bandwidth sharing: A study of congestion at flow level. In Proc. ACM SIGCOMM, 2001.
[3]
A. W. Berger, Y. Kogan, Dimensioning bandwidth for elastic traffic in high-speed data networks. IEEE/ACM Trans. on Networking 8, 5 (2000) 643--654.
[4]
T. Bonald, The Erlang model with non-Poisson call arrivals. In: Proc. ACM Sigmetrics / IFIP Performance, 2006.
[5]
T. Bonald, M. Jonckheere, A. Proutière, Insensitive load balancing. In: Proc. ACM Sigmetrics / IFIP Performance, 2004.
[6]
T. Bonald and A. Proutière, Insensitivity in processor-sharing networks. Performance Evaluation 49 (2002) 193--209.
[7]
T. Bonald and A. Proutière, Insensitive bandwidth sharing in data networks. Queueing Systems 44, 1 (2003) 69--100.
[8]
R. Boucherie and N. van Dijk, Product forms for queueing networks with state dependent multiple job transitions. Adv. App. Prob. 23 (1991) 152--187.
[9]
J. W. Cohen, The Generalized Engset Formula. Phillips Telecommunications Review 18 (1957) 158--170.
[10]
T. O. Engset, On the calculation of switches in an automatic telephone system. In Tore Olaus Engset: The man behind the formula, Eds: A. Myskja, O. Espvik, 1998. First appeared as an unpublished report in Norwegian, 1915.
[11]
O. Enomoto, H. Miyamoto, An Analysis of mixtures of multiple bandwidth traffic on time division switching networks. In Proc. of the 7th International Teletraffic Congress, 1973.
[12]
A. K. Erlang, Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges. In: The life and works of A. K. Erlang, Eds: E. Brockmeyer, H. L. Halstrom, A. Jensen, 1948. First published in Danish, 1917.
[13]
E. Gelenbe, Queuing networks with negative and positive customers. J. App. Prob. 28 (1991) 656--663.
[14]
L. A. Gimpelson, Analysis of mixtures of wide and narrow-band traffic. IEEE Trans. Comm. Technology 13, 3 (1965) 258--266.
[15]
D. P. Heyman, T. V. Lakshman, A. L. Neidhardt, A new method for analysing feedback-based protocols with applications to engineering Web traffic over the Internet. In Proc. ACM SIGMETRICS, 1997.
[16]
A. Hordijk and N. van Dijk, Adjoint processes, job local balance and insensitivity of stochastic networks. Bull:44 session Int. Stat. Inst. 50 (1982) 776--788.
[17]
J. R. Jackson, Networks of waiting lines. Operat. Res. 5 (1957) 518--521.
[18]
J. S. Kaufman, Blocking in a shared resource environment. IEEE Trans. Commun. 29 (1981) 1474--1481.
[19]
F. P. Kelly, Reversibility and Stochastic Networks, Wiley, 1979.
[20]
F. P. Kelly, Loss networks. Annals of Applied Probability 1 (1991) 319--378.
[21]
L. Massoulié and J. W. Roberts, Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15 (2000) 185--201.
[22]
J. W. Roberts, A service system with heterogeneous user requirement. In Performance of Data Communications Systems and Their Applications, G. Pujolle, Ed. Amsterdam, The Netherlands: North-Holland, 1981, pp. 423--431.
[23]
R. Schassberger, Insensitivity of steady state distributions of generalized semi-Markov processes with speeds. Advances in Applied Probability 10 (1978) 836--851.
[24]
R. Schassberger, The insensitivity of stationary distributions in networks of queues. Advances in Applied Probability 10 (1978) 906--912.
[25]
R. Schassberger, Two remarks on insensitive stochastic models. Advances in Applied Probability 18 (1986) 791--814.
[26]
R. F. Serfozo, Introduction to Stochastic Networks, Springer Verlag, 1999.
[27]
B. A. Sevastyanov, An ergodic theorem for Markov processes and its application to telephone systems with refusals. Theor. Probability Appl. 2 (1957) 104--112.
[28]
P. Whittle, Partial balance and insensitivity. Journal of Applied Probability 22 (1985) 168--176.

Cited By

View all
  • (2024)Queueing Systems With Fractional Number of Servers: Analysis and Practical Implementation of the Erlang-B Traffic ModelIEEE Access10.1109/ACCESS.2024.349163712(166268-166280)Online publication date: 2024
  • (2022)Designing optimal allocations for cancer screening using queuing network modelsPLOS Computational Biology10.1371/journal.pcbi.101017918:5(e1010179)Online publication date: 27-May-2022
  • (2019)Approximate Counting, the Lovász Local Lemma, and Inference in Graphical ModelsJournal of the ACM10.1145/326893066:2(1-25)Online publication date: 5-Apr-2019
  • Show More Cited By

Index Terms

  1. Insensitive queueing models for communication networks

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools
    October 2006
    638 pages
    ISBN:1595935045
    DOI:10.1145/1190095
    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]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 October 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. communication networks
    2. insensitivity
    3. partial reversibility

    Qualifiers

    • Article

    Acceptance Rates

    Overall Acceptance Rate 90 of 196 submissions, 46%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 07 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Queueing Systems With Fractional Number of Servers: Analysis and Practical Implementation of the Erlang-B Traffic ModelIEEE Access10.1109/ACCESS.2024.349163712(166268-166280)Online publication date: 2024
    • (2022)Designing optimal allocations for cancer screening using queuing network modelsPLOS Computational Biology10.1371/journal.pcbi.101017918:5(e1010179)Online publication date: 27-May-2022
    • (2019)Approximate Counting, the Lovász Local Lemma, and Inference in Graphical ModelsJournal of the ACM10.1145/326893066:2(1-25)Online publication date: 5-Apr-2019
    • (2018)Randomized Algorithms for Scheduling Multi-Resource Jobs in the CloudIEEE/ACM Transactions on Networking10.1109/TNET.2018.286364726:5(2202-2215)Online publication date: 1-Oct-2018
    • (2016)Measurement of Mobile Switching Centres Throughput in GSM Network Integrating Sliding Window Algorithm with a Single Server Finite Queuing ModelJournal of Computer Networks and Communications10.1155/2016/20613472016(2)Online publication date: 1-Oct-2016
    • (2016)Scheduling Storms and Streams in the CloudACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/29040801:4(1-28)Online publication date: 2-Aug-2016
    • (2016)Randomized algorithms for scheduling VMs in the cloudIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524536(1-9)Online publication date: Apr-2016
    • (2016)Blocking evaluation and analysis of dynamic WDM networks under heterogeneous ON/OFF trafficOptical Switching and Networking10.1016/j.osn.2015.11.00120:C(35-45)Online publication date: 1-Apr-2016
    • (2016)Flexible bed allocations for hospital wardsHealth Care Management Science10.1007/s10729-016-9364-420:4(453-466)Online publication date: 8-Apr-2016
    • (2015)Network dimensioning with carrier aggregation2015 IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN)10.1109/DySPAN.2015.7343929(336-347)Online publication date: Sep-2015
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media