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(n^2.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