- 产品与解决方案
- 行业解决方案
- 服务
- 支持
- 合作伙伴
- 新华三人才研学中心
- 关于我们
IS-IS快速收敛技术白皮书
关键词：IS-IS、快速收敛、BFD、指数退避定时器、快速扩散技术、增强SPF算法、部分路由计算算法、快速下发技术
摘 要：路由收敛过程由故障探测、路由信息扩散、路由计算、路由下发等几个环节组成，H3C采用了一系列技术对路由收敛的各环节进行优化，大大提高了路由收敛速度。本文描述了H3C IS-IS为了实现快速收敛采用的各种技术、使用场景以及应用意义。
缩略语：
缩略语 | 英文全名 | 中文解释 |
IS-IS | Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol | 中间系统到中间系统路由协议 |
BFD | Bidirectional Forwarding Detection | 双向转发探测协议 |
ISPF | Incremental SPF | 增强SPF算法 |
PRC | Partial Route Calculation | 部分路由计算 |
LSP | Link State Protocol Data Unit | 链路状态协议数据单元 |
LSDB | Link State Database | 链路状态数据库 |
RIB | Routing Information Base | 路由信息数据库 |
FIB | Forwarding Information Base | 转发信息数据库 |
目 录
随着Internet的飞速发展，Internet正在被越来越多具有不同需求的用户使用，语音、视频等新兴网络业务也在蓬勃发展，高质量业务对路由收敛速度提出更严格的要求。
路由收敛过程由故障探测、路由信息扩散、路由计算、路由下发等几个环节组成。
IS-IS是基于链路状态的路由协议，工作机制是各设备间互相扩散描述链路状态的LSP，并且各设备最终形成同样的LSDB，在LSDB基础上进行路由计算生成路由信息并保存到RIB中，RIB选取最优路由并下发给FIB用于指导报文转发。
当网络发生链路故障时，与故障链路相连的设备及时探测到故障并更新LSP进行全网扩散，网络中的其它设备重新收集LSP、生成新的LSDB并重新进行路由计算生成新的路由信息，最终转发流量得以恢复，整个过程称为路由收敛。
图1 IS-IS收敛示意图
如图1所示，Router B监测到与Router A相连的链路发生故障，重新生成描述与Router A相连链路的LSP并扩散给Router C，同时启动路由计算过程重新计算路由；Router C收到Router B发送的新LSP后也会启动路由计算过程重新进行路由计算。全网所有设备都完成LSP的重新收集以及路由重新计算后，路由收敛过程结束。
从以上过程可以看出，要加快路由收敛速度，需要解决以下几个问题：
l 快速探测到链路故障
l 快速生成新的LSP并进行快速扩散
l 快速进行路由计算即用最短的时间生成最新的路由信息
l 快速将最新的路由信息下发给FIB
为了有效解决以上问题，H3C采用以下技术来提高路由收敛速度：
l 采用BFD技术来提高故障探测速度；
l 通过退避算法来缩短LSP生成以及路由计算的等待时间；
l 通过快速扩散技术提高LSP的全网扩散速度；
l 通过增强SPF、部分路由计算等算法缩短路由计算时间；
l 通过快速下发技术提高路由下发FIB的速度。
通过采用以上一系列技术对路由收敛的各环节进行优化，大大提高了路由收敛速度。
通过对故障探测、路由信息扩散、路由计算、路由下发等几个环节进行优化，可以大大提高路由收敛速度，为语音、视频等对中断时间高度敏感的业务在Internet的成功应用奠定基础，也使得IP承载网取代传统电信网络并提供高可靠性的电信应用成为可能。
l IS（Intermediate System，中间系统）。相当于TCP/IP中的路由器，是IS-IS协议中生成路由和传播路由信息的基本单元。在下文中IS和路由器具有相同的含义。
l IS-IS（Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol，中间系统到中间系统域内路由信息交换协议），是一种目前比较主流的内部网关协议（Interior Gateway Protocol，IGP），用于自治系统内部。IS-IS是一种链路状态协议，使用最短路径优先（Shortest Path First，SPF）算法进行路由计算。
l LSDB（Link State Database，链路状态数据库）。所有的网络内部连接状态组成了链路状态数据库，在每一个IS中都至少有一个LSDB。IS使用SPF算法，利用LSDB来生成自己的路由，各个IS最终会生成一样的LSDB。
l LSP（Link State Protocol Data Unit，链路状态报文）。在IS-IS中，每一个IS都会生成一个LSP，此LSP包含了本IS的所有链路状态信息。每个IS收集所有的LSP生成自己的LSDB。
l BFD（Bidirectional Forwarding Detection，双向转发探测协议），提供一种通用的、标准化的、协议无关的快速故障检测机制，为各上层协议如路由协议、MPLS等统一地快速检测两台路由器间双向转发路径的故障。
l ISPF（Incremental SPF，增强SPF算法），主要用于部分拓扑发生变化的情况，在这种情况下不需要重新计算整个网络拓扑，而只是将变化了的少量拓扑进行修正，从而大大节约路由计算时间。
l PRC（Partial Route Calculate，部分路由计算算法），主要用于只是路由信息发生变化的情况，在这种情况下不需要重新计算网络拓扑，只是根据原有的拓扑生成新的路由信息即可，从而大大节约路由计算时间。
如果通过链路层来进行故障检测，那么链路层协议不同，故障检测时间也不同。例如链路层协议为POS时，可以在50毫秒内检测到链路故障；而当两台路由器通过以太网相连时，如果一台路由器接口状态为Down，而另一台路由器接口状态仍为Up时，只能通过协议自身的握手机制来检测链路故障。IS-IS通过Hello报文进行链路故障检测，故障检测时间在1秒以上，无法满足快速收敛（毫秒级）的要求。
BFD提供一种通用的、标准化的、协议无关的快速故障检测机制，为各上层协议如路由协议、MPLS等统一地快速检测两台路由器间双向转发路径的故障。
BFD在两台路由器上建立会话，用来监测两台路由器间的双向转发路径，为上层协议服务。BFD本身并没有发现机制，而是靠被服务的上层协议通知其该与谁建立会话，会话建立后如果在检测时间内没有收到对端的BFD控制报文则认为发生故障，并通知被服务的上层协议，上层协议进行相应的处理。
由于BFD报文的标准与协议无关，可以通过硬件芯片处理BFD探测报文的收发，提高报文的收发速度以及探测速度，实现50ms以内的快速故障探测。
为了避免LSP频繁振荡对网络带来的冲击，LSP的生成存在一个最小间隔的限制，即同一个LSP在最小间隔内不允许重复生成，一般缺省最小时间间隔为5秒，作了这种限制后，路由收敛速度受到较大影响。
为了在抑制网络变化导致资源浪费的同时能够尽快响应网络拓扑变化，H3C采用退避算法智能定时器技术来解决这个问题。所谓退避算法智能定时器，就是指定时器可以自动根据触发的频繁程度计算不同的定时器时间间隔，触发的越频繁，其定时器的时间间隔就越长，从而起到惩罚抑制的目的。
当同时指定了初始间隔、惩罚增量（LSP生成时间增量）和最大间隔后，系统就可以根据网络拓扑变化的频繁程度自动调节LSP生成时间间隔。在网络拓扑比较稳定时，LSP生成时间间隔为初始间隔；在网络变化频繁的情况下LSP生成时间间隔将会在指定的初始间隔和最大间隔之间变化，变化的规律为“惩罚增量”×2n，即随着LSP反复生成的次数增多，其生成间隔就会越大，直到到达“最大间隔”为止。当时间间隔连续三次达到最大，则下一次的时间间隔又会被重置为初始间隔，开始新一轮的惩罚抑制功能。
通过退避算法智能定时器，可以有效解决LSP快速生成与抑制频繁生成之间的矛盾，既可以避免LSP频繁振荡对网络带来的冲击，也可以在不增加资源占用的情况下加快LSP生成速度、快速响应网络拓扑变化。
除了LSP快速生成之外，为了全网用较快的速度实现LSDB同步，LSP的快速扩散也是一个非常重要的环节。
由于LSP数量比较庞大，通常为了减轻大量LSP一起发送时对网络设备带来的冲击，一般IS-IS都是采用周期性分批扩散LSP的方法，例如1秒扩散多个LSP，以达到减轻网络负担的目的。但是采用这种机制后，当链路发生变化时可能不能及时将LSP扩散出去，影响的路由的快速收敛。
为了解决该问题，H3C实现了flash-flood功能。使能flash-flood功能后，当LSP发生变化而导致SPF重新计算时，不再等待周期性分批扩散，而是把导致SPF重新计算的LSP立即扩散出去，从而有效缩短拓扑变化时全网设备上LSDB不一致的时间，提高全网的快速收敛性能。虽然LSP数量很多，但每次网络出现故障而需要发生变化的LSP却很少，所以将这部分发生变化的LSP进行单独的快速扩散对系统的资源占用影响很有限，这样就用最小的代价实现了关键功能。一般flash-flood特性可以将LSP扩散速度提高到数十毫秒级别。
当网络拓扑发生变化时，IS-IS重新进行路由计算耗时较长主要有两个原因：
l 路由计算有一个最小时间间隔，当网络拓扑发生变化时需要等待一段时间才能进行路由计算
l 在网络拓扑情况复杂并且路由数量较多时，路由计算本身计算量太大而导致处理时间较长
H3C采用以下技术解决上述两个问题：
为了避免频繁进行路由计算给CPU带来负担，IS-IS路由计算存在一个最小时间间隔的限制，即在最小时间间隔内不允许重复进行路由计算，一般缺省最小时间间隔为10秒，作了这种限制后使得路由计算等待时间过长，当网络拓扑发生变化时，会影响路由的快速收敛。
和LSP快速生成技术类似，H3C采用退避算法智能定时器来解决路由快速计算和抑制频繁计算之间的矛盾，使得在较为稳定的网络中路由收敛速度得到大幅度提高。
IS-IS路由计算采用了SPF算法，SPF是目前被各种基于链路状态的路由协议（OSPF/IS-IS等）广泛使用并且比较成熟完善的路由计算方法，它采用Dijkstra算法计算最短路径。其基本思路是根据LSDB里描述的拓扑信息构建SPT（Shortest Path Tree，最短路径生成树），然后将LSDB里描述的路由信息作为树上的叶子生成最终路由。图2给出了最短路径树与叶子之间的基本关系图。
在SPF算法实现中，任何链路状态信息的变化都需要全部重新计算，即重新构建最短路径树，重新生成所有路由。这对于目前网络拓扑通常比较复杂、路由数量也很大的现代网络而言，进行一次全部路由的计算会占用大量系统资源，对系统造成很大冲击，同时，由于处理工作量太大造成耗时太长而无法满足路由快速收敛的需求。
而在实际网络应用中，某些链路状态信息的变化并不需要让所有路由都全部重新计算，主要表现为以下几个方面：
l 某些链路状态信息的变化不需要重新计算任何路由，例如，如果F和G之间除了图2给出已经在最短路径树上的路径外，还有额外的备份路径，则这条没有在最短路径树上的备份路径如果被删除是不影响任何拓扑和路由的。
l 某些链路状态信息的变化影响路由信息而不影响网络拓扑，例如G上的叶子即可达IP前缀发生变化，则只要重新生成对应的路由信息即可，整个最短路径树不需要发生任何变化。
l 某些链路状态信息的变化只影响部分拓扑的变化，例如F和G之间的链路断了，是不影响B、C、D、E之间的拓扑结构和路由信息的。
基于以上考虑，为了节约系统的CPU资源，加快路由收敛速度，可以对普通的SPF算法做出改进，根据链路信息变化的不同情况做出不同处理，使得重新进行路由计算的波及面控制在最小范围内，以提高系统的性能。
目前采用的改进方案有两种：
l PRC（Partial Routing Calculate）：只改变叶子时是不需要重新计算最短路径树的，只要根据现有的最短路径树重新生成对应的路由即可。这种直接根据最短路径树已有的拓扑信息而修正叶子节点即修正IP路由信息的处理，一般叫做部分路由计算（Partial Routing Calculate，PRC）。这是业界比较成熟并且广泛使用的方案，在RFC2328的16.5节Incremental updates -- summary-LSAs和16.6节Incremental updates -- AS-external-LSAs分别论述了OSPF针对三类五类LSA进行部分路由计算的具体方法，而ISO10589的附录C.2 SPF algorithm for computing equal cost paths中也简单提到了部分路由计算的基本思想。
l ISPF（Incremental Shortest Path First）：当网络的拓扑结构发生变化，即影响到最短路径树的结构时，只将受影响的部分节点进行重新计算拓扑结构，即只对最短路径树受影响的部分进行修正，而不需要重建整棵最短路径树。
总的来说，PRC用来处理网络拓扑不变而路由信息发生改变的情况，而ISPF用来处理网络拓扑结构发生改变的情况。通过采用以上两种技术，当网络拓扑或者路由信息发生变化时，系统不需要进行全部路由计算，每次只是根据网络变化的不同情况做出最精简的处理，使得路由计算处理工作量降到最低，从而大大节约路由计算所占用的时间。
IS-IS完成LSDB的收集并重新路由计算生成路由信息后，路由收敛过程剩余很重要的一个环节就是将路由信息下发到FIB中用于指导转发，而路由下发速度也是影响路由收敛整体速度的一个很重要因素，尤其对于分布式设备，转发信息需要从主控板通过板间透传下发到各个接口板的芯片，整体效率很低，严重影响了最终的路由收敛整体速度，为了解决该问题，H3C采用了自主知识产权的路由快速批量下发技术，大大缩短了分布式设备板间透传和下发芯片的时间，目前路由下发整体速度可以达到10k条/秒的级别。
路由快速收敛技术只是尽可能的缩短路由收敛时间，因此为了路由收敛后流量能够得到恢复，必须以冗余备份组网为基础，即到达某目的地必须存在两条或者两条以上的的路径，这样一旦主路径发生故障后可以通过其它路径到达同样的目的地。路由快速收敛技术只是实现用较快的速度找到其它路径，并将流量切换到新的路径上进行转发的功能。
另外，实现路由快速收敛技术后最终的收敛速度与产品硬件性能密切相关，不同的产品有一定差异。
目前，H3C所有支持IS-IS功能的产品均支持IS-IS快速收敛技术。
l ISO10589
l RFC1195
l draft-ietf-bfd-base-04
Copyright ©2007-2010 杭州华三通信技术有限公司 版权所有，保留一切权利。
非经本公司书面许可，任何单位和个人不得擅自摘抄、复制本文档内容的部分或全部，并不得以任何形式传播。
本文档中的信息可能变动，恕不另行通知。
产品与解决方案
售前咨询
售后咨询
人工在线咨询
