Kth Widest Available Bandwidth Path Algorithm
Huang Jia · Chinese Journal of Computers · 2004
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.