计算机网络原理
第五章 第3节
回顾一下前面的
数据平面：分组来了，查表转发。 控制平面：路由表、转发表是怎么算出来的。
这一部分我们大概来看一下：
距离向量路由算法 DV；
DV 的信息扩散、链路变化、无穷计数问题；
LS 和 DV 的对比；
为什么互联网不能用一个平面路由；
AS 自治系统；
AS 内部路由协议：RIP、OSPF；
AS 之间路由协议：BGP；
OSPF 的层次化。
路由算法理论：LS、DV 现实协议实现：RIP、OSPF、BGP 互联网扩展性：AS 层次化路由
二、距离向量 DV 的核心思想
DV 全称：
中文叫：距离向量路由选择。
它的基本思想是：
每个路由器只知道自己到邻居的链路代价，然后和邻居交换“我到各个目的地的距离估计”，再根据邻居的信息更新自己的路由表。
它不像 LS 一样知道全网拓扑。
LS 是：知道全网地图，我自己算最短路。
DV 是：
只问邻居：“你到各个地方有多远？”然后我自己加上到邻居的距离，选最小的。
三、DV 中每个路由器维护什么？
每个路由器维护一张距离向量表，大概长这样：
目的 ｜ 下一跳 ｜ 代价 A ｜ Z ｜ 14 B ｜ Q ｜ 10 C ｜ Y ｜ 5
含义是：
到目的 A，我应该先发给邻居 Z，总代价是 14。
所以 DV 表里最重要的两个东西是：
到每个目的地的最小代价；
对应的下一跳邻居。
四、Bellman-Ford 方程
DV 的数学核心是 Bellman-Ford 方程：
含义：
：节点 $x$ 到目的 $y$ 的最小代价估计；
：节点 $x$ 的某个邻居；
：从 $x$ 到邻居 $v$ 的直接链路代价；
：邻居 $v$ 到目的 $y$ 的代价估计。
这公式怎么理解？
从 $x$ 到 $y$ ，第一跳一定要先走某个邻居 $v$ 。
如果第一跳走 $v$ ，总代价就是：
也就是：
把所有邻居都试一遍，选最小的那个。
五、DV 小例子
假设节点 $u$ 的邻居有：
链路代价是：
邻居告诉 $u$ ：
那么 $u$ 到 $z$ 的代价是：
所以： $u$ 到 $z$ 最好先走 $x$ ，总代价 4。
路由表中写：
目的 ｜ 下一跳 ｜ 代价 z ｜ x ｜ 4
六、DV 算法的运行过程
每个节点都重复做三件事。
1. 等待事件
事件包括：
自己到邻居的链路代价改变；
收到邻居发来的距离向量。
2. 重新计算自己的 DV
收到邻居信息后，用 Bellman-Ford 方程更新：
对每一个目的 $y$ 都算一遍。
3. 如果自己的 DV 变化，就通知邻居
如果某个目的地的最小代价变了，或者下一跳变了，就把新的距离向量发给邻居。
邻居收到后再更新。
这样一轮一轮迭代，直到所有节点的表都稳定。
七、DV 的三个特点
1. 迭代式
DV 不是一次算完，而是不断根据邻居信息更新。
2. 异步
所有路由器不需要同时更新。
谁收到消息，谁就可以先算。
3. 分布式
每个节点只和邻居交换信息，不需要知道全网拓扑。
所以 DV 更像：
局部交流，逐渐扩散，全网收敛。
八、DV 迭代过程怎么理解？
刚开始 $t=0$ 时，每个节点只知道：
自己到自己是 0，到直接邻居是链路代价，到其他节点是无穷大。
比如节点 $a$ 一开始知道：
其他目的暂时是：
t = 1
每个节点把自己的 DV 发给邻居。
比如 $b$ 收到来自 $a,c,e$ 的 DV。
然后 $b$ 计算：
对每个目的 $y$ 都算一遍。
t = 2
节点又把更新后的 DV 发给邻居。
这时候一个节点可以学到两跳以内的信息。
t = 3、t = 4
信息继续往外扩散。
一般可以理解成：
第 1 轮知道邻居的信息； 第 2 轮知道两跳范围的信息； 第 3 轮知道三跳范围的信息； 继续下去，最终全网收敛。
所以 DV 的信息传播有点像“水波扩散”。
九、DV 中状态信息的扩散
：c 的状态只有 c 自己知道；
：c 的信息传到邻居，比如 b、f；
：影响到距离 c 两跳的节点；
：影响到三跳外；
：继续扩散。
所以 DV 的传播特点是：一跳一跳往外传。
这和 LS 不一样。
LS 是：每个路由器把链路状态泛洪给所有路由器。
DV 是：只告诉邻居，邻居再告诉它们的邻居。
十、链路代价变化：好消息传得快
如果链路代价变小，比如原来 $x$ 到 $y$ 的代价是 4，现在变成 1。
那么：
发现到 $x$ 更近了；
更新自己的 DV；
告诉邻居；
邻居发现通过 $y$ 到 $x$ 更便宜，也更新；
信息很快扩散。
这叫：好消息传得快。
因为一旦发现更短路径，大家都愿意立刻采用。
十一、链路代价变坏：坏消息传得慢
如果链路代价变大，问题就复杂了。
比如原来：
后来变成：
假设 $z$ 原来通过 $y$ 到 $x$ ， $y$ 又以为可以通过 $z$ 到 $x$ 。
这时候可能出现：
以为 $z$ 有路， $z$ 以为 $y$ 有路。
它们互相误导，代价一点点增加。
这就是：count-to-infinity，无穷计数问题。
十二、无穷计数问题
无穷计数的本质是：
路由器只知道邻居告诉自己的距离，但不知道邻居的路径到底经过谁。
所以当某条链路坏掉后，邻居可能还在用旧信息，以为对方有路。
比如：
到 $x$ 的链路代价变大；
问 $z$ ：你到 $x$ 多远？
说：我到 $x$ 是 5；
但其实 $z$ 的路径可能是通过 $y$ 到 $x$ ；
听了以后，以为自己可以通过 $z$ 到 $x$ ；
又以为可以通过 $y$ ；
二者互相骗，代价慢慢增加。
这就是坏消息传得慢。
十三、毒性逆转 Poison Reverse
为了解决两个节点之间的简单环路，DV 里可以用：
毒性逆转 poison reverse。
规则是：
如果我到目的 $x$ 的下一跳是邻居 $v$ ，那么我告诉 $v$ ：我到 $x$ 的距离是无穷大。
比如 $z$ 到 $x$ 是通过 $y$ 走的，那么 $z$ 告诉 $y$ ：
意思是：你别通过我去 x，因为我本来就是通过你去 x 的。
这样可以防止两节点之间的 ping-pong 回环。
但是注意：毒性逆转不能彻底解决所有多节点环路。
比如三台以上路由器形成的环，仍然可能出现问题。
十四、LS 和 DV 的对比
对比 ｜ LS 链路状态 ｜ DV 距离向量 知道的信息 ｜ 全网拓扑和链路代价 ｜ 只知道邻居和邻居的距离估计 信息传播 ｜ 向全网泛洪 LS 分组 ｜ 只和邻居交换 DV 算法 ｜ Dijkstra ｜ Bellman-Ford 收敛速度 ｜ 通常较快 ｜ 可能较慢 消息复杂度 ｜ 需要全网泛洪，开销较大 ｜ 邻居间交换，收敛时间与变化有关 稳定性问题 ｜ 可能路由振荡 ｜ 可能路由环路、无穷计数 典型协议 ｜ OSPF ｜ RIP
十五、为什么需要可扩展路由？
前面学的 LS、DV 都比较理想化。
如果整个互联网所有路由器都在一个平面上运行 LS 或 DV，会出大问题。
1. 规模太大
互联网有海量网络和路由器。
如果每台路由器都保存全网路由信息，路由表太大。
如果每次链路变化都通知全网，消息量太大。
2. 管理自治性
互联网不是一个人管理的。
不同网络属于不同组织：
学校
公司
ISP
数据中心
运营商
它们不可能都用同一套内部路由策略。
每个网络的管理员都希望控制自己网络内部的路由方式。
所以需要层次化。
十六、AS：自治系统
互联网采用的可扩展方案是：
把互联网划分成很多自治系统 AS。
AS 全称：
自治系统。
一个 AS 通常是：
一个 ISP 或一个大型组织管理的一组路由器和网络。
每个 AS 有一个唯一的 AS Number，简称 ASN。
例如：
一个校园网可以是一个 AS；
一个运营商网络可以包含一个或多个 AS；
一个大型公司也可能有自己的 AS。
十七、AS 内部路由和 AS 间路由
互联网路由分成两层。
1. AS 内部路由 intra-AS routing
也叫：域内路由。
它解决的是：在同一个 AS 内部，路由怎么走。
特点：
同一个 AS 内部通常运行同一种内部路由协议；
不同 AS 可以使用不同的内部协议；
管理员可以自己决定内部路由策略。
典型协议：
RIP
OSPF
EIGRP
IS-IS
2. AS 间路由 inter-AS routing
也叫：域间路由。
它解决的是：不同 AS 之间怎么互联，去别的 AS 应该走哪个出口。
典型协议：
BGP 全称：
边界网关协议。
十八、网关路由器 Gateway Router
在 AS 的边缘，连接其他 AS 的路由器叫：
网关路由器 gateway router。
它有两个作用：
对内部 AS 来说，它是出去到外部网络的出口；
对外部 AS 来说，它是进入该 AS 的入口。
所以内部路由协议要解决：
怎么到达本 AS 的网关。
外部路由协议 BGP 要解决：
哪个网关能到达哪个外部目的网络。
十九、RIP 协议
RIP 全称：
它是一个经典的 AS 内部路由协议。
RIP 使用的是：距离向量 DV 算法。
RIP 的度量指标
RIP 的 cost 是：
每经过一个路由器，跳数加 1。
所以 RIP 不看：
带宽
延迟
拥塞
只看经过多少跳。
RIP 的最大跳数
RIP 规定最大跳数是：
如果跳数为 16，就认为不可达。
所以 RIP 只适合小型网络。
二十、RIP 的通告
RIP 路由器会和邻居交换路由通告。
特点：
每 30 秒和邻居交换一次；
如果路由改变，也可以触发通告；
在对方请求下也可以发送通告；
每个通告最多包含 25 个目标子网的信息。
通告内容一般是：
也就是：
目标子网 ｜ 跳数 u ｜ 1 v ｜ 2 w ｜ 2
二十一、RIP 例子怎么更新？
假设路由器 D 原来的表里：
目的子网 ｜ 下一跳 ｜ 跳数 w ｜ A ｜ 2 y ｜ B ｜ 2 z ｜ B ｜ 7 x ｜ - ｜ 1
现在 A 发给 D 一个距离向量：
目的 ｜ 从 A 到目的的跳数 w ｜ 1 x ｜ 1 z ｜ 4
D 到 A 是 1 跳。
所以 D 通过 A 到 z 的代价是：
原来 D 到 z 是通过 B，跳数 7。
现在通过 A 是 5，更短。
所以更新：
目的子网 ｜ 下一跳 ｜ 跳数 z ｜ A ｜ 5
这就是 RIP 中 DV 更新的方法
二十二、RIP 链路失效和恢复
如果 180 秒没有收到某个邻居的通告，RIP 会认为：
这个邻居或链路失效了。
然后：
标记经过这个邻居的路由失效；
发送新的通告给邻居；
邻居再继续扩散；
整个网络逐渐更新。
为了避免 ping-pong 回路，RIP 使用：
毒性逆转 poison reverse。
并且 RIP 中：
也就是不可达。
二十三、RIP 的实现
RIP 是由应用进程实现的。
常见实现是：
它通过 UDP 传输 RIP 报文。
这说明：
虽然 RIP 是网络层路由协议，但它的报文传输使用了运输层 UDP 服务。
二十四、OSPF 协议
OSPF 全称：
它也是 AS 内部路由协议。
OSPF 使用的是：链路状态 LS 算法。
OSPF 的特点
1. 开放
Open 表示：协议规范公开可用。
2. 使用 LS 算法
每个路由器泛洪 OSPF 链路状态通告。
每个路由器得到全 AS 的拓扑和链路代价后，运行 Dijkstra 算法计算路由表。
3. 直接运行在 IP 上
OSPF 报文直接封装在 IP 中。
它不像 RIP 那样使用 UDP，也不是 TCP。
4. 支持多种链路代价
OSPF 的链路代价可以根据：
带宽
延迟
管理员配置
来设置。
5. 支持认证
OSPF 报文可以经过认证，防止恶意攻击或者伪造路由信息。
二十五、OSPF 和 RIP 对比
对比 ｜ RIP ｜ OSPF 算法 ｜ DV ｜ LS 度量 ｜ 跳数 ｜ 链路代价，可配置 最大范围 ｜ 15 跳，适合小网络 ｜ 适合较大 AS 信息交换 ｜ 邻居间交换 DV ｜ 泛洪链路状态通告 计算方法 ｜ Bellman-Ford ｜ Dijkstra 传输方式 ｜ UDP ｜ 直接封装在 IP 收敛 ｜ 较慢，可能无穷计数 ｜ 通常较快 安全 ｜ 较弱 ｜ 支持认证
二十六、OSPF 的层次化
如果一个 AS 很大，所有路由器都在一个 LS 域里泛洪，也会很重。
所以 OSPF 支持层次化，把 AS 分成多个区域：
本地区域 area
骨干区域 backbone area
为什么要分区域？
为了减少：
链路状态通告的泛洪范围；
每台路由器需要保存的拓扑信息；
Dijkstra 计算压力。
每个路由器只需要知道：
自己所在区域的详细拓扑，以及去其他区域的大致方向。
二十七、OSPF 中几类路由器
1. Internal Router
内部路由器。
它只属于一个区域，在该区域内部运行 OSPF。
2. Area Border Router
区域边界路由器。
它连接本地区域和骨干区域。
作用是：汇总本区域到外部区域的距离，并向骨干区域通告。
3. Backbone Router
骨干路由器。
它在骨干区域内部运行 OSPF。
骨干区域负责连接各个区域。
4. Boundary Router
边界路由器。
它连接其他 AS。
也就是 AS 对外的出口。
二十八、层次化 OSPF 的理解
一个 AS 内部被分成：
每个普通区域内部：只泛洪本区域内的链路状态信息。
骨干区域：负责连接各个区域。
如果 area1 的路由器要到 area3：
大概路径是：
这种层次化降低了全网 LS 泛洪的压力。
二十九、BGP 的位置
BGP 是：
也叫：外部网关协议。
它和 RIP、OSPF 不同。
RIP、OSPF 是在一个 AS 内部用的。
BGP 是在 AS 和 AS 之间用的。
BGP 解决的问题（商业问题和实际的关系问题或许会多一些）
BGP 主要解决：
到某个外部网络前缀，应该经过哪些 AS，选择哪个 AS 出口。
它不是简单地找最短路。
因为 AS 之间路由有很多策略因素，比如：
商业关系；
谁给谁付钱；
是否允许某些流量经过；
出口策略；
运营商政策。
所以 BGP 是策略路由，不只是最短路径路由。
三十、整体逻辑
DV 是一种分布式路由算法。每个路由器只和邻居交换距离向量，用 Bellman-Ford 方程更新自己的路由表。
它简单，但可能出现路由环路、无穷计数，坏消息传得慢。RIP 就是基于 DV 的 AS 内部协议，使用跳数作为度量，最大 15 跳，每 30 秒交换一次通告，16 跳表示不可达。
LS 是另一种路由算法，每个路由器通过泛洪获得全网拓扑，然后用 Dijkstra 算法计算最短路径。OSPF 就是基于 LS 的 AS 内部协议，支持链路代价、认证和层次化区域。
由于互联网太大，不能把所有路由器放在一个平面里运行一个路由算法，所以采用 AS 层次化。
每个 AS 内部运行自己的内部路由协议，比如 RIP 或 OSPF；AS 之间通过 BGP 交换路由信息。
三十一、回顾
1. DV 核心公式
含义：从 x 到 y，试所有邻居 v，选总代价最小的那个作为下一跳。
2. DV 三个特点
迭代式
异步
分布式
3. DV 的问题
路由环路
无穷计数
坏消息传得慢
4. 毒性逆转
如果我到某目的地是通过邻居 v，那么我告诉 v：我到这个目的地的距离是无穷大。
作用：防止两个节点之间的简单环路。
5. RIP
基于 DV；
度量是跳数；
最大 15 跳；
16 跳表示不可达；
每 30 秒交换通告；
180 秒没收到通告认为链路失效；
通过 UDP 实现；
每个通告最多 25 个目标子网。
6. OSPF
基于 LS；
使用 Dijkstra；
泛洪链路状态通告；
直接运行在 IP 上；
支持认证；
支持层次化区域。
7. AS
自治系统，一个管理域内的一组路由器和网络，通常属于一个 ISP 或组织。
8. AS 内部路由 vs AS 间路由
类型 ｜ 作用 ｜ 协议 AS 内部路由 ｜ 一个 AS 内部怎么走 ｜ RIP、OSPF AS 间路由 ｜ AS 与 AS 之间怎么走 ｜ BGP
9. OSPF 层次化
本地区域 area
骨干区域 backbone
区域边界路由器 area border router
骨干路由器 backbone router
边界路由器 boundary router
DV 通过邻居交换距离向量，用 Bellman-Ford 方程逐步更新路由表；RIP 是典型 DV 协议。LS 通过泛洪链路状态，让每个路由器获得全网拓扑，用 Dijkstra 算最短路径；OSPF 是典型 LS 协议。互联网规模太大，所以用 AS 层次化：AS 内部用 RIP/OSPF，AS 之间用 BGP。