Competitive Analysis of Constrained Queueing Systems

Abstract

We consider the classical problem of constrained queueing (or switched networks): There is a set of N queues to which unit sized packets arrive. The queues are interdependent, so that at any time step, only a subset of the queues can be activated. One packet from each activated queue can be transmitted, and leaves the system. The set of feasible subsets that can be activated, denoted S, is downward closed and is known in advance. The goal is to find a scheduling policy that minimizes average delay (or flow time) of the packets. The constrained queueing problem models several practical settings including packet transmission in wireless networks and scheduling cross-bar switches.

In this paper, we study this problem using the the competitive analysis: The packet arrivals can be adversarial and the scheduling policy only uses information about packets currently queued in the system. We present an online algorithm, that for any epsilon > 0, has average flow time at most O(R^2/epsilon^3*OPT+NR) when given (1+epsilon) speed, i.e., the ability to schedule (1+epsilon) packets on average per time step. Here, R is the maximum number of queues that can be simultaneously scheduled, and OPT is the average flow time of the optimal policy. This asymptotic competitive ratio O(R^3/epsilon^3) improves upon the previous O(N/epsilon^2) which was obtained in the context of multi-dimensional scheduling [Im/Kulkarni/Munagala, FOCS 2015]. In the full general model where N can be exponentially larger than R, this is an exponential improvement. The algorithm presented in this paper is based on Makespan estimates which is very different from that in [Im/Kulkarni/Munagala, FOCS 2015], a variation of the Max-Weight algorithm. Further, our policy is myopic, meaning that scheduling decisions at any step are based only on the current composition of the queues. We finally show that speed augmentation is necessary to achieve any bounded competitive ratio.