Longest-queue-first scheduling with intermittent sampling

摘要

A prototypical scheduling problem in communication networks is that a server needs to select, from a set of parallel queues, a job for processing to achieve a pre-determined objective. Classical scheduling schemes that yield performance guarantees typically assume that the server has instant access to the realtime information of the entire system state. However, this is costly and hence rarely achievable in practice. A much more relaxed and realistic assumption is that the server only operates under intermittent sampling, where the server samples and thereby obtains the system information at random times. In this paper, we formalize this relaxed and more realistic model and using the well-known longest-queue-first policy as a particular scheduling scheme, study the resulting impacts on system stability and performance due to intermittent system updates. Through extensive simulations, we identify the key message that has practical value: Longest-queue-first scheduling scheme performs well under intermittent sampling.