计算机网络：路由协议及其作用

1.路由算法

路由算法就是根据度量标准，从众多路径中高效地选择出最佳路由路径。路由算法主要分为两类：

全局式路由算法：每个路由器都拥有网络中其他路由器的全部信息，以及网络的流量状态，也叫LS——链路状态算法。

分布式路由算法：每个路由器只有相邻路由器的信息，没有网络中所有路由器的全局信息，通过迭代计算并与相邻结点交换信息，节点逐渐计算出到达某目的节点或一组目的节点的最低代价路径，也叫DV——距离矢量算法。距离通常用时延或跳数表示，跳数指的是数据包经过的路由器的数目。

第一类：链路状态路由选择算法LS。

（1）确认邻居路由器并获得它们的IP地址。当路由器开始工作后，首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回应答消息，其中包含它自身的IP地址。

（2）测量邻居路由器的应答时延（或者其他重要的网络参数，比如平均流量）。路由器向整个网络发送询问分组数据包，每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，便可以计算出延时。该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间，及目的路由器处理分组数据包和应答的时间。

（3）向网络中的其他路由器广播自己的路由信息，同时接收其他路由器的路由信息。这样，每一个路由器都能够知道网络的拓扑以及状态。

（4）使用一个合适的算法，如Dijkstra最短路径算法，确定网络中两个节点之间的最佳路由。路由器通过（3）建立整个网络的拓扑图，图中的每一条边都有权值，表示代价。代价可以是延时和平均流量的函数，也可以是节点间的跳数（即距离）。

第二类：距离矢量路由选择算法DV。

距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近节点上。主要在RIP协议中使用。

距离矢量路由选择算法的基本思想：每个路由器维护一个距离矢量表，通过相邻路由器之间的距离矢量通告，进行距离矢量表的更新。每个距离矢量表项包括两部分：到达目的节点的最佳传输路径、到达目的节点所需时间或距离。通信子网中的其他每个路由器在表中占据一个表项，并作为该表项的索引。每隔一段时间，路由器会向所有邻居节点发送它到每个目的节点的距离表，同时它也接收每个邻居节点发来的距离表。经过一段时间后，每个路由器都会获得网络中各路由器距离矢量信息，路由器只需要查看这个距离矢量表就可以为不同来源分组找到一条最佳的路由。

2.路由协议

路由协议根据路由算法生成路由表，并选择最佳路径进行数据包转发。它规定了IP数据报在网络中存储和转发的方式。网络的拓扑和状态是不断变化的，如某路由器可能宕机。为了使路由表准确反映路由信息，路由器之间必须不断进行信息交换。路由协议的一个作用就是定义路由器间信息交换的规范。

一方面，Internet的规模非常大，如果让所有的路由器知道整个网络的拓扑，则路由表将非常大，处理起来也太耗时；路由器间的信息交换量也非常大，而交换路由信息所需的带宽就会使因特网的通信链路饱和。

另一方面，许多大型单位不愿意外界了解自己单位网络的布局细节和本单位网络所采用的路由选择协议，但同时还希望连接到因特网上。

为了保障各单位的利益，又便于路由选择，Internet被定义为许多自治系统（AS，Autonomous System）的集合。每一个AS通常由一个单位或组织内部的多个网络互连构成，由一个相对独立的管理机构管理（如ISP），有权自主决定AS内部的路由协议。

由于划分了自治系统，Internet中使用的路由协议可以分为两类。

（1）内部网关协议（IGP，Interior Gateway Protocol）：自治系统内部使用的路由选择协议，这类路由选择协议使用得最多，如RIP和OSPF协议。

（2）外部网关协议（EGP，External Gateway Protocol）：如果源主机和目的主机处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息进行转换，并传递到另一个自治系统中。这样的协议就是外部网关协议（EGP）。在外部网关协议中目前使用最多的是EGP-4。

图4-15中，自治系统A与自治系统B的内部路由选择协议不同，比如自治系统A采用RIP协议，而自治系统B采用的是OSPF协议。当自治系统A的主机H1与自治系统B中主机H2通信时，路由器R1须将RIP协议转换成OSPF协议。

图4-15　自治系统和内部网关协议、外部网关协议

3.路由信息协议

路由信息协议（RIP）是内部网关协议，是IGP中最先得到广泛使用的协议，是一种分布式的基于距离向量的路由选择协议。

RIP的特点：

第一，仅和相邻路由器交换信息。

第二，按固定的时间间隔交换路由信息，如每隔30秒。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。在收到邻居的路由表后，计算更新自己的路由表。

第三，以距离（跳数）作为路由选择的标准。允许一条路径最多只能包含15个路由器，而跳数为16则认为不可达。因此，RIP只适用于小型的自治系统。

第四，由于路由器仅与邻居定时交换路由信息，因此，RIP实现简单，但会影响路由协议收敛的速度，甚至可能不收敛。路由协议的收敛指的是所有的路由器最终都拥有整个自治系统的全局路由信息。

4.开放式最短路径优先协议

开放式最短路径优先（OSPF，Open Shortest Path First）协议是分布式的链路状态协议。所谓“开放式”表明OSPF协议不是受某一家厂商控制，而是公开发表的。所谓“最短路径优先”表明其使用Dijkstra算法，计算出到达每一网络的最短路径，并在检测链路的变化情况（如链路失效）时，执行该算法快速收敛到新的无环路拓扑。

与RIP协议相比，OSPF协议有以下特点：

第一，OSPF路由器收集其所在网络区域上各路由器的连接状态信息，即链路状态信息（Link-State），生成链路状态数据库（Link-State Database）。该链路状态数据库实际上是整个网络的拓扑图。OSPF路由器利用“最短路径优先算法（SPF）”，独立地计算出到达任意目的地的路由。

第二，路由器所发送的是与本路由器相连所有路由器的状态，并且仅当链路状态发生变化时，才进行信息交换，而不是定时信息交换。“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”（metric）。

第三，信息交换采用洪泛法，向所有路由器发送此信息。

第四，分层路由：为了适用于规模大的网络，OSPF将网络分割成一些“区域”（Area），区域内的路由器仅在区域内部交换链路状态信息（LSA）。不同区域通过各区域边界的路由器进行路由聚合后交换LS A。因而，每个路由器的链路状态数据库都可以保持合理的大小，路由计算的时间、报文数量都不会过大。OSPF的更新过程收敛得快是其重要优点。

（1）OSPF区域。

为了使OSPF能够用于规模很大的网络，OSPF将网络分割成一个“主干”连接的一组相互独立的部分，这些相互独立的部分被称为“区域”（Area），“主干”的部分称为“主干区域”。每个区域就如同一个独立的网络，该区域的OSPF路由器只收集、交换和保存该区域的链路状态。区域也不能太大，在一个区域内的路由器最好不超过200个。每一个区域都有一个32bit的区域标识符（用点分十进制表示）。

OSPF区域主要分为主干区域和非主干区域，在上层的区域叫作主干区域（backbone area）。主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在下层的区域。

（2）OSPF中的四种路由器。

在OSPF多区域网络中，路由器可以按不同的需要，同时成为以下四种路由器中的几种。

内部路由器：所有端口在同一区域的路由器，维护一个链路状态数据库。

主干路由器：具有连接主干区域端口的路由器。

区域边界路由器（ABR）：具有连接多区域端口的路由器，一般作为一个区域的出口。ABR为每一个所连接的区域建立链路状态数据库，负责将所连接区域的路由摘要信息发送到主干区域，而主干区域上的ABR则负责将这些信息发送到各个区域。

自治域系统边界路由器（ASBR）：至少拥有一个连接外部自治域网络（如非OSPF的网络）端口的路由器，负责将非OSPF网络信息传入OSPF网络。

（3）OSPF链路状态公告类型。(www.xing528.com)

OSPF路由器之间交换链路状态公告（LSA）信息。OSPF的LSA中包含连接的端口、使用的Metric及其他变量信息。OSPF路由器收集链接状态信息，并使用SPF算法来计算到各节点的最短路径。LSA有以下几种不同功能的报文。

LSA TYPE 1：路由器LS A，由每台路由器为所属的区域产生的LSA，描述本区域路由器链路到该区域的状态和代价。一个边界路由器可能产生多个LSA TYPE 1。

LSA TYPE 2：网络LSA，由指定路由器DR产生，含有连接某个区域路由器的所有链路状态和代价信息。只有DR可以监测该信息。

LSA TYPE3：网络汇总LSA，由ABR产生，含有ABR与本地内部路由器的连接信息，可以描述本区域到主干区域的链路信息。它通常汇总缺省路由而不是传送汇总的OSPF信息给其他网络。

LSA TYPE 4：ASBR汇总LSA，由ABR产生，由主干区域发送到其他ABR，含有ASBR的链路信息。与LSA TYPE 3的区别在于TYPE 4描述到OSPF网络的外部路由，而TYPE 3则描述区域内路由。

LSA TYPE 5：自治系统外部LSA，由ASBR产生，含有关于自治域外的链路信息。除了存根区域和完全存根区域，LSA TYPE 5在整个网络中发送。

LSA TYPE 6：多播LSA，可以让路由器利用链路状态数据库的信息构造用于多播报文的多播发布树。

LSA TYPE 7：非纯末节区域LS A，由ASBR产生的关于NSSA的信息。LSA TYPE 7可以转换为LSA TYPE 5。

（4）报文类型。

Hello报文：通过周期性地发送来发现和维护邻接关系。

DD（链路状态数据库描述）报文：描述本地路由器保存的LSDB（链路状态数据库）。

LSR（LS Request）报文：向邻居请求本地没有的LSA。

LSU（LS Update）报文：向邻居发送其请求或更新的LSA。

LSAck（LS ACK）报文：收到邻居发送的LSA后发送的确认报文。

（5）OSPF报文格式，如图4-16所示。

图4-16　OSPF报文格式

版本：占8bit，OSPF的版本号。“2”表示OSPFv2。

类型：占8bit，OSPF报文的类型，（4）中的5种报文类型之一。

分组长度：占16bit，OSPF分组总长度，包括OSPF首部，单位为字节。

路由器标识符：占32bit，路由器在区域内的唯一标识，可以用路由器上的端口IP。

区域标识符：占32bit，发送该OSPF分组的路由器端口所属的区域。

校验和：占16bit，除“认证”字段之外的整个报文的校验和。

认证类型：占16bit，“0”：不认证；“1”：简单认证；“2”：MD5认证。

5.外部网关协议

边界网关协议（BGP）是一种外部网关协议，用于在不同的自治系统（AS）之间交换路由信息，是唯一一个能处理因特网路由选择的协议。当两个AS需要交换路由信息时，每个AS都必须指定一个运行BGP的节点作为“BGP发言人”，来代表AS与其他的AS交换路由信息。这个节点可以是一个主机，但通常是路由器来执行BGP。两个AS中利用BGP交换信息的路由器也被称为边界网关（Border Gateway）或边界路由器（Border Router）。

BGP的较新版本是1995年发表的BGP-4（BGP的第4个版本）。

对于Internet来说，由于网络规模非常大，自治系统的数量也非常大，自治系统之间要寻找最佳路由是不现实的，BGP只能是力求寻找一条能够到达目的网络且比较好的路由。

同一个自治系统（AS）中的两个或多个对等实体之间运行的BGP被称为I BGP（Internal/Interior BGP）。归属不同的AS的对等实体之间运行的BGP称为EBGP（External/Exterior BGP），如图4-17所示。

图4-17　自治系统和BGP发言人

BGP发言人与其他自治系统中的BGP发言人交换路由信息，要先建立TCP连接，然后在此连接上交换BGP报文，以建立BGP会话，利用BGP会话交换路由信息。

（1）报文类型。

打开（OPEN）报文：是TCP连接建立后发送的第一个消息，用于建立BGP对等体之间的连接关系。

更新（UPDATE）报文：用于在对等体之间交换路由信息。它既可以发布可达路由信息，也可以撤销不可达路由信息。

保活（KEEPALIVE）报文：BGP会周期性地向对等体发出保活消息，用来保持连接的有效性。

通知（NOTIFICATION）报文：当BGP检测到错误状态时，就向对等体发出Notification消息，之后BGP连接会立即中断。

（2）BGP报文格式。BGP的报文格式如图4-18所示。

图4-18　BGP报文格式

标记（Marker）：由16个字节构成。标记字段的值是一个通信双方（对等路由器）都可认可的字节串，双方都统一使用该值来标识一个合法的BGP报文的开始。通常，标记字段用于承载认证信息。对于通信双方，在任何情况下标记的值都必须保持一致。

报文长度：2字节，制定了以字节为单位计算的报文总长度。最小的报文为19节，最大允许报文长度为4096字节。

报文类型：1字节，指出报文所属的类型。

报文数据：不同的报文类型，报文数据不同。

随堂练习

什么是自治系统？RIP，OSPF，BGP都是解决什么问题的？