2019/01/18 by Tang, Dengwang, Subramanian, Vijay G.
#FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Networking and Internet Architecture (cs.NI) #Performance (cs.PF) #Probability (math.PR) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.1901.09094
In a computing center with a huge amount of machines, when a job arrives, a dispatcher need to decide which machine to route this job to based on limited information. A classical method, called the power-of-d choices algorithm is to pick d servers independently at random and dispatch the job to the least loaded server among the d servers. In this paper, we analyze a low-randomness variant of this dispatching scheme, where d queues are sampled through d independent non-backtracking random walks on a k-regular graph G. Under certain assumptions of the graph G we show that under this scheme, the dynamics of the queuing system converges to the same deterministic ordinary differential equation (ODE) for the power-of-d choices scheme. We also show that the system is stable under the proposed scheme, and the stationary distribution of the system converges to the fixed point of the ODE.