第k条最大可用带宽路径算法

该文提出了无环路的第k条最大可用带宽路径算法．由于具有凹性的带宽和具有加性的代价存在本质区别，第k条最大可用带宽路径算法不能通过简单修改第k条最短路径算法得到．该文结合两个新定义的路径操作和修改的二重扫除算法完成第k条最大可用带宽路径算法，并证明其正确性、无环性和具有多项式复杂性，最后给出实例并讨论算法实际应用．该文解决了基于带宽度量的路由算法中一类很基本的问题；因算法采用能反映网络实时特性的可用带宽作为路由度量，能直接保证网络带宽资源的最优利用．

Kth Widest Available Bandwidth Path Algorithm

Currently, most routing algorithms adopt cost as the prime metric. Nevertheless, additive cost cannot be transformed to concave bandwidth that is the definite representative of real network, therefore, bandwidth is more suitable to be the prime metric than cost and it is necessary to study bandwidth related algorithms in depth. This paper proposes a novel loopless k th widest available bandwidth routing algorithms. Due to the essential difference between additive cost and concave bandwidth, the novel algorithm cannot be simply attained from modified k th shortest path algorithm. Henceforth, this paper defines two new path operations and takes advantage of modified double sweep algorithm to construct k th widest available bandwidth paths. Thereafter, correctness and looplessness of the algorithm are proved as well as its polynomial complexity. At last, an illustration of algorithm and discussion on algorithm application are provided. K th widest available bandwidth algorithm is of great theoretical significance in that it solves a kind of fundamental routing problems that adopt bandwidth as the prime metric. Furthermore, it has great practical significance for the reason that it can guarantee the optimal usage of network bandwidth resources by virtue of the adoption of available bandwidth metric.