Analyzing the performance of greedy maximal scheduling via local pooling and graph theory

Berk Birand, Maria Chudnovsky, Bernard Ries, Paul Seymour, Gil Zussman, Yori Zwols

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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 (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 7xn, 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.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
DOIs
StatePublished - Jun 15 2010
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2010
CountryUnited States
CitySan Diego, CA
Period3/14/103/19/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Keywords

  • Graph theory
  • Local pooling
  • Scheduling
  • Switches
  • Throughput maximization
  • Wireless networks

Fingerprint Dive into the research topics of 'Analyzing the performance of greedy maximal scheduling via local pooling and graph theory'. Together they form a unique fingerprint.

  • Cite this

    Birand, B., Chudnovsky, M., Ries, B., Seymour, P., Zussman, G., & Zwols, Y. (2010). Analyzing the performance of greedy maximal scheduling via local pooling and graph theory. In 2010 Proceedings IEEE INFOCOM [5462046] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2010.5462046