article

Insensitivity in processor-sharing networks

Authors:

T. Bonald,

A. ProutièreAuthors Info & Claims

Performance Evaluation, Volume 49, Issue 1-4

Pages 193 - 209

https://doi.org/10.1016/S0166-5316(02)00110-4

Published: 01 September 2002 Publication History

Abstract

We consider an open network of processor-sharing nodes with state-dependent service capacities, i.e., the speed of each node may depend on the number of customers at any node. We demonstrate that the stationary distribution of the network state is insensitive to the distribution of service times if and only if the service capacities are balanced, i.e., the considered network is a Whittle network. The stationary distribution then has a closed-form expression and the expected sojourn time of a customer at any node is proportional to its required quantity of service. These results are extended to the cases of closed networks and state-dependent arrival rates and routing. Two simple examples illustrate the practical interest of these results in the context of communication networks.

References

[1]

{1} F. Baccelli, P. Brémaud, Palm probability and stationary queues, Lect. Notes Stat. 41 (1987).

Google Scholar

[2]

{2} A.D. Barbour, Generalized semi-Markov schemes and open queueing networks, J. Appl. Probab. 19 (1982) 469-474.

Crossref

Google Scholar

[3]

{3} F. Baskett, K.M. Chandy, R.R. Muntz, F.G. Palacios, Open, closed and mixed networks of queues with different classes of customers, J. Assoc. Comput. Mach. 22 (1975) 248-260.

Digital Library

Google Scholar

[4]

{4} S. Ben Fredj, T. Bonald, A. Proutière, G. Regnié, J.W. Roberts, Statistical bandwidth sharing: a study of congestion at flow level, in: Proceedings of the ACM SIGCOMM Conference, 2001.

Crossref

Google Scholar

[5]

{5} D. Bertsekas, R. Gallager, Data Networks, Prentice-Hall, Englewood Cliffs, NJ, 1987.

Crossref

Google Scholar

[6]

{6} T. Bonald, L. Massouliè, Impact of fairness on internet performance, in: Proceedings of the ACM SIGMETRICS Conference, 2001.

Crossref

Google Scholar

[7]

{7} T. Bonald, A. Proutière, Insensitive bandwidth sharing, in: Proceedings of the IEEE GLOBECOM Conference, 2002.

Crossref

Google Scholar

[8]

{8} T. Bonald, A. Proutière, G. Régnié, J.W. Roberts, Insensitivity results in statistical bandwidth sharing, in: Proceedings of the ITC 17 Conference, Elsevier, Amsterdam, 2001.

Google Scholar

[9]

{9} D. Burman, Insensitivity in queueing systems, Adv. Appl. Probab. 13 (1981) 846-859.

Crossref

Google Scholar

[10]

{10} X. Chao, M. Miyazawa, R.F. Serfozo, H. Takada, Markov network processes with product form stationary distributions, Queueing Syst. 28 (1998) 377-401.

Crossref

Google Scholar

[11]

{11} J.W. Cohen, The multiple phase service network with generalized processor sharing, Acta Inform. 12 (1979) 245-284.

Digital Library

Google Scholar

[12]

{12} W. Henderson, Insensitivity and reversed Markov processes, Adv. Appl. Probab. 15 (1983) 752-768.

Crossref

Google Scholar

[13]

{13} F.P. Kelly, Reversibility and Stochastic Networks, Wiley, New York, 1979.

Google Scholar

[14]

{14} F.P. Kelly, Loss networks, Ann. Appl. Probab. 1 (1991) 319-378.

Crossref

Google Scholar

[15]

{15} L. Kleinrock, Queueing Systems, Vol. 2, Wiley, New York, 1975.

Google Scholar

[16]

{16} L. Massoulié, J.W. Roberts, Bandwidth sharing and admission control for elastic traffic, Telecommun. Syst. 15 (2000) 185-201.

Digital Library

Google Scholar

[17]

{17} M. Miyazawa, Insensitivity and product-form decomposability of reallocatable GSMP, Adv. Appl. Probab. 25 (1993) 415-437.

Crossref

Google Scholar

[18]

{18} M. Miyazawa, H. Takada, Traffic flows and product form solutions in stochastic transfer networks, Queueing Syst. 37 (2001) 199-232.

Crossref

Google Scholar

[19]

{19} S. Oueslati Boulahia, E. Oubagha, An approach to elastic flow routing, in: Proceedings of the ITC 16 Conference, Elsevier, Amsterdam, 1999.

Google Scholar

[20]

{20} R. Schassberger, Insensitivity of steady state distributions of generalized semi-Markov processes with speeds, Adv. Appl. Probab. 10 (1978) 836-851.

Crossref

Google Scholar

[21]

{21} R. Schassberger, Two remarks on insensitive stochastic models, Adv. Appl. Probab. 18 (1986) 791-814.

Crossref

Google Scholar

[22]

{22} R.F. Serfozo, Markovian network processes: congestion-dependent routing and processing, Queueing Syst. 5 (1989) 5-36.

Digital Library

Google Scholar

[23]

{23} R.F. Serfozo, Queueing networks with dependent nodes and concurrent movements, Queueing Syst. 13 (1993) 143-182.

Crossref

Google Scholar

[24]

{24} R.F. Serfozo, Introduction to Stochastic Networks, Springer, Berlin, 1999.

Google Scholar

[25]

{25} P. Whittle, Partial balance and insensitivity, J. Appl. Probab. 22 (1985) 168-176.

Crossref

Google Scholar

Cited By

View all

Scully ZHarchol-Balter MScheller-Wolf A(2020)Simple Near-Optimal Scheduling for the M/G/1Proceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33794774:1(1-29)Online publication date: 5-Jun-2020
https://dl.acm.org/doi/10.1145/3379477
Vasantam TMukhopadhyay AMazumdar R(2019)The Mean-field Behavior of Processor Sharing Systems with General Job Lengths Under the SQ(d) PolicyACM SIGMETRICS Performance Evaluation Review10.1145/3308897.330892446:3(54-55)Online publication date: 25-Jan-2019
https://dl.acm.org/doi/10.1145/3308897.3308924
Maguluri SBurle SSrikant R(2018)Optimal heavy-traffic queue length scaling in an incompletely saturated switchQueueing Systems: Theory and Applications10.1007/s11134-017-9562-x88:3-4(279-309)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11134-017-9562-x
Show More Cited By

Index Terms

Insensitivity in processor-sharing networks

Recommendations

On the distribution of the number of customers in the symmetric M/G/1 queue

We consider an M / G /1 queue with symmetric service discipline. The class of symmetric service disciplines contains, in particular, the preemptive last-come-first-served discipline and the processor-sharing discipline. It has been conjectured in ...
Towards an Erlang formula for multiclass networks

Consider a multiclass stochastic network with state-dependent service rates and arrival rates describing bandwidth-sharing mechanisms as well as admission control and/or load balancing schemes. Given Poisson arrival and exponential service requirements, ...
Insensitivity to service-time distributions for fluid queueing models
ValueTools '13: Proceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools

We study fluid limits based on ordinary differential equations (ODEs) for Markovian queueing models where nonexponential service times are fit by appropriate Coxian distributions to match their first and second moments. We focus on a heavy-load regime, ...

Reviews

Reviewer: James Speybroeck

An excellent example of scholarship in the affirmation of techniques addressing insensitivity in processor-sharing networks is presented in this paper. The authors clearly state the purpose of the paper: to show that the stationary distribution of the network state is insensitive to the distribution of service times, if and only if the service capabilities are balanced. After this introduction, the authors painstakingly present their research. The model and the balance property that characterize whittle networks are described in the first part of the paper. Insensitivity results and performance results are detailed. The paper ends with a presentation of two examples that illustrate the beneficial results of the research. The definitions and theorems presented are sophisticated. They deal with whittle networks, conditional expected sojourn time, closed networks, state-dependent arrival rates and routing, and application of the research to communication networks. This paper is certainly not bedtime reading, but if you are a professional concerned with processor-sharing networks, it will be of significant interest. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Performance Evaluation Volume 49, Issue 1-4

September 2002

503 pages

ISSN:0166-5316

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 September 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Scully ZHarchol-Balter MScheller-Wolf A(2020)Simple Near-Optimal Scheduling for the M/G/1Proceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33794774:1(1-29)Online publication date: 5-Jun-2020
https://dl.acm.org/doi/10.1145/3379477
Vasantam TMukhopadhyay AMazumdar R(2019)The Mean-field Behavior of Processor Sharing Systems with General Job Lengths Under the SQ(d) PolicyACM SIGMETRICS Performance Evaluation Review10.1145/3308897.330892446:3(54-55)Online publication date: 25-Jan-2019
https://dl.acm.org/doi/10.1145/3308897.3308924
Maguluri SBurle SSrikant R(2018)Optimal heavy-traffic queue length scaling in an incompletely saturated switchQueueing Systems: Theory and Applications10.1007/s11134-017-9562-x88:3-4(279-309)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11134-017-9562-x
Bramson MD'Auria BWalton N(2017)Proportional Switching in First-in, First-out NetworksOperations Research10.1287/opre.2016.156565:2(496-513)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1287/opre.2016.1565
Berg BDorsman JHarchol-Balter M(2017)Towards Optimality in Parallel SchedulingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544991:2(1-30)Online publication date: 19-Dec-2017
https://dl.acm.org/doi/10.1145/3154499
Dao-Thi TFourneau JTran M(2017)Whittle networks with resetsProceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools10.1145/3150928.3150940(28-35)Online publication date: 5-Dec-2017
https://dl.acm.org/doi/10.1145/3150928.3150940
Bonald TComte C(2017)Balanced fair resource sharing in computer clustersPerformance Evaluation10.1016/j.peva.2017.08.006116:C(70-83)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.peva.2017.08.006
(2017)Whittle-networks with signalsPerformance Evaluation10.1016/j.peva.2016.12.001109:C(8-22)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.peva.2016.12.001
Maguluri SBurle SSrikant R(2016)Optimal Heavy-Traffic Queue Length Scaling in an Incompletely Saturated SwitchACM SIGMETRICS Performance Evaluation Review10.1145/2964791.290146644:1(13-24)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/2964791.2901466
Maguluri SBurle SSrikant RAlouf SJean-Marie AHegde NProutière A(2016)Optimal Heavy-Traffic Queue Length Scaling in an Incompletely Saturated SwitchProceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science10.1145/2896377.2901466(13-24)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/2896377.2901466
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

On the distribution of the number of customers in the symmetric M/G/1 queue

Towards an Erlang formula for multiclass networks

Insensitivity to service-time distributions for fluid queueing models

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations