论文部分内容阅读
摘要：该文主要分析了路由环路产生的原因和当前基于距离矢量路由协议和链路状态路由协议的路由环路避免机制，通过分析得到当前主流环路避免机制存在的问题。最后介绍了路由环路避免技术的发展趋势和路由环路解決方法性能的考量。
关键词：路由环路；链路状态路由协议；距离矢量路由协议；避免机制；性能
当网络拓扑发生改变时，路由器将对路由表进行维护，如果网络收敛缓慢或其他原因导致错误路由的添加，就有可能出现路由环路问题。基本上，路由环路的形成都是因为到达目的路径的不确定性或矛盾的路由条目选择而造成的。路由环路造成网络动荡，引起数据包进入黑洞，进而丢包，造成网络资源的严重浪费，严重的会导致网络瘫痪。为此，避免路由环路的技术就应运而生了。路由避免技术主要是通过路由协议本身的一些机制来实现。
1路由环路影响及产生的主要原因
互联网技术的快速发展使应用种类越来越多样化，路由技术无疑成为网络通信的核心技术。因此，对路由协议的健壮性和可靠性要求也越来越高。现有的边界网络路由协议（BGP）已无法满足当前网络路由协议的性能和可靠性等需求。大量文献研究表明，BGP较差的可靠性将会直接影响互联网的可靠性。Kushman、Kandula S等人通过实验分析提出接近50%的VoIP故障出现在BGP更新报文后的15分钟内；Labovitz等人指出，报文丢失的主要原因之一是因为路由在短时间内的变化所致，许多IP地址因为BGP的抖动而在短时间内不可访问。
因此互联网的可靠性很大程度依赖于路由协议。互联网是一个不断变化的网络，其拓扑结构也因链路（或节点）故障发生而不断变化，在变化的网络拓扑结构中能够快速收敛得到正确路由是互联网可靠性的重要保证。出于稳定性考虑，当前互联网路由协议通常只选择一条“最佳”路径到达目的地，这种单路径路由协议不具备瞬时恢复能力，路由收敛的延迟可能会导致瞬时路由环路或者瞬时路由失效等故障。
在采用不同路由算法的动态路由协议中，其路由协议的收敛速度也不一样。如果动态路由协议的路由收敛速度越慢，就越容易出现路由环路。基于距离矢量的路由协议是最容易产生路由环路。以RIP动态路由协议为例，运行RIP协议的路由器需要定期将整张路由表向相连的邻居路由器广播，邻居路由器接收到这些路由更新信息后，按照距离矢量算法生成路由表。在RIP协议中设置了四个计时器来进行路由更新，其中抑制计时器为180秒，更新计时器为30秒，在极限情况下RIP协议的收敛时间可能达到210秒。在这么长的收敛时间里很有可能产生路由环路。通常RIP协议通过采用最大跳数、水平分割、路由毒化和毒性逆转等技术来防止路由环路，但这些技术也存在局限性，如无法解决多个路由器发生路由环路问题。在基于链路状态的路由协议中，因为网络拓扑的变化，网络会发布新的链路状态信息，其余路由节点在收到新的链路状态信息后会重新计算机路由并更新、转发信息库，但是由于各路由节点内外环境的差异等原因导致各路由节点收到的拓扑更新信息和使用新转发表的时间是不一样的，因此分散的路由节点对网络拓扑结构的认知失调，可能导致每个路由节点转发的路径之间产生环路。
2路由环路避免机制
在传统路由算法中，基于链路状态算法比基于距离矢量算法更具优越性，所以相对来说链路状态算法的路由协议更少出现路由环路。因此在大型网络中基本上都采用基于链路状态算法的路由协议来进行路由收敛。
文献中提出基于链路状态快速感知的环路避免机制：主要利用CR在路由更新之前快速获取最新的网络拓扑信息，通过控制路由器的重计算次序来避免环路的产生。文献中提出以时间作为目的地序号来解决路由环路的方法：对消息项序号的重新设计，添加时间（Tim of Day，TOD）信息，避免因为节点休眠重启或者路由超时删除时，路由消息项序号重新计数引发的重复广播过期路由消息项的问题。按照路由更新的原则，选择消息项序号最新的消息项，从根本上解决了路由消息循环传输的问题，确保在任何时刻网络中都不会存在路由消息循环和暂态路由环路。文献中提出BGP采用AS_PATH属性检测机制来实现环路避免，文献中提出采用LFGM（Loop-Free Guarantee Mechanism）可使节点获得更多不会产生环路的可达路径。LFGM不仅能够满足多径路由的无环需求，而且与最优路径选路及等代价最优路径选路方式相比，节点将能够获取更多数量的可用路由，从而为路由选择提供了更大的可操作空间。文献中提出一种偏转路由方案以增强网络在发生瞬时链路或节点故障情况下的可用性。
上文提出，如果动态路由协议的路由收敛速度越慢，就越容易出现路由环路。针对该问题，IETF提出无环替代路方案和Not-via技术，以及后来其他研究人员提出的FIR、Safeguard、FCP、MRC等技术。上述技术基本上都可以保证单失效情况下路由的100%快速恢复，但其性能与网络的拓扑结构和权重配置有很大关系，可能导致流量分配不均衡问题。因此，文献提出基于单向转发环的快速重路由策略，通过在网络中预先简历两个单向转发环路来保证单失效情况下网络路由的快速恢复。
3存在的问题
当前，大多数大型ISP（网络服务提供商）网络使用ISIS（中间系统协4g）或者OSPF（开放最短路由优先协议）这两个协议作为域内路由协议。作为典型的链路状态协议，ISIS和OSPF都需要通过链路状态通告在节点间交互网络拓扑信息，以此来保证网络中的所有节点链路状态数据库的一致性。因此当有链路或网络设备发生失效时，路由器需要检测并全网通报这一失效信息，以便其他路由器获知这一拓扑结构的变化。从检测到失效到全网所有节点的链路状态数据库最终重新达到一致这个过程称为重收敛过程。然而重收敛过程将会给网络带来丢包以及延迟过长等潜在问题。
对于传统业务，路由环路避免过程中的重收敛过程所造成的影响往往是可以容忍的。但近些年来，随着对时延和丢包敏感的实时业务的大规模普及，用户对网络性能的要求也变得越来越严格。对于IP电话、流媒体、网游以及远程视频会议等实时业务来说，丢包或长延时都将明显的降低它们的性能甚至造成业务中断。因此如何避免丢包以及降低时延已经成为一个不得不面对的问题。
4总结
路由环路避免机制致力于解决网络中环路问题，但该问题一直存在于各种路由环境中，并且严重影响路由协议陛能。解决路由环路问题往往以牺牲某部分陛能为代价，因此判断该环路解决机制的重要因素应该分为以下两点：（1）该机制是否解决路由环路问题；（2）该机制应用后对其他性能的影响程度。现今，网络应用的快速发展使通信质量越来越受到重视，因此网络的可靠性和稳定性成为研究人员的研究热点，其中IP路由环路的避免技术研究无疑是研究热点的重中之重，但是从目前的情况上来看，现存的环路避免算法的复杂度都比较高，因此其工程可行性较差，此问题的有效解决有待于进一步的研究。
关键词：路由环路；链路状态路由协议；距离矢量路由协议；避免机制；性能
当网络拓扑发生改变时，路由器将对路由表进行维护，如果网络收敛缓慢或其他原因导致错误路由的添加，就有可能出现路由环路问题。基本上，路由环路的形成都是因为到达目的路径的不确定性或矛盾的路由条目选择而造成的。路由环路造成网络动荡，引起数据包进入黑洞，进而丢包，造成网络资源的严重浪费，严重的会导致网络瘫痪。为此，避免路由环路的技术就应运而生了。路由避免技术主要是通过路由协议本身的一些机制来实现。
1路由环路影响及产生的主要原因
互联网技术的快速发展使应用种类越来越多样化，路由技术无疑成为网络通信的核心技术。因此，对路由协议的健壮性和可靠性要求也越来越高。现有的边界网络路由协议（BGP）已无法满足当前网络路由协议的性能和可靠性等需求。大量文献研究表明，BGP较差的可靠性将会直接影响互联网的可靠性。Kushman、Kandula S等人通过实验分析提出接近50%的VoIP故障出现在BGP更新报文后的15分钟内；Labovitz等人指出，报文丢失的主要原因之一是因为路由在短时间内的变化所致，许多IP地址因为BGP的抖动而在短时间内不可访问。
因此互联网的可靠性很大程度依赖于路由协议。互联网是一个不断变化的网络，其拓扑结构也因链路（或节点）故障发生而不断变化，在变化的网络拓扑结构中能够快速收敛得到正确路由是互联网可靠性的重要保证。出于稳定性考虑，当前互联网路由协议通常只选择一条“最佳”路径到达目的地，这种单路径路由协议不具备瞬时恢复能力，路由收敛的延迟可能会导致瞬时路由环路或者瞬时路由失效等故障。
在采用不同路由算法的动态路由协议中，其路由协议的收敛速度也不一样。如果动态路由协议的路由收敛速度越慢，就越容易出现路由环路。基于距离矢量的路由协议是最容易产生路由环路。以RIP动态路由协议为例，运行RIP协议的路由器需要定期将整张路由表向相连的邻居路由器广播，邻居路由器接收到这些路由更新信息后，按照距离矢量算法生成路由表。在RIP协议中设置了四个计时器来进行路由更新，其中抑制计时器为180秒，更新计时器为30秒，在极限情况下RIP协议的收敛时间可能达到210秒。在这么长的收敛时间里很有可能产生路由环路。通常RIP协议通过采用最大跳数、水平分割、路由毒化和毒性逆转等技术来防止路由环路，但这些技术也存在局限性，如无法解决多个路由器发生路由环路问题。在基于链路状态的路由协议中，因为网络拓扑的变化，网络会发布新的链路状态信息，其余路由节点在收到新的链路状态信息后会重新计算机路由并更新、转发信息库，但是由于各路由节点内外环境的差异等原因导致各路由节点收到的拓扑更新信息和使用新转发表的时间是不一样的，因此分散的路由节点对网络拓扑结构的认知失调，可能导致每个路由节点转发的路径之间产生环路。
2路由环路避免机制
在传统路由算法中，基于链路状态算法比基于距离矢量算法更具优越性，所以相对来说链路状态算法的路由协议更少出现路由环路。因此在大型网络中基本上都采用基于链路状态算法的路由协议来进行路由收敛。
文献中提出基于链路状态快速感知的环路避免机制：主要利用CR在路由更新之前快速获取最新的网络拓扑信息，通过控制路由器的重计算次序来避免环路的产生。文献中提出以时间作为目的地序号来解决路由环路的方法：对消息项序号的重新设计，添加时间（Tim of Day，TOD）信息，避免因为节点休眠重启或者路由超时删除时，路由消息项序号重新计数引发的重复广播过期路由消息项的问题。按照路由更新的原则，选择消息项序号最新的消息项，从根本上解决了路由消息循环传输的问题，确保在任何时刻网络中都不会存在路由消息循环和暂态路由环路。文献中提出BGP采用AS_PATH属性检测机制来实现环路避免，文献中提出采用LFGM（Loop-Free Guarantee Mechanism）可使节点获得更多不会产生环路的可达路径。LFGM不仅能够满足多径路由的无环需求，而且与最优路径选路及等代价最优路径选路方式相比，节点将能够获取更多数量的可用路由，从而为路由选择提供了更大的可操作空间。文献中提出一种偏转路由方案以增强网络在发生瞬时链路或节点故障情况下的可用性。
上文提出，如果动态路由协议的路由收敛速度越慢，就越容易出现路由环路。针对该问题，IETF提出无环替代路方案和Not-via技术，以及后来其他研究人员提出的FIR、Safeguard、FCP、MRC等技术。上述技术基本上都可以保证单失效情况下路由的100%快速恢复，但其性能与网络的拓扑结构和权重配置有很大关系，可能导致流量分配不均衡问题。因此，文献提出基于单向转发环的快速重路由策略，通过在网络中预先简历两个单向转发环路来保证单失效情况下网络路由的快速恢复。
3存在的问题
当前，大多数大型ISP（网络服务提供商）网络使用ISIS（中间系统协4g）或者OSPF（开放最短路由优先协议）这两个协议作为域内路由协议。作为典型的链路状态协议，ISIS和OSPF都需要通过链路状态通告在节点间交互网络拓扑信息，以此来保证网络中的所有节点链路状态数据库的一致性。因此当有链路或网络设备发生失效时，路由器需要检测并全网通报这一失效信息，以便其他路由器获知这一拓扑结构的变化。从检测到失效到全网所有节点的链路状态数据库最终重新达到一致这个过程称为重收敛过程。然而重收敛过程将会给网络带来丢包以及延迟过长等潜在问题。
对于传统业务，路由环路避免过程中的重收敛过程所造成的影响往往是可以容忍的。但近些年来，随着对时延和丢包敏感的实时业务的大规模普及，用户对网络性能的要求也变得越来越严格。对于IP电话、流媒体、网游以及远程视频会议等实时业务来说，丢包或长延时都将明显的降低它们的性能甚至造成业务中断。因此如何避免丢包以及降低时延已经成为一个不得不面对的问题。
4总结
路由环路避免机制致力于解决网络中环路问题，但该问题一直存在于各种路由环境中，并且严重影响路由协议陛能。解决路由环路问题往往以牺牲某部分陛能为代价，因此判断该环路解决机制的重要因素应该分为以下两点：（1）该机制是否解决路由环路问题；（2）该机制应用后对其他性能的影响程度。现今，网络应用的快速发展使通信质量越来越受到重视，因此网络的可靠性和稳定性成为研究人员的研究热点，其中IP路由环路的避免技术研究无疑是研究热点的重中之重，但是从目前的情况上来看，现存的环路避免算法的复杂度都比较高，因此其工程可行性较差，此问题的有效解决有待于进一步的研究。