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

Abstract

Efficient operation of wireless networks and switches requires using simple 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. 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 extended abstract, we characterize all the network graphs in which Local Pooling holds under primary interference constraints. We then 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, we demonstrate that using graph theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms. The proofs of the results have been omitted for brevity and can be found in [1].

Original languageEnglish (US)
Title of host publicationProc. 2010 ACM Workshop on Wireless of the Students, by the Students, for the Students, S3 '10, Co-located with MobiCom'10 and 11th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing,MobiHoc'10
PublisherAssociation for Computing Machinery
Pages17-19
Number of pages3
ISBN (Print)9781450301442
DOIs
StatePublished - Jan 1 2010
Event2010 ACM Workshop on Wireless of the Students, by the Students, for the Students, S3 '10 - Chicago, IL, United States
Duration: Sep 20 2010Sep 24 2010

Publication series

NameProceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM

Other

Other2010 ACM Workshop on Wireless of the Students, by the Students, for the Students, S3 '10
CountryUnited States
CityChicago, IL
Period9/20/109/24/10

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Algorithms
  • Design
  • Performance

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 Proc. 2010 ACM Workshop on Wireless of the Students, by the Students, for the Students, S3 '10, Co-located with MobiCom'10 and 11th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing,MobiHoc'10 (pp. 17-19). (Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM). Association for Computing Machinery. https://doi.org/10.1145/1860039.1860045