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

1、IGP 快速收敛技术白皮书华为技术有限公司Huawei Technologies Co., Ltd.IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 i目 录1 前言 .12 技术简介 .23 关键技术 .33.1 ISPF.33.2 PRC .53.3 智能定时器 .63.4 链路状态信息快速通告 .74 典型应用 .75 结束语 .8附录 A 参考资料 .9附录 B 缩略语 .9IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 1IGP 快速收敛技术白皮书摘 要：IGP快速收敛是一项综合性的技术，它通过ISPF

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

3、系 统IGP路 由 管 理 平 面FIB链 路 状 态 信 息 的 接 收链 路 状 态 信 息 的 扩 散 路 由 计 算若要使得路由收敛的速度加快，就需要针对上述几个关键过程进行优化。其中，IGP 路由计算结果路由管理平面FIB 的过程与软件系统的设计有关，不在本文的描述范围之内，可参阅相关的文档。IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 2IGP 快速收敛技术主要关注于链路状态信息的接收、发送，以及路由计算过程的优化。其中路由计算的优化是重点。目前的主流 IGP 协议（ISIS、OSPF）使用经典的 SPF 算法计算网络拓扑信息以及路由信息

4、。在绝大多数情况下，当链路状态信息（对应于 ISIS 协议中的 LSP、OSPF 协议中的LSA）发生变化时，整个网络拓扑以及路由需要全部重新计算。对于现在的骨干网络，通常网络拓扑都比较复杂，路由量非常巨大，同时路由收敛性能要求也比较高。这种情况下，全部网络信息重新计算一遍不仅消耗的时间长、收敛慢，而且会耗费大量的 CPU 资源，对网络设备以及软件系统都造成了一定的冲击，如果是很少一点的网络信息变化而导致的全部重新计算，带来的消耗更是没有必要。在这种情况下，IGP 协议的快速收敛就体现出了其巨大的优势。2 技术简介快速收敛是由多项技术结合而成的。在路由计算方面，主要的思想就是“增量计算”（即，

5、只计算变化的部分，而不是全部计算）。SPF 算法将整个网络信息分为两个部分（如下图所示）：一个部分是网络的顶点（对应于网络中的路由器、共享网段）和边（路由器以及共享网段之间的链路）组成的网络拓扑；另一个部分是挂在顶点上的叶子（网段路由、主机路由）。进行路由计算的路由器称为“根（ROOT ）”；路由计算的第一步就是根据拓扑计算出以 ROOT 为根的一棵最短路径树，第二步就是根据最短路径树计算各个顶点上的叶子（路由）。IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 3RTA RTB RTCRTD RTEROOT ROOT 根 节 点RTA 顶 点在 最 短

6、 路 径树 上 的 边不 在 最 短 路径 树 上 的 边叶 子 （ 路 由 ）针对网络拓扑中的最短路径树的增量计算称为 ISPF(Incremental SPF)；而针对叶子（路由）的增量计算则称为 PRC (Partial Route Calculate)。“增量计算”能够极大地提高单路由器的计算性能，降低 CPU 负荷。另一方面，普通的路由计算定时器一般在 10 秒时间间隔，也阻碍了路由计算的快速进行，因此定时器的优化也成为要点。采用指数退避的形式来控制定时器的超时时间间隔从短间隔逐步增加到长间隔，可以有效的加快路由的计算速度，同时避免了短时间内进行多次的路由计算。本文以下将这种定时器称

7、为“智能定时器”。在只有少量信息变化的情况下，如果要求整个网络的快速收敛，不仅要求单路由器的快速计算，同时还需要变化的路由信息能够快速的传播到整个网络中，采用“链路状态信息快速通告”的技术可以实现这一需求。3 关键技术3.1 ISPF在 SPF 计算中，网络是由顶点（路由器以及共享网段）以及边（路由器之间以及与共享网段之间的链接）构成，最终形成一棵以计算路由器为根的最短路径树；而路由则是附着在树的顶点上的叶子。ISIS 以及 OSPF 协议在数据库中存储的是自己特定格式的链路信息，这些信息并不能直接IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 4反映

8、出拓扑的情况以及路由与拓扑的关系，因此 SPF 必须通过全部的计算过程来确定最短路径树，并计算出路由。但是，SPF 并不保存这个计算结果；这样当有信息发生变化时， SPF 只能再次全部重新计算一遍。ISPF 只处理网络拓扑的信息，即只负责计算出最短路径树。通过重新组织链路信息，ISPF 形成了一个直接反映网络拓扑的“图”状数据库；而计算出的最短路径树则保存在这个“图”中。当链路状态信息发生变化，ISPF 会判断出哪部分网络拓扑受到了影响，从而只计算那些受到了影响的部分，而不是全部网络拓扑。如下图所示：RTARTB RTCRTD RTE RTFRTHRTA 为根节点（进行计算的路由器），链路 R

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

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

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

12、算过程、以及 Transit Area 的更新过程请参见“RFC2328”。IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 63.3 智能定时器为了能够快速响应网络信息的变化，同时由不会过于频繁的进行路由计算，采用了“智能定时器”的技术。所谓“智能定时器”，是指能够根据预先配置的参数，依照指数退避的规律动态的改变时间间隔的定时器。智能定时器有三个可配置的参数：初始时间间隔、递增时间间隔、最大时间间隔。定时器最初的时间间隔就是“初始时间间隔”，第二次的时间间隔则是“递增时间间隔”，之后每次的时间间隔都会是前一次的 2 倍，即“递增时间间隔”2 n，直到到

13、达“最大时间间隔”为止。通常情况下，“初始时间间隔”可以配置为 10 毫秒左右（或者小于 10 毫秒），可以快速响应突然的变化；“递增时间间隔”则可以设置在几十毫秒或者 1 秒的级别；“最大时间间隔”可以设置在 5 秒或者 10 秒的级别。初 始时 间 间 隔 递 增时 间 间 隔 2递 增时 间 间 隔 最 大时 间 间 隔第 一 次计 算 请 求第 一 次计 算第 二 次计 算 请 求第 二 次计 算第 三 、 四次计 算 请 求第 三 次计 算智能定时器是一个循环定时器，时间间隔不断增大。一方面，他的初始时间很短，可以迅速响应网络变化；另一方面，他的时间间隔不断增加，可以防止频繁的网络变

14、化导致的频繁的路由计算。但是在以下三种情况下，智能定时器将被重置或者停止：（1） 时间间隔连续三次达到了最大。如果此时有路由计算请求，那么下一次的时间间隔被重置为“初始时间间隔”；否则定时器被停止；（2） 新产生的路由计算请求与前一次路由计算的时间间隔超过了“最大时间间隔”，那么立即重置定时器的时间间隔为“初始时间间隔”；（3） 协议进程被 RESET。IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 7在特殊情况下（例如网络信息相对稳定，网络的任何变化都要求得到最快速的响应），智能定时器的“初始时间间隔”允许配置为 0，使得第一次计算请求立即得到执行；

15、“最大时间间隔”也可以配置为 0，表示每一次都立即进行路由计算。但是如果变化信息较多，将导致非常频繁的路由计算，因此不建议这样的配置。在 ISIS 以及 OSPF 协议中规定，同一个链路状态报文不应该频繁的产生。 OSPF 协议建议的缺省时间间隔为 5 秒，而 ISIS 协议建议的缺省时间间隔则是 30 秒，这个时间对于现在的网络性能来说都太长，而使用智能定时器来控制这个时间间隔，可以很好的解决“频繁产生”与“时间间隔长”之间的矛盾。3.4 链路状态信息快速通告链路状态信息快速通告技术只针对 ISIS 协议而言。根据 ISIS 协议，当收到一条新的 LSP时，只会在这条 LSP 上标记 SRM

16、 标志，之后通过定时器定时发送带有 SRM 标志的 LSP。这种设置就延缓了网络变化的传递，增大了整个网络的收敛速度。为了避免这种情况，ISIS 快速收敛允许在每次进行路由计算之前，将一定数量（可以配置）的 LSP 泛洪出去，在很大程度上提高了网络的收敛速度。对于 OSPF 协议，当收到新的 LSA 时就会立即泛洪出去，因此不需要在这方面使用这样的技术。4 典型应用复 杂 网 络简 单 网 络Router如上图所示，是 IGP 快速收敛应用的典型网络之一。在 Router 上将智能定时器的“初始IGP 快速收敛技术白皮书 http:/ 2007 华为技术有限公司 版权所有，侵权必究 8时间间隔

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