NDLI: Load balancing via random local search in closed and open systems

Please wait, while we are loading the content...

Practical performance models for complex, popular applications

Elon: enabling efficient and long-term reprogramming for wireless sensor networks

On the flow-level dynamics of a packet-switched network

Optimal recovery of single disk failure in RDP code storage systems

Coloring spatial point processes with applications to peer discovery in large wireless networks

Detecting sources of computer viruses in networks: theory and experiment

Qualitative properties of α-weighted scheduling policies

Randomized load balancing with general service time distributions

Distributed caching over heterogeneous mobile networks

A distributed scheduling algorithm for wireless networks with constant overhead and arbitrary binary interference

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

Distributed sensor network localization from local connectivity: performance analysis for the HOP-TERRAIN algorithm

Incentive compatibility and dynamics of congestion control

A query language and runtime tool for evaluating behavior of multi-tier servers

Optimal tradeoff between exposed and hidden nodes in large wireless networks

Incentivizing peer-assisted services: a fluid shapley value approach

CWS: a model-driven scheduling policy for correlated workloads

Load balancing via random local search in closed and open systems

An analytical framework to infer multihop path reliability in MANETs

Successive c-optimal designs: a scalable technique to optimize the measurements on large networks

A unifying approach to product-forms in networks with finite capacity constraints

Self-synchronizing properties of CSMA wireless multi-hop networks

Dynamics in congestion games

Small subset queries and bloom filters using ternary associative memories, with applications

Scheduling in multichannel wireless networks with flow-level dynamics

Leveraging parallelism for multi-dimensional packetclassification on software routers

RSIO: automatic user interaction detection and scheduling

A unified modeling framework for distributed resource allocation of general fork and join processing networks

Channel fragmentation in dynamic spectrum access systems: a theoretical study

Deep diving into BitTorrent locality

Optimality, fairness, and robustness in speed scaling designs

Transparent, lightweight application execution replay on commodity multiprocessor operating systems

Inferring applications at the network layer using collective traffic statistics

The price of anarchy in parallel queues revisited

Optimal propagation of security patches in mobile wireless networks: extended abstract

Managing the cost, energy consumption, and carbon footprint of internet services

Coordinated power management of voltage islands in CMPs

Rigorous statistical analysis of internet loss measurements

Semidefinite optimization for transient analysis of queues

CFTL: a convertible flash translation layer adaptive to data access patterns

A case for unsupervised-learning-based spam filtering

Distributed averaging in dynamic networks

Program behavior prediction using a statistical metric model

Delay optimal queue-based CSMA

Characterizing and modeling user activity on smartphones: summary

Detecting traffic anomalies using an equilibrium property

Characterizing the soft error vulnerability of multicores running multithreaded applications

Can multipath mitigate power law delays?: effects of parallelism on tail performance

Distributed user profiling via spectral methods

Load balancing via random local search in closed and open systems

Content Provider	ACM Digital Library
Author	Ganesh, Ayalvadi Manjunath, D. Proutiere, Alexandre Simatos, Florian Lilienthal, Sarah
Abstract	In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate. This approach to load balancing contrasts with traditional approaches where clients make smart server selections upon arrival (e.g., Join-the-Shortest-Queue policy and variants thereof). Load resampling is particularly relevant in scenarios where clients cannot predict the load of a server before being actually attached to it. An important example is in wireless spectrum sharing where clients try to share a set of frequency bands in a distributed manner. We first analyze the natural Random Local Search (RLS) strategy. Under this strategy, after sampling a new server randomly, clients only switch to it if their service rate is improved. In closed systems, where the client population is fixed, we derive tight estimates of the time it takes under RLS strategy to balance the load across servers. We then study open systems where clients arrive according to a random process and leave the system upon service completion. In this scenario, we analyze how client migrations within the system interact with the system dynamics induced by client arrivals and departures. We compare the load-aware RLS strategy to a load-oblivious strategy in which clients just randomly switch server without accounting for the server loads. Surprisingly, we show that both load-oblivious and load-aware strategies stabilize the system whenever this is at all possible. We further demonstrate, using large-system asymptotics, that the average client sojourn time under the load-oblivious strategy is not considerably reduced when clients apply smarter load-aware strategies.
Starting Page	287
Ending Page	298
Page Count	12
File Format	PDF
ISBN	9781450300384
DOI	10.1145/1811039.1811072
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Mean field asymptotics Stability analysis
Content Type	Text
Resource Type	Article

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

Load balancing via random local search in closed and open systems

0 LOAD BALANCING VIA RANDOM LOCAL SEARCH IN CLOSED AND OPEN SYSTEMS

Load balancing via random local search in closed and open systems

Load balancing via random local search in closed and open systems

Load Balancing via Random Local Search in Closed and Open systems

Load balancing via random local search in closed and open systems (2010)

Asymptotics of Insensitive Load Balancing and Blocking Phases

An incentive algorithm for a closed stochastic network: data and mean-field analysis

Stability and Efficiency of a Random Local Load Balancing Protocol (2003)

Load balancing via random local search in closed and open systems

Similar Documents

Load balancing via random local search in closed and open systems

0 LOAD BALANCING VIA RANDOM LOCAL SEARCH IN CLOSED AND OPEN SYSTEMS

Load balancing via random local search in closed and open systems

Load balancing via random local search in closed and open systems

Load Balancing via Random Local Search in Closed and Open systems

Load balancing via random local search in closed and open systems (2010)

Asymptotics of Insensitive Load Balancing and Blocking Phases

An incentive algorithm for a closed stochastic network: data and mean-field analysis

Stability and Efficiency of a Random Local Load Balancing Protocol (2003)

Load balancing via random local search in closed and open systems