满足路径约束的最优路算法

Path-Constrained Path-Optimization Routing

满足路径约束的最优路问题已被证明是NP hard问题。本文针对源点到宿点满足两个QoS(服务质量)度量的路由问题,给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的,表明算法是有效的。

The problem of path-constrained path-optimization routing is proved to be NP-hard one that cannot be exactly solved in polynomial time. In this paper we describe a heuristic algorithm for a source to a destination routing problem satisfying two QoS (Quality of service)metrics which is defined as follows. Given a directed graph with two weights, cost and delay, on each link, we find the cheapest path such that the total delay of the path is no more than a given threshold. Our algorithm is polynomial, which demonstrates its good efficiency.