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

Article

Insensitive load balancing

Authors:

A. ProutiéreAuthors Info & Claims

SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Pages 367 - 377

https://doi.org/10.1145/1005686.1005729

Published: 01 June 2004 Publication History

Abstract

A large variety of communication systems, including telephone and data networks, can be represented by so-called Whittle networks. The stationary distribution of these networks is insensitive, depending on the service requirements at each node through their mean only. These models are of considerable practical interest as derived engineering rules are robust to the evolution of traffic characteristics. In this paper we relax the usual assumption of static routing and address the issue of dynamic load balancing. Specifically, we identify the class of load balancing policies which preserve insensitivity and characterize optimal strategies in some specific cases. Analytical results are illustrated numerically on a number of toy network examples.

References

[1]

M. Alanyali, B. Hajek, Analysis of simple algorithms for dynamic load balancing, Mathematics of Operations Research 22-4 (1997) 840--871.

Digital Library

[2]

T. Bonald, A. Proutiére, Insensitivity in processor-sharing networks, Performance Evaluation 49 (2002) 193--209.

Digital Library

[3]

T. Bonald, A. Proutiére, Insensitive bandwidth sharing in data networks, Queueing Systems 44-1 (2003) 69--100.

Digital Library

[4]

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

Digital Library

[5]

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

Digital Library

[6]

M.B. Combe, O.J. Boxma, Optimization of static traffic allocation policies, Theoretical Computer Science 125 (1994) 17--43.

Digital Library

[7]

A. Ephremides, P. Varaiya, J. Walrand, A simple dynamic routing problem, IEEE Transactions on Automatic control 25 (1980) 690--693.

[8]

M. Harchol-Balter, M. Crovella, C. Murta, On choosing a task assignment policy for a distributed server system, IEEE journal of parallel and distributed computing 59 (1999) 204--228.

Digital Library

[9]

A. Hordijk, G. Koole, On the assignment of customers to parallel queues, Probability in the Engineering and Informational Sciences 6 (1992) 495--511.

[10]

F.P. Kelly, Blocking Probabilities in Large Circuit-switched Networks, Adv. Applied Probability 18 (1986) 473--505.

[11]

F.P. Kelly, Routing and capacities allocations in networks with trunk reservations. Mathematics of operations research 15 (1990) 771--793.

Digital Library

[12]

F.P. Kelly, Network routing, Philosophical Transactions of the Royal Society A337 (1991) 343--367.

[13]

F.P. Kelly, Loss Networks, Annals of Applied Probabilities 1-3 (1991) 319--378.

[14]

F.P. Kelly, Bounds on the performance of dynamic routing schemes for highly connected networks, Mathematics of Operations Research 19 (1994) 1--20.

Digital Library

[15]

F.P. Kelly, Mathematical modelling of the Internet, in: Mathematics Unlimited - 2001 and Beyond (Editors B. Engquist and W. Schmid), Springer-Verlag, Berlin (2001) 685--702.

[16]

J. van Leeuwaarden, S. Aalto, J. Virtamo, Load balancing in cellular networks using first policy iteration, Technical Report, Networking Laboratory, Helsinki University of Technology, 2001.

[17]

D. Mitra, R.J. Gibbens, B.D. Huang, State dependent routing on symmetric loss networks with trunk reservations, IEEE Transactions on communications 41-2 (1993) 400--411.

[18]

S. Nelakuditi, Adaptive proportional routing: a localized QoS routing approach, in: Proc. of IEEE Infocom, 2000.

[19]

R. Nelson, T. Philips, An approximation for the mean response time for shortest queue routing with general interarrival and service times, Performance evaluation 17 (1993) 123--139.

Digital Library

[20]

S. Oueslati-Boulahia, E. Oubagha, An approach to routing elastic flows, in: Proc. of ITC 16, 1999.

[21]

R. Serfozo, Introduction to stochastic networks, Springer, 1999.

[22]

P. Sparaggis, C. Cassandras, D. Towley, Optimal control of multiclass parallel service systems with and without state information, in: proc. of the 32nd Conference on Decision Control, San Antonio, 1993.

[23]

S. Stidham, Optimal control of admission to a queueing system, IEEE Transactions on Automatic Control 30-8 (1985) 705--713.

[24]

A.N. Tantawi and D. Towsley, Optimal static load balancing in distributed computer systems, Journal of the ACM 32-2 (1985) 445--465.

Digital Library

[25]

D. Towsley, D. Panayotis, P. Sparaggis, C. Cassandras, Optimal routing and buffer allocation for a class of finite capacity queueing systems, IEEE Trans. on Automatic Control 37-9 (1992) 1446--1451.

[26]

W. Whitt, Deciding which queue to join: some counterexamples, Operations research 34-1 (1986) 226--244.

Digital Library

[27]

W. Winston, Optimality of the shortest line discipline, Journal of Applied Probability 14 (1977) 181--189.

Cited By

Ferragut APaganini F(2024)Queueing analysis of imbalance between multiple server pools with an application to 3-phase EV chargingACM SIGMETRICS Performance Evaluation Review10.1145/3649477.364949651:4(43-53)Online publication date: 23-Feb-2024
https://dl.acm.org/doi/10.1145/3649477.3649496
van der Boor MComte C(2021)Load Balancing in Heterogeneous Server Clusters: Insights From a Product-Form Queueing Model2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)10.1109/IWQOS52092.2021.9521355(1-10)Online publication date: 25-Jun-2021
https://doi.org/10.1109/IWQOS52092.2021.9521355
Grosof IScully ZHarchol-Balter M(2019)Load Balancing GuardrailsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261573:2(1-31)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326157
Show More Cited By

Index Terms

Insensitive load balancing
1. Mathematics of computing
  1. Probability and statistics

Recommendations

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, ...
Insensitive load balancing

A large variety of communication systems, including telephone and data networks, can be represented by so-called Whittle networks. The stationary distribution of these networks is insensitive, depending on the service requirements at each node through ...
Insensitive versus efficient dynamic load balancing in networks without blocking

So-called Whittle networks have recently been shown to give tight approximations for the performance of non-locally balanced networks with blocking, including practical routing policies such as joining the shortest queue. In the present paper, we turn ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

June 2004

450 pages

ISBN:1581138733

DOI:10.1145/1005686

General Chair:
E. G. Coffman
Columbia University
,
Program Chairs:
Zhen Liu
IBM Research
,
Arif Merchant
HP Labs

ACM SIGMETRICS Performance Evaluation Review Volume 32, Issue 1
June 2004
432 pages
ISSN:0163-5999
DOI:10.1145/1012888
Issue’s Table of Contents

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: 01 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMETRICS04

Sponsor:

SIGMETRICS04: SIGMETRICS 2004 / PERFORMANCE 2004

June 10 - 14, 2004

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
743
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ferragut APaganini F(2024)Queueing analysis of imbalance between multiple server pools with an application to 3-phase EV chargingACM SIGMETRICS Performance Evaluation Review10.1145/3649477.364949651:4(43-53)Online publication date: 23-Feb-2024
https://dl.acm.org/doi/10.1145/3649477.3649496
van der Boor MComte C(2021)Load Balancing in Heterogeneous Server Clusters: Insights From a Product-Form Queueing Model2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)10.1109/IWQOS52092.2021.9521355(1-10)Online publication date: 25-Jun-2021
https://doi.org/10.1109/IWQOS52092.2021.9521355
Grosof IScully ZHarchol-Balter M(2019)Load Balancing GuardrailsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261573:2(1-31)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326157
Vasantam TMukhopadhyay AMazumdar R(2019) Insensitivity of the mean field limit of loss systems under SQ( d ) routeing Advances in Applied Probability10.1017/apr.2019.4151:4(1027-1066)Online publication date: 15-Nov-2019
https://doi.org/10.1017/apr.2019.41
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
Naveen KMassoulie LBaccelli ECarneiro Viana ATowsley DChoffnes DVan der Merwe K(2015)On the Interaction between Content Caching and Request Assignment in Cellular Cache NetworksProceedings of the 5th Workshop on All Things Cellular: Operations, Applications and Challenges10.1145/2785971.2785975(37-42)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1145/2785971.2785975
Huang ZCorrigan DNarayanan SZhu TBentley EMedley M(2015)Distributed and dynamic spectrum management in airborne networksMILCOM 2015 - 2015 IEEE Military Communications Conference10.1109/MILCOM.2015.7357540(786-791)Online publication date: Oct-2015
https://doi.org/10.1109/MILCOM.2015.7357540
Li YZhang ZBoley D(2014)From Shortest-Path to All-PathIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.20325:7(1745-1755)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1109/TPDS.2013.203
Kameda HAltman ETouati CLegrand A(2012)Nash equilibrium based fairnessMathematical Methods of Operations Research10.1007/s00186-012-0389-276:1(43-65)Online publication date: 11-May-2012
https://doi.org/10.1007/s00186-012-0389-2
Mäkelä AManner J(2011)Bundling Consumer Connections -- A Performance AnalysisProceedings of the 2011 IEEE Workshops of International Conference on Advanced Information Networking and Applications10.1109/WAINA.2011.8(682-689)Online publication date: 22-Mar-2011
https://dl.acm.org/doi/10.1109/WAINA.2011.8
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