IGP快速收敛技术白皮书.doc

IGP 快速收敛技术白皮书

华为技术有限公司
Huawei Technologies Co., Ltd.

IGP 快速收敛技术白皮书

目 录
1 前言 1
2 技术简介 2
3 关键技术 3
3.1 ISPF 3
3.2 PRC 5
3.3 智能定时器 6
3.4 链路状态信息快速通告 7
4 典型应用 7
5 结束语 8
附录A 参考资料 9
附录B 缩略语 9

Copyright ©2007 华为技术有限公司 版权所有侵权必究
i

IGP 快速收敛技术白皮书

IGP快速收敛技术白皮书
摘 要：IGP快速收敛是一项综合性的技术，它通过ISPF、PRC来实现单路由器上的路由快速计算，结合链路状态信息的快速通告、指数退避定时器等技术来实现整个网络的路由快速收敛。本篇文档介绍了IGP快速收敛中所用到的先进技术，最后，阐明了快速收敛对于现代组网的重要意义。
关键词：快速收敛、ISIS、OSPF、ISPF、PRC、指数退避定时器、智能定时器
1 前言
如下图所示，在一台路由器上，路由系统中的路由收敛过程大致可以分解为以下几个步骤1）IGP收到变化的链路状态报文；（2）IGP将变化的链路状态报文通告给邻居，并进行路由计算；（3）IGP根据计算结果向路由管理平面通告路由的变化；（4）路由管理平面将变化的路由下刷到FIB中，指导转发。

若要使得路由收敛的速度加快，就需要针对上述几个关键过程进行优化。其中，IGP路由计算结果－>路由管理平面－>FIB的过程与软件系统的设计有关，不在本文的描述范围之内，可参阅相关的文档。
IGP快速收敛技术主要关注于链路状态信息的接收、发送，以及路由计算过程的优化。其中路由计算的优化是重点。
目前的主流IGP协议（ISIS、OSPF）使用经典的SPF算法计算网络拓扑信息以及路由信息。在绝大多数情况下，当链路状态信息（对应于ISIS协议中的LSP、OSPF协议中的LSA）发生变化时，整个网络拓扑以及路由需要全部重新计算。
对于现在的骨干网络，通常网络拓扑都比较复杂，路由量非常巨大，同时路由收敛性能要求也比较高。这种情况下，全部网络信息重新计算一遍不仅消耗的时间长、收敛慢，而且会耗费大量的CPU资源，对网络设备以及软件系统都造成了一定的冲击，如果是很少一点的网络信息变化而导致的全部重新计算，带来的消耗更是没有必要。
在这种情况下，IGP协议的快速收敛就体现出了其巨大的优势。
2 技术简介
快速收敛是由多项技术结合而成的。
在路由计算方面，主要的思想就是“增量计算即，只计算变化的部分，而不是全部计算）。SPF算法将整个网络信息分为两个部分（如下图所示）：一个部分是网络的顶点（对应于网络中的路由器、共享网段）和边（路由器以及共享网段之间的链路）组成的网络拓扑；另一个部分是挂在顶点上的叶子（网段路由、主机路由）。进行路由计算的路由器称为“根（ROOT）”；路由计算的第一步就是根据拓扑计算出以ROOT为根的一棵最短路径树，第二步就是根据最短路径树计算各个顶点上的叶子（路由）。

针对网络拓扑中的最短路径树的增量计算称为ISPF(Incremental SPF)；而针对叶子（路由）的增量计算则称为PRC (Partial Route Calculate)。“增量计算”能够极大地提高单路由器的计算性能，降低CPU负荷。
另一方面，普通的路由计算定时器一般在10秒时间间隔，也阻碍了路由计算的快速进行，因此定时器的优化也成为要点。采用指数退避的形式来控制定时器的超时时间间隔从短间隔逐步增加到长间隔，可以有效的加快路由的计算速度，同时避免了短时间内进行多次的路由计算。本文以下将这种定时器称为“智能定时器”。
在只有少量信息变化的情况下，如果要求整个网络的快速收敛，不仅要求单路由器的快速计算，同时还需要变化的路由信息能够快速的传播到整个网络中，采用“链路状态信息快速通告”的技术可以实现这一需求。
3 关键技术
3.1 ISPF
在SPF计算中，网络是由顶点（路由器以及共享网段）以及边（路由器之间以及与共享网段之间的链接）构成，最终形成一棵以计算路由器为根的最短路径树；而路由则是附着在树的顶点上的叶子。
ISIS以及OSPF协议在数据库中存储的是自己特定格式的链路信息，这些信息并不能直接反映出拓扑的情况以及路由与拓扑的关系，因此SPF必须通过全部的计算过程来确定最短路径树，并计算出路由。但是，SPF并不保存这个计算结果；这样当有信息发生变化时，SPF只能再次全部重新计算一遍。
ISPF只处理网络拓扑的信息，即只负责计算出最短路径树。通过重新组织链路信息，ISPF形成了一个直接反映网络拓扑的“图”状数据库；而计算出的最短路径树则保存在这个“图”中。当链路状态信息发生变化，ISPF会判断出哪部分网络拓扑受到了影响，从而只计算那些受到了影响的部分，而不是全部网络拓扑。
如下图所示：

RTA为根节点（进行计算的路由器），链路RTCàRTF（红色的链路）的cost由3增长为5，那么受到影响的部分只有RTF、RTH两台路由器（红色圈中），而其他部分的路由器（黑色圈中）则没有受到影响。ISPF会判断出这种影响范围，之后只计算更新RTF、RTH发布的路由。
网络拓扑变化的位置不同，收到影响的范围就不同，ISPF计算所消耗的时间就不同，所以，ISPF计算所消耗的时间是不确定的，即使是在相同的网络结构中。当然，如果发生变化的是根节点的边（图中的RTAàRTB和RTAàRTC），那么受影响的范围就包括了整个拓扑，在这种情况下，ISPF相当于进行了全部重新计算。

3.2 PRC
任何一条路由都是网络节点上的“一片树叶”，在SPF术语中称为叶子。这个比喻很形象，同时也反映出了路由与网络节点之间的关系：从根节点看，只要到网络节点的最短路径确定了，那么到节点发布的路由的最短路径也就确定了。因此，PRC就是直接利用ISPF计算出的最短路径树来计算叶子路由的。当有路由信息改变，PRC直接判断出那条路由（叶子）发生了变化，之后直接进行路由的选择与更新（基于现有的ISPF的计算结果）。
由于ISIS以及OSPF协议的链路信息格式的限制，路由信息与网络节点（发布路由器）之间的关系并不直接，不同发布者发布的相同路由直接也没有直接的联系，因此PRC重新组织数据库。如下图所示：

一方面以“路由”为基点，将所有发布了这条路由的因素组织在一起，这样在计算路由时可以很直观的在所有因素中选择最佳路由；另一方面以“发布者”为基点，将这个发布者发布的所有路由都集结在一起，这样当ISPF宣布某个节点的最短路径发生变化时，这个节点发布的所有路由都会被直接的更新。
特别的，对于OSPF协议，这种数据库的组织方式还可以方便的实现Transit Area的Summary路由（第三类以及第四类）更新过程，而不用重新进行整个区域的计算详细的Summary路由计算过程、以及Transit Area的更新过程请参见“RFC2328”。

3.3 智能定时器
为了能够快速响应网络信息的变化，同时由不会过于频繁的进行路由计算，采用了“智能定时器”的技术。所谓“智能定时器”，是指能够根据预先配置的参数，依照指数退避的规律动态的改变时间间隔的定时器。
智能定时器有三个可配置的参数：初始时间间隔、递增时间间隔、最大时间间隔。定时器最初的时间间隔就是“初始时间间隔”，第二次的时间间隔则是“递增时间间隔”，之后每次的时间间隔都会是前一次的2倍，即“递增时间间隔”×2n，直到到达“最大时间间隔”为止。
通常情况下，“初始时间间隔”可以配置为10毫秒左右（或者小于10毫秒），可以快速响应突然的变化；“递增时间间隔”则可以设置在几十毫秒或者1秒的级别；“最大时间间隔”可以设置在5秒或者10秒的级别。

智能定时器是一个循环定时器，时间间隔不断增大。一方面，他的初始时间很短，可以迅速响应网络变化；另一方面，他的时间间隔不断增加，可以防止频繁的网络变化导致的频繁的路由计算。但是在以下三种情况下，智能定时器将被重置或者停止：
（1） 时间间隔连续三次达到了最大。如果此时有路由计算请求，那么下一次的时间间隔被重置为“初始时间间隔”；否则定时器被停止；
（2） 新产生的路由计算请求与前一次路由计算的时间间隔超过了“最大时间间隔”，那么立即重置定时器的时间间隔为“初始时间间隔”；
（3） 协议进程被RESET。
在特殊情况下（例如网络信息相对稳定，网络的任何变化都要求得到最快速的响应），智能定时器的“初始时间间隔”允许配置为0，使得第一次计算请求立即得到执行；“最大时间间隔”也可以配置为0，表示每一次都立即进行路由计算。但是如果变化信息较多，将导致非常频繁的路由计算，因此不建议这样的配置。
在ISIS以及OSPF协议中规定，同一个链路状态报文不应该频繁的产生。OSPF协议建议的缺省时间间隔为5秒，而ISIS协议建议的缺省时间间隔则是30秒，这个时间对于现在的网络性能来说都太长，而使用智能定时器来控制这个时间间隔，可以很好的解决“频繁产生”与“时间间隔长”之间的矛盾。

3.4 链路状态信息快速通告
链路状态信息快速通告技术只针对ISIS协议而言。根据ISIS协议，当收到一条新的LSP时，只会在这条LSP上标记SRM标志，之后通过定时器定时发送带有SRM标志的LSP。这种设置就延缓了网络变化的传递，增大了整个网络的收敛速度。
为了避免这种情况，ISIS快速收敛允许在每次进行路由计算之前，将一定数量（可以配置）的LSP泛洪出去，在很大程度上提高了网络的收敛速度。
对于OSPF协议，当收到新的LSA时就会立即泛洪出去，因此不需要在这方面使用这样的技术。
4 典型应用

如上图所示，是IGP快速收敛应用的典型网络之一。在Router上将智能定时器的“初始时间间隔”配置为1毫秒；当网络中只有简单路由的变化时，Router上的路由收敛速度（流量切换速度）可以控制在10毫秒的量级；而对于某处的网络拓扑变化，Router上也能够很快的计算出结果。特别的，当这种变化发生在“简单网络”中时，Router根本不会去计算“复杂网络”所对应的巨大量的网络信息。
通常情况下，网络拓扑规模越大、结构越复杂，快速收敛技术带来的效果越明显（收敛时间可以提高1～3个量级），而这种快速收敛的效果具有不确定性。在相同的组网状况下，对于同一台路由器而言，不同位置的网络变化所引起的路由收敛时间会不同，而相同位置的网络变化所引起的不同路由器上的收敛时间也会不同。
在考虑路由收敛时间时，不能仅仅考虑IGP路由计算的时间。正如前面所述，路由收敛时间还要包括IGP路由计算结果－>路由管理平面－>FIB的过程所消耗的时间，通常情况下，这个时间与发生变化的路由的数量有关，数量越大，收敛时间越长。
5 结束语
使用IGP快速收敛特性，路由器的路由收敛速度可以得到极大的提高，同时降低了CPU的负载。使用智能定时器可以很方便的根据网络自身的特点，控制路由计算的反应速度以及计算频度，增强软件系统以及网络系统的路由稳定性。

8
Copyright ©2007 华为技术有限公司 版权所有，侵权必究

IGP 快速收敛技术白皮书

附录A 参考资料
List of reference 参考资料清单：
ISO10589, “Intermediate-System to Intermediate-System”
RFC2328, “OSPF Version 2”
Internet Draft, “draft-alaettinoglu-ISIS-convergence-00”
附录B 缩略语
英文缩写
英文全称
中文解释
IGP
Internal Gateway Protocol
内部网关协议

ISIS
Intermediate-System to Intermediate-System
中间系统到中间系统
OSPF
Open Shortest Path First
最短路径优先
ISPF
Incremental SPF
增量SPF
PRC
Partial Route Calculate
部分路由计算
LSP
Link State Protocol Data Unit
链路状态协议数据单元
LSA
Link State Advertisement
链路状态通告

Copyright ©2007 华为技术有限公司 版权所有，侵权必究
9