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

Research on Multi-constrained QoS Routing Based on Extended Dijkstra

作　　者：袁玉莹 付雄[1] YUAN Yu-ying;FU Xiong(School of Computer Science,Nanjing University of Posts&Telecommunications,Nanjing 210003,China)

机构地区：[1]南京邮电大学计算机学院,江苏南京210003

出　　处：《计算机技术与发展》2021年第11期122-128,共7页Computer Technology and Development

基　　金：国家自然科学基金资助项目(61202354)

摘　　要：为了满足以太网业务中双路径路由计算的多约束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.

关 键 词：多约束QOS路由 DIJKSTRA算法 蚁群算法 时延 带宽 代价 丢包率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]