Change search
ReferencesLink to record
Permanent link

Direct link
Load balancing via random local search in closed and open systems
KTH, School of Electrical Engineering (EES), Automatic Control.
Show others and affiliations
2012 (English)In: Queueing systems, ISSN 0257-0130, E-ISSN 1572-9443, Vol. 71, no 3, 321-345 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2012. Vol. 71, no 3, 321-345 p.
Keyword [en]
Mean field asymptotics, Stability analysis
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-99225DOI: 10.1007/s11134-012-9315-9ISI: 000305730300004ScopusID: 2-s2.0-84863103117OAI: diva2:541916
ICT - The Next Generation

QC 20120726

Available from: 2012-07-26 Created: 2012-07-23 Last updated: 2013-04-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Proutiere, Alexandre
By organisation
Automatic Control
In the same journal
Queueing systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 38 hits
ReferencesLink to record
Permanent link

Direct link