Joint scheduling and instantaneously decodable network coding

Danail Traskov; Muriel Médard; Parastoo Sadeghi; Ralf Koetter

doi:10.1109/GLOCOM.2009.5425315

Joint scheduling and instantaneously decodable network coding

Danail Traskov^*, Muriel Médard, Parastoo Sadeghi, Ralf Koetter

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

35 Citations (Scopus)

Abstract

We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog.

Original language	English
Title of host publication	GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference
DOIs	https://doi.org/10.1109/GLOCOM.2009.5425315
Publication status	Published - 2009
Event	2009 IEEE Global Telecommunications Conference, GLOBECOM 2009 - Honolulu, HI, United States Duration: 30 Nov 2009 → 4 Dec 2009

Publication series

Name	GLOBECOM - IEEE Global Telecommunications Conference

Conference

Conference	2009 IEEE Global Telecommunications Conference, GLOBECOM 2009
Country/Territory	United States
City	Honolulu, HI
Period	30/11/09 → 4/12/09

Access to Document

10.1109/GLOCOM.2009.5425315

Cite this

@inproceedings{c3fdcc65184b40f4ad3f4851312ad2c8,

title = "Joint scheduling and instantaneously decodable network coding",

abstract = "We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog.",

author = "Danail Traskov and Muriel M{\'e}dard and Parastoo Sadeghi and Ralf Koetter",

year = "2009",

doi = "10.1109/GLOCOM.2009.5425315",

language = "English",

isbn = "9781424441488",

series = "GLOBECOM - IEEE Global Telecommunications Conference",

booktitle = "GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference",

note = "2009 IEEE Global Telecommunications Conference, GLOBECOM 2009 ; Conference date: 30-11-2009 Through 04-12-2009",

}

Traskov, D, Médard, M, Sadeghi, P & Koetter, R 2009, Joint scheduling and instantaneously decodable network coding. in GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference., 5425315, GLOBECOM - IEEE Global Telecommunications Conference, 2009 IEEE Global Telecommunications Conference, GLOBECOM 2009, Honolulu, HI, United States, 30/11/09. https://doi.org/10.1109/GLOCOM.2009.5425315

TY - GEN

T1 - Joint scheduling and instantaneously decodable network coding

AU - Traskov, Danail

AU - Médard, Muriel

AU - Sadeghi, Parastoo

AU - Koetter, Ralf

PY - 2009

Y1 - 2009

N2 - We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog.

AB - We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog.

UR - http://www.scopus.com/inward/record.url?scp=77951605048&partnerID=8YFLogxK

U2 - 10.1109/GLOCOM.2009.5425315

DO - 10.1109/GLOCOM.2009.5425315

M3 - Conference contribution

SN - 9781424441488

T3 - GLOBECOM - IEEE Global Telecommunications Conference

BT - GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference

T2 - 2009 IEEE Global Telecommunications Conference, GLOBECOM 2009

Y2 - 30 November 2009 through 4 December 2009

ER -

Joint scheduling and instantaneously decodable network coding

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this