Fast bandwidth-constrained shortest path routing algorithm
Bangyan Zhang, Hussein Talaat Mouftah · IEE Proceedings - Communications · 2006
QoS routing has been a critical issue for providing QoS in high-speed networks. The authors present the design of a fast routing algorithm for selecting the shortest path connecting a pair of nodes subject to a bandwidth constraint. The algorithm works by combining the strategies of informed search and backwards routing. Its worst-case computational complexity is deduced to be O(∣E∣lg∣V∣), where ∣E∣ and ∣V∣ represent the number of links and nodes in the network, respectively. Simulation results indicate, however, that the designed algorithm can greatly reduce the average-case running time in computing such constrained shortest paths as compared with existing work.