• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
Date
2012
Dewey
Principes généraux des mathématiques
Sujet
Local Pooling; Greedy Maximal Scheduling; Graph Theory
Journal issue
IEEE/ACM Transactions on Networking
Volume
20
Number
1
Publication date
2012
Article pages
163-176
Publisher
Institute of Electrical and Electronics Engineers
DOI
http://dx.doi.org/10.1109/TNET.2011.2157831
URI
https://basepub.dauphine.fr/handle/123456789/8168
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Birand, Berk
Chudnovsky, Maria
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Seymour, Paul
Zussman, Gil
Zwols, Yori
Type
Article accepté pour publication ou publié
Abstract (EN)
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 $7times 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.