TY - GEN
T1 - Optimal distributed multicast routing using network coding
AU - Cui, Yi
AU - Xue, Yuan
AU - Nahrstedt, Klara
PY - 2007
Y1 - 2007
N2 - 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 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 his problem can be solved in a distributed fashion: each node akes 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 example in this paper is maximum lifetime routing in multi-hop wireless network.
AB - 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 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 his problem can be solved in a distributed fashion: each node akes 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 example in this paper is maximum lifetime routing in multi-hop wireless network.
UR - http://www.scopus.com/inward/record.url?scp=38549140745&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38549140745&partnerID=8YFLogxK
U2 - 10.1109/ICC.2007.595
DO - 10.1109/ICC.2007.595
M3 - Conference contribution
AN - SCOPUS:38549140745
SN - 1424403537
SN - 9781424403530
T3 - IEEE International Conference on Communications
SP - 3610
EP - 3615
BT - 2007 IEEE International Conference on Communications, ICC'07
T2 - 2007 IEEE International Conference on Communications, ICC'07
Y2 - 24 June 2007 through 28 June 2007
ER -