Reliability evaluation of a multicast over coded packet networks

被引:0
作者
M. A. Raayatpanah
P. M. Pardalos
机构
[1] Kharazmi University,Department of Mathematics
[2] University of Florida,Center for Applied Optimization, Department of Industrial and Systems Engineering
来源
Journal of Combinatorial Optimization | 2018年 / 35卷
关键词
Communication network; Network coding; Network optimization; Multicast; Reliability;
D O I
暂无
中图分类号
学科分类号
摘要
Network coding is a generalization of conventional routing methods that allows a network node to code information flows before forwarding them. While it has been theoretically proved that network coding can achieve maximum network throughput, theoretical results usually do not consider the stochastic nature in information processing and transmission, especially when the capacity of each arc becomes stochastic due to failure, attacks, or maintenance. Hence, the reliability measurement of network coding becomes an important issue to evaluate the performance of the network under various system settings. In this paper, we present analytical expressions to measure the reliability of multicast communications in coded networks, where network coding is most promising. We define the probability that a multicast rate can be transmitted through a coded packet network under a total transmission cost constraint as the reliability metric. To do this, we first introduce an exact mathematical formulation to construct multicast connections over coded packet networks under a limited transmission cost. We then propose an algorithm based on minimal paths to calculate the reliability measurement of multicast connections and analyze the complexity of the algorithm. Our results show that the reliability of multicast routing with network coding improved significantly compared to the case of multicast routing without network coding.
引用
收藏
页码:921 / 940
页数:19
相关论文
共 82 条
[1]  
Ahlswede R(2000)Network information flow IEEE Trans Inf Theory 46 1204-1216
[2]  
Cai N(1999)A heuristic technique for generating minimal path and cutsets of a general network Comput Ind Eng 36 45-55
[3]  
Li SYR(2013)Analysis of tree-based multicast routing in wireless sensor networks with varying network metrics Int J Commun Syst 26 1327-1340
[4]  
Yeung RW(2009)Wireless broadcast using network coding IEEE Trans Vehicular Technol 58 914-925
[5]  
Al-Ghanim Amjed M(2014)Convergence study of decentralized min-cost subgraph algorithms for multicast in coded networks IEEE Trans Inf Theory 60 410-421
[6]  
Bala Krishna M(2011)Optimal sub-graph selection over coded networks with delay and limited-size buffering the authors consider IET Commun 5 1497-1505
[7]  
Doja MN(2017)A robust optimization approach for multicast network coding under uncertain link costs Optim Lett 11 429-444
[8]  
Dong N(1985)Reliability bounds for multistate systems with multistate components Oper Res 33 153-160
[9]  
Tuan T(2015)Improving transmission reliability in wireless sensor networks using network coding Telecommun Syst 59 509-521
[10]  
Thinh N(2005)Polynomial time algorithms for multicast network code construction IEEE Trans Inf Theory 51 1973-1982