Algorithmically Efficient Networks

In this paper, we are interested in identifying algorithmically efficient networks. That is, determine minimal structural properties of a network that are sufficient to design simple, distributed algorithms to operate a communication network efficiently. The key algorithmic tasks in a communication network pertain scheduling (physical layer) and congestion control (network layer). Recent exciting progress has led to the understanding that good algorithmic solution for joint scheduling and congestion control can be obtained via combination of the “maximum weight scheduling” of Tassiulas and Ephremides (1992) along with a rate controller inspired by flow-level resource allocation model (e.g. Kelly, Maullo and Tan (1998)). Since the rate controller, by design, is simple and distributed, the key algorithmic challenge lies in designing efficient implementation of “maximum weight scheduling” in the network. In general, this involves solving a network-wide hard combinatorial optimization problem (maximum weight independent set) every time. And this problem, in general is known to be computationally hard. Motivated to find algorithmically efficient networks, we characterize a large class of network structure that allow for simple, distributed algorithm design for finding approximate maximum weight independent set (or schedule). Specifically, we establish that for any network structure with geometry (i.e. polynomial growth of network neighborhood), an algorithm, that determines schedule of each node based information obtained from constant-depth local neighborhood, achieves essentially optimal performance. Our algorithm allows for a smooth trade-off between overhead for computing schedule versus the performance. The key technical innovation is based on a novel graph decomposition algorithm, which we believe should be of interest in its own right. It should be noted that our results immediately apply to wireless network deployed in a geographic area as they naturally posses geometry. In general, a network designer may engineer the network so as to induce geometry and therefore allow for efficient algorithm design