LOAD BALANCING FOR REMOTE QUEUES

Abstract

Nowadays, mobile apps allow customers to access real-time information of service systems (e.g., estimated waiting times). In these systems, customers are usually distant from servers, and it takes time for them to reach a service station (e.g., traveling times). Based on the information, customers may decide where to visit if they can be served by multiple servers. To ensure efficient service, it is important to balance the number of customers waiting at each station. It is known that load balancing policies that rely on current information, such as the join-the-shortest-queue policy, may induce queue length oscillations in the presence of information delays and seriously hurt the system performance. To mitigate the oscillation phenomenon, we rely on randomization techniques and propose a policy called the randomized-join-shortest-queue policy. This policy is proven to achieve state-space-collapse, where queue lengths asymptotically equalize. On top of that, the proposed policy is proved to be asymptotically optimal for minimizing a customer's time to service (i.e., the sum of the traveling delay and the waiting time). We also establish a lower bound for the time to service and demonstrate how to minimize the performance gap by fine-tuning the randomized policy.