一种改进的多约束最佳路径算法研究

An Enhanced Algorithm for Multiple Constraints Optimal Path Calculation

本文描述了MPLS网络中的多约束最佳路径问题,以及该问题的各种变型.分析了现有的解决这些问题的算法存在的各种缺陷,并针对一般性的多约束最佳路径问题的解法,提出了改进的具体措施.通过具体的实例分析和计算机仿真,验证了新算法在性能上的改善,主要的性能指标包括路径计算的成功比率和路径的平均代价等.结合仿真结果讨论了算法中涉及到的关键参数对算法性能的影响.

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 Constraints Optimal Path (MCOP) problem. Recent years, some algorithms have been proposed in literature, but suffered from various disadvantages.They can not meet the practical requirements. In this paper, a formal definition of MCOP problem is stated. A novel enhanced heuristic for solving 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. Using extensive simulations on random graphs and random assigned link weights, the improvement of the new algorithm proposed is verified, and the impact of some key design parameters on the performance is discussed.