一种基于可行性的启发式多约束QoS寻路算法

Feasibility-based Heuristic Multi-constrained QoS Routing Algorithm

在现有的有限网络资源的基础上,如何更好的为流媒体业务提供良好的服务质量(QoS),是多约束QoS路由算法要解决的一个重要问题。在网络中寻找满足多个约束条件的路径(MCP)的问题是一个NP完全问题。本文介绍了MCP问题的主要解决方法,利用BFS(breath first search)算法计算复杂度低的特点,提出了一种对可行节点到达目的节点进行估计,并以此来决定搜索方向的启发式算法。通过实例的演示和实验对比、分析,验证了该算法的正确性,可行性以及优越性。

In order to satisfy the streaming media business finite net resources, the multi-constrained QoS routing is with a good QoS （quality-of-service） based on the modern becoming increasingly more important. In general, multi- constrained path selection, with or without optimization, is an NP-complete problem that cannot be effectively solved in polynomial time. In this paper, we propose a heuristic algorithm to select the node by which the source is more likely to reach the destination. This algorithm searches the network graph in the right direction and is more efficient in finding the feasible path until an optimal path is acquired. Experiment results show that this algorithm is feasible and superior.