BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Load Balancing via Random Local Search in Closed and Open systems 
 - Sarah Lilienthal\, Statistical Laboratory\, University of Cambridge
DTSTART:20100601T150000Z
DTEND:20100601T160000Z
UID:TALK25120@talks.cam.ac.uk
CONTACT:Neil Walton
DESCRIPTION:We analyze the performance of random load resampling and migra
 tion\nstrategies in parallel server systems. Clients initially attach to a
 n\narbitrary server\, but may switch servers independently at random insta
 nts\nof time in an attempt to improve their service rate. This approach to
  load\nbalancing contrasts with traditional approaches where clients make 
 smart\nserver selections upon arrival (e.g.\, Join- the-Shortest-Queue pol
 icy and\nvariants thereof ). Load resampling is particularly relevant in s
 cenarios\nwhere clients cannot predict the load of a server before being a
 ctually\nattached to it. An important example is in wireless spectrum shar
 ing where\nclients try to share a set of frequency bands in a distributed 
 manner. We\n&#64257\;rst analyze the natural Random Local Search (RLS) str
 ategy. Under\nthis strategy\, after sampling a new server randomly\, clien
 ts only switch to\nit if their service rate is improved. In closed systems
 \, where the client\npopulation is &#64257\;xed\, we derive tight estimate
 s of the time it takes\nunder RLS strategy to balance the load across serv
 ers. We then study open\nsystems where clients arrive according to a rando
 m process and leave the\nsystem upon service completion. In this scenario\
 , we analyze how client\nmigrations within the system interact with the sy
 stem dynamics induced by\nclient arrivals and departures. We compare the l
 oad-aware RLS strategy to a\nload-oblivious strategy in which clients just
  randomly switch server\nwithout accounting for the server loads. Surprisi
 ngly\, we show that both\nload-oblivious and load-aware strategies stabili
 ze the system whenever this\nis at all possible. We further demonstrate\, 
 using large-system asymptotics\,\nthat the average client sojourn time und
 er the load-oblivious strategy is\nnot considerably reduced when clients a
 pply smarter load-aware strategies.\n\nThis is joint work with A. Ganesh\,
  D. Manjunath\, A. Proutiere and F. Simatos\n\n
LOCATION:MR14\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR