多约束路由的分层计算方法

The Layered Route Calculating Method with Multiple Constraints

针对多约束参数限制下服务质量路由的寻找问题,提出一种分层式计算思想。设想把路由计算方式分为两层,第一层工作是计算源与目的节点间的可达路径集,第二层则是在路径集中寻找满足条件的路由。研究出一种可达路径集计算方法,在此基础上推出了具体的分层式路由计算方法,采用由少到多逐一增加串联链路和节点数量递进方式进行,一旦寻找到满足条件的路由,则给出结果,退出计算。通过算例详细介绍了路径集与路由寻找的计算方法,并论证了路径集算法的正确性,阐明了路由新算法的时间复杂性及诸多优点,提出了适应多约束参数传输的状态信息交换协议改进建议。通过仿真实验验证了路由新算法的正确性,同时也说明新算法完全能够满足实际需要。

A layered calculating method is proposed to solve the problem of multiple Qos-constrained routing. This method includes two steps. The first step is to calculate the reachability set of route from source node to target node; and the second step is to find within the set a route that satisfies the constraints. Based on the algorithm of reachability route set, the paper introduces an idiographic layered calculating method of path finding. The method incrementally adds serial links and nodes one by one. Once a path satisfying constraints is found, the result is output and the calculation exits. The calculation methods of reachability route set and path finding introduced in detail through examples, and the correctness of the algorithm is testified. The paper also analyzes the reduced time-domain complexity and many other merits of the algorithm. Recommendations are offered to improve the network state information switching protocol to adapt the proved to be correct with transmission of multiple constraint parameters. The new calculating method simulation and can satisfy the need of practical use.