ISIS路由协议中路由计算研究

摘 要：路由算法在路由器中至关重要,好的路由算法能够提高路由器性能。分析了目前常用的几种ISIS路由算法，SPF、ISPF和PRC以及工业界采用的简化SPF算法。在此基础上提出一种改进方案是半拓扑SPF算法，在较稳定的网络中使得路由计算速度大大提高。

关键词：ISIS； SPF； ISPF； PRC； 简化SPF； 半拓扑SPF

中图分类号：

TN915-34

文献标识码：A

文章编号：1004-373X(2011)19

-0094

-03

Routing Algorithm Analysis of ISIS Protocol

LI Jun-jie

(Beijing Jiaotong University, Beijing 100044, China)

Abstract： Routing algorithm is very important in the router, which can improve router′s performance. Several common ISIS routing algorithms such as SPF, ISPF, PRC and a simplified SPF algorithm used in the industry are analyzed. A semi-topological SPF is proposed, which improves route calculation speed greatly in the stable network.

Keywords： ISIS; SPF; ISPF; PRC; simplified SPF; semi-topological SPF

收稿日期：2011-04-18

OSPF协议过于复杂大大限制了支持的路由器的数量和路由的条数，ISIS路由协议相对于OSPF来说实现简单，所以越来越多的企业采用ISIS协议作为网络中的IGP协议［1］，如何更高效的实现ISIS协议是当前研究的热点。路由计算是协议的核心部分，因此加快路由计算来加快路由收敛越来越受到重视，很多学者研究改进路由算法来加快路由计算。本文分析了几种工业中应用的路由算法和它们的不足，在此基础上提出┮恢职胪仄SPF算法。

1 常见的路由计算方案分析

1.1 SPF算法

SPF最短路径优先算法，采用Dijkstra算法，在链路状态路由协议中用来计算到网络的最短路径［2］。每台路由器都是以自己为根节点，其他路由器为叶子节点，根据网络拓扑信息生成一棵最短路径树SPT，然后计算出根节点到各个目的地的最短路径，但 SPF并不保存这棵最短路径树，当链路状态发生变化时，不论是否影响网络的拓扑结构，SPF 只能再次全部重新计算一遍这棵最短路径树［3］。网络规模扩大的时候，链路状态变化频率增加，SPF计算频度增加，同时链路状态数据库随之增大，每次SPF的计算时间也会很长，基于以上不足，工业界提出了ISPF算法和PRC结合的改进方案。

1.2 ISPF算法和PRC算法结合

1.2.1 ISPF算法介绍

ISPF(Incremental SPF)是指增量路由计算，它每次只对变化的一部分路由进行计算，而不是对全部路由重新计算［4］。ISPF改进了SPF算法，第一次计算时需要计算全部节点，之后只是计算受影响的节点，大大降低了CPU的占用率，提高了网络收敛速度。ISPF算法实现的关键点是如何选取要计算的最小范围和如何在选定的范围内重新计算，同时要求：每次计算完成后保存SPT，记录SPT上每个节点的路径；建立节点同路由之间的对应关系，每次只更新变化节点的路由信息。

链路状态变化对路由计算的影响：

(1) cost增加，处于删除状态的link看作是cost从有效值增加到无穷大。若link不是SPT上的有效路径，cost增加后不影响SPT树结构，不需重新计算；若link在SPT上，cost增加需要重新计算。

(2) cost减少，新增link可看作是cost从无穷减少到有效值。cost减少时无论link在不在SPT上都需要重新计算，因为此时可能影响其他路由器的路径。

(3) 若仅仅是link的下一跳(邻居路由器)变化或者协议类型变化(由ISIS变为OSPF)，cost不变，则不需重新计算，只需更新相关节点的下一跳。

(4) SPT上节点状态变化对link的影响。节点处于删除状态，则与该节点相连的所有link都标记为删除状态，需要重新计算；节点处于过载状态，则所有到达该节点的link都标记为受影响状态，需要重新计算；节点从过载状态恢复正常或者是新增节点，则SPT上节点到该节点的link都标记为受影响状态，需要重新计算。

ISPF第一次计算时要计算全部节点，之后只计算变化的部分，每次计算完成后要记录整个拓扑关系，保存生成的最短路径树SPT，ISPF能够形成一个直接反映网络拓扑的“图”状数据库，而计算出的SPT则保存在这个“图”中［5］。当链路状态发生变化时，根据上述原则判断是否需重构SPT树，若需要则按一定原则得到拓扑变化影响到的节点，然后在受影响的节点范围内做SPF计算即ISPF，其他未受到影响的节点拓扑关系保持不变。根据增量计算结果更新SPT树，并将受到影响节点的路由进行更新，即PRC部分路由计算。

1.2.2 PRC部分路由计算

PRC是部分路由计算，它与ISPF配合使用。PRC的原理也是只计算变化的那一部分，但PRC不需要计算节点路径，而是根据ISPF算出来的SPT来更新路由［6］。如果ISPF计算后的SPT改变，PRC处理所有变化的节点上的所有路由；如果经过ISPF计算后的SPT并没有变化，只有叶子节点变化，则PRC只处理变化的叶子节点的路由信息。

PRC计算是为了处理变化的ISIS路由，而ISIS路由的变化由叶子节点变化引起。系统节点的变化必然引起系统节点上叶子节点的变化，因此在PRC计算时要先处理变化的系统节点，然后处理变化的叶子节点。PRC算法实现时先提交变化节点，将节点下的路由放入路由变化表中，然后遍历路由变化列表，将变化的路由下刷到路由管理的IP路由表。

1.2.3 ISPF算法的不足

网络拓扑变化的位置不同，受到影响的范围就不同，ISPF计算所消耗的时间就不同。最坏情况是整个拓扑受到影响，ISPF相当于进行了全部重新计算。ISPF算法进行路由计算的时间包括搜寻受影响节点的计算时间，增量路由计算的时间和PRC计算的时间。┮话闱榭鱿滤蜒笆苡跋旖诘愕募扑愫驮隽柯酚杉扑愕氖奔渥芎突岜燃扑闳部拓扑的时间少，因此ISPF在大多数情况下能够减少计算开销、增加收敛速度。但ISPF算法实现流程过于复杂，在某种网络中的计算效率比SPF还要差［7］，例如某一链路的变化引起整个拓扑结构的变化，则增量路由计算的时间其实是整个拓扑计算的时间，使用ISPF算法还增加了搜寻时间，此时ISPF算法反而会比传统的SPF算法开销更大，因此工业界又提出了简化SPF算法。

1.3 简化SPF算法

简化SPF算法是先判断链路的变化是否需要重构SPT树，如果不影响SPT结构，采用PRC进行路由信息更新；如果影响到SPT，则所有节点直接进行全部的SPF计算重构SPT。简化SPF算法需要记录整个网络的拓扑关系，保存每次SPF计算生成的SPT树。此时PRC用来处理网络拓扑不变而路由信息发生改变的情况，这样就是根据网络变化的不同情况做出最精简的处理，使得路由计算处理工作量降到最低，从而大大节约路由计算所用时间［8］。

上面已经介绍了各种链路变化以及是否需要重构SPT，有些链路的变化是不需要重构SPT的。简化SPF算法与ISPF计算时间相比，判定链路变化是否需要重新计算拓扑的时间复杂度比确定受影响的节点范围的时间复杂度小得多，虽然计算全部拓扑的时间大于增量拓扑计算的时间，但对于节点变化影响大部分网络拓扑时，简化SPF算法能够减少很多无效计算。但有时变化的节点靠近叶子节点，受影响的节点范围很小，全部节点进行SPF计算又增加了路由计算时间，没有充分利用原来的SPT［9］，因此本文提出了半拓扑SPF算法。

2 半拓扑SPF算法

半拓扑SPF算法是先判断链路的变化是否影响网络的拓扑结构，是否需要重构SPT树，如果不影响SPT结构，直接采用PRC更新路由信息；如果影响到SPT，则判断变化的链路指向的节点在网络中的拓扑层次，若在上层则全部节点进行SPF计算，若在下层则采用ISPF找出受影响的节点进行变化部分的增量路由计算，重构SPT后采用PRC算法更新路由。半拓扑SPF算法需要记录整个网络的拓扑关系，同时要保存每次SPF计算生成的SPT树，还要保存每个路由器所在的网络层次。

简单网络的SPT结构图如图1所示。第一次路由计算时对全部节点进行SPF计算，构造SPT时同时标记┟扛雎酚善魉在的网络层次，因为存在等价路由，所以节点所属层次按最小的层次算，如图1中第二层左面的节点，它同时也在第三层，这时就按第二层来算。当变化的链路影响拓扑结构时，找出这条链路的目的节点，若该节点所在的层次小于全网层次的50%，则认为是上层网络受到影响，否则就是下层网络受到影响，如上面的SPT结构图共有6层，若1层和2层节点受影响，则全部节点进行SPF计算重构SPT，其他层节点受影响时，则采用ISPF算法寻找受影响的节点进行增量路由计算。若是新增节点则找出所有和该节点建立邻居的节点的最小层次，判断该最小层次的下一层在网络中的层次，因为该新增节点的源节点路由不变不需重新计算；若是SPT上节点发生变化则判断该节点所在的层次，然后依据该层次进行判断采用哪种算法。

图1 最短路径树SPT

半拓扑SPF算法进行路由计算的时间包括判定变化的链路是否需要重新进行拓扑计算的时间，判定采用哪种路由算法的时间，拓扑计算的时间和PRC计算的时间。当受影响的节点在网络上半层时，半拓扑SPF算法比简化SPF算法多了判断采用那种路由算法的时间，但该时间极短，与ISPF算法相比少了寻找受影响节点的时间，虽然全部节点进行SPF计算时间比部分路由计算多，但总体上还是优于ISPF算法；当受影响的节点在网络的下半层时，半拓扑SPF算法相对于ISPF算法多了判断采用那种路由算法的时间，相对于简化SPF，找出受影响的节点再进行增量路由计算的时间小于全部节点进行SPF计算的时间。从总体上看半拓扑SPF算法是以牺牲较小的内存空间换取了路由计算速度的提高。

3 结 语

本文主要分析了几种路由算法，SPF是比较传统的算法，但现在的网络拓扑复杂而且变化频繁，导致路由量巨大，路由计算速度慢，于是工业界采用增量计算ISPF和PRC算法来加快路由计算，但当拓扑变化发生在拓扑结构的上层时，ISPF比SPF计算更复杂，由此工业界提出了简化SPF，但当拓扑变化发生在拓扑结构的下层时又增加了计算时间，因此本文提出半拓扑SPF算法，从总体上看此算法最优。节点总数不变时减少网络层次，增加每台路由器的邻接路由器数量可以改善网络结构［10］。改进的路由算法结合优化的网络结构能进一步提高路由计算的速度。

参 考 文 献

［1］别碧勇.ISIS路由协议及其在IP网络工程设计中的应用［J］.铁道勘测与设计，2006(1)：47-53.

［2］华为技术有限公司.DA000009 IS-IS路由协议ISSUE 3.0［M］.深圳:华为技术有限公司，2007.

［3］何涛.ISIS协议在IP网络中的设计与应用［D］.北京：北京邮电大学，2007.

［4］Stim.ISIS的几种快速收敛特性［EB/OL］.［2007-10-31］.，2007.

［5］华为技术有限公司.IGP快速收敛技术白皮书［M］.深圳:华为技术有限公司，2007.

［6］任荣锦.IP网络中IGP路由快速收敛的探讨与实现［D］.广州：华南理工大学，2006.

［7］李园花,李健,赵凯.基于链路状态路由快速收敛技术的研究［J］.网络安全技术与应用，2009(3)：9-11.

［8］佚名.IS-IS快速收敛技术白皮书［M］.杭州:杭州华三通信技术有限公司，2007.

［9］高占春,柴广宏.ATN路由器中路由算法IS-IS的研究与改进［J］.数据通信，2005(3)：35-38.

［10］邓永平,徐建峰.IGP路由收敛分析及优化［J］.电信科学，2005(4)：13-15.