Fast bandwidth-constrained quality of service routing via bidirectional search

Scalability has been a crucial design concern for quality of service routing protocols to be deployed in high-speed communications networks. The issue of bandwidth-constrained widest-shortest path (WSP) routing, which selects the WSP connecting a pair of nodes subject to a bandwidth constraint is studied. The design objective is to enable fast route calculation in identifying such constrained paths. To achieve this goal, a polynomial optimal algorithm using bidirectional search is designed. The complexity of the designed algorithm 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 demonstrate that the designed algorithm can significantly reduce the average-case computational overhead caused by the calculation of such constrained routes as compared with related work.