Load balancing and the power of preventive probing
Faculty of Sciences. Mathematics and Computer Science
Performance evaluation review
, p. 65-67
University of Antwerp
Consider a randomized load balancing problem consisting of a large number n of server sites each equipped with K servers. Under the greedy policy, clients randomly probe a site to check whether there is still a server available. If not, d 􀀀 1 other sites are probed and the task is assigned to the site with the fewest number of busy servers. If all the servers are also busy in each of these d 􀀀 1 sites, the task is lost. This short paper analyzes a set of policies, i.e., (L; d) policies, that will occasionally probe additional sites even when there is still a server available at the site that was probed rst. Using mean eld methods, we show that these policies, that preventively probe other sites, can achieve the same loss probability while requiring a lower overall probe rate.