TY - JOUR
T1 - Analyzing the performance of greedy maximal scheduling via local pooling and graph theory
AU - Birand, Berk
AU - Chudnovsky, Maria
AU - Ries, Bernard
AU - Seymour, Paul
AU - Zussman, Gil
AU - Zwols, Yori
N1 - Funding Information:
Manuscript received April 17, 2010; revised February 14, 2011; accepted May 11, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor I. Keslassy. Date of publication August 01, 2011; date of current version February 15, 2012. This work was supported in part by the NSF under Grants DMS-0758364, CNS-0916263, and CNS-10-54856; the CIAN NSF ERC under Grant EEC-0812072; the FNR under Grant TR-PDR BFR08-17; the ONR under Grant N00014-01-1-0608; and an IBM Ph.D. Fellowship. A preliminary version of this paper was presented at the IEEE International Conference on Computer Communications (INFOCOM), San Diego, CA, Mar. 15–19, 2010.
PY - 2012/2
Y1 - 2012/2
N2 - 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 σ-Local Pooling conditions hold, GMS achieves σ% 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 × 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.
AB - 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 σ-Local Pooling conditions hold, GMS achieves σ% 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 × 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.
KW - Graph theory
KW - Local Pooling (LoP)
KW - Scheduling
KW - Switches
KW - Throughput maximization
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=84857363947&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84857363947&partnerID=8YFLogxK
U2 - 10.1109/TNET.2011.2157831
DO - 10.1109/TNET.2011.2157831
M3 - Article
AN - SCOPUS:84857363947
SN - 1063-6692
VL - 20
SP - 163
EP - 176
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 1
ER -