Super-Fast Delay Tradeoffs for Utility Optimal Fair Scheduling in Wireless Networks

We consider the fundamental delay tradeoffs for utility optimal scheduling in a general network with time-varying channels. A network controller acts on randomly arriving data and makes flow control, routing, and resource allocation decisions to maximize a fairness metric based on a concave utility function of network throughput. A simple set of algorithms are constructed that yield total utility within$O(1/V)$of the utility-optimal operating point, for any control parameter$V≫0$, with a corresponding end-to-end network delay that grows only logarithmically in$V$. This is the first algorithm to achieve such “super-fast” performance. Furthermore, we show that this is the best utility-delay tradeoff possible. This work demonstrates that the problem of maximizing throughput utility in a data network is fundamentally different than related problems of minimizing average power expenditure, as these latter problems cannot achieve such performance tradeoffs.