基于图搜索的网络路由算法的复杂度分析

On the Complexities of Routing Algorithmsin Computer Network

本文以图搜索问题作为计算机网络路由选择问题的数学模型，探讨了路由算法的几个基本性质。对于网络路由算法的空间耗费，本文的主要结论是，（１）．不可能有最大空间耗费小于０（Ｍ）的路由算法，（Ｍ）是网络中所含的ＩＭＰ个数；（２）．不存在普遍最优的可采纳路由算法。

Modelling the routing problem of computer network by graph search,some general properties of routing algorithms are discussed in this paper. For spacecomplexies of routing algorithms, our conclusions are: (1). there exists no such arouting algorithm whose worst-case space complexity is less than O(M), where Mis the number of IMPs in the considered network, (2). there exists no general bestrouting algorithm.