• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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

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, 1, p. 163-176. 10.1109/TNET.2011.2157831

Type
Article accepté pour publication ou publié
Date
2012
Journal name
IEEE/ACM Transactions on Networking
Volume
20
Number
1
Publisher
Institute of Electrical and Electronics Engineers
Pages
163-176
Publication identifier
10.1109/TNET.2011.2157831
Metadata
Show full item record
Author(s)
Birand, Berk

Chudnovsky, Maria

Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Seymour, Paul

Zussman, Gil

Zwols, Yori
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.
Subjects / Keywords
Local Pooling; Greedy Maximal Scheduling; Graph Theory

Related items

Showing items related by title and author.

  • Thumbnail
    Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory 
    Zussman, Gil; Seymour, Paul; Zwols, Yori; Birand, Berk; Ries, Bernard; Chudnovsky, Maria (2010) Communication / Conférence
  • Thumbnail
    Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part I. Basic graphs 
    Ries, Bernard; Chudnovsky, Maria; Zwols, Yori (2011) Article accepté pour publication ou publié
  • Thumbnail
    Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part II. Nontrivial strip-structures 
    Zwols, Yori; Ries, Bernard; Chudnovsky, Maria (2011) Article accepté pour publication ou publié
  • Thumbnail
    Optimal edge-coloring with edge rate constraints 
    Dereniowski, Dariusz; Kubiak, W.; Ries, Bernard; Zwols, Yori (2013) Article accepté pour publication ou publié
  • Thumbnail
    On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs 
    Golumbic, Martin Charles; Ries, Bernard (2013) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo