互联网路由选择协议

overview

在网络通信中，由于主机、路由器分布的复杂性，为了网络的性能，做出较好的路由选择至关重要。

基本概念

理想的路由算法

理想的路由选择算法应该具有如下的特点：

• 1.路由算法必须是正确且完整的
• 2.算法在计算上简单
• 3.算法应能适应通信量和网络拓扑的变化，也就是要有自适应性，网络发生故障时要能够根据网络的实际情况，包括故障、速度等情况，自适应地改变路由以均衡链路负载，也就是鲁棒性(robustness)
• 4.算法应该具有稳定性
• 5.算法应该是公平地
• 6.算法应该是最佳的

若从路由算法能否自适应变化分类，可以分为静态路由选择测量（非自适应路由选择）和动态路由选择策略（自适应路由选择）

分层次的路由选择协议

互联网的规模非常大，如果让所有的路由器都知道哪个网络应该怎样传送，路由表会非常大，处理难度也大；一些机构存在局域网的需求，即希望接入互联网的同时不暴露内部的网络拓扑和内部的协议。
基于上面两个原因，可以把网络划分为多个较小的自治系统（autonomous system），简称AS。AS是在某种技术/协议管理下的一组路由器，这些路由器使用系统内部的路由选择协议和度量，一个AS对外以整体存在，且内部使用统一的路由选择协议（类似于欧盟）。
目前，一个ISP就是一个大的AS，其内部继续细分小AS。
基于这样的层次原则，路由选择协议可以分为两类：

• （1）内部网关协议IGP：AS内部使用的路由选择协议，与其他AS的协议无关，亦称域内路由选择，例如RIP、OSPF
• （2）外部网关协议EGP：AS之间通信时使用的路由选择协议，亦称域间路由选择，例如BGP-4。

如果源主机和目的主机属于两个AS，在各自的AS内部传输时使用IGP，当数据报传输的AS边界时就需要使用EGP传输到目的主机所属的AS边界。

内部网关协议RIP

工作原理

Routing Information Protocol(路由信息协议RIP)是一种分布式的，基于距离向量的路由选择协议，优点：简单。
RIP要求网络路由器都要维护自己到其他每一个网络的距离记录，组合成距离向量。在RIP中距离的定义是这样的：
从与本路由器直连的路由器距离为1，与非直连路由器额距离为所经过的路由器数量（不包括源目的主机）+1。
RIP中距离亦称“跳数”，RIP允许一条路径最多包含15个路由器，即16跳，因此距离大于16的路由器相当于不可达。所以RIP只适用于小型AS。
RIP只考虑源目的主机之间的路由器数量，不考虑其他跳数更多但是时延更低的路由（判别依据有且仅有跳数）。

RIP的特点

• 仅和相邻路由器交换信息
• 路由器之间交换的信息包括了本路由器所知道的整个路由表
• 按固定的时间间隔交换信息，一般是30s

一开始各个路由器的路由表是空的，信息交换时路由表的改写比较频繁，但是随着时间的推移，路由表会趋向平衡，收敛到稳定状态。

路由表与距离向量算法

路由表存储的信息包括：对于每一个路由器，到达某个网络（主机）的距离（最短距离），要去到这个网络的下一跳路由器（即，下一步应该去哪）

假设X的路由表如下：

目标网络	最短距离	下一跳
A	3	B
B	1	直接交付
D	6	C
…	…	…

（实际上是“A,3,B”这样的形式）

距离向量算法：

对于每一个从相邻路由器发来的RIP报文，做如下操作：

• 1.Y对于X发来的RIP报文，修改此报文的所有项：把下一跳的项都改为X，并把“最短距离”都+1：

  目标网络	最短距离	下一跳
  A	4	X
  B	2	X
  D	7	X
  …	…	…

• 2.对于修改后的路由表，进行如下操作：

  • if(X原来的路由表中没有目标网络为N的信息)：把N所在的行添加到自身（Y路由器）的路由表中
  • else:（即N已在Y的路由表中）
    • if(原来去向N的下一跳路由器为X)：使用该行替换原来关于N的信息
    • else：（即N已存在与Y的路由表中，而且下一跳不是X）
      • if（若收到的信息到达N的距离d小于原来路由表中到达N的距离）：更新
      • else：不更新，查看收到路由表的下一项

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

RIP协议报文格式

• RIP报文的首部为4字节，其中的命令字段代表报文的意义。
• 路由部分由多个路由信息构成，每个路由信息20个字节，每个RIP报文最多包含25个路由信息，构成路由表。
  • 地址族标识符，亦称地址类别，用于标志所使用的地址协议，例如IP协议对应为2
  • 路由标记记录自治系统号ASN（Autonomous System Number），因为路由器可能收到本AS之外的路由信息。
  • 接下来的十六字节分别表示目标网络地址、子网掩码、下一跳路由地址、距离。

内部网关协议OSPF

基本特点

开放最短路径优先OSPF(Open Shortest Path First)的原理很简单，但是实现较为复杂。OSPF使用分布式链路状态协议。与RIP相比，有如下特点：

• 每个路由器都向本AS的所有路由器发送信息（洪泛法）
• 发送的信息为与本路由器相邻的所有路由器的链路状态，即说明本路由器和哪些路由器相邻，以及该链路的度量(metric)，可以表示费用、距离等等指标。
• 只有当链路状态变化时，路由器才向所有路由器使用洪泛法发送信息，非周期性发送。

由于各个路由器之间频繁交换信息，因此所有的路由器最终都能建立一个链路状态数据库(link-state database)，也就是全网拓扑结构图。OSPF的链路状态数据库能够较快的进行更新，更新过程收敛较快。
OSPF会将一个大AS划分为若干个更小的区域(area)，每个区域都有其标识符，这样可以把洪泛法，交换的信息局限在一个area，而不是整个AS，减少了网络的通信量。每个区域的路由器只知道本区域完整拓扑，而不知道其他区域的信息。OSPF使用层次结构的区域划分，上层区域称为主干区域(backbone area)，标识符为0.0.0.0；主干区域连接其他下层区域，从其他区域发来的信息由区域边界路由器(area border router)概括。
OSPF不使用UDP而是直接用IP数据报发送，其数据报很短，可以减少路由信息的通信量。OSPF数据包格式如下：

OSPF还具有如下特点：

• OSPF允许管理员给每条路指派不同的代价，OSPF对于不同类型的业务可以得出不同路由
• 如果到同一目的网络有多个相同代价路由，可以将通信量分配给这几条路径，即负载均衡

其他特点参考谢希仁版《计算机网络》

外部网关协议BGP

用于AS之间的选路
BGP的使用环境和内部网关协议不同，

• 一方面，互联网的规模太大，使得AS与AS之间的路由选择很困难，计算最短路的开销太大，AS内部选择的度量对于通过几个AS的长路由参考意义不大，AS之间交换的应该是可达性信息（即“可达”或“不可达”）。
• 另一方面，AS之间的路由选择应该结合实际环境和法规。

所以，BGP只能尽力寻找一条可到的较好的路由（不能存在环/圈），而不是最佳路由（因为没办法定义最佳）。BGP采用了路径向量(path vector)路由选择协议。
配置BGP时，每个AS都需要至少选择一个路由器作为“BGP发言人”，一般是边界路由器，不同AS的边界路由之间用共享网络连接。BGP发言人互相交换可达性信息，各个BGP根据自选策略从收到的路由信息中找出达到各个AS的较好路由。
vector)路由选择协议**。
配置BGP时，每个AS都需要至少选择一个路由器作为“BGP发言人”，一般是边界路由器，不同AS的边界路由之间用共享网络连接。BGP发言人互相交换可达性信息，各个BGP根据自选策略从收到的路由信息中找出达到各个AS的较好路由。