Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorBhulai, dr. S.
dc.contributor.advisorDajani, dr. K.
dc.contributor.advisorCiucu, dr. F.
dc.contributor.authorJanssen, J.S.
dc.date.accessioned2012-03-27T17:00:57Z
dc.date.available2012-03-27
dc.date.available2012-03-27T17:00:57Z
dc.date.issued2012
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/10233
dc.description.abstractLoad balancing is very relevant in networking, where incoming requests (jobs) have to be divided over various servers by dispatchers. The goal is mostly to minimize response times. Research in this field becomes ever more relevant by the current trend where users generate an increasing amount of internet traffic and data centers become larger and larger. A commonly used load balancing algorithm that uses randomization and performs well, is SQ(d). It sends an arriving job to the shortest of d queues, chosen uniformly at random. In most research this d is kept fixed and its performance is analyzed asymptotically in the number of servers. In this thesis we keep the number of servers finite and apply the theory of Markov decision processes (MDPs) to the load balancing problem. We model the SQ(d) algorithm as a Markov reward process and make it an MDP by introducing communication costs and allowing d to vary. Since MDPs are not scalable, we came up with a heuristic coined Dynamic SQ(d), that outperforms algorithms widely used in practice, such as SQ(2) and Join the Shortest Queue, for a fairly broad range of parameter values.
dc.description.sponsorshipUtrecht University
dc.format.extent5337321 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.titleDynamic Load Balancing for High Dimensional Systems
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsRandomized load balancing, SQ(d), supermarket model, Cloud computing, Markov decision processes, structural properties of the relative value function, partial information models, heuristics.
dc.subject.courseuuMathematical Sciences


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record