基于扩展Dijkstra的多约束QoS路由研究

Research on Multi-constrained QoS Routing Based on Extended Dijkstra

为了满足以太网业务中双路径路由计算的多约束QoS要求,提出了一种基于扩展Dijkstra的多约束QoS双路径路由算法,旨在网络中能够高效地寻找到符合QoS约束限制的路径。算法首先对网络拓扑进行两次简化,去除不满足带宽约束的边以及孤立的网络节点,从而减少网络规模的复杂度以及后续的计算量;然后利用蚁群算法的信息素更新步骤,引入多个QoS度量参数的约束限制,用是否满足约束限制条件来确定惩罚因子的数值,通过调整目标函数值达到调整信息素增量函数大小的目的,将时延、带宽、代价、丢包率、抖动五个QoS度量值约束通过目标函数转换成一个度量值约束,最后利用扩展的Dijkstra算法求解满足多约束QoS的最优解。文中主要从迭代次数、时延、带宽、代价、丢包率、抖动六个方面对算法进行有效性分析,实验结果表明,该算法在时间效率以及求解精度上优于蚁群算法和遗传算法,能很好地实现以太网业务中的多约束QoS双路径路由计算。

We present a multi-constrained QoS dual-path routing algorithm based on extended Dijkstra to satisfy the requirement of finding out dual-path routing with the limit of multi-constrained QoS in Ethernet services.It is designed to figure out the path which can meet the constraints of QoS efficiently in the network.The algorithm firstly simplifies the network topology twice which can remove edges that do not meet the constraints of bandwidth and isolated network nodes,thereby reducing the complexity of network scale and the subsequent workload.Next,the multiple constraints of QoS measurement parameters is introduced by using the pheromone update step of ant colony algorithm to determine the value of the penalty factor by whether the constraint conditions are met.The value of the objective function is adjusted to achieve the purpose of adjusting the value of the pheromone increment function.The five QoS measurement constraints of delay,bandwidth,cost,loss and jitter are converted into a metric value constraint through the objective function.Finally,the optimal solution is figured out that satisfies the multi-constrained QoS by using the extended Dijkstra algorithm.We mainly analyze the effectiveness of the algorithm from six aspects of iteration,delay,bandwidth,cost,loss and jitter.Experiment shows that the proposed algorithm is better than ant colony algorithm and genetic algorithm both in terms of time efficiency and precision,and can realize multi-constrained QoS dual-path route calculation in Ethernet service.