互联网的路由选择协议

这篇文章开始我们一起来学习下几种常用的路由选择协议，也就是要讨论路由表是怎样得出的。

基本概念

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

• 算法必须是正确的和完整的
  即沿着路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。

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

• 算法应能适应通信量和网络拓扑的变化
  当网络中的通信量发生变化时，算法能自适应的改变路由。当某个结点、链路发生故障，或者修理好再投入运行时，算法能及时改变路由。

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

• 算法应是公平的
  路由选择算法应对所有用户都是平等的，例如仅仅使某个用户的端到端时延为最小，但却不考虑其它用户，这明显是不公平的。

• 算法应是最佳的
  路由选择算法应当能够找出最好的路由，使得分组平均时延最小，而网络吞吐量最大。

从路由算法能否随网络的通信量或拓扑自适应的进行调整变化的角度来划分，有两大类：

• 静态路由选择策略
  也叫作非自适应路由选择，其特点是简单、开销较小，但不能及时适应网络的变化。小网络可以使用它，人工配置每一条路由。
• 动态路由选择策略
  也叫作自适应路由选择，其特点是能较好的适应网络的变化，但实现起来较为复杂，开销也比较大。因此，它适用于较大的网络。

由于以下两个原因，互联网采用分层次的路由选择协议：
（1）互联网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，那么这种路由表将非常大，处理起来也太花时间，而所有这些路由器之间交换路由信息所需的带宽就会使互联网的通信链路饱和。

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

因此，把整个互联网划分为许多较小的自治系统，自治系统是在单一技术管理下的一组路由器，这些路由器使用一种自治系统内部的路由选择协议和共同的度量。一个自治系统对其它自治系统表现出的是一个单一的和一致的路由选择策略。在目前的互联网中，一个大的ISP就是一个自治系统，这样，互联网就把路由选择协议划分为两大类，即：
（1）内部网关协议IGP（Interior Gateway Protocol）
即在一个自治系统内部使用的路由选择协议，与互联网中的其它自治系统选用的路由选择协议无关。目前这类路由选择协议使用的最多，如RIP和OSPF协议。
（2）外部网关协议EGP（External Gateway Protocol）
若源主机和目的主机在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中，这样的协议就是外部网关协议EGP，目前使用最多的外部网关协议是BGP的版本4，BGP-4。如下图所示：

两个自治系统互连在一起，每个自治系统决定自己内部运行哪一个内部路由选择协议。每一个自治系统都有一个或多个路由器，除运行本系统的内部路由选择协议外，还要运行自治系统间的路由选择协议。

内部网关协议RIP

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

RIP不能在两个网络之间同时使用多条路由，它选择一条具有最少路由器的路由，哪怕还存在另一条高速，但路由器较多的路由。分布式路由选择协议的特点就是每一个路由器都要不断的和其它一些路由器交换路由信息，有3个问题值得讨论：
（1）和哪些路由器交换信息
仅和相邻路由器交换信息。如果两个路由器之间的通信不需要经过另一个路由器，那么这两个路由器就是相邻的。RIP协议规定，不相邻的路由器不交换信息。

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

（3）何时交换
按固定的时间间隔交换路由信息，例如，每隔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）若3分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即距离设置为16

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

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

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

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

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

RIP协议让一个自治系统中的所有路由器都和自己的相邻路由器定期交换路由信息，并不断更新路由表，使得从每一个路由器到每一个目的网络的路由都是最短的。

（十二）网络层--路由选择协议