Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2009 | Published
Book Section - Chapter Open

On the impact of heterogeneity and back-end scheduling in load balancing designs


Load balancing is a common approach for task assignment in distributed architectures. In this paper, we show that the degree of inefficiency in load balancing designs is highly dependent on the scheduling discipline used at each of the backend servers. Traditionally, the back-end scheduler can be modeled as Processor Sharing (PS), in which case the degree of inefficiency grows linearly with the number of servers. However, if the back-end scheduler is changed to Shortest Remaining Processing Time (SRPT), the degree of inefficiency can be independent of the number of servers, instead depending only on the heterogeneity of the speeds of the servers. Further, switching the back-end scheduler to SRPT can provide significant improvements in the overall mean response time of the system as long as the heterogeneity of the server speeds is small.

Additional Information

© 2009 IEEE. This work was supported by NSF CCF 0830511, Microsoft Research, and the Lee Center for Advanced Networking.

Attached Files

Published - Chen2009p8164Ieee_Infocom_2009_-_Ieee_Conference_On_Computer_Communications_Vols_1-5.pdf



Additional details

August 20, 2023
October 20, 2023