Scheduling for network coded multicast: a distributed approach
We address the problem of maximizing the throughput for network coded multicast traffic in a wireless network in the bandwidth limited regime. For the joint scheduling and subgraph selection problem, we model valid network configurations as stable sets in an appropriately defined conflict graph. The...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/59368 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826197788109570048 |
|---|---|
| author | Heindlmaier, Michael Traskov, Danail Koetter, Ralf Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Heindlmaier, Michael Traskov, Danail Koetter, Ralf Medard, Muriel |
| author_sort | Heindlmaier, Michael |
| collection | MIT |
| description | We address the problem of maximizing the throughput for network coded multicast traffic in a wireless network in the bandwidth limited regime. For the joint scheduling and subgraph selection problem, we model valid network configurations as stable sets in an appropriately defined conflict graph. The problem formulation separates the combinatorial difficulty of scheduling from the arising optimization problem and facilitates the application of less complex scheduling policies. Lagrangian relaxation gives rise to two subproblems, a multiple shortest path, and a maximum weight stable set (MWSS) problem. For the latter we propose a greedy approach which can be computed in a distributed fashion, thus yielding a fully decentralized algorithm. Simulation results show that our technique is nearly optimal and outperforms heuristics such as orthogonal scheduling by a large margin. |
| first_indexed | 2024-09-23T10:53:28Z |
| format | Article |
| id | mit-1721.1/59368 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:53:28Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/593682022-09-30T23:44:46Z Scheduling for network coded multicast: a distributed approach Heindlmaier, Michael Traskov, Danail Koetter, Ralf Medard, Muriel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel Medard, Muriel We address the problem of maximizing the throughput for network coded multicast traffic in a wireless network in the bandwidth limited regime. For the joint scheduling and subgraph selection problem, we model valid network configurations as stable sets in an appropriately defined conflict graph. The problem formulation separates the combinatorial difficulty of scheduling from the arising optimization problem and facilitates the application of less complex scheduling policies. Lagrangian relaxation gives rise to two subproblems, a multiple shortest path, and a maximum weight stable set (MWSS) problem. For the latter we propose a greedy approach which can be computed in a distributed fashion, thus yielding a fully decentralized algorithm. Simulation results show that our technique is nearly optimal and outperforms heuristics such as orthogonal scheduling by a large margin. United States. Defense Advanced Research Projects Agency (DARPA) (subcontract No. 18870740-37362-C) European Union. NEWCOM++ 2010-10-15T15:03:11Z 2010-10-15T15:03:11Z 2009-12 2009-11 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5626-0 INSPEC Accession Number: 11036762 http://hdl.handle.net/1721.1/59368 Heindlmaier, M. et al. “Scheduling for Network Coded Multicast: A Distributed Approach.” GLOBECOM Workshops, 2009 IEEE. 2009. 1-6. © Copyright 2010 IEEE https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/GLOCOMW.2009.5360767 2009 IEEE GLOBECOM Workshops Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Heindlmaier, Michael Traskov, Danail Koetter, Ralf Medard, Muriel Scheduling for network coded multicast: a distributed approach |
| title | Scheduling for network coded multicast: a distributed approach |
| title_full | Scheduling for network coded multicast: a distributed approach |
| title_fullStr | Scheduling for network coded multicast: a distributed approach |
| title_full_unstemmed | Scheduling for network coded multicast: a distributed approach |
| title_short | Scheduling for network coded multicast: a distributed approach |
| title_sort | scheduling for network coded multicast a distributed approach |
| url | http://hdl.handle.net/1721.1/59368 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT heindlmaiermichael schedulingfornetworkcodedmulticastadistributedapproach AT traskovdanail schedulingfornetworkcodedmulticastadistributedapproach AT koetterralf schedulingfornetworkcodedmulticastadistributedapproach AT medardmuriel schedulingfornetworkcodedmulticastadistributedapproach |