An enhanced algorithm for multiple constraints optimal path calculation
Sheng Wang, Hong Wang, Lemin Li · 2004
One of the key issues in the design of a QoS-oriented service is how to identify a feasible route which satisfies multiple constraints while simultaneously achieving efficient utilization of network resource. The underlying problem can be stated as a multiple constraint optimal path (MCOP) problem. Some algorithms have been proposed in the literature, but they suffered from various disadvantages and cannot meet the practical requirements. A formal definition of the MCOP problem is stated. A novel enhanced heuristic algorithm for solving the MCOP problem is proposed, in which elegant path searching techniques are used to achieve higher performance in terms of path selection success ratio and average path cost. The advantage of the proposed algorithm is verified via extensive simulations on networks with random topologies and link weights. The impact of some key design parameters on the performance is discussed.