How to share network resources mathematically

A new approach for the network resource allocation problem by constructing randomized scheduling algorithms

Article  |  Spring 2014

The problem of dynamically allocating shared resources is fundamental to modern high-speed communication networks. The pioneering ALOHA algorithm was developed in the 1970s by Norman Abramson and his colleagues at the University of Hawaii to address this problem, and since then, it has long been the subject of a significant amount of research in computer science, electrical engineering, and operations research. Various types of scheduling solutions have been proposed and some of them are currently used in practice, conforming to IEEE standards.

Despite the long history and great importance of the problem, it is known to be notoriously difficult to design and analyze such scheduling algorithms that address this problem in an optimal way. Most mathematically-tractable algorithms cannot be implemented in practice due to their high algorithmic complexity and the need for coordinated scheduling decisions. On the other hand, practically-usable ones should be simple and distributed, where most such algorithms are known to be hard to analyze mathematically, i.e., they might not have optimal performance.

A priori, it is not even clear whether a simple, distributed algorithm of provable optimal performance does exist. This open question is resolved by a paper published on Jan. 2012 in the journal The Annals of Applied Probability by KAIST Assistant Professor Jinwoo Shin and MIT Associate Professor Devavrat Shah. This paper develops a novel approach to the resource allocation problem by constructing randomized scheduling algorithms for two representative network model classes: wireless networks and buffered circuit switched networks. These algorithms are simple and elegant and enable distributed implementation by requiring only local state information and few logical operations per scheduling decision. Moreover, it is shown that the algorithms are throughput optimal, meaning that their throughput performance is no worse than that of any scheduling algorithm. The result is mathematically proved in part by making a fascinating connection between the probability theory for stochastic networks and the computational theory for statistical estimations.

In particular, the paper relates the ergodicity of a Markovian dynamic on the space of schedules with mixing times of the Glauber dynamics on graphs. Relying on deep insight into the nature of optimal scheduling algorithms, together with creative technical developments, the paper establishes an outstanding result in both the areas of applied probability and communication. As evidenced by a growing body of related work, the ideas in this paper are broadly applicable and can be expected to generate significant momentum in the near future.