适用于线性网络编码关键路径的实时性算法  

Novel Real-time Algorithm for Critical Path of Linear Network Coding

作　　者：韩晓冬 高飞[2] 张立炜 HAN Xiao-dong;GAO Fei;ZHANG Li-wei(Information Center,Ministry of Science and Technology of the People’s Republic of China,Beijing 100862,China;School of Information and Electronics,Beijing Institute of Technology,Beijing 100081,China)

机构地区：[1]中华人民共和国科学技术部信息中心,北京100862 [2]北京理工大学信息与电子学院,北京100081

出　　处：《计算机科学》2020年第9期232-237,共6页Computer Science

基　　金：国家自然科学基金项目(61271258)。

摘　　要：如今,人类社会存储和交换的信息总量呈几何级数飞速增长,数据传输的吞吐量和实时性亟待提升。然而,现有的网络编码研究专注于提升吞吐量,忽略了实时性对大数据网络多路径传输性能的重大影响。为此,文中针对线性网络编码的最快到达问题,提出一种矩阵优化相乘的关键路径算法,以提高算法的实时性。具体地,使用抽象代数分析关键路径算法,构造了关键路径的交换环代数,并证明了最优子结构性质。仿真结果显示,随着网络节点个数n的增加,基于Strassen思想优化的关键路径算法能够极大地降低计算复杂度,成功将时间复杂度降至O(n 2.81 lg n),缩短了传播时延,提高了数据传输的实时性。当n>6时,相比基于重复平方关键路径算法,基于Strassen关键路径算法的时间开销的增长速率明显更低;特别地,当n=12时,基于Strassen关键路径算法的计算量约是基于重复平方关键路径算法的2/3,而其所需的时间开销约为后者的1/2。Nowadays,the amount of stored and exchanged information in human society is growing geometrically,and the throughput and real-time performance of data transmission need to be improved.While existing studies of network coding focus on improving throughput,the significant impacts of the real-time performance on multipath transmission in big data networks are ignored.This paper addresses the fastest arrival problem for linear network coding,and proposes a critical path computation algorithm with optimizatized matrix multiplication to improve the real-time performance.In particular,this paper uses the abstract algebra to analyze the critical path algorithm,constructs the commutative ring for the critical path,and proves the optimal substructure property.Simulation results show that the optimized algorithm significantly reduces the time complexity of critical path computation to O(n2.81lg n),shortens the propagation delays and improves the real-time performance.The time-cost growth rate based on the Strassen critical path algorithm is significantly lower than the repeated square path algorithm while n>6.Specially,while n=12,the computational complexity based on the Strassen critical path algorithm is approximately 2/3 compared to the repetitive squared critical path algorithm,and the time overhead required is about 1/2 compared to the latter.

关 键 词：关键路径 代数结构 交换环 矩阵乘法 线性网络编码 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]