[1]袁玉莹,付 雄.基于扩展 Dijkstra 的多约束 QoS 路由研究[J].计算机技术与发展,2021,31(11):122-128.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 020]
　YUAN Yu-ying,FU Xiong.Research on Multi-constrained QoS Routing Based on Extended Dijkstra[J].,2021,31(11):122-128.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 020]
点击复制

基于扩展 Dijkstra 的多约束 QoS 路由研究()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
31
期数:
2021年11期
页码:
122-128
栏目:
网络与安全
出版日期:
2021-11-10

文章信息/Info

Title:
Research on Multi-constrained QoS Routing Based on Extended Dijkstra
文章编号:
1673-629X(2021)11-0122-07
作者:
袁玉莹; 付 雄
南京邮电大学 计算机学院,江苏 南京 210003
Author(s):
YUAN Yu-ying; FU Xiong
School of Computer Science,Nanjing University of Posts & Telecommunications,Nanjing 210003,China
关键词:
多约束 QoS 路由; Dijkstra 算法; 蚁群算法; 时延; 带宽; 代价; 丢包率
Keywords:
multi-constrained QoS routing; Dijkstra algorithm; ant colony algorithm; delay; bandwidth; cost; loss
分类号:
TP393
DOI:
10. 3969 / j. issn. 1673-629X. 2021. 11. 020
摘要:
为了满足以太网业务中双路径路由计算的多约束 QoS 要求,提出了一种基于扩展 Dijkstra 的多约束 QoS 双路径路由算法, 旨在网络中能够高效地寻找到符合 QoS 约束限制的路径。 算法首先对网络拓扑进行两次简化,去除不满足带宽约束的边以及孤立的网络节点,从而减少网络规模的复杂度以及后续的计算量;然后利用蚁群算法的信息素更新步骤,引入多个 QoS 度量参数的约束限制,用是否满足约束限制条件来确定惩罚因子的数值,通过调整目标函数值达到调整信息素增量函数大小的目的,将时延、带宽、代价、丢包率、抖动五个 QoS 度量值约束通过目标函数转换成一个度量值约束,最后利用扩展的 Dijkstra 算法求解满足多约束 QoS 的最优解。 文中主要从迭代次数、时延、带宽、代价、丢包率、抖动六个方面对算法进行有效性分析,实验结果表明,该算法在时间效率以及求解精度上优于蚁群算法和遗传算法,能很好地实现以太网业务中的多约束 QoS 双路径路由计算。
Abstract:
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.

相似文献/References:

[1]纪亚劲,刘艳清,赵礼峰.求解最小费用流的一种新算法[J].计算机技术与发展,2018,28(01):108.[doi:10. 3969/ j. issn. 1673-629X.2018.01.023]
　JI Ya-jin,LIU Yan-qing,ZHAO Li-feng.A New Algorithm for Solving Minimum Cost Flow[J].,2018,28(11):108.[doi:10. 3969/ j. issn. 1673-629X.2018.01.023]
[2]卫泓宇,刘冠灵,谢爱倍,等.基于单目视觉的智能物料分拣机器人的设计[J].计算机技术与发展,2020,30(02):98.[doi:10. 3969 / j. issn. 1673-629X. 2020. 02. 020]
　WEI Hong-yu,LIU Guan-ling,XIE Ai-bei,et al.Design of Intelligent Material Sorting Robot Based on Monocular Vision[J].,2020,30(11):98.[doi:10. 3969 / j. issn. 1673-629X. 2020. 02. 020]
[3]王树梅,黄 石,臧禹顺.基于 Dijkstra 算法的城市物流公交系统优化[J].计算机技术与发展,2021,31(10):179.[doi:10. 3969 / j. issn. 1673-629X. 2021. 10. 030]
　WANG Shu-mei,HUANG Shi,ZANG Yu-shun.Public Transportation System Optimization of Urban Logistics Based on Dijkstra Algorithm[J].,2021,31(11):179.[doi:10. 3969 / j. issn. 1673-629X. 2021. 10. 030]

更新日期/Last Update: 2021-11-10