Paper Info
Title
Network Coding in Minimal Multicast Networks
Abstract
We investigate the network coding problem in a certain class of minimal multicast networks. In a multicast coding network, a source S needs to deliver h symbols, or packets, to a set of destinations T over an underlying communication network modeled by a graph G. A coding network is said to be h-minimal if it can deliver h symbols from S to the destination nodes, while any proper subnetwork of G can deliver at most h — 1 symbols to the set of destination nodes. This problem is motivated by the requirement to minimize the amount of network resources allocated for a multicast connections. We show that surprisingly, minimal multicast networks have unique properties that distinguish them from the general case of multicast networks. In particular, we show that it is possible to determine whether a 2-minimal network has a routing solution (i.e., a solution without encoding nodes) in polynomial time, while this problem is NP-hard in general. In addition, we show that if a 2-minimal network is planar, then the minimum size of the required field for linear network codes is at most 3. Also, we investigate several structural properties of 2-minimal networks and generalize our results for h > 2.
Year
DOI
Venue
2006
10.1109/ITW.2006.1633835
Punta del Este, Uruguay
Keywords
Field
DocType
network coding,galois fields,polynomial time,resource allocation,polynomials,communication networks,encoding,routing,intelligent networks,resource management
Linear network coding,Source-specific multicast,Protocol Independent Multicast,Multicast address,Computer science,Xcast,Computer network,Theoretical computer science,Pragmatic General Multicast,Distance Vector Multicast Routing Protocol,Multicast,Distributed computing
Conference
ISBN
Citations 
PageRank 
1-4244-0036-8
5
0.61
References 
Authors
8
3
Name
Order
Citations
PageRank
Salim Y. El Rouayheb118818.00
Georghiades, C.N.283795.26
Alexander Sprintson347230.84