IP网络中的快速路由微环避免算法

doi:10.11772/j.issn.1001-9081.2015.12.3325

计算机应用 ›› 2015, Vol. 35 ›› Issue (12): 3325-3330.DOI: 10.11772/j.issn.1001-9081.2015.12.3325

IP网络中的快速路由微环避免算法

杨诗琦, 虞红芳, 罗龙

光纤传感与通信教育部重点实验室(电子科技大学), 成都 611731

收稿日期:2015-06-23 修回日期:2015-08-17 出版日期:2015-12-10 发布日期:2015-12-10
通讯作者: 杨诗琦(1990-),女,陕西宝鸡人,硕士研究生,主要研究方向:路由算法、卫星通信
作者简介:虞红芳(1975-),女,浙江萧山人,教授,博士,主要研究方向:网络虚拟化、软件定义网络;罗龙(1989-),女,四川成都人,硕士,主要研究方向:网络路由、软件定义网络。
基金资助:
国家973计划项目(2013CB329103);国家自然科学基金资助项目(61271171)。

Fast routing micro-loop avoidance algorithm in IP network

YANG Shiqi, YU Hongfang, LUO Long

Key Laboratory of Optical Fiber Sensing and Communications, Education Ministry of China;University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China

Received:2015-06-23 Revised:2015-08-17 Online:2015-12-10 Published:2015-12-10

摘要/Abstract

摘要： 在IP网络中,当链路权重发生变化时,可能产生路由微环问题。路由微环会引发网络延迟和丢包,无法满足实时业务对高水平服务质量的需求。因此针对该问题,提出一种快速路由微环避免算法,该算法设计一个权重序列,将链路权重按照该序列有序地重新配置,使得链路权重被重置后的路由重收敛过程中没有微环产生。在计算权重序列时,该算法首先定义安全权重区间的概念来描述避免路由微环产生的条件,随后利用该条件搜索出一组安全权重范围,同时使用剪枝技术缩小搜索空间、提高搜索效率,最后从各范围中取出一个值组成最后的权重序列。利用典型网络拓扑对算法进行仿真测试,实验结果表明,所提算法在87%的拓扑中平均需要5次中间权重配置就能避免微环。此外,相对于现有其他使用迭代调整链路权重以解决路由微环的算法,该算法计算时间复杂度降低一个数量级,计算效率提高30%~80%。所提算法能够大幅缩短计算时间,更加高效地解决路由微环问题,避免由此引发的网络延迟和丢包,从而提供高水平的网络服务质量。

关键词: IP网络, 路由微环, 微环避免, 重收敛

Abstract: When a link weight changes in network with Internet Protocol (IP), routing loops may occur. Such loops increase the network latency and cause packet losses, which cannot meet the needs of high-level real-time service. A fast routing micro-loop avoidance algorithm using a weight sequence was proposed. The link weights were reallocated according to the weight sequence so that no loops would occur during convergence phase. In order to calculate the weight sequence, a safety weight interval was defined to describe the condition for avoiding loops, then the safety interval was used to search a set of safety weight ranges. During calculation, the prunning technology was used to reduce search range and improve efficiency. At last, the final weight sequence was obtained from these ranges. The simulation test results using typical network topology algorithm show that in average five times of link weight reallocation can successfully avoid loops in 87% of topologies. In addition, compared with other existing algorithms using iterative adjustment link weights to solve the routing micro-loop, the computational complexity of the proposed algorithm was greatly reduced by an order of magnitude and the computational efficiency was improved by 30%-80%. The proposed algorithm can greatly shorten the calculation time and more efficiently solve the problem of routing micro-loop, which will avoid network latency and packet loss to provide a high level of service quality.

Key words: Internet Protocol (IP) network, routing micro-loop, micro-loop avoidance, reconvergence

中图分类号:

TP393.02

杨诗琦, 虞红芳, 罗龙. IP网络中的快速路由微环避免算法[J]. 计算机应用, 2015, 35(12): 3325-3330.

YANG Shiqi, YU Hongfang, LUO Long. Fast routing micro-loop avoidance algorithm in IP network[J]. Journal of Computer Applications, 2015, 35(12): 3325-3330.

参考文献

[1] FILSFILS C, FRANCOIS P, SHAND M, et al. RFC 6571, Loop-Free Alternate (LFA) applicability in Service Provider (SP) networks[S]. Fremont:IETF, 2012:1-35.
[2] SHAND M, BRYANT S, PREVIDI S, et al. RFC 6976, Framework for loop-free convergence using the ordered Forwarding Information Base (oFIB) approach[S]. Geneva:IETF, 2013:1-28.
[3] FRANCOIS P, BONAVENTURE O. Avoiding transient loops during the convergence of link-state routing protocols[J]. IEEE/ACM Transactions on Networking, 2007, 15(6):1280-1292.
[4] SONG Z. Research on IP fast rerouting technology[D]. Chengdu:University of Electronic Science and Technology of China, 2010:136-177. (宋哲.IP快速重路由技术的研究[D].成都:电子科技大学,2010:136-177.)
[5] JIA B. Research on fast recovery of IP network with multi-topology routing technology[D]. Chengdu:University of Electronic Science and Technology of China, 2010:136-422. (贾冰.多拓扑路由技术应用于IP网络快速恢复的研究[D].成都:电子科技大学,2010:136-422.)
[6] CLAD F, MERINDOL P, PANSIOT J J, et al. Graceful convergence in link-state IP networks:a lightweight algorithm ensuring minimal operational impact[J]. IEEE/ACM Transactions on Networking, 2014, 22(1):300-312.
[7] FRANCOIS P, SHAND M, BONAVENTURE O. Disruption free topology reconfiguration in OSPF networks[C]//Proceedings of the 2007 IEEE International Conference on Computer Communications. Piscataway:IEEE, 2007:89-97.
[8] CLAD F, MERINDOL P, VISSICCHIO S, et al. Graceful router updates in link-state protocols[C]//Proceedings of the 2013 IEEE International Conference on Network Protocols. Piscataway:IEEE, 2013:1-10.
[9] HENGARTNER U, MOON S, MORTIER R, et al. Detection and analysis of routing loops in packet traces[J]. Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurment. New York:ACM, 2002:107-112.
[10] RAMALINGAM G, REPS T. On the computational complexity of dynamic graph problems[J]. Theoretical Computer Science, 1996, 158(1/2):233-277.
[11] PALMER C R, STEFFAN J G. Generating network topologies that obey power laws[C]//Proceedings of the 2000 Global Telecommunications Conference. Piscataway:IEEE, 2000, 1:434-438.
[12] SPRING N, MAHAJAN R, WETHERALL D, et al. Measuring ISP topologies with rocketfuel[J]. ACM SIGCOMM Computer Communication Review, 2002, 32(4):133-145.

IP网络中的快速路由微环避免算法

Fast routing micro-loop avoidance algorithm in IP network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	魏多吕光宏. 基于蚁群算法的IP网络流量矩阵估计[J]. 计算机应用, 2013, 33(01): 92-94.
[2]	杜毓聪金连文. 通过WiFi移动IP网络操控家用机器人方案在PDA上的实现[J]. 计算机应用, 2009, 29(07): 1865-1867.
[3]	魏镇韩陈鸣. ISP拓扑测量中的完整性评估方法研究[J]. 计算机应用, 2008, 28(8): 1954-1958.
[4]	李蔚李源刘洋. 基于移动代理技术的移动IP网络中链路快速建立方法[J]. 计算机应用, 2008, 28(4): 837-840.
[5]	李桂林李建华. 基于P2P的SIP网络研究[J]. 计算机应用, 2007, 27(8): 1877-1880.
[6]	吴振强，马建峰. 宽带无线IP网络安全体系结构模型[J]. 计算机应用, 2005, 25(08): 1730-1733.
[7]	陶猛，黄小红，刘峰. 基于ADSP-BF533的多媒体通信终端设计与实现[J]. 计算机应用, 2005, 25(03): 717-719.
[8]	侯越先，何丕廉，傅爱玲. 一种快速冗余容错编码方法及其在IP网络QoS控制中的应用[J]. 计算机应用, 2005, 25(03): 560-562.