NDLI: Asymptotics of Insensitive Load Balancing and Blocking Phases

Content Provider	ACM Digital Library
Author	Jonckheere, Matthieu Prabhu, Balakrishna J.
Abstract	Load balancing with various types of load information has become a key component of modern communication and information systems. In many systems, characterizing precisely the blocking probability allows to establish a performance trade-off between delay and losses. We address here the problem of giving robust performance bounds based on the study of the asymptotic behavior of the insensitive load balancing schemes when the number of servers and the load scales jointly. These schemes have the desirable property that the stationary distribution of the resulting stochastic network depends on the distribution of job sizes only through its mean. It was shown that they give good estimates of performance indicators for systems with finite buffers, generalizing henceforth Erlang's formula whereas optimal policies are already theoretically and computationally out of reach for networks of moderate size. We study a single class of traffic acting on a symmetric set of processor sharing queues with finite buffers and we consider the case where the load scales with the number of servers.We characterize the response of symmetric systems under those schemes at different scales and show that three amplitudes of deviations can be identified according to whether ρ < 1, ρ = 1, and ρ > 1. A central limit scaling takes place for a sub-critical load;for ρ=1, the number of free servers scales like $n^{\{θ/θ+1\}}$ (θ being the buffer depth and n being the number of servers) and is of order 1 for super-critical loads. This further implies the existence of different phases for the blocking probability. Before a (refined) critical load $ρ_{c}(n)=1-a$ n- {θ/θ+1}, the blocking is exponentially small and becomes of order n- {θ/θ+1} at $ρ_{c}(n).$ This generalizes the well-known Quality and Efficiency Driven (QED) regime or Halfin-Whitt regime for a one-dimensional queue, and leads to a generalized staffing rule for a given target blocking probability.
Starting Page	311
Ending Page	322
Page Count	12
File Format	PDF
ISSN	01635999
DOI	10.1145/2964791.2901454
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	44
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Qed-jagerman-halfin-whitt regime Mean-field scalings Insensitive load balancing Blocking phases
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Asymptotics of Insensitive Load Balancing and Blocking Phases

Asymptotics of Insensitive Load Balancing and Blocking Phases

Asymptotics of Insensitive Load Balancing and Blocking Phases

Rare-event simulation for multi-server queues in the Halfin-Whitt regime

Insensitive load balancing

Load balancing via random local search in closed and open systems

Geographical Load Balancing across Green Datacenters:A Mean Field Analysis

A mean field model of work stealing in large-scale systems

Asymptotics of Insensitive Load Balancing and Blocking Phases

Asymptotics of Insensitive Load Balancing and Blocking Phases

Similar Documents

Asymptotics of Insensitive Load Balancing and Blocking Phases

Asymptotics of Insensitive Load Balancing and Blocking Phases

Asymptotics of Insensitive Load Balancing and Blocking Phases

Rare-event simulation for multi-server queues in the Halfin-Whitt regime

Insensitive load balancing

Load balancing via random local search in closed and open systems

Geographical Load Balancing across Green Datacenters:A Mean Field Analysis

A mean field model of work stealing in large-scale systems

Asymptotics of Insensitive Load Balancing and Blocking Phases

Asymptotics of Insensitive Load Balancing and Blocking Phases