Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory

Presented on 12 Jan at ICORES 2015

Keynote Lecturer: Bernard Ries

Abstract: Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput. However, it was recently shown that in networks in which some specific conditions (called the Local Pooling conditions) are satisfied, GMS achieves 100% throughput. Therefore, it is of interst to know exactly which networks satisfy these conditions, i.e. to identify the specific network topologies that satisfy the Local Pooling conditions. Using structural graph theory, we provide the first characterization of all the network graphs in which Local Pooling conditions hold under primary interference constraints (in these networks GMS achieves 100% throughput). This leads to a linear time algorithm for identifying Local Pooling-satisfying graphs. This is joint work with Berk Birand, Maria Chudnovsky, Paul Seymour, Gil Zussman and Yori Zwols.