第二章第四节 互联网的路由选择协议
基本概念
理想的路由算法应具有如下特点：(1)算法必须正确、完整；(2)算法易于计算；(3)算法具有自适应性，即能适应通信量与网络拓扑的变化；(4)稳定性；(5)公平性；(6)算法应是最优的。实际的路由算法应尽可能接近理想的路由算法。
分层的路由选择协议
互联网采用分层次的路由选择协议，整个互联网被划分为许多较小的自治系统AS。于是，路由选择协议分为两类：(1)内部网关协议IGP：自治系统内部使用的路由选择协议，如RIP、OSPF协议；(2)外部网关协议：各自治系统间使用的路由选择协议，如BGP-4。
内部网关协议RIP
工作原理
RIP协议要求网络中的每个路由器均维护一个从自身到所有其他网络的距离，即跳数。RIP协议有如下特点：
- 只与相邻路由器交换信息。
- 路由器无保留地交换信息。
- 路由器按固定的时间间隔交换信息。
路由表中的主要信息为：(1)到某个网络的最短距离；(2)下一跳的地址；路由器更新要做的就是刷新到各个网络的最短距离及其应该经过的下一跳地址。即RIP协议所使用的距离向量算法。
距离向量算法
对每一相邻路由器发来的RIP报文，路由器根据此报文更新路由表：
(1)对地址为X的相邻路由器发来的RIP报文中的路由表，将路由表中的所有路由的下一跳项改为X、距离项的值加1；
(2)对修改后的每一路由r：若路由器的路由表中没有到r中目的网络y的路由，则将此路由添加到路由器的路由表中。否则，记路由器的路由表中到目的网络y的路由为s，(i)若s的下一跳地址为X，则将r替换s；(ii)s的下一跳地址非X，若r的距离小于s的距离，则将r替换s。
(3)若3分钟未收到相邻路由器的路由表，则将此相邻路由器标记为不可达。
RIP协议的报文格式
其中路由标记填入自治系统号ASN。RIP实现简单、开销小，存在的问题是传递故障信息的速度很慢，适用于小规模网络。
内部网关协议OSPF
工作原理
OSPF为分布式链路状态协议，具有以下3个特点：
- 采用洪泛法向所有相邻的路由器发送信息；
- 发送的信息为与自身相邻的所有路由器的链路状态，链路状态包含费用、距离、时延、带宽等等；
- 只有链路状态发生变化时，发生变化的路由器才使用洪泛法向所有相邻的路由器发送信息；
各路由器之间频繁交换链路状态信息，最终所有的路由器都能建立一个链路状态数据库，即全网的拓扑结构图。每个路由器根据拓扑结构图使用Dijkstra算法计算到各路由器的路由。
划分区域
OSPF为适应大规模的自治系统，将其划分为若干个小范围——区域，每一区域有一个32位的标识符。此时再使用洪泛法发送信息时就只在区域内传递。为使得区域间能发送消息，OSPF会定义一个主干区域，其他区域均为边界区域。主干区域的标识符为0.0.0.0，它连接所有的边界区域，来自其他区域的信息先汇集到该区域的边界路由器，进入主干区域后流入目的区域。如下是一个例子。
OSPF协议报文格式
OSPF使用IP数据报传递信息，OSPF分组使用如下图的24字节固定长度头部，如下图为OSPF协议报文格式。
OSPF报文共有5种类型。其中路由器标识符标志发送此报文的路由器接口IP地址。OSPF具有以下特点：
- OSPF允许管理员给每条路由指派不同的代价；
- 若到目的网络存在多条代价相同的路由，OSPF可将通信量分配到多条路径，达到多路由间的负载均衡；
- 所有使用OSPF协议的路由器在交换时都会进行鉴别，确保仅在可信赖的路由器间交换链路状态信息；
- OSPF支持可变长度的子网划分与无分类的编址CIDR；
- 由于网络中的链路状态经常变化，因此OSPF让每一个链路状态带有一个32位的序号，每次链路状态改变序号加1，且OSPF协议规定增长的速率不超过次/5s；
5类OSPF报文
- 问候报文。发现与维持相邻路由器的可达性；
- 数据库描述报文。向相邻路由器发送自身链路状态数据库中所有链路状态项目的摘要信息；
- 链路状态请求报文。向目的路由器请求其发送某些链路状态项目的详细信息；
- 链路状态更新报文。使用洪泛法向全网更新链路状态；
- 链路状态确认报文。对链路更新分组进行确认；
除问候报文外，其余四类报文均用来进行链路状态数据库的同步。一个刚刚工作的路由器先通过问候报文得知有哪些路由器与之物理相邻。每个路由器向相邻路由器发送数据库描述报文，路由器再根据这些数据库描述报文向对应路由器发送链路状态请求报文。通过一系列交互，建立起全网同步的链路数据库。上述同步的示意图如下。
外部网关协议BGP
工作原理
在配置BGP时，每个自治系统的管理员至少选择一个路由器作为”BGP发言人”，BGP发言人使用TCP连接交换路由信息。BGP发言人与自治系统AS之间的关系如下图。各BGP发言人之间交换的信息就是达到某个网络需经过的自治系统。
BGP协议支持无分类域间路由选择CIDR，因此使用BGP协议的路由器的每条路由应包含目的网络前缀、下一跳IP地址、到达目的网络需经过的自治系统序列。若某个BGP发言人收到其他BGP发言人的路径通知，它需要检查自身是否在通知的路径中，若在，则不能采用此路径，避免形成回路。
路由器运行稳定后，路由器只需要在自治系统发生变化时发送BGP报文。
4类BGP报文
- OPEN报文。与相邻的BGP发言人建立关系，初始化通信；
- UPDATE报文。告知某一路由的信息(不能增加多条)，以及列出要撤销的多条路由；
- KEEPALIVE报文。周期性地证实连接的连通性。
- NOTIFICATION报文。发送检测到的差错。
BGP报文格式
4类BGP报文具有同样的通用BGP头部，如下图所示。
KEEPALIVE报文只有BGP头部，共19字节。OPEN报文主体有6个字段：版本、本自治系统号、保持时间、BGP标识符、可选参数长度、可选参数；UPDATE报文主体有5个字段：不可行路由长度、撤销路由列表、路径属性总长度、路径属性、网络层可达信息。NOTIFICATION报文有3个字段：差错代码、差错子代码、差错数据。
路由器简介
典型的路由器结构如下。
