摘要
建立最大带宽路径一直是网络路由研究 ,尤其是在最近的网络 Qo S路由研究中的基本问题 .在以往的文献中 ,有人提出了利用修改的 Dijkstra算法或修改的 Bellm an- Ford算法来构建最大带宽路径 .该文给出了一个简单的证明 ,指出了最大生成树与最大带宽路径之间的特殊关系 ,证明了可以使用修改的 Kruskal算法来构建最大带宽路径 .文中给出了修改的 Kruskal算法 ,并且与已有的 Dijkstra算法作了性能上的比较 .尽管从理论上说 ,Dijstra算法和 Kruskal算法的时间复杂度具有同样的阶 ,但在多种不同网络结构上的模拟测试结果表明 ,用 Kruskal算法构建最大带宽路径的实际运行比 Dijkstra算法至少要快 3倍 ,而且在实现上比 Dijkstra算法更简单、灵活 .
Constructing maximum bandwidth paths has been a basic operation in the study of network routing,in particular in the recent study of network QoS routing. In the literature,it has been proposed that a maximum bandwidth path be constructed by a modified Dijkstra's algorithm or by a modified Bellman-Ford algorithm. In this short note,we present a very simple proof to show an interesting relation between a maximum spanning tree and a maximum bandwidth path. According to this proof,the Max-Bandwidth path problem can be solved based on a maximum spanning tree of the network. This observation suggests that the Max-Bandwidth path problem can be solved using Kruskal's algorithm,which is a well-known algorithm for minimum spanning tree construction. A modified Kruskal's algorithm for Max-Bandwidth path is given in this paper and compared with the modified Dijkstra's algorithm being suggested before. Although Dijkstra's algorithm and Kruskal's algorithm have the same time complexity asymptotically,Kruskal's algorithm takes a simpler form and runs much faster practically. We have programmed both algorithms and compared their performance based on a variety of network topologies. From the simulation results,we can see that for low link density networks such as mesh network,hypercube networks,networks of link density 1% and networks of link density 5%,Kruskal's algorithm in general is at least five times as fast as Dijkstra's algorithm. Even on dense networks of link density 40%,Kruskal's algorithm is still more than three times as fast as Dijkstra's algorithm. Besides the advantage of running time, we also indicate other advantages of our approach over the traditional approaches. Our results should have significant impact on the research and implementation of network applications.
出处
《计算机学报》
EI
CSCD
北大核心
2002年第10期1116-1120,共5页
Chinese Journal of Computers
基金
海外青年学者合作研究基金 ( 6 992 82 0 1)
长江学者奖励基金资助
