Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding

Fang Zhao, Muriel Médard, Desmond Lun, Asuman Ozdaglar

Research output: Chapter in Book/Report/Conference proceedingChapter

3 Citations (Scopus)

Abstract

Network coding, introduced by Ahlswede et al. in their pioneering work [1], has generated considerable research interest in recent years, and numerous subsequent papers, e.g., [2-6], have built upon this concept. One of the main advantages of network coding over traditional routed networks is in the area of multicast, where common information is transmitted from a source node to a set of terminal nodes. Ahlswede et al. showed in [1] that network coding can achieve the maximum multicast rate, which is not achievable by routing alone. When coding is used to perform multicast, the problem of establishing minimum cost multicast connection is equivalent to two effectively decoupled problems: one of determining the subgraph to code over and the other of determining the code to use over that subgraph. The latter problem has been studied extensively in [5, 7-9], and a variety of methods have been proposed, which include employing simple random linear coding at every node. Such random linear coding schemes are completely decentralized, requiring no coordination between nodes, and can operate under dynamic conditions [10]. These papers, however, all assume the availability of dedicated network resources.

Original languageEnglish (US)
Title of host publicationNew Directions in Wireless Communications Research
PublisherSpringer US
Pages317-349
Number of pages33
ISBN (Print)9781441906724
DOIs
StatePublished - Dec 1 2009

Fingerprint

Network coding
Costs
Availability

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this

Zhao, F., Médard, M., Lun, D., & Ozdaglar, A. (2009). Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding. In New Directions in Wireless Communications Research (pp. 317-349). Springer US. https://doi.org/10.1007/978-1-4419-0673-1_12
Zhao, Fang ; Médard, Muriel ; Lun, Desmond ; Ozdaglar, Asuman. / Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding. New Directions in Wireless Communications Research. Springer US, 2009. pp. 317-349
@inbook{1d45b31bdb3e4b3ca9583f75b30a5bb6,
title = "Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding",
abstract = "Network coding, introduced by Ahlswede et al. in their pioneering work [1], has generated considerable research interest in recent years, and numerous subsequent papers, e.g., [2-6], have built upon this concept. One of the main advantages of network coding over traditional routed networks is in the area of multicast, where common information is transmitted from a source node to a set of terminal nodes. Ahlswede et al. showed in [1] that network coding can achieve the maximum multicast rate, which is not achievable by routing alone. When coding is used to perform multicast, the problem of establishing minimum cost multicast connection is equivalent to two effectively decoupled problems: one of determining the subgraph to code over and the other of determining the code to use over that subgraph. The latter problem has been studied extensively in [5, 7-9], and a variety of methods have been proposed, which include employing simple random linear coding at every node. Such random linear coding schemes are completely decentralized, requiring no coordination between nodes, and can operate under dynamic conditions [10]. These papers, however, all assume the availability of dedicated network resources.",
author = "Fang Zhao and Muriel M{\'e}dard and Desmond Lun and Asuman Ozdaglar",
year = "2009",
month = "12",
day = "1",
doi = "10.1007/978-1-4419-0673-1_12",
language = "English (US)",
isbn = "9781441906724",
pages = "317--349",
booktitle = "New Directions in Wireless Communications Research",
publisher = "Springer US",
address = "United States",

}

Zhao, F, Médard, M, Lun, D & Ozdaglar, A 2009, Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding. in New Directions in Wireless Communications Research. Springer US, pp. 317-349. https://doi.org/10.1007/978-1-4419-0673-1_12

Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding. / Zhao, Fang; Médard, Muriel; Lun, Desmond; Ozdaglar, Asuman.

New Directions in Wireless Communications Research. Springer US, 2009. p. 317-349.

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding

AU - Zhao, Fang

AU - Médard, Muriel

AU - Lun, Desmond

AU - Ozdaglar, Asuman

PY - 2009/12/1

Y1 - 2009/12/1

N2 - Network coding, introduced by Ahlswede et al. in their pioneering work [1], has generated considerable research interest in recent years, and numerous subsequent papers, e.g., [2-6], have built upon this concept. One of the main advantages of network coding over traditional routed networks is in the area of multicast, where common information is transmitted from a source node to a set of terminal nodes. Ahlswede et al. showed in [1] that network coding can achieve the maximum multicast rate, which is not achievable by routing alone. When coding is used to perform multicast, the problem of establishing minimum cost multicast connection is equivalent to two effectively decoupled problems: one of determining the subgraph to code over and the other of determining the code to use over that subgraph. The latter problem has been studied extensively in [5, 7-9], and a variety of methods have been proposed, which include employing simple random linear coding at every node. Such random linear coding schemes are completely decentralized, requiring no coordination between nodes, and can operate under dynamic conditions [10]. These papers, however, all assume the availability of dedicated network resources.

AB - Network coding, introduced by Ahlswede et al. in their pioneering work [1], has generated considerable research interest in recent years, and numerous subsequent papers, e.g., [2-6], have built upon this concept. One of the main advantages of network coding over traditional routed networks is in the area of multicast, where common information is transmitted from a source node to a set of terminal nodes. Ahlswede et al. showed in [1] that network coding can achieve the maximum multicast rate, which is not achievable by routing alone. When coding is used to perform multicast, the problem of establishing minimum cost multicast connection is equivalent to two effectively decoupled problems: one of determining the subgraph to code over and the other of determining the code to use over that subgraph. The latter problem has been studied extensively in [5, 7-9], and a variety of methods have been proposed, which include employing simple random linear coding at every node. Such random linear coding schemes are completely decentralized, requiring no coordination between nodes, and can operate under dynamic conditions [10]. These papers, however, all assume the availability of dedicated network resources.

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

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

U2 - 10.1007/978-1-4419-0673-1_12

DO - 10.1007/978-1-4419-0673-1_12

M3 - Chapter

AN - SCOPUS:84891521874

SN - 9781441906724

SP - 317

EP - 349

BT - New Directions in Wireless Communications Research

PB - Springer US

ER -

Zhao F, Médard M, Lun D, Ozdaglar A. Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding. In New Directions in Wireless Communications Research. Springer US. 2009. p. 317-349 https://doi.org/10.1007/978-1-4419-0673-1_12