Bhambay, Sanidhay and Mukhopadhyay, Arpan (2022) Optimal load balancing in heterogeneous server systems. In: 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), Turin, Italy, 19-23 Sep 2022. Published in: Proceedings of the 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt) doi:10.23919/WiOpt56218.2022.9930523 (In Press)

Preview

PDF WRAP-Optimal-load-balancing-in-heterogeneous-server-systems-Mukhopadhyay-2022.pdf - Accepted Version - Requires a PDF viewer. Download (538Kb) | Preview

Request Changes to record.

Abstract

A fundamental problem in large-scale data centers is to reduce the average response time of jobs. The Join-the-Shortest-Queue (JSQ) load balancing scheme is known to minimise the average response time of jobs for homogeneous systems consisting of identical servers. However, heterogeneous systems consisting of servers with different speeds, JSQ performs poorly. Furthermore, JSQ suffers from high communication overhead as it requires knowledge of the queue length of all servers while assigning incoming jobs to one of the destination servers. Therefore, the Join-the-Idle-Queue (JIQ) scheme was introduced which not only reduces the communication overhead but also minimises the average response time of jobs under homogeneous systems. Despite these advantages, JIQ is still known to be inefficient in minimising the average response time of jobs under heterogeneous systems. In this paper, we consider a speed-aware version of JIQ for heterogeneous systems and show that it achieves delay optimality in the fluid limit. One of the technical challenges to establishing this optimality is to show the tightness of the sequence of steady-state distributions indexed by system size. We show this tightness result by evaluating the drift of appropriate Lyapunov functions. This approach to proving tightness is different from the usual coupling approach used for homogeneous systems. Another important challenge in proving the optimality result is to establish the fluid limit which is done using the time-scale separation technique. Finally, using the monotonicity of the fluid process we have shown that the fluid limit has a unique and globally attractive fixed point.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Client/server computing -- Mathematical models, Stochastic processes, Fluid Dynamics
Journal or Publication Title:	Proceedings of the 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)
Publisher:	IEEE
Official Date:	1 November 2022
Dates:	Date Event 1 November 2022 Available 2 July 2022 Accepted
DOI:	10.23919/WiOpt56218.2022.9930523
Status:	Peer Reviewed
Publication Status:	In Press
Reuse Statement (publisher, data, author rights):	© 2022 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	3 October 2022
Date of first compliant Open Access:	5 October 2022
Conference Paper Type:	Paper
Title of Event:	2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)
Type of Event:	Conference
Location of Event:	Turin, Italy
Date(s) of Event:	19-23 Sep 2022
Related URLs:	Organisation Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads