1.2 路由表的形成
本节讨论距离矢量型路由协议算法和链路状态型路由协议算法。
1.2.1 距离矢量型路由协议
距离矢量型路由协议的名字来源于它的工作原理，即路由算法。运行距离矢量型路由协议的路由器在向它的邻居通告路由信息时通告两项内容：一个是距离，例如，跳数；一个是方向，它转发数据的接口。RIPv1、RIPv2和IGRP协议属于距离矢量型路由协议，EIGRP协议被看做一种高级距离矢量型路由协议（在思科的技术文档中也经常称其为混合路由协议）。
1.路由表的形成
距离矢量路由算法周期性地在路由器之间传送路由表的完整拷贝，并累加路由的度量值。路由器之间通过这样的机制可以就网络的拓扑变化进行定期更新。但是，即使没有网络的拓扑变化，这种更新依然定期发生，如图1-9所示。
图1-9 路由表的更新示意图
每个路由器都从与其直接相邻的路由器接收路由表。路由器根据它们从彼此临近路由器接收的信息确定到达目的网络的最佳路径。但是距离矢量法无法使一个路由器了解到一个网络的确切拓扑信息。一台路由器学习到的路由信息都是它的邻居通告的，而邻居的路由表又是从邻居的邻居那里获得的，并不一定可靠，所以有“谣传协议”之称。这样一台一台地通告下去，最终所有的路由器都学习到了所有路由。
下面以路由信息协议版本1（RIPv1）为例解释一下路由表的形成。RIPv1是早期开发的典型的距离矢量型路由协议，它的路由表更新周期是30秒，以跳数（Hop Count），即跨越路由器的个数为度量值。拓扑结构如图1-10所示。
图1-10 路由表的形成过程（1）
IP路由功能默认是开启的，当3台路由器的接口配置了IP地址并“Up”起来后，它们首先把自己直连的网络号写入路由表，代表它已经识别到了到达直连网络的路由。路由表中的3项内容分别是：第一项，网络号（也可以是子网），如10.0.0.0，表示目标路由，意思是它已经知道到达10.0.0.0这个网络的路由了；第二项，接口号，代表去往目标网络数据的出口，即方向；第三项，度量值。因为是直连的，没有跨越任何路由器，所以是0跳。
当A、B、C运行了RIP后，它们分别向邻居通告它们的路由表。A、C向B通告，B向A、C通告。
A向B通告两条路由，分别是10.0.0.0和11.0.0.0，度量值为当前度量值加1。因为路由器B要想通过A转发数据到达上述两个网络，至少还要经由A，所以在原来的度量值基础上再加1。
路由器B收到A的路由信息后更新自己的路由表。B没有10.0.0.0的路由，因此把该路由写入路由表，并表示出距离是1跳；该路由是从它的s0接口学习到的，即如果要把数据发往10.0.0.0，应该从它的s0接口发出。11.0.0.0的路由B本身就有，而且距离为0，当收到距离为1的路由更新信息时，由于没有自己已经识别的路由近，所以不予采纳。
同理，路由器B只采纳路由器C通告过来的两条路由中的13.0.0.0这条路由。
在B通告给A和C的路由信息中，A只采纳12.0.0.0这条路由，C只采纳11.0.0.0这条路由。
这次更新周期过后的路由表如图1-11所示。
图1-11 路由表的形成过程（2）
当B的下一个更新周期到时，B把自己的路由表通告给A和C。这4条路由分别是：11.0.0.0，hop=1；12.0.0.0，hop=1；10.0.0.0，hop=2；13.0.0.0，hop=2。
A对照自己的路由表与这些路由进行比较。10.0.0.0和11.0.0.0这两条路由不如自己路由表中的优，不采纳。12.0.0.0这条路由和现有的路由相等，并且都是B通告的，A对该路由条目的老化时间进行刷新，重新计算老化时间。因为缺少13.0.0.0的路由，A采纳了B通告的路由13.0.0.0。
C对照自己的路由表做同样的比较，最后采纳了10.0.0.0的路由。
此时的路由表如图1-12所示。
图1-12 路由表的形成过程（3）
至此，3台路由器对网络上的所有应该了解的路由都学习到了，这种状态称为路由收敛，达到路由收敛状态所花费的时间叫做收敛时间（Convergence Time）。
从上述过程可以看出，这种协议不适合运行在大型网络中，因为网络越大收敛越慢。路由表没有收敛时某些数据是不能转发的。因为缺少路由，人们期望快速收敛，这样可以减少路由器不正确的路由选择。
2.负载均衡
负载均衡指在多条到达同一目的地的路径上共同传送数据。Cisco路由器默认地支持4条等值路径负载均衡。距离矢量型路由协议都支持等值路径的负载均衡。IGRP和EIGRP协议还支持非等值路径的负载均衡。
1.2.2 路由环路的形成
如图1-13所示，当路由器R1、R2、R3都运行了距离矢量型路由协议RIP之后，它们定期地向直连邻居通告自己的路由表。
172.16.0.0/16是和R1直连的网络，所以R2所了解的到达172.16.0.0的路由是R1通告给R2的；R3所了解的到达172.16.0.0的路由是路由器R2通告的。经过一段时间后，路由收敛，路由表处于稳定状态。这时R1的路由表显示出到达172.16.0.0的距离是0跳（直连）；R2的路由表显示出到达172.16.0.0的距离是1跳，该信息来源于R1；R3的路由表显示到达172.16.0.0的距离是2跳，该信息来源于R2。
图1-13 路由环路的形成（1）
假设从某个时间起172.16.0.0出现了故障变得不可用了，那么R1首先更新它的路由表，把该路由条目从路由表中删去，如图1-14所示。当它的更新周期到时就把该信息通告给R2。
图1-14 路由环路的形成（2）
但是如果在R1的路由更新周期还没有到时，R2的更新周期却到了，R2把自己的路由表通告给R1（当然也通告给R3，R3不修改路由表，因为内容没有变化），其中包含有到达172.16.0.0的路由条目，并且距离是2跳（当然这是个错误的信息）。由于R1当前没有到达172.16.0.0的路由，所以R1接收并把该条路由写入路由表，如图1-15所示。
图1-15 路由环路的形成（3）
之后R1的路由更新周期到，R1就把它的整个路由表通告给了R2，其中包含这个错误的路由条目。由于R2最初是从R1处学习到的到达172.16.0.0的路由，所以这次R1的路由更新信息它依然接收，此时在R2的路由表中显示，到达172.16.0.0的路由的度量值为3，如图1-16所示。
图1-16 路由环路的形成（4）
然后，当R2的更新周期到来时，它会以hop=4通告给R1和R3。R1和R3把路由表修改为到达网络172.16.0.0的距离为4，如图1-17所示。
图1-17 路由环路的形成（5）
如果没有其他因素影响，这种循环将永远持续下去，度量值将会累加到无穷大（Count to Infinity）。
在这种情况下，如果路由器R1收到目标是172.16.0.0的数据，根据路由表的指示，它将把数据转交给R2。R2收到数据后查阅路由表，根据路由表的指示，它将把数据回送给R1。路由环路由此在R1和R2之间形成。
1.2.3 避免环路的技术
路由环路的危害非常大，应该采取措施避免路由环路的形成。解决路由环路的方法也有多种。
1.定义最大跳数
解决路由环路的办法之一是对度量值定义一个极限值，当跳数累加到该极限值时，路由器就认为该路由不可达，也就不在使用这条路由了，从而有限度地避免了路由环路。这样做的缺点是它将限制路由更新信息在大型网络中的传播，造成这种协议不适合运行在大型网络中。
不同的协议有不同的极限值。RIP协议的最大值是16跳，IGRP协议的默认最大值为100跳。
2.避免路由回传
从1.2.2节的例子可以看出，路由环路产生的主要原因是R2把来源于R1的路由172.16.0.0又通告给了R1。如果R2不回传来源于R1的路由信息，路由环路也就不会产生。基于这个原因，人们开发了一个协议来解决路由回传问题。这个协议称为Split Horizon（许多资料将其翻译为“水平分割”，但Horizon没有水平的意思，所以笔者认为这种翻译欠妥）。
Split Horizon的含义是：禁止路由器从接口通告那些来自该接口的路由信息。即从某个接口学习到的路由信息不能再从该接口通告出去，通俗地讲，就是不回传路由信息，如图1-18所示。该功能在路由器上默认是启动的，但可以关闭。
图1-18 Split Horizon示意图
3.触发更新
再次分析路由环路的形成原因。当R1发现172.16.0.0失效后，并没有立即把该路由变化的信息通告给邻居，因为它的更新周期还没到。而此时R2的更新周期先行到达，把它的路由表通告给了R1，由此R1得到了错误的路由条目。这表明周期性地更新机制是距离矢量型路由协议的又一缺点。如果R1使用触发更新（Triggered Update）机制通告路由表，当它发现172.16.0.0失效后，就立即把该信息通告给邻居，R2就马上得到172.16.0.0不可达的信息，它就不可能把错误的信息（172.16.0.0可达）回传给R1，环路也就不可能产生。由此看来，触发更新机制比周期性更新机制更有效。一旦网络拓扑发生变化最先检测到该变化的路由器就立即发出一个路由更新信息，不必等待更新周期的到来。这样既提高了效率，缩短了收敛时间，也能避免路由环路。
4.路由毒化和反向毒化
当R1检测到172.16.0.0不可用后，立即向R2发出一个包含该路由被毒化的路由更新，即把到达172.16.0.0路由的度量值设为最大跳数，对于RIP来说是16跳，表明该路由不可用，如图1-19所示。作为R1邻居的R2也把到达网络172.16.0.0的路由毒化，当更新周期到达时把该路由回应给R1，这叫反向毒化（Poison Reverse）。同时R2也会把这条毒化路由通告给其他邻居。反向毒化避免了不正确的路由信息回传，因此路由环路不能形成。
图1-19 路由毒化和反向毒化
5.保持计时器
从另外一个角度来看路由环路和计算到无穷的问题。当172.16.0.0不可用之后，R1收到R2的路由更新信息并且采纳，而后又把这个不正确的信息再次通告给了R2，R2又采纳，这样，这个错误的信息便一直循环下去。
如果R1在检测到172.16.0.0不可用之后，立即向R2发出一个路由更新信息，告诉R2 172.16.0.0不可用（也告诉其他邻居，如果有的话），就是前面所谈到的触发更新。R2在收到R1的路由更新信息后，立即对该条路由启动一个保持计时器（Hold-down Timer）,使其在一段时间内不再变化，类似冻结，这个问题可能就解决了，如图1-20所示。
图1-20 保持计时器
随着R2路由信息的通告，R2的其他邻居也就知道了172.16.0.0不可用，这些邻居都会把该条路由“冻结”一段时间。该信息被邻居通告给邻居的邻居，这样下去使得网络上尽可能多的路由器都知道了网络拓扑变化的信息，避免把不正确的路由信息反传而形成环路。
在“冻结”时期如果原来的路由恢复了（如R1又通告R2 172.16.0.0可用了），保持计时器结束并使用该路由；如果其他邻居（非R1）通告了一条比原路由（原来R1通告的路由）更好的路由，“冻结”结束并采纳新路由；所有比原路由更差的路由都不采纳，除非“冻结”已经结束。
除此之外，保持计时器还可以起到稳定网络的作用，避免由于某一点网络拓扑的变化引起大面积的网络波动。
以上谈到的这些特性都与距离矢量型路由协议的路由环路有关，但不仅仅是为了解决路由环路才使用这些特性，比如保持计时器特性在链路状态型路由协议中也使用，但不是解决环路的，而是用于增强网络的稳定性的。这些特性也并非独立运行，往往结合使用。
实际上，网络拓扑发生变化及路由器的处理步骤是这样的，如图1-21所示。
图1-21 拓扑变化后的路由更新过程
●第一步，172.16.0.0失效。
●第二步，当R1检测到172.16.0.0失效后立即向R2发送路由更新（触发更新）信息。
●第三步，R2收到172.16.0.0失效信息后马上把该路由“冻结”，并启动一个保持计时器。
●第四步，R2向R3发出路由更新（触发更新）信息，同时R2向R1发出反向毒化路由信息。
●第五步，R3启动保持计时器“冻结”172.16.0.0路由。
●第六步，R3向其他邻居发送触发更新信息并向R2发送反向毒化路由信息。
如果没有关于到达172.16.0.0的新的路由信息，最终它们会把这条路由从路由表中删除。
1.2.4 链路状态型路由协议
链路状态型路由协议的典型代表是OSPF（Open Shortest Path First，开放最短路径优先）。链路状态型路由协议的路由算法与距离矢量型路由协议的路由算法运行截然不同。运行距离矢量型路由协议的路由器依靠它的邻居获取路由信息，实际上，它对远方的网络状况一无所知，仅是“听说”而已。链路状态型协议则不同。运行链路状态型路由协议的路由器是通过获取远方网络的链路状态信息，了解整个网络或既定区域的，这种认识是直接的、完整的。链路的一系列参数描述了链路的状态，例如，链路类型、IP地址与掩码、带宽、延迟及可靠度等。
1.计算路由表
链路状态型路由协议与距离矢量型路由协议的最大不同在于路由表的来历。链路状态型路由协议的路由表是自己计算得来的，分三个步骤完成。
第一步，建立邻居关系。链路状态型路由协议依赖路由器之间的链路状态获取对整个网络或既定区域拓扑的认识，所以相邻路由器在通告路由信息之前必须相互识别，了解哪些链路上存在哪些邻居。这项工作是通过发送Hello数据包完成的。如图1-22所示，R1认识到在12.0.0.0/8的网络上存在邻居R2和R3；R2认识到在12.0.0.0/8的网络上存在邻居R1和R3；R3认识到在12.0.0.0/8的网络上存在邻居R1和R2，在13.0.0.0/8的网络上有邻居R4；R4认识到在13.0.0.0/8的网络上有邻居R3。Hello包负责建立和维护邻居关系，确保在邻居间的通信是双向的。
图1-22 建立邻居关系
第二步，交换链路状态信息。当邻居关系确定之后，路由器使用链路状态广播包（Link State Advertisement，LSA）向邻居通告自己所直连的链路的状态信息（如图1-23所示），也称为链路状态描述信息。该信息包括诸如链路类型、通告者的地址和LSA的序号（用于确定LSA的新旧程度）等。
图1-23 扩散LSA
路由器只把链路状态描述信息发给邻居，邻居复制该信息后再转发给它的邻居，这个过程称为扩散（Flooding）。最终使这份来自某路由器的原始的链路状态描述信息传遍整个网络或既定区域。每台路由器把所有的链路状态描述信息搜集起来构建自己的拓扑结构（链路状态）数据库，如图1-24所示。由于路由器收集的信息是原始的（没有经过转发邻居的篡改），所以它对网络拓扑的认识也是直接的和真实的，而且在同一个区域工作的路由器有相同的拓扑数据库。
图1-24 链路状态数据库
第三步，计算路由表。每台路由器根据自己构建的拓扑结构数据库，使用SPF算法计算出最近路径并体现在路由表中，如图1-25所示。
图1-25 运行SPF算法计算出路由表
SPF是一种数学算法，它把网络看做一组由点到点链路连接起来的节点（Node），每条链路都有代价（Cost），然后计算出从某节点出发到达网络中其他任意节点的最小代价路径。计算的最终结果是一个树型的拓扑，树的根就是出发节点。因为是树型拓扑，所以没有环路。运行SPF的路由器都以自己为树的根计算到达其他节点的最佳路由。图1-26所示的是路由器B计算的到达其他路由器的最佳路径示意图（关于SPF算法已超出本书范围，这里只是让读者对此算法有个直观的了解才引用图1-26的）。
图1-26 SPF算法
2.路由信息的维护
路由协议在刚开始运行时，链路上有大量的LSA在扩散，当路由表第一次收敛之后，路由器就不再扩散LSA了，但仍然定期发送Hello数据包以维持它们的邻居关系。当网络拓扑结构发生变化时，与变化链路直连的路由器就发出链路状态更新的LSA，通告这一变化。该链路状态更新LSA所通告的内容仅包含发生变化的链路的有关信息，没有发生变化的链路的状态信息不再通告，这种更新方式称为增量更新。
收到链路发生变化的LSA后，路由器把它和自己链路状态数据库中相应的条目作对比，如果收到的LSA条目不存在于自己的链路状态数据库中或者比自己库中的条目新，则把该条目写入数据库中，并扩散该信息。然后运行SPF算法，根据新的链路状态数据库生成新的路由表。如果和原有条目相同，则忽略它。如果收到的LSA比自己已知的旧，路由器则用自己的新信息向发送方发送一个链路状态更新LSA。
3.链路状态型路由协议的特点
链路状态型路由协议和距离矢量型路由协议相比有以下特点：
●没有跳数限制。
●以路径花费（Cost）值作为选择最佳路径的度量。Cost是能够体现带宽的一个参数，所以路由器可以根据链路的实际带宽选择路径。
●事件触发（Event-triggered）的更新机制。并非像距离矢量型协议一样定期更新。
●增量更新。因为更新的信息量比较少所以路由收敛快。
●更新的是链路状态数据库而不是路由表。
●所有路由器有一个完整和同步的网络拓扑图，所以没有环路。
●路由器需要更多的内存和更大的处理能力。
●网络初期LSA的扩散可能会占用大量的带宽。
●需要对网络进行优化设计，这样既能减小拓扑库也能优化网络性能。