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

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

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