Load balancing via random local search in closed and open systems.
Saved in:
| Title: | Load balancing via random local search in closed and open systems. |
|---|---|
| Authors: | Ganesh, Ayalvadi1 a.ganesh@bristol.ac.uk, Lilienthal, Sarah2 s.lilienthal@statslab.cam.ac.uk, Manjunath, D.3 dmanju@ee.iitb.ac.in, Proutiere, Alexandre4 alepro@kth.se, Simatos, Florian5 florian.simatos@m4x.org |
| Source: | Queueing Systems. Jul2012, Vol. 71 Issue 3, p321-345. 25p. |
| Subjects: | Load balancing (Computer networks), Systems migration, Queuing theory, Simulation methods & models, Computer systems |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Queueing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 77350707 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Load balancing via random local search in closed and open systems. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ganesh%2C+Ayalvadi%22">Ganesh, Ayalvadi</searchLink><relatesTo>1</relatesTo><i> a.ganesh@bristol.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Lilienthal%2C+Sarah%22">Lilienthal, Sarah</searchLink><relatesTo>2</relatesTo><i> s.lilienthal@statslab.cam.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Manjunath%2C+D%2E%22">Manjunath, D.</searchLink><relatesTo>3</relatesTo><i> dmanju@ee.iitb.ac.in</i><br /><searchLink fieldCode="AR" term="%22Proutiere%2C+Alexandre%22">Proutiere, Alexandre</searchLink><relatesTo>4</relatesTo><i> alepro@kth.se</i><br /><searchLink fieldCode="AR" term="%22Simatos%2C+Florian%22">Simatos, Florian</searchLink><relatesTo>5</relatesTo><i> florian.simatos@m4x.org</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Queueing+Systems%22">Queueing Systems</searchLink>. Jul2012, Vol. 71 Issue 3, p321-345. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Load+balancing+%28Computer+networks%29%22">Load balancing (Computer networks)</searchLink><br /><searchLink fieldCode="DE" term="%22Systems+migration%22">Systems migration</searchLink><br /><searchLink fieldCode="DE" term="%22Queuing+theory%22">Queuing theory</searchLink><br /><searchLink fieldCode="DE" term="%22Simulation+methods+%26+models%22">Simulation methods & models</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Queueing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=77350707 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s11134-012-9315-9 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 321 Subjects: – SubjectFull: Load balancing (Computer networks) Type: general – SubjectFull: Systems migration Type: general – SubjectFull: Queuing theory Type: general – SubjectFull: Simulation methods & models Type: general – SubjectFull: Computer systems Type: general Titles: – TitleFull: Load balancing via random local search in closed and open systems. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ganesh, Ayalvadi – PersonEntity: Name: NameFull: Lilienthal, Sarah – PersonEntity: Name: NameFull: Manjunath, D. – PersonEntity: Name: NameFull: Proutiere, Alexandre – PersonEntity: Name: NameFull: Simatos, Florian IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Jul2012 Type: published Y: 2012 Identifiers: – Type: issn-print Value: 02570130 Numbering: – Type: volume Value: 71 – Type: issue Value: 3 Titles: – TitleFull: Queueing Systems Type: main |
| ResultId | 1 |
