【摘要】 对多个加性QoS约束下的链路分离路径问题进行了研究,针对现有算法求解结果依赖于网络结构,难以保证对任意网络都可求得可行解和最优解的问题,提出了一种与网络结构无关的多约束链路分离路径路由算法(MCLPRA,multiple constrained link-disjoint path routing algorithm)。该算法基于SAMCRA,采用对解空间先分类,然后按类进行处理和搜索的方法,引入了控制搜索深度的参数,可保证对任意网络都能求得可行解。理论分析表明,MCLPRA能够在现有算法不能求解的情况下解得可行解和最优解。仿真结果显示,MCLPRA的可行解平均求解成功率明显高于现有算法且所求路径对长度也比现有算法更短。更多还原

【Abstract】 The problem of finding link-disjoint paths under multiple additive QoS constraints was studied.Since the existing algorithms depended on network’s structure and could not guarantee to find feasible solutions for arbitrary net-works,a novel algorithm called multiple constrained link-disjoint path routing algorithm(MCLPRA) was proposed.MCLPRA was based on SAMCRA and didn’t rely on the network’s structure.By introducing the parameter to control its search depth,dividing the solution space into different classes and performing searching according to the classes respectively,MCLPRA was able to obtain the feasible solutions for arbitrary networks.Theoretic analysis shows that MCLPRA can get the feasible and optimal solutions when traditional schemes can not.Comprehensive simulations also show that MCLPRA has better performances than existing algorithms in terms of higher average successful rate of getting feasible solutions with shorter average total length of the obtained path pair.更多还原