3:30 pm, Seminar Hall
Performance Guarantees of Distributed Algorithms Using Graph and Hypergraph Interference Models
A general open problem in networking is: what are the fundamental limits to the performance that is achievable with some given amount of resources. More specifically, if each node in a network has information only up to d hops away, then what are the limits to performance? We study this problem for wireless networks under the primary interference model, where each communication link has a minimum bandwidth requirement. Wireless links in the same vicinity contend for the shared wireless medium, and this interference is modeled by a conflict graph or a hypergraph. The worst-case performance of admission control and scheduling algorithms is the largest factor by which the network can overestimate the resources required to satisfy a given set of flow rates.
We propose a distance-$d$ distributed algorithm for this problem. We show that if each node knows the demands of all links in a ball of radius d centered at the node, then there is a distributed algorithm whose performance is away from that of an optimal, centralized algorithm by a factor of at most (2d + 3)/(2d + 2). This bound on performance is independent of the structure of the network graph. The tradeoff between performance and complexity of the distributed algorithm is also analyzed. We analyze the performance of a greedy, distributed scheduling algorithm called maximal scheduling, for both graph and hypergraph interference models, and show improvement over previous bounds.