> For the complete documentation index, see [llms.txt](https://lfool.gitbook.io/computer-network/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lfool.gitbook.io/computer-network/di-si-zhang-wang-luo-ceng/5.-lu-you-suan-fa-lu-you-xie-yi.md).

# 5. 路由算法 & 路由协议

## 1. 路由算法

![](/files/-ME1bgUPKZkhCOtFWi2z)

通过路由算法，可以填充路由器的转发表，从而可以进行有效的转发

### 1.1 路由算法的分类

静态路由算法（非自适应路由算法）

* 管理员手动配置路由信息
* **优点：**简便、可靠，在负荷稳定、拓扑变化不大的网络中运行效果很好，广泛用于高度安全性的军事网络和较小的商业网络
* **缺点：**路由更新慢，不适用大型网络

动态路由算法（自适应路由算法）

* 路由器间彼此交换信息，按照路由算法优化出路由表项
* **优点：**路由更新快，适用于大型网络，及时响应链路费用或网络拓扑变化
* **缺点：**算法复杂，增加网络负担

动态路由算法分为：

* **（全局性）**链路状态路由算法 **OSPF**

  所有路由掌握完整的网络拓扑和链路费用信息
* **（分散性）**距离向量路由算法 **RIP**

  路由器只掌握物理相连的邻居及链路费用

### 1.2 分层的路由选择协议

**出现的原因：**

1. 因特网规模很大
2. 许多单位不想让外界知道自己的路由选择协议，但还想连入因特网

**自治系统AS：**在单一的技术管理下的一组路由器，而这些路由器使用一种 AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由，同时还使用一种 AS 之间的路由协议以确定在 AS 之间的路由。

一个 AS 内的所有网络都属于一个行政单位来管辖，一个自治系统的所有路由器在本自治系统内都必须连通。

![](/files/-ME2-r61JbG0hBoxB2qU)

![](/files/-ME2-w-VTMgB4BN5vbiQ)

## 2. RIP 协议 & 距离向量算法

RIP 是一种分布式的基于**距离向量**的路由选择协议，是因特网的协议标准，最大的优点是简单。

RIP 协议要求网络中每一个路由器都维护**从它自己到其他每一个目的网络的唯一最佳距离记录**（即一组距离）

距离：通常为“跳数”，即从源端口到目的端口所经过的路由器个数，经过一个路由器跳数 +1。特别的，与路由器直接相连的网络距离为 1。RIP 允许一条路由最多只能包含 15 个路由器，因此距离为 **16 表示网络不可达**。

RIP 协议只适用于**小互联网**

![](/files/-ME2dfyu5micMQMdiUfr)

### 2.1 RIP 协议的三个问题

**RIP 协议和谁交换？**

* 仅和相邻路由器交换信息

**多久交换一次？**

* 每 30 秒交换一次路由信息，然后路由器根据新信息更新路由表。若超过 180 秒没有收到邻居路由器的通告，则判定邻居没了，并更新自己路由表

**交换什么？**

* 路由器交换的信息是自己的路由表

路由器刚开始工作时，只知道直接连接的网络的距离（距离为 1），接着每一个路由器也只和数据非常有限的相邻路由器交换并更新路由信息。

经过若干次更新后，所有路由器最终都会知道到达本自治网络任何一个网络的最短距离和下一跳路由器的地址，即“**收敛**”

### 2.2 距离向量算法

![](/files/-ME2hhbwvOX1y2QCtsb3)

1. 修改相邻路由器发来的 RIP 报文中所有表项

   对地址为 X 的相邻路由器发来的 RIP 报文，修改此报文中的所有项目：把 下一跳 字段中的地址改为 X，并把**所有的距离字段 + 1**
2. 对修改后的 RIP 报文中的每一个项目，进行一下步骤
   * $$R\_1$$ 路由表中若没有Net3，则把该项目填入 $$R\_1$$ 路由表
   * $$R\_1$$ 路由表若有Net3，则查看下一跳路由器地址：
     * 若下一跳是 X，则用收到的项目替换源路由表中的项目
     * 若下一跳不是 X，原来距离比从 X 走的距离远则更新，否则不作处理
3. 若 180s 还没有收到相邻路由器 X 的更新路由表，则把 X 记为不可达的路由器，即把距离设置为 16
4. 返回

### 2.3 例题

![](/files/-ME2hskaxTk6gnu_UA7p)

### 2.4 RIP 协议的报文格式

![](/files/-ME2iKuBsyI71c6oBPVn)

### 2.5 RIP 协议好消息传得快，坏消息传得慢

RIP特点：当网络出现故障时，要经过比较长的时间（例如数分钟）才能将此信息传送到所有的路由器，“**收敛慢**”

### 2.6 知识脑图

![](/files/-ME2jYbWIzM-SC1T1q88)

## 3. OSPF 协议 & 链路状态算法

开放最短路径优先协议 OSPF 协议：“开放” 标明 OSPF 协议不是受某一家厂商控制，而是**公开发表**的；“最短路径优先” 是因为使用了 **Dijkstra** 提出的**最短路径算法 SPF**

OSPF 最主要的特点就是使用分布式的**链路状态协议**

### 3.1 OSPF 协议三个问题

**和谁交换？**

* 使用洪泛向自治系统内**所有路由器**发送信息，即路由器通过输出端口向所有相邻的路由器发送信息，而每一个相邻路由器又再次将信息发往其他所有的相邻路由器。**广播**

**交换什么？**

* 发送的信息就是与本路由器**相邻的所有路由器的链路状态**（本路由器和哪些路由器相邻，以及该链路的度量/代价 —— 费用、距离、时延、带宽等）

**多久交换？**

* 只有当**链路状态发送改变时**，路由器才向所有路由器洪泛发送此信息

最后，所有路由器都能建立一个**链路状态数据库**，即**全网拓扑图**

### 3.2 链路状态路由算法

1. 每个路由器发现它的邻居结点【HELLO 问候分组】，并了解邻居结点的网络地址
2. 设置到它的每个邻居结点的成本度量 metric
3. 构造【DD 数据库描述分组】，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息
4. 如果 DD 分组中摘要信息自己都有，则邻站不做处理；如果有没有的或者是更新的，则发送【LSR链路状态请求分组】请求自己没有的和比自己更新的信息
5. 收到邻站的 LSR 分组后，发送【LSU 链路状态更新分组】进行更新
6. 更新完毕后，邻站返回一个【LSAck 链路状态确认分组】进行确认

   只要一个路由器的链路状态发送变化：
7. 洪泛发送【LSU 链路状态更新分组】进行更新
8. 更新完毕后，其他站返回一个【LSAck 链路状态确认分组】进行确认
9. 使用 Dijkstra 根据自己的链路状态数据库构造到其他结点间的最短路径

### 3.3 OSPF 的区域

为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫做区域。

每一个区域都有一个 32 位的区域标识符（用点分十进制表示）

区域也不能太大，在一个区域内的路由器最好不超过 200个

![](/files/-ME3BZ2voA8vBncV-7_T)

### 3.4 OSPF 分组

![](/files/-ME3Bfwn5GsFRQgN36u7)

### 3.5 OSPF 其他特点

1. 每隔 **30min**，要刷新一次数据库中的链路状态
2. 由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当**互联网规模很大**时，OSPF 协议要比距离向量协议 RIP 好得多
3. OSPF 不存在坏消息传的慢的问题，它的**收敛速度很快**

## 4. BGP 协议

### 4.1 BGP 协议三个问题

**和谁交换？**

* 与其他 AS 的邻站 BGP 发言人交换信息

**交换什么？**

* 交换的网络可达性的信息，即要到达某个网络所要经过的一系列 AS

**多久交换？**

* 发生变化时更新有变化的部分

![](/files/-ME3Z_O_J9GJsZC3Oc2W)

### 4.2 BGP 协议交换信息的过程

BGP 所交换的网络可达性信息就是要**到达某个网络所要经过的一系列 AS**。当 BGP 发言人互相交换了网络可达性信息后，各 BGP 发言人就根据所采用的策略从收到的路由信息中找出到达各 AS 的较好路由

BGP 发言人交换路径向量：

* 自治系统 $$AS\_2$$ 的 BGP 发言人通知主干网 $$AS\_1$$ 的 BGP 发言人：要到达网络 $$N\_1、N\_2、N\_3、N\_4$$ 可经过 $$AS\_2$$ 

![](/files/-ME3bAHLbdeUtJTeVSZB)

* 主干网还可发出通知：要到达网络 $$N\_5、N\_6、N\_7$$ 可沿路径（ $$AS\_1、AS\_3$$ ）

![](/files/-ME3ba7ClGt0V9sSixIQ)

### 4.3 BGP 协议报文格式

一个 BGP 发言人与其他自治系统中的 BGP 发言人要交换信息，就要**先建立 TCP 连接**，即通过 TCP 传送，然后在此连接上交换 BGP 报文以建立 BGP 会话（session），利用 BGP 会话交换路由信息

![](/files/-ME3cBktIAxOm-MVwarZ)

### 4.4 BGP 协议特点

* BGP 支持 **CIDR**，因此 BGP 的路由表也就应当包含目的网络前缀、下一跳路由器，以及到达该目的网络所要经历的各个自治系统序列。
* 在 BGP 刚刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在**发生变化时更新有变化的部分**。这样做对节省网络带宽和减少路由器的处理开销都有好处。

### 4.5 BGP-4 的四种报文

1. **OPEN（打开）报文：**用来与相邻的另一个 BGP 发言人建立关系，并认证发送方
2. **UPDATE（更新）报文：**通告新路径或撤销原路径
3. **KEEPALIVE（保活）报文：**在无 UPDATE 时，周期性证实邻站的连通性：也作为 OPEN 的确认
4. **NOTIFICATION（通知）报文：**报告先前报文的差错；也被用于关闭连接

## 5. 三种路由协议比较

* **RIP** 是一种分布式的基于**距离向量**的内部网关路由选择协议，通过广播 **UDP** 报文来交换路由信息
* **OSPF** 是一个内部网关协议，要交换的信息量较大，应使报文的长度尽量短，所以不使用传输层协议（如TCP/UDP），而直接采用 **IP**
* **BGP** 是一个外部网关协议，在不同的自治系统之间交换路由信息，由于网络环境复杂，需要保证可靠传输，所以采用 **TCP**

![](/files/-ME3etKnXjYWdtyMs4Pb)