Optimal server assignment in multi-server queueing systems with random connectivities

摘要

We study the problem of assigning $K$ identical servers to a set of $N$parallel queues in a time-slotted queueing system. The connectivity of eachqueue to each server is randomly changing with time; each server can serve atmost one queue and each queue can be served by at most one server during eachtime slot. Such a queueing model has been used in addressing resourceallocation problems in wireless networks. It has been previously proven thatMaximum Weighted Matching (MWM) is a throughput-optimal server assignmentpolicy for such a queueing system. In this paper, we prove that for a systemwith i.i.d. Bernoulli packet arrivals and connectivities, MWM minimizes, instochastic ordering sense, a broad range of cost functions of the queue lengthssuch as total queue occupancy (which implies minimization of average queueingdelays). Then, we extend the model by considering imperfect services where itis assumed that the service of a scheduled packet fails randomly with a certainprobability. We prove that the same policy is still optimal for the extendedmodel. We finally show that the results are still valid for more generalconnectivity and arrival processes which follow conditional permutationinvariant distributions.