计算机网络--互联网的路由选择协议

上节介绍了网际控制报文协议 ICMP

这节介绍互联网的路由选择协议

一、有关路由选择协议的几个基本概念

1.1 理想的路由算法

路由选择协议的核心就是路由算法，即需要何种算法来获得路由表中的各项目。一个理想的路由算法应具有如下的一些特点：

（1）算法必须是正确的和完整的。这里，“正确”的含义是：沿着各路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。

（2）算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。

（3）算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。当网络中的通信量发生变化时，算法能自适应地改变路由以均衡各链路的负载。当某个或某些结点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时地改变路由。有时称这种自适应性为“稳健性” (robustness)。

（4）算法应具有稳定性。在网络通信量和网络拓扑相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使得出的路由不停地变化。

（5）算法应是公平的。路由选择算法应对所有用户（除对少数优先级高的用户） 都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显地不符合公平性的要求。

（6）算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组平均时延最小而网络的吞吐量最大。虽然我们希望得到“最佳”的算法，但这并不总是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均时延或最大吞吐量更加重要。因此， 所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

一个实际的路由选择算法，应尽可能接近于理想的算法。在不同的应用条件下，对以上提出的六个方面也可有不同的侧重。

应当指出，路由选择是个非常复杂的问题，因为它是网络中的所有结点共同协调工作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络中出了某些故障。此外，当网络发生拥塞时，就特别需要有能缓解这种拥塞的路由选择策略，但恰好在这种条件下，很难从网络中的各结点获得所需的路由选择信息。

倘若从路由算法能否随网络的通信量或拓扑自适应地进行调整变化来划分，则只有两大类，即静态路由选择策略与动态路由选择策略。静态路由选择也叫做非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。对于很简单的小网络，完全可以采用静态路由选择，用人工配置每一条路由。动态路由选择也叫做自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。因此，动态路由选择适用于较复杂的大网络。

1.2 分层次的路由选择协议

互联网采用的路由选择协议主要是自适应的（即动态的）、分布式路由选择协议。由于以下两个原因，互联网采用分层次的路由选择协议：

（1）互联网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使互联网的通信链路饱和。

（2）许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到互联网上。

为此， 可以把整个互联网划分为许多较小的自治系统(autonomous system)，一般都记为AS。自治系统 AS 是在单一技术管理下的一组路由器，而这些路由器使用一种自治系统内部的路由选择协议和共同的度量。 一个 AS 对其他 AS 表现出的是一个单一的和一致的路由选择策略。

在目前的互联网中，一个大的 ISP 就是一个自治系统。这样， 互联网就把路由选择协议划分为两大类，即：

（1）内部网关协议 IGP (Interior Gateway Protocol) 即在一个自治系统内部使用的路由选择协议，而这与在互联网中的其他自治系统选用什么路由选择协议无关。目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。

（2）外部网关协议 EGP (External Gateway Protocol) 若源主机和目的主机处在不同的自治系统中（这两个自治系统可能使用不同的内部网关协议），当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议 EGP。目前使用最多的外部网关协议是 BGP 的版本 4（BGP-4）。

自治系统之间的路由选择也叫做域间路由选择(interdomain routing)，而在自治系统内部的路由选择叫做域内路由选择(intradomain routing)。

下图是两个自治系统互连在一起的示意图。每个自治系统自己决定在本自治系统内部运行哪一个内部路由选择协议（例如，可以是 RIP，也可以是 OSPF）。但每个自治系统都有一个或多个路由（图中的路由器 R1 和 R2）除运行本系统的内部路由选择协议外，还要运行自治系统间的路由选择协议（BGP-4）。

自治系统和内部网关协议、外部网关协议

这里我们要指出两点：

（1）互联网的早期 RFC 文档中未使用“路由器”而是使用“网关”这一名词。但是在新的 RFC 文档中又改用“路由器”这一名词，因此有的书把原来的 IGP 和 EGP 分别改为IRP（内部路由器协议）和 ERP（外部路由器协议）。

（2）RFC 采用的名词 IGP 和 EGP 是协议类别的名称。但 RFC 在使用名词 EGP 时出现了一点混乱，因为最早的一个外部网关协议的协议名字正好也是 EGP。后来发现该RFC 提出的 EGP 有不少缺点，就设计了一种更好的外部网关协议，叫做边界网关协议 BGP(Border Gateway Protocol)，用来取代旧的 RFC 827 外部网关协议 EGP。实际上，旧协议EGP 和新协议 BGP 都属于外部网关协议 EGP 这一类别。因此在遇到名词 EGP 时，应弄清它是指旧协议 EGP还是指外部网关协议 EGP 这个类别。

总之，使用分层次的路由选择方法，可将互联网的路由选择协议划分为：

内部网关协议 IGP：具体的协议有多种，如 RIP 和 OSPF 等。外部网关协议 EGP：目前使用的协议就是 BGP。

对于比较大的自治系统，还可将所有的网络再进行一次划分。例如，可以构筑一个链路速率较高的主干网和许多速率较低的区域网。每个区域网通过路由器连接到主干网。 当在一个区域内找不到目的站时，就通过路由器经过主干网到达另一个区域网，或者通过外部路由器到别的自治系统中去查找。下面对这两类协议分别进行介绍。

二、内部网关协议 RIP

2.1 工作原理

RIP (Routing Information Protocol)是内部网关协议 IGP 中最先得到广泛使用的协议，它的中文名称叫做路由信息协议，但很少被使用。 RIP 是一种分布式的基于距离向量的路由选择协议，是互联网的标准协议，其最大优点就是简单。

RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录（因此，这是一组距离，即“距离向量”）。 RIP 协议将“距离”定义如下：

从一路由器到直接连接的网络的距离定义为 1。从一路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。“加 1”是因为到达目的网络后就进行直接交付，而到直接连接的网络的距离已经定义为 1。

RIP 协议的“距离”也称为“跳数” (hop count)，因为每经过一个路由器，跳数就加1。 RIP 认为好的路由就是它通过的路由器的数目少，即“距离短”。 RIP 允许一条路径最多只能包含 15 个路由器。因此“距离”等于 16 时即相当于不可达。可见 RIP 只适用于小型互联网。

需要注意的是，到直接连接的网络的距离也可定义为 0（采用这种定义的理由是：路由器在和直接连接在该网络上的主机通信时，不需要经过另外的路由器。既然每经过一个路由器要将距离加 1，那么不再经过路由器的距离就应当为 0）。作者编写的其他版本的教材过去也曾使用过这种定义。但两种不同的定义对实现 RIP 协议并无影响，因为重要的是要找出最短距离，将所有的距离都加 1 或都减 1，对选择最佳路由其实是一样的。

RIP 不能在两个网络之间同时使用多条路由。 RIP 选择一条具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。

RIP 协议的特点是：

（1）仅和相邻路由器交换信息。如果两个路由器之间的通信不需要经过另一个路由器，那么这两个路由器就是相邻的。 RIP 协议规定，不相邻的路由器不交换信息。

（2）路由器交换的信息是当前本路由器所知道的全部信息，即自己现在的路由表。也就是说，交换的信息是：“我到本自治系统中所有网络的（最短）距离，以及到每个网络应经过的下一跳路由器”。

（3）按固定的时间间隔交换路由信息，例如，每隔 30 秒。然后路由器根据收到的路由信息更新路由表。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。

这里要强调一点：路由器在刚刚开始工作时， 它的路由表是空的。然后路由器就得出到直接相连的几个网络的距离（这些距离定义为 1）。接着，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。但经过若干次的更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。

看起来 RIP 协议有些奇怪，因为“我的路由表中的信息要依赖于你的，而你的信息又依赖于我的。”然而事实证明，通过这样的方式—“我告诉别人一些信息，而别人又告诉我一些信息。我再把我知道的更新后的信息告诉别人，别人也这样把更新后的信息再告诉我”，最后在自治系统中所有的结点都得到了正确的路由选择信息。在一般情况下， RIP 协议可以收敛，并且过程也较快。“收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。

路由表中最主要的信息就是：到某个网络的距离（即最短距离），以及应经过的下一跳地址。路由表更新的原则是找出到每个目的网络的最短距离。这种更新算法又称为距离向量算法。下面就是 RIP 协议使用的距离向量算法。

2.2 距离向量算法

对每一个相邻路由器发送过来的 RIP 报文，进行以下步骤：

（1）对地址为 X 的相邻路由器发来的 RIP 报文，先修改此报文中的所有项目：把“下一跳”字段中的地址都改为 X，并把所有的“距离” 字段的值加 1（见后面的解释 1）。每一个项目都有三个关键数据，即：到目的网络 N，距离是 d，下一跳路由器是 X。

（2）对修改后的 RIP 报文中的每一个项目，进行以下步骤：

若原来的路由表中没有目的网络 N，则把该项目添加到路由表中（见解释 2）

否则（即在路由表中有目的网络 N，这时就再查看下一跳路由器地址）

若下一跳路由器地址是 X，则把收到的项目替换原路由表中的项目（见解释 3）

否则（即这个项目是：到目的网络 N，但下一跳路由器不是 X）

若收到的项目中的距离 d 小于路由表中的距离，则进行更新（见解释 4），

否则什么也不做。（见解释 5）

（3）若 3 分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即把距离置为 16（距离为 16 表示不可达）。

（4）返回。

上面给出的距离向量算法的基础就是 Bellman-Ford 算法（或 Ford-Fulkerson 算法）。这种算法的要点是这样的：

设 X 是结点 A 到 B 的最短路径上的一个结点。若把路径 A→B 拆成两段路径 A→X 和X→B，则每一段路径 A→X 和 X→B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径。

下面是对上述距离向量算法的五点解释。

解释 1：这样做是为了便于进行本路由表的更新。假设从位于地址 X 的相邻路由器发来的 RIP 报文的某一个项目是：“Net2, 3, Y”，意思是“我经过路由器 Y 到网络 Net2 的距离是3”，那么本路由器就可推断出：“我经过 X 到网络 Net2 的距离应为 3 + 1 = 4”。于是，本路由器就把收到的 RIP 报文的这一个项目修改为“Net2, 4, X”，作为下一步和路由表中原有项目进行比较时使用（只有比较后才能知道是否需要更新）。读者可注意到，收到的项目中的Y 对本路由器是没有用的，因为 Y 不是本路由器的下一跳路由器地址。

解释 2：表明这是新的目的网络，应当加入到路由表中。例如，本路由表中没有到目的网络 Net2 的路由，那么在路由表中就要加入新的项目“Net2, 4, X”。

解释 3：为什么要替换呢？因为这是最新的消息，要以最新的消息为准。到目的网络的距离有可能增大或减小，但也可能没有改变。例如，不管原来路由表中的项目是“Net2, 3,X”还是“Net2, 5, X”，都要更新为现在的“Net2, 4, X”。

解释 4：例如，若路由表中已有项目“Net2, 5, P”，就要更新为“Net2, 4, X”。因为到网络 Net2 的距离原来是 5，现在减到 4， 更短了。

解释 5： 若距离更大了，显然不应更新。若距离不变，更新后得不到好处，因此也不更新。

【例】已知路由器 R6 有第一个表所示的路由表。现在收到相邻路由器 R4 发来的路由更新信息，如第二个表所示。试更新路由器 R6的路由表。

【解】如同路由器一样，我们不需要知道该网络的拓扑。

先把第二个表中的距离都加 1，并把下一跳路由器都改为 R4。得出下表

把这个表的每一行和第一个表进行比较。

第一行在第一个表中没有，因此要把这一行添加到第一个表中。

第二行的 Net2 在第一个表中有，且下一跳路由器也是 R4。因此要更新（距离增大了）。

第三行的 Net3 在第一个表中有，但下一跳路由器不同。于是就要比较距离。新的路由信息的距离是 2，小于原来表中的 4，因此要更新。

这样，得出更新后的 R6的路由表如下表所示。

RIP 协议让一个自治系统中的所有路由器都和自己的相邻路由器定期交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。这里还应注意：虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。

2.3 RIP 协议的报文格式

现在较新的 RIP 版本是 1998 年 11 月公布的 RIP2（已成为互联网标准），新版本协议本身并无多大变化，但性能上有些改进。 RIP2 可以支持变长子网掩码和无分类域间路由选择 CIDR。此外， RIP2 还提供简单的鉴别过程支持多播。

下图是 RIP2 的报文格式，它和 RIP1 的首部相同，但后面的路由部分不一样。从图还可看出， RIP 协议使用运输层的用户数据报 UDP 进行传送（使用 UDP 的端口 520）。

RIP2 的报文格式

RIP 报文由首部和路由部分组成。

RIP 的首部占 4 个字节，其中的命令字段指出报文的意义。例如， 1 表示请求路由信息， 2 表示对请求路由信息的响应或未被请求而发出的路由更新报文。首部后面的“必为0”是为了 4 字节字的对齐。

RIP2 报文中的路由部分由若干个路由信息组成。每个路由信息需要用 20 个字节。 地址族标识符（又称为地址类别）字段用来标志所使用的地址协议。如采用 IP 地址就令这个字段的值为 2（原来考虑 RIP 也可用于其他非 TCP/IP 协议的情况）。 路由标记填入自治系统号ASN (Autonomous System Number)，这是考虑使 RIP 有可能收到本自治系统以外的路由选择信息。再后面指出某个网络地址、该网络的子网掩码、 下一跳路由器地址以及到此网络的距离。一个 RIP 报文最多可包括 25 个路由，因而 RIP 报文的最大长度是 4 + 20 × 25 = 504字节。如超过，必须再用一个 RIP 报文来传送。

RIP2 还具有简单的鉴别功能。若使用鉴别功能，则将原来写入第一个路由信息（20 字节）的位置用作鉴别。这时应将地址族标识符置为全 1（即 0xFFFF），而路由标记写入鉴别类型，剩下的 16 字节为鉴别数据。在鉴别数据之后才写入路由信息，但这时最多只能再放入 24 个路由信息。

RIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。我们可以用下图的简单例子来说明。设三个网络通过两个路由器互连起来，并且都已建立了各自的路由表。图中路由器交换的信息只给出了我们感兴趣的一行内容。路由器 R1 中的“1, 1, 直接”表示“到网 1 的距离是 1，直接交付”。路由器 R2 中的“1,2, R1”表示“到网 1 的距离是 2，下一跳经过 R1”。

现在假定路由器 R1 到网 1 的链路出了故障， R1 无法到达网 1。于是路由器 R1 把到网 1的距离改为 16（表示到网 1 不可达），因而在 R1 的路由表中的相应项目变为“1, 16, 直接”。但是，很可能要经过 30 秒钟后 R1 才把更新信息发送给 R2。然而 R2 可能已经先把自己的路由表发送给了 R1，其中有“1, 2, R1”这一项。

RIP 协议的缺点：坏消息传播得慢

R1 收到 R2 的更新报文后，误认为可经过 R2 到达网 1，于是把收到的路由信息“1, 2,R1”修改为：“1, 3, R2”，表明“我到网 1 的距离是 3，下一跳经过 R2”，并把更新后的信息发送给 R2。

同理， R2 接着又更新自己的路由表为“1, 4, R1”，以为“我到网 1 距离是 4，下一跳经过 R1”。

这样的更新一直继续下去，直到 R1和 R2到网 1 的距离都增大到 16 时， R1和 R2才知道原来网 1 是不可达的。 RIP 协议的这一特点叫做： 好消息传播得快，而坏消息传播得慢。网络出故障的传播时间往往需要较长的时间(例如数分钟)。 这是 RIP 的一个主要缺点。

但如果一个路由器发现了更短的路由，那么这种更新信息就传播得很快。

为了使坏消息传播得更快些，可以采取多种措施。例如，让路由器记录收到某特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送。

总之， RIP 协议最大的优点就是实现简单，开销较小。但 RIP 协议的缺点也较多。首先， RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。其次，路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。最后，“坏消息传播得慢”，使更新过程的收敛时间过长。因此，对于规模较大的网络就应当使用下一节所述的 OSPF 协议。然而目前在规模较小的网络中，使用 RIP 协议的仍占多数。

三、内部网关协议 OSPF

3.1 OSPF 协议的基本特点

这个协议的名字是开放最短路径优先 OSPF (Open Shortest Path First)。它是为克服 RIP的缺点在 1989 年开发出来的。 OSPF 的原理很简单，但实现起来却较复杂。“开放”表明OSPF 协议不是受某一家厂商控制，而是公开发表的。“ 最短路径优先”是因为使用了Dijkstra 提出的最短路径算法 SPF。 OSPF 的第二个版本 OSPF2 已成为互联网标准协议。

请注意： OSPF 只是一个协议的名字， 它并不表示其他的路由选择协议不是“最短路径优先”。实际上，所有的在自治系统内部使用的路由选择协议（包括 RIP 协议）都是要寻找一条最短的路径。

OSPF 最主要的特征就是使用分布式的链路状态协议(link state protocol)，而不是像 RIP那样的距离向量协议。和 RIP 协议相比， OSPF 的三个要点和 RIP 的都不一样：

（1）向本自治系统中所有路由器发送信息。这里使用的方法是洪泛法(flooding)，这就是路由器通过所有输出端口向所有相邻的路由器发送信息。而每一个相邻路由器又再将此信息发往其所有的相邻路由器（但不再发送给刚刚发来信息的那个路由器）。这样，最终整个区域中所有的路由器都得到了这个信息的一个副本。更具体的做法后面还要讨论。我们应注意， RIP 协议是仅仅向自己相邻的几个路由器发送信息。

（2）发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。所谓 “链路状态”就是说明本路由器都和哪些路由器相邻 ，以及该链路的“度量” (metric)。 OSPF 将这个“度量”用来表示费用、距离、时延、带宽，等等。这些都由网络管理人员来决定，因此较为灵活。有时为了方便就称这个度量为“代价”。我们应注意，对于 RIP 协议，发送的信息是：“到所有网络的距离和下一跳路由器”。

（3）只有当链路状态发生变化时，路由器才向所有路由器用洪泛法发送此信息。而不像RIP 那样，不管网络拓扑有无发生变化，路由器之间都要定期交换路由表的信息。

从上述的三个方面可以看出， OSPF 和 RIP 的工作原理相差较大。由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库(link-state database)，这个数据库实际上就是全网的拓扑结构图。这个拓扑结构图在全网范围内是一致的（这称为链路状态数据库的同步）。因此，每一个路由器都知道全网共有多少个路由器，以及哪些路由器是相连的，其代价是多少，等等。每一个路由器使用链路状态数据库中的数据，构造出自己的路由表（例如，使用 Dijkstra 的最短路径路由算法）。我们注意到， RIP 协议的每一个路由器虽然知道到所有的网络的距离以及下一跳路由器，但却不知道全网的拓扑结构（只有到了下一跳路由器，才能知道再下一跳应当怎样走）。

OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点。

为了使 OSPF 能够用于规模很大的网络， OSPF 将一个自治系统再划分为若干个更小的范围， 叫做区域(area)。下图就表示一个自治系统划分为四个区域。每一个区域都有一个32 位的区域标识符（用点分十进制表示）。当然，一个区域也不能太大，在一个区域内的路由器最好不超过 200 个。

OSPF 划分为两种不同的区域

划分区域的好处就是把利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。为了使每一个区域能够和本区域以外的区域进行通信， OSPF 使用层次结构的区域划分。在上层的区域叫做主干区域(backbonearea)。主干区域的标识符规定为 0.0.0.0。主干区域的作用是用来连通其他在下层的区域。从其他区域来的信息都由区域边界路由器(area border router)进行概括。在图中，路由器R3， R4 和 R7 都是区域边界路由器，而显然，每一个区域至少应当有一个区域边界路由器。在主干区域内的路由器叫做主干路由器(backbone router)，如 R3， R4， R5， R6和 R7。一个主干路由器可以同时是区域边界路由器，如 R3， R4 和 R7。在主干区域内还要有一个路由器专门和本自治系统外的其他自治系统交换路由信息。这样的路由器叫做自治系统边界路由器（如图中的 R6）。

采用分层次划分区域的方法虽然使交换信息的种类增多了，同时也使 OSPF 协议更加复杂了。但这样做却能使每一个区域内部交换路由信息的通信量大大减小，因而使 OSPF 协议能够用于规模很大的自治系统中。这里，我们再一次地看到划分层次在网络设计中的重要性。

OSPF 不用 UDP 而是直接用 IP 数据报传送（其 IP 数据报首部的协议字段值为 89）。OSPF 构成的数据报很短。这样做可减少路由信息的通信量。数据报很短的另一好处是可以不必将长的数据报分片传送。分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。

OSPF 分组使用 24 字节的固定长度首部（见下图），分组的数据部分可以是五种类型分组中的一种。下面简单介绍 OSPF 首部各字段的意义。

（1）版本 当前的版本号是 2。

（2）类型 可以是五种类型分组中的一种。

（3）分组长度 包括 OSPF 首部在内的分组长度，以字节为单位。

（4）路由器标识符 标志发送该分组的路由器的接口的 IP 地址。

（5）区域标识符 分组属于的区域的标识符。

（6）检验和 用来检测分组中的差错。

（7）鉴别类型 目前只有两种， 0（不用）和 1（口令）。

（8）鉴别 鉴别类型为 0 时就填入 0， 鉴别类型为 1 则填入 8 个字符的口令。

OSPF 分组用 IP 数据报传送

除了以上的几个基本特点外， OSPF 还具有下列的一些特点：

（1）OSPF 允许管理员给每条路由指派不同的代价。例如，高带宽的卫星链路对于非实时的业务可设置为较低的代价，但对于时延敏感的业务就可设置为非常高的代价。因此，OSPF 对于不同类型的业务可计算出不同的路由。链路的代价可以是 1 至 65535 中的任何一个无量纲的数，因此十分灵活。商用的网络在使用 OSPF 时，通常根据链路带宽来计算链路的代价。 这种灵活性是 RIP 所没有的。

（2）如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫做多路径间的负载平衡（load balancing）。在代价相同的多条路径上分配通信量是通信量工程中的简单形式。 RIP 只能找出到某个网络的一条路径。

（3）所有在 OSPF 路由器之间交换的分组（例如，链路状态更新分组）都具有鉴别的功能，因而保证了仅在可信赖的路由器之间交换链路状态信息。

（4）OSPF 支持可变长度的子网划分和无分类的编址 CIDR。

（5）由于网络中的链路状态可能经常发生变化，因此 OSPF 让每一个链路状态都带上一个 32 位的序号，序号越大状态就越新。 OSPF 规定，链路状态序号增长的速率不得超过每 5秒钟 1 次。这样，全部序号空间在 600 年内不会产生重复号。

3.2 OSPF 的五种分组类型

OSPF 共有以下五种分组类型：

（1）类型 1， 问候(Hello)分组，用来发现和维持邻站的可达性。

（2）类型 2， 数据库描述(Database Description)分组，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。

（3）类型 3， 链路状态请求(Link State Request)分组，向对方请求发送某些链路状态项目的详细信息。

（4）类型 4， 链路状态更新(Link State Update)分组，用洪泛法对全网更新链路状态。这种分组是最复杂的，也是 OSPF 协议最核心的部分。路由器使用这种分组将其链路状态通知给邻站。链路状态更新分组共有五种不同的链路状态。

（5）类型 5， 链路状态确认(Link State Acknowledgment)分组，对链路更新分组的确认。

OSPF 规定，每两个相邻路由器每隔 10 秒钟要交换一次问候分组。这样就能确知哪些邻站是可达的。对相邻路由器来说，“可达”是最基本的要求，因为只有可达邻站的链路状态信息才存入链路状态数据库（路由表就是根据链路状态数据库计算出来的）。在正常情况下，网络中传送的绝大多数 OSPF 分组都是问候分组。若有 40 秒钟没有收到某个相邻路由器发来的问候分组，则可认为该相邻路由器是不可达的，应立即修改链路状态数据库，并重新计算路由表。

其他的四种分组都是用来进行链路状态数据库的同步。所谓同步就是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器叫做“完全邻接的” (fully adjacent)路由器。不是完全邻接的路由器表明它们虽然在物理上是相邻的，但其链路状态数据库并没有达到一致。

当一个路由器刚开始工作时，它只能通过问候分组得知它有哪些相邻的路由器在工作，以及将数据发往相邻路由器所需的“代价”。如果所有的路由器都把自己的本地链路状态信息对全网进行广播，那么各路由器只要将这些链路状态信息综合起来就可得出链路状态数据库。但这样做开销太大，因此 OSPF 采用下面的办法。

OSPF 让每一个路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。摘要信息主要就是指出有哪些路由器的链路状态信息（以及其序号）已经写入了数据库。经过与相邻路由器交换数据库描述分组后，路由器就使用链路状态请求分组，向对方请求发送自己所缺少的某些链路状态项目的详细信息。通过一系列的这种分组交换，全网同步的链路数据库就建立了。下图给出了 OSPF 的基本操作，说明了两个路由器需要交换各种类型的分组。

OSPF 的基本操作

在网络运行的过程中，只要一个路由器的链路状态发生变化，该路由器就要使用链路状态更新分组，用洪泛法向全网更新链路状态。 OSPF 使用的是可靠的洪泛法，其要点见下图所示。设路由器 R 用洪泛法发出链路状态更新分组。图中用一些小的箭头表示更新分组。第一次先发给相邻的三个路由器。这三个路由器将收到的分组再进行转发时，要将其上游路由器除外。可靠的洪泛法是在收到更新分组后要发送确认（收到重复的更新分组只需要发送一次确认）。图中的空心箭头表示确认分组。

用可靠的洪泛法发送更新分组

为了确保链路状态数据库与全网的状态保持一致， OSPF 还规定每隔一段时间，如 30分钟，要刷新一次数据库中的链路状态。

由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时， OSPF 协议要比距离向量协议 RIP 好得多。由于OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。

若 N 个路由器连接在一个以太网上，则每个路由器要向其他(N - 1)个路由器发送链路状态信息，因而共有 N(N－1)个链路状态要在这个以太网上传送。 OSPF 协议对这种多点接入的局域网采用了指定的路由器(designated router)的方法，使广播的信息量大大减少。指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

四、外部网关协议 BGP

1989 年，公布了新的外部网关协议—边界网关协议 BGP。为简单起见，后面我们把目前使用最多的版本 BGP-4 经常简写为 BGP。最近已经陆续发布了一些 BGP-4 的更新文档，但目前 BGP-4 仍然是草案标准。

我们首先应当弄清，在不同自治系统 AS 之间的路由选择为什么不能使用前面讨论过的内部网关协议，如 RIP 或 OSPF？

我们知道，内部网关协议（如 RIP 或 OSPF）主要是设法使数据报在一个 AS 中尽可能有效地从源站传送到目的站。在一个 AS 内部也不需要考虑其他方面的策略。然而 BGP 使用的环境却不同。这主要是因为以下的两个原因：

第一， 互联网的规模太大，使得自治系统 AS 之间路由选择非常困难。连接在互联网主干网上的路由器，必须对任何有效的 IP 地址都能在路由表中找到匹配的目的网络。目前在互联网的主干网路由器中，一个路由表的项目数早已超过了 5 万个网络前缀。如果使用链路状态协议，则每一个路由器必须维持一个很大的链路状态数据库。对于这样大的主干网用Dijkstra 算法计算最短路径时花费的时间也太长。另外，由于自治系统 AS 各自运行自己选定的内部路由选择协议，并使用本 AS 指明的路径度量，因此，当一条路径通过几个不同AS 时，要想对这样的路径计算出有意义的代价是不太可能的。例如，对某 AS 来说，代价为 1000 可能表示一条比较长的路由。但对另一 AS 代价为 1000 却可能表示不可接受的坏路由。因此，对于自治系统 AS 之间的路由选择， 要用“代价”作为度量来寻找最佳路由也是很不现实的。 比较合理的做法是在自治系统之间交换“可达性”信息（即“可到达”或“不可到达”）。例如，告诉相邻路由器：“到达目的网络 N 可经过自治系统 ASx”。

第二， 自治系统 AS 之间的路由选择必须考虑有关策略。由于相互连接的网络的性能相差很大，根据最短距离（即最少跳数）找出来的路径，可能并不合适。也有的路径的使用代价很高或很不安全。还有一种情况，如自治系统 AS1 要发送数据报给自治系统 AS2，本来最好是经过自治系统 AS3。但 AS3 不愿意让这些数据报通过本自治系统的网络，因为“这是他们的事情，和我们没有关系。”但另一方面，自治系统 AS3 愿意让某些相邻自治系统的数据报通过自己的网络，特别是对那些付了服务费的某些自治系统更是如此。因此，自治系统之间的路由选择协议应当允许使用多种路由选择策略。这些策略包括政治、安全或经济方面的考虑。例如，我国国内的站点在互相传送数据报时不应经过国外兜圈子，特别是，不要经过某些对我国的安全有威胁的国家。这些策略都是由网络管理人员对每一个路由器进行设置的，但这些策略并不是自治系统之间的路由选择协议本身。还可举出一些策略的例子，如：“仅在到达下列这些地址时才经过 ASx”，“ASx 和 ASy 相比时应优先通过 ASx”，等等。显然，使用这些策略是为了找出较好的路径而不是最佳路径。

由于上述情况，边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。 BGP 采用了路径向量(path vector)路由选择协议，它与距离向量协议（如 RIP）和链路状态协议（如 OSPF）都有很大的区别。

在配置 BGP 时，每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“BGP 发言人”。一般说来，两个 BGP 发言人都是通过一个共享网络连接在一起的，而BGP 发言人往往就是 BGP 边界路由器，但也可以不是 BGP 边界路由器。

一个 BGP 发言人与其他 AS 的 BGP 发言人要交换路由信息，就要先建立 TCP 连接（端口号为 179），然后在此连接上交换 BGP 报文以建立 BGP 会话(session)，利用 BGP 会话交换路由信息，如增加了新的路由，或撤销过时的路由，以及报告出差错的情况等等。使用 TCP 连接能提供可靠的服务，也简化了路由选择协议。使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此成为对方的邻站(neighbor)或对等站(peer)。

下图表示 BGP 发言人和自治系统 AS 的关系的示意图。在图中画出了三个自治系统中的 5 个 BGP 发言人。每一个 BGP 发言人除了必须运行 BGP 协议外，还必须运行该自治系统所使用的内部网关协议，如 OSPF 或 RIP。

BGP 发言人和自治系统 AS 的关系

边界网关协议 BGP 所交换的网络可达性的信息就是要到达某个网络（用网络前缀表示）所要经过的一系列自治系统。当 BGP 发言人互相交换了网络可达性的信息后，各 BGP发言人就根据所采用的策略从收到的路由信息中找出到达各自治系统的较好路由。下图表示从上图的 AS1 上的一个 BGP 发言人构造出的自治系统连通图，它是树形结构，不存在回路。

自治系统 AS 的连通图举例

下图给出了一个 BGP 发言人交换路径向量的例子。自治系统 AS2 的 BGP 发言人通知主干网的 BGP 发言人：“要到达网络 N1, N2, N3 和 N4 可经过 AS2。”主干网在收到这个通知后，就发出通知：“要到达网络 N1, N2, N3 和 N4 可沿路径（AS1, AS2）。”同理，主干网还可发出通知：“要到达网络 N5, N6和 N7 可沿路径（AS1, AS3）。”

BGP 发言人交换路径向量的例子

从上面的讨论可看出， BGP 协议交换路由信息的结点数量级是自治系统个数的量级，这要比这些自治系统中的网络数少很多。要在许多自治系统之间寻找一条较好的路径，就是要寻找正确的 BGP 发言人（或边界路由器），而在每一个自治系统中 BGP 发言人（或边界路由器）的数目是很少的。这样就使得自治系统之间的路由选择不致过分复杂。

BGP 支持无分类域间路由选择 CIDR，因此 BGP 的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的自治系统序列。由于使用了路径向量的信息，就可以很容易地避免产生兜圈子的路由。如果一个 BGP 发言人收到了其他 BGP 发言人发来的路径通知，它就要检查一下本自治系统是否在此通知的路径中。如果在这条路径中，就不能采用这条路径（因为会兜圈子）。

在 BGP 刚刚运行时， BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销方面都有好处。

BGP-4 的四种报文：

（1）OPEN（打开）报文，用来与相邻的另一个 BGP 发言人建立关系，使通信初始化。

（2）UPDATE（更新）报文，用来通告某一路由的信息，以及列出要撤销的多条路由。

（3）KEEPALIVE（保活）报文，用来周期性地证实邻站的连通性。

（4）NOTIFICATION（通知）报文，用来发送检测到的差错。

若两个邻站属于两个不同 AS，而其中一个邻站打算和另一个邻站定期地交换路由信息，这就应当有一个商谈的过程（因为很可能对方路由器的负荷已很重因而不愿意再加重负担）。因此，一开始向邻站进行商谈时就必须发送 OPEN 报文。如果邻站接受这种邻站关系，就用 KEEPALIVE 报文响应。这样，两个 BGP 发言人的邻站关系就建立了。

一旦邻站关系建立了，就要继续维持这种关系。双方中的每一方都需要确信对方是存在的，且一直在保持这种邻站关系。为此，这两个 BGP 发言人彼此要周期性地交换KEEPALIVE 报文（一般每隔 30 秒）。 KEEPALIVE 报文只有 19 字节长（只用 BGP 报文的通用首部），因此不会造成网络上太大的开销。

UPDATE 报文是 BGP 协议的核心内容。 BGP 发言人可以用 UPDATE 报文撤销它以前曾经通知过的路由，也可以宣布增加新的路由。撤销路由可以一次撤销许多条，但增加新路由时，每个更新报文只能增加一条。

BGP 可以很容易地解决距离向量路由选择算法中的“坏消息传播得慢”这一问题。当某个路由器或链路出故障时，由于 BGP 发言人可以从不止一个邻站获得路由信息，因此很容易选择出新的路由。距离向量算法往往不能给出正确的选择，是因为这些算法不能指出哪些邻站到目的站的路由是独立的。

下图给出了 BGP 报文的格式。四种类型的 BGP 报文具有同样的通用首部，其长度为 19 字节。通用首部分为三个字段。 标记(marker)字段为 16 字节长，用来鉴别收到的 BGP报文（这是假定将来有人会发明出合理的鉴别方案）。当不使用鉴别时，标记字段要置为全1。 长度字段指出包括通用首部在内的整个 BGP 报文以字节为单位的长度，最小值是 19，最大值是 4096。 类型字段的值为 1 到 4，分别对应于上述四种 BGP 报文中的一种。

OPEN 报文共有 6 个字段，即版本（1 字节，现在的值是 4）、 本自治系统号（2 字节，使用全球唯一的 16 位自治系统号，由 ICANN 地区登记机构分配）、 保持时间（2 字节，以秒计算的保持为邻站关系的时间）、 BGP 标识符（4 字节，通常就是该路由器的 IP 地址）、可选参数长度（1 字节） 和可选参数。

BGP 报文具有通用的首部

UPDATE 报文共有 5 个字段，即不可行路由长度（2 字节，指明下一个字段的长度）、撤销的路由（列出所有要撤销的路由）、 路径属性总长度（ 2 字节，指明下一个字段的长度）、 路径属性（定义在这个报文中增加的路径的属性）和网络层可达性信息 NLRI(Network Layer Reachability Information)。最后这个字段定义发出此报文的网络，包括网络前缀的位数、 IP 地址前缀。

KEEPALIVE 报文只有 BGP 的 19 字节长的通用首部。

NOTIFICATION 报文有 3 个字段，即差错代码（1 字节）、差错子代码（1 字节）和差错数据（给出有关差错的诊断信息）。

来自：《计算机网络》--谢希仁