Optimal Distributed Multicast Routing using Network Coding: Theory and Applications

Cui, Yi; Xue, Yuan; Nahrstedt, Klara

Permalink

https://hdl.handle.net/2142/10897 Copy

Description

Title

Optimal Distributed Multicast Routing using Network Coding: Theory and Applications

Author(s)

• Cui, Yi
• Xue, Yuan
• Nahrstedt, Klara

Issue Date

2004-08

Keyword(s)

Networking

Abstract

Multicast is an important communication paradigm, also a problem well known for its difficulty (NP-completeness) to achieve certain optimization goals, such as minimum network delay. Recent advances in network coding\cite{ahlswede,koetter} has shed a new light onto this problem. In network coding, forwarding nodes can perform arbitrary operations on data received, other than forwarding or replicating, to enhance throughput of a multicast session. In this paper, we show that with the aid of network coding, the once intractable optimal multicast routing problem becomes tractable. In this problem, given a set of multicast sessions and their traffic demands, one tries to route the multicast traffic regarding various objectives, such as to minimize overall delay, or to maximize the battery life of each node. We further show that this problem can be solved in a distributed fashion: each node makes its own routing decisions based on periodic updating information from neighboring nodes. We prove that starting from any initial routing assignment, the proposed distributed routing algorithm is able to converge to the point where the value of the objective function is optimized. Our solution can be fit into a variety of networks to achieve different optimization goals. The examples in this paper include minimum delay routing in overlay multicast, and maximum lifetime routing in multi-hop wireless network.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10897

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections