Solving the MCOP problem optimally
Wen-Lin Yang · 2003
Providing guaranteed end-to-end quality of service (QoS) is a key issue for deploying multimedia applications on broadband integrated services networks. To support such a QoS-based service, a problem concerning how to select a feasible end-to-end path in order to satisfy multiple QoS constraints simultaneously must be studied. Two exact algorithms, branch-and-bound and extended Bellman-Ford algorithms, are proposed for this NP-complete problem. In spite of the time complexity of the branch-and-bound algorithm being O(d/sup n/) at the worst case, simulation results show that the branch-and-bound method not only outperforms the extended Bellman-Ford method, but also is an efficient method when it is applied to random networks and practical networks like ANSNET. As for mesh networks, it is observed that our branch-and-bound method is efficient only for networks where the number of hops of the desired MCOP (multiple constrained optimal path) is less than 15.