# 4.4 路由算法和路由协议
## 4.4.1 路由算法的分类
### 1、静态路由
非自适应路由算法（手动配置路由信息）
* 优点
* 简单可靠
* 适用于负荷稳定、拓扑变化不大的网络
* 缺点
* 路由更新慢
* 不适用于大网络
### 2、动态路由
自适应路由算法（路由器彼此交换信息，按照算法优化出路由表）
* 优点
* 路由更新快
* 适用于大型网络
* 及时响应链路变化和网络拓扑变化
* 缺点
* 算法复杂
* 增加网络负担
#### （1）全局性
所有路由器掌握完整的网络拓扑和链路费用信息
应用：链路状态路由算法（OSPF）
#### （2）分散性
路由器仅掌握物理相联的邻居和链路费用
应用：距离向量算法（RIP）
## 4.4.2 层次路由
**自治系统AS**：在单一的技术管理下的一组路由器
* 这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS内的路由
* 同时还使用一种AS之间的路由协议以确定在AS之间的路由
* 一个AS内的所有网络都属于一个行政单位来管辖
* 一个自治系统的所有路由器在本自治系统内都必须连通
#### 意义
* 因特网规模很大，直接连接会导致路由表很大
* 不想让外界知道自己的路由选择协议，但还想连入因特网
#### 具体使用的协议
* **内部网关协议IGP**：AS内部使用的协议
* RIP，OSPF
* **外部网关协议EGP**：AS之间使用的
* BGP
## 4.4.3 RIP协议
RIP是一种分布式的基于**距离向量**的路由选择协议，是因特网的协议标准，最大优点是简单
RIP协议要求网络中每一个路由器都维护从它自己到其他每一个目的网络的唯一**最佳距离记录**（即一组距离）
### 1、RIP路由表的结构
* **目的网络**
* **距离**
* 跳数，即从源端口到目的端口所经过的路由器个数
* 直接与路由器相联的网络距离为1
* 最大允许路由器数量为15，因此**距离为16表示网络不可达**
* **下一跳路由器**
* 对于直连的网络，直接交付
### 2、RIP协议的信息交换
* 每一个路由器**仅和相邻路由器交换**信息
* 路由器交换的信息是自己的**路由表**
* 每30秒交换一次路由信息，然后路由器根据新信息更新路由表
* 若超过180s没收到邻居路由器的通告，则判定邻居没了，并更新自己路由表，将包含邻居的路由信息删除
* 路由器之间通过**RIP报文**交换路由表信息
* RIP本质是UDP报文，是**应用层协议**
* 一个RIP报文最多包含25个路由信息，多的表项需要分次发送
* 当时间足够后，路由器的路由表基本上包含本网络的所有路由信息，称为**收敛**
### 3、距离向量算法
假设路由器X发送了一条RIP报文到路由器A，则A处理RIP报文的逻辑如下：
1. 将RIP报文中的距离+1
2. 将RIP报文的下一跳路由器改为X
3. 检查本身路由表中是否包含相应目的网络
* 存在目的网络，检查其下一跳地址
* 是X，则用新收到的信息替换
* 不是X，则与新收到的距离相比较，保留距离小的
* 不存在目的网络
* 将收到的信息填入路由表
4. 若180秒后还没收到X的更新路由表，则把X记为不可达的路由器，即把距离设置为16
{% hint style="info" %}
例：考虑如图所示的子网，该子网使用了距离-向量算法，下面的向量刚刚到达路由器C：
* 来自B的向量为（5，0，8，12，6，2）
* 来自D的向量为（16，12，6，0，9，10）
* 来自E的向量为（7，6，3，9，0，4）
经过测量，C到B、D和E的延迟分别为6，3和5，那么C到达所有结点的最短路径是什么？
距离向量表示该路由器到其它各个路由器的距离，0表示本机。
将距离向量加上传输延迟即得到新的距离向量：
* C-B：（11，6，14，18，12，8）
* C-D：（19，15，9，3，12，13）
* C-E：（12，11，8，14，5，9）
将自己的对应向量修改位0，其它选最短，即得到最短路径：
（11，6，0，3，5，8）
{% endhint %}
**RIP协议好消息传得快，坏消息传得慢**，称为慢收敛
**慢收敛是导致发生路由回路的根本原因**
## 4.4.4 OSPF协议
**开放最短路径优先OSPF协议**
* 开放标明OSPF协议不是受某一家厂 商控制，而是公开发表的
* 最短路径优先是因为使用了Dijkstra提出的最短路径算法SPF
OSPF最主要的特征就是使用**分布式的链路状态协议**
OSPF分组以IP数据报的结构传输，是**网络层协议**。
### 1、OSPF的数据交换
* 使用洪泛法向自治系统内**所有路由器**发送信息
* 路由器通过输出端口向所有相邻的路由器发送信息
* 每一个相邻路由器又再次将此信息发往其所有的相邻路由器
* 发送的信息就是与本路由器相邻的所有路由器的链路状态
* 本路由器和哪些路由器相邻
* 该链路的度量/代价
* 费用
* 距离
* 时延
* 带宽等
* 只有当链路状态发生变化时，路由器才向所有路由器洪泛发送此信息
最后，所有路由器都能建立一个链路状态数据库，即**全网拓扑图**。
### 2、链路状态路由算法
1. 每个路由器发现它的邻居结点，通过发送**HELLO问候分组**，并了解邻居节点的网络地址
2. 设置到它的每个邻居的成本度量metric
3. 构造**DD数据库描述分组**，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息
* 如果DD分组中的摘要自己都有，则邻站不做处理
* 如果有没有的或者是更新的，则发送**LSR链路状态请求分组**请求自已没有的和比自己更新的信息
4. 收到邻站的LSR分组后，发送**LSU链路状态更新分组**进行更新
5. 更新完毕后，邻站返回一个**LSAck链路状态确认分组**进行确认
6. 使用Dijkstra根据自己的链路状态数据库构造到其他节点间的最短路径
当任意一个路由器的链路状态发生变化时，重复5、6两步，广播更新全部链路状态数据库
### 3、OSPF的区域
OSPF为了便于管理，将一个AS又划分为多个小的**区域**。
区域分为两种：主干区域和其他区域
路由器也分为以下几种
* **自治系统边界路由器**：连接主干区域与AS外部的路由器
* **主干路由器**：位于主干区域内的路由器
* **区域边界路由器**：连接主干区域和其他内部区域的路由器
* **区域内部路由器**：内部区域中的路由器
### 4、OSPF的特点
* 每隔30min刷新一次数据库中的链路状态
* 由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系
* 因此**当互联网规模很大时，OSPF协议要比距离向量协议RIP好得多**
* OSPF不存在坏消息传的慢的问题，它的**收敛速度很快**
## 4.4.5 BGP协议
**BGP发言人**：即BGP边界路由器
### 1、BGP的数据交换
* 与其他AS的邻站BGP发言人交换信息
* 交换的网络可达性的信息，即要到达某个网络所要经过的一系列AS
* 发生变化时更新有变化的部分
实际上，BGP交换的是各个发言人所掌握的路径向量。
BGP报文本质是TCP报文，是**应用层协议**。
### 2、BGP协议的特点
* BGP支持CIDR，因此BGP的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的 各个自治系统序列
* 在BGP刚刚运行时，BGP的邻站是交换整个的BGP路由表。但以后只需要在发生变化时更新有变化的部分。这样 做对节省网络带宽和减少路由器的处理开销都有好处
### 3、BGP-4报文类型
* OPEN（打开）报文
* 用来与相邻的另一个BGP发言人建立关系，并认证发送方。
* UPDATE（更新）报文
* 通告新路径或撤销原路径
* KEEPALIVE（保活）报文
* 在无UPDATE时，周期性证实邻站的连通性
* 也作为OPEN的确认
* NOTIFICATION（通知）报文
* 报告先前报文的差错
* 也被用于关闭连接。
## 4.4.6 三种协议的对比
