计算机网络路由算法的理论与进展

Theory and progress of computer network routing algorithm

为了解大型网络的路由算法的理论基础和研究动向,分析计算机网络模型和网络拓扑的特点,得出运筹学中的图论、排队论和动态规划理论是路由计算的基础。图论中最短路径树的理论是路由算法的重要理论。排队论中的M/M/1/K和M/M/m排队是比较接近网络实际的延迟计算模型。按照动态规划思想进行路由计算的方法,比枚举算法计算量小且能够获得最佳路径。静态路由算法是动态路由算法的基础,为了提高动态路由算法的实用性,网络动态信息检测技术和新网络模型研究将是今后一个时期的研究热点问题。

In order to comprehend the research tendency about the routing algorithm of large networks,analyzing the characteristic of computer network model and computer network topology,it is pointed out that the graph theory,queuing theory and dynamic programming are the basis of routing calculation in this article. The shortest path theory is the main theory for the study of routing algorithm. The M / M /1 / k and M / M / m queue is the delay calculation models which approximate the real network. The method that according to Dynamic programming is faster than enumeration and could obtain the best path. Static routing algorithm is the base of dynamic algorithm. For the sake of enhancing the practicability of dynamic routing algorithm,the research of network dynamic information detecting techniques and new network model will be the hot spots in the next period.