互联网的路由选择协议

分层次的路由选择协议

由于以下两个原因，互联网选择分层次的路由选择协议

1. 互联网的规模十分庞大，如果让每个路由器都直到所有网络应该怎样到达，处理起来的时间和资源开销太大
2. 许多单位不愿意让外界了解自己单位的网络布局细节和采用的路由选择协议，同时还希望连接到互联网上

因此，把整个互联网划分为许多较小的自治系统，自治系统是在单一技术管理下的一组路由器，这些路由器使用一种自治系统内部的路由选择协议和共同的度量。一个自治系统对其它自治系统表现出的是一个单一的和一致的路由选择策略。在目前的互联网中，一个大的ISP就是一个自治系统，这样，互联网就把路由选择协议划分为两大类，即：

• 内部网关协议IGP（Interior Gateway Protocol）
  • 即在一个自治系统内部使用的路由选择协议，与互联网中的其它自治系统选用的路由选择协议无关。目前这类路由选择协议使用的最多，如RIP和OSPF协议。
• 外部网关协议EGP（External Gateway Protocol）
  • 若源主机和目的主机在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中，这样的协议就是外部网关协议EGP，目前使用最多的外部网关协议是BGP的版本4，BGP-4。如下图所示：

自治系统之间的路由选择也叫域间路由选择，自治系统之内的路由选择也叫域内路由选择

EGP是外部网关协议的最早的一个版本，后来设计了新的路由选择协议边界网关协议BGP

总之，我们可以将互联网的路由选择协议分为：

• 内部网关协议 IGP：如RIP和OSPF等；
• 外部网关协议EGP：目前正在使用的版本是BGP-4

对于规模较大的自治系统，还可以将所有的网络再进行一次划分，例如可以构筑一个链路速率较高的主干网络和许多速率较低的区域网

内部网关协议RIP

IP（Routing Information Protocol），它是内部网关协议IGP中最先得到广泛使用的协议，是一种分布式的基于距离向量的路由选择协议，是互联网的标准协议，其最大优点就是简单。RIP要求网络中的每一个路由器都要维护从它自己到其它每一个目的网络的距离记录。RIP协议将“距离”定义如下：从一路由器到直接相连的网络的距离为1，从一路由器到非直接连接的网络的距离定义为所经过的路由器数加1。这个距离也称为跳数，因为每经过一个路由器，跳数就加1，RIP认为好的路由就是它通过的路由器的数目少。RIP允许一条路径最多只能包含15个路由器。因此，距离等于16时即相当于不可达，可见RIP只适用于小型互联网。

RIP不能在两个网络之间同时使用多条路由，它选择一条具有最少路由器的路由，哪怕还存在另一条高速，但路由器较多的路由。分布式路由选择协议的特点就是每一个路由器都要不断的和其它一些路由器交换路由信息，有3个问题值得讨论：

• 和哪些路由器交换信息

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

• 交换什么信息

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

• 何时交换

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

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

路由表更新的原则是找到每个目的网络的最短距离，这种更新算法又称为 距离向量算法。

距离向量算法

对每一个相邻路由器发送过来的RIP报文，进行如下步骤：
（1）对地址为X的相邻路由器发来的RIP报文，先修改此报文中的所有项目：把“下一跳”字段中的地址都改为X，并把所有的“距离”字段的值加1（解释1）。每一个项目都有3个关键数据，即：目的网络N，距离D，下一跳路由器X

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

若原来的路由表中没有目的网络N，则把该项目添加到路由表中（解释2）
否则（有目的网络N，则查看下一跳路由器地址）
若下一跳路由器地址是X，则把收到的项目替换原路由表中的项目（解释3）
否则（到目的网络N，但下一跳路由器不是X）
若收到的项目中的距离D小于路由表中的距离，则进行更新（解释4）
否则什么也不做（解释5）

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

• 解释1：为了便于进行本路由表的更新

• 解释2：表明这是新的网络，应当加入到本路由表中

• 解释3：因为这是最新的消息，要以最新的消息为准。到目的网络的距离有可能增大或减小，但也可能没有改变，不管怎样，都要更新

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

• 解释5：若距离更大了，则不应该更新；若距离不变，也不更新

RIP算法的分析

RIP算法的一个特点是好消息传播地快，坏消息传播地慢，当网络出现故障时，要经过较长的时间才能将此消息传送到所有的路由器

一个可行的改进策略是：让路由器记录收到某特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传播

总之，RIP协议的最大优点就是实现简单、开销较小

OSPF协议

OSPF的原理可以理解为，各个路由器之间频繁地交换链路状态信息。因此所有的路由器最终都能建立一个链路状态数据库，这个数据库实际上是全网的拓扑结构图。这个拓扑结构图再全网范围内是一致的(称为链路状态数据库的同步)