Record Details

Load balancing via random local search in closed and open systems

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Load balancing via random local search in closed and open systems
 
Creator GANESH, A
LILIENTHAL, S
MANJUNATH, D
PROUTIERE, A
SIMATOS, F
 
Subject Mean field asymptotics
Stability analysis
NETWORKS
 
Description In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach themselves 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 use large-system asymptotics to characterize system performance, and augment this with simulations, which suggest that the average client sojourn time under the load-oblivious strategy is not considerably reduced when clients apply smarter load-aware strategies.
 
Publisher SPRINGER
 
Date 2014-10-16T13:54:43Z
2014-10-16T13:54:43Z
2012
 
Type Article
 
Identifier QUEUEING SYSTEMS, 71(3)321-345
http://dx.doi.org/10.1007/s11134-012-9315-9
http://dspace.library.iitb.ac.in/jspui/handle/100/15718
 
Language en