Computer Science ›› 2020, Vol. 47 ›› Issue (9): 232-237.doi: 10.11896/jsjkx.190800023

• Computer Network • Previous Articles     Next Articles

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

HAN Xiao-dong1,2, GAO Fei2, ZHANG Li-wei1   

  1. 1 Information Center,Ministry of Science and Technology of the People’s Republic of China,Beijing 100862,China
    2 School of Information and Electronics,Beijing Institute of Technology,Beijing 100081,China
  • Received:2019-08-06 Published:2020-09-10
  • About author:HAN Xiao-dong,born in 1983,Ph.D,engineer.Her main research interests include network coding and network security.
    GAO Fei,born in 1959,Ph.D,professor.Her main research interests include wireless communication technology,image signal processing and network security.
  • Supported by:
    National Natural Science Foundation of China (61271258).

Abstract: 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.81lgn),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.

Key words: Algebraic structure, Critical path, Exchange ring, Linear network coding, Matrix multiplication

CLC Number: 

  • TP301.6
[1] AKPAKWU G A,SILVA B J,HANCKE G P,et al.A Survey on 5G Networks for the Internet of Things:Communication Technologies and Challenges [J].IEEE Access,2018,6:3619-3647.
[2] FANG D F,QIAN Y,HU Q Y.Security for 5G Mobile Wireless Networks [J].IEEE Access,2018,6:4850-4874.
[3] CUI J X,DONG G L,LI H T,et al.Prospect of Application of Physical Layer Network Coding in Deep Space Communication [C]//2016 IEEE International Conference of Online Analysis and Computing Science (ICOACS).2016:131-134.
[4] JARZYNA M,ZWOLINSKI W,JACHURA M,et al.Optimi-zing deep-space optical communication under power constraints[C]//Free-Space Laser Communication and Atmospheric Propagation XXX. International Society for Optics and Photonics,2018.
[5] VAN J,SMETTERS D K,THORNTON J D,et al.Networking Named Content [C]//CoNEXT’09 Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.New York:ACM,2009:1-12.
[6] CAO J X,PEI D,ZHANG X P,et al.Fetching Popular Data from the Nearest Replica in NDN [C]//2016 25th International Conference on Computer Communication and Networks (ICCCN).2016:1-9.
[7] ZHAO Z F,TAN X B,SU J X.Adaptive traffic scheduling via network coding in NDN [C]//2016 35th Chinese Control Conference (CCC).2016:7200-7205.
[8] AUBRY E,SILVERSTON T,CHRISMENT I.Green growth in NDN:Deployment of content stores [C]//2016 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN).2016:1-6.
[9] ALSHWEDE R,CAI N,LI S Y R,et al.Network information flow [J].IEEE Transactionson Information Theory,2000,46(4):1204-1216.
[10] HO T,MÉDARD M,KOETTER R,et al.A Random LinearNetwork Coding Approach to Multicast [J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.
[11] HU G,XU K,XU Y.Deadline-Aware Opportunistic NetworkCoding for Multi-Relay-Aided Single-Source Single-Destination.
Network [J].IEEE Communications Letters,2017,21(10):2282-2285.
[12] ZHU J.Exploiting Opportunistic Network Coding for Improving Wireless Reliability Against Co-Channel Interference [J] . IEEE Transactions on Industrial Informatics,2016,12(5):1692-1701.
[13] ZOHDY M,ELBATT T,NAFIE M.Maximum Throughput Opportunistic Network Coding in Two-Way Relay Networks [C]//IEEE International Conference on Communication.2015:913-918.
[14] AMIRI M M,GUNDUZ D.Fundamental Limits of Coded Caching:Improved Delivery Rate-Cache Capacity Tradeoff [J].IEEE Transactions on Communications,2017,65(2):806-815.
[15] JOHARI S,OJHA A.Quickest path problems in stochastic-flow networks with time constraint:A fast and reliable solution [C]//2013 3rd IEEE International Advance Computing Conference (IACC).2013:322-325.
[16] SEGARRA S,MARQUES A G,RIBEIRO A.Optimal Graph-Filter Design and Applications to Distributed Linear Network Operators [J].IEEE Transactions on Signal Processing,2017,65(15):4117-4131.
[17] ETZION T,STORME L.Galois geometries and coding theory [J].Designs,Codes and Cryptography,2016,78(1):311-350.
[18] CORMEN T H,LEISERSON C E,et al.Introduction to Algorithm [M].MIT Press,2005.
[19] HAN X D,GAO F,WANG A H.Network Coding Transmission Performance Under the NDN Protocol [J].Transactions of Beijing Institute of Technology,2017,37(5):506-510.
[20] VASSILEVSKA V.Efficient Algorithms for Path Problems[D].Pittsburgh:Carnegie Mellon University,2008.
[21] AHO A V,HOPCROFT J E,ULLMAN J D.The Design and Analysis of Computer Algorithms [M].Addision-Wesley Publishing Company,1974.
[1] HU Rong, YANG Wang-dong, WANG Hao-tian, LUO Hui-zhang, LI Ken-li. Parallel WMD Algorithm Based on GPU Acceleration [J]. Computer Science, 2021, 48(12): 24-28.
[2] YANG Fei, MA Yu-chun, HOU Jin and XU Ning. Research on Acceleration of Matrix Multiplication Based on Parallel Scheduling on MPSoC [J]. Computer Science, 2017, 44(8): 36-41.
[3] HAN Yao-jun. Method for Finding Critical Paths Based on Concurrent Reachable Marking Graph with Tags [J]. Computer Science, 2016, 43(11): 121-125.
[4] GUO Ya-qiong and SONG Jian-xin. Optimal Task-level Scheduling Based on Multimedia Applications in Cloud [J]. Computer Science, 2015, 42(Z11): 413-416.
[5] YIN Meng-jia, XU Xian-bin, XIONG Zeng-gang and ZHANG Tao. Quantitative Performance Analysis Model of Matrix Multiplication Based on GPU [J]. Computer Science, 2015, 42(12): 13-17.
[6] XING Lu,LIANG Hua-guo,YAN Lu-ming,ZHANG Li-na and YU Tian-song. Aging Path Reduction Algorithm for Type of Logic Gates [J]. Computer Science, 2014, 41(5): 24-26.
[7] XIANG Lin-hong,CHEN Yu-wen and ZHANG Yu-lin. High Order Matrix Multiplication by MapReduce Algorithm Based on Hadoop Platform [J]. Computer Science, 2013, 40(Z6): 96-98.
[8] . Algorithm for Finding the Critical Paths Based on Petri Net [J]. Computer Science, 2012, 39(6): 201-203.
[9] LI Lei, HAN Wen-hao. Implementation of Pipeline Structure on FPGA for SHA-1 [J]. Computer Science, 2011, 38(7): 58-60.
[10] ZENE Bin,AN Hong,WANG Li. Profile Information and Critical Path Length Based Software Fanout Tree Generation Algorithm [J]. Computer Science, 2010, 37(3): 248-252.
[11] XIE Zhi-qiang,ZHANG Lei,YANG Jing. Integrated Scheduling Algorithm of Complex Product Based on Scheduling Long-path [J]. Computer Science, 2010, 37(2): 150-153.
[12] LI Xun, LI Peng ,GU Qing ,CHEN Dao-Xu (State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093). [J]. Computer Science, 2008, 35(2): 301-302.
[13] WANG Zhen-Ming,DU Zhi-Hui (Department of Computer Science and Technology, Tsinghua University, Beijing, 100084). [J]. Computer Science, 2006, 33(4): 80-84.
Full text



No Suggested Reading articles found!