Skip to main content

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

## Author(s): Birand, Berk; Chudnovsky, Maria; Ries, Bernard; Seymour, Paul D.; Zussman, Gil; et al

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1vt0f
 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, or GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e. g., 50% throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100% throughput. Moreover, in networks in which the sigma-Local Pooling conditions hold, GMS achieves sigma% throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks, GMS achieves 100% throughput). This leads to a linear-time algorithm for identifying Local-Pooling-satisfying graphs. Moreover, by using similar graph-theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 x n, GMS is guaranteed to achieve 66% throughput, thereby improving upon the previously known 50% lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies, its performance could be very bad. Overall, the paper demonstrates that using graph-theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms. Publication Date: Feb-2012 Electronic Publication Date: 1-Aug-2011 Citation: Birand, Berk, Chudnovsky, Maria, Ries, Bernard, Seymour, Paul, Zussman, Gil, Zwols, Yori. (2012). Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory. IEEE-ACM TRANSACTIONS ON NETWORKING, 20 (163 - 176. doi:10.1109/TNET.2011.2157831 DOI: doi:10.1109/TNET.2011.2157831 ISSN: 1063-6692 Pages: 163 - 176 Type of Material: Journal Article Journal/Proceeding Title: IEEE-ACM TRANSACTIONS ON NETWORKING Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.