计算机网络原理

第五章第1节-第2节

这一章开始就是网络层：控制平面。

前一章数据平面讲的是：分组到了路由器，怎么查表、怎么转发。

这一章控制平面讲的是：

这些转发表是怎么算出来的？路由器怎么知道去某个目的网络应该走哪条路？

控制平面负责计算路由，生成转发表；数据平面负责按转发表转发分组。

一、先区分：转发 vs 路由

这个是第 5 章的入口。

1. 转发 forwarding：数据平面

转发是路由器内部的局部动作：

把分组从某个输入端口转到合适的输出端口。

比如路由器收到目的 IP 为 130.130.130.5 的包，查表发现应该从 Eth1 发出去，这就是转发。

所以转发回答的是：这个包来了，我现在从哪个口发出去？

2. 路由 routing：控制平面

路由是全网范围的路径计算：

决定分组从源主机到目的主机应该经过哪些路由器。

它回答的是：从源到目的，整条路怎么走？

所以本节实现的就是路由层面

二、控制平面的两种实现方式

网络层控制平面有两种典型方式。

1. 每路由器控制平面：传统方式

传统网络中，每台路由器都有自己的控制平面。

每个路由器内部运行路由算法，和别的路由器交换路由信息，然后自己算出转发表。

比如：

RIP

OSPF

BGP

都属于传统路由协议体系。

这种方式可以理解成：

每台路由器都是一个独立的小脑袋，大家互相交流，然后各自算路由表。

2. SDN 控制平面：逻辑集中控制

SDN 是 Software-Defined Networking，软件定义网络。

它把控制逻辑集中到一个远程控制器里。

路由器/交换机本身主要负责数据平面转发。

控制器负责：

收集网络状态计算路径下发转发表/流表

可以理解成：一个大脑控制很多交换设备，设备只负责执行。

和前面 OpenFlow 对应：

SDN 是思想，OpenFlow 是控制器给交换机下发表项的一种协议。

三、路由以“网络/子网”为单位，而不是以主机为单位

互联网中路由一般不是对每一台主机单独算路由，而是对一个子网、一个网络前缀算路由。

比如：

200.23.16.0/23

表示一个网络。

路由器只需要知道：

去 200.23.16.0/23 这个网络，下一跳是谁。

不需要为这个网络里的每一台主机都单独保存一条路由。

因为主机太多了。

如果为每台主机都存路由，路由表会爆炸。

所以互联网路由通常是：

目标网络前缀 → 下一跳

比如：

目标网络｜下一跳 200.23.16.0/23 ｜ IPx 199.31.0.0/16 ｜ IPy

这样可以大大减少路由信息量。

四、路由问题可以抽象成图(可以看算法数据结构里面的图论)

路由算法通常把网络抽象成一个图：

G=(N|E)

其中：

N

：节点集合，通常表示路由器

E

：边集合，表示路由器之间的链路

每条链路有一个代价：

c(x|y)

表示从节点 $x$ 到节点 $y$ 的链路代价。

链路代价可以是什么？（也就是权重）

链路代价可以由网络管理员定义，比如：

延迟

带宽的反比

拥塞程度

人为配置的权重

链路费用

一般代价越小，表示这条链路越“好”。

路径代价

如果路径是：

{x}_{1}\to {x}_{2}\to {x}_{3}\to ⋯\to {x}_{p}

那么路径总代价是：

c({x}_{1}|{x}_{2})+c({x}_{2}|{x}_{3})+⋯+c({x}_{p-1}|{x}_{p})

路由算法的目标通常就是：

找总代价最小的路径。

五、最优化原则

sink tree，叫汇集树。

意思是：

对某个目的节点来说，所有其他节点到它的最短路径会组成一棵树。

比如所有节点都要去目的节点 D，那么每个节点都会选择一条到 D 的最优路径，这些路径合起来就是 D 的汇集树。

路由算法本质上就是：

给每个目的网络或目的节点，找到对应的最优路径树。

六、路由算法应该满足什么原则？

一个好的路由算法要满足这些要求：

1. 正确性 correctness

算出来的路由必须正确。

不能出现：

到不了目的地

路由环路

转发错误

2. 简单性 simplicity

算法不能太复杂。

路由器资源有限，协议也要容易实现和维护。

3. 健壮性 robustness

网络拓扑和通信量会变。

算法要能适应：

链路断开

路由器故障

代价变化

新节点加入

4. 稳定性 stability

路由结果不能一直乱变。

如果路由频繁震荡，网络会不稳定。

5. 公平性 fairness

不同流量、不同用户之间尽量公平。

6. 最优性 optimality

希望找到代价最小的路径。

不过实际中“最优”经常和稳定性、简单性冲突，所以现实协议往往是折中。

七、路由算法分类

1. 全局 vs 分布式

全局算法

每个路由器知道整个网络拓扑和所有链路代价。

然后自己算最短路径。

典型代表：链路状态算法 Link State，LS。

分布式算法

每个路由器一开始只知道自己和邻居之间的代价。

它通过和邻居交换信息，逐步更新自己的路由表。

典型代表：

距离向量算法 Distance Vector，DV。

2. 静态 vs 动态

静态路由

路由变化很慢，甚至由管理员手动配置。

动态路由

路由会根据网络变化自动调整。

比如链路代价变化、链路故障，路由协议会重新计算。

八、链路状态路由 LS：整体思想

链路状态算法的核心是：

每个路由器先获得整个网络拓扑和链路代价，然后用 Dijkstra 算法计算到所有目的节点的最短路径。（Dj算法我的leetcode笔记里有）

它的特点是：每台路由器都知道全网地图。

九、LS 路由的工作过程

第 1 步：发现邻居节点

路由器上电后，会在各个接口发送 HELLO 分组。

邻居路由器收到后回复。

这样路由器就知道：

我旁边有哪些路由器。

在 LAN 里，通过广播 HELLO 也可以发现邻居。

第 2 步：测量到邻居的代价

路由器需要知道到邻居的链路代价。

可以通过：

发送探测分组

对方立即响应

计算往返时间 RTT

或者由管理员直接配置链路代价

比如测得从 A 到 B 延迟是 5ms，那么可以把代价设为 5。

其实也就是图建立的初始化，用邻接表弄一个图出来

第 3 步：组装链路状态分组 LSP

每个路由器会生成一个 LS 分组，里面描述：

我是谁，我的邻居是谁，到这些邻居的链路代价是多少。

LS 分组通常包括：

发送者名称

序号 Seq

年龄 Age

邻居列表

到邻居的代价

第 4 步：把 LS 分组扩散到所有路由器

这一步叫 flooding，泛洪。

每个路由器把自己的 LS 分组发给全网所有其他路由器。

最终每台路由器都能获得：

全网拓扑 + 所有链路代价。

为什么需要序号 Seq？

为了避免旧信息、重复信息一直传播。

每个路由器记录：

某个源路由器发来的最新序号是多少。

如果收到旧序号的 LSP，就丢弃。

如果收到新序号的 LSP，就转发。

为什么需要 Age？

因为有些路由器可能崩溃了，或者旧的 LSP 因为某些原因一直存在。

Age 字段会随时间减少。

当 Age 减到 0，这个 LSP 就被丢弃。

所以 Age 用来防止旧信息长期存在。

第 5 步：用 Dijkstra 算最短路径

当每个路由器都有全网拓扑后，就从自己作为源点，运行 Dijkstra 算法。

算出：

自己到所有其他节点的最短路径。

然后生成转发表。

十、Dijkstra 算法中的符号

(|)

表示节点 $x$ 到邻居 $y$ 的直接链路代价。

如果 $x$ 和 $y$ 不是直接邻居：

c(x|y)=\infty

𝑮𝑯()

表示从源点到节点 $v$ 的当前已知最短路径代价估计。

注意一开始只是估计，后面会逐步变成确定值。

()

表示当前最短路径上，节点 $v$ 的前驱节点。

也就是：从源点到 $v$ 的路径中， $v$ 前面那个节点是谁。

用 $p(v)$ 可以最后反推出整条路径。

{𝒂𝒃}^{'}

表示已经确定最短路径的节点集合。

也叫永久节点集合。

十一、Dijkstra 算法的步骤

假设源点是 $u$ 。

初始化

{N}^{'}={u}

也就是源点先确定。

对于每个节点 $v$ ：

如果 $v$ 是 $u$ 的邻居：

D(v)=c(u|v)p(v)=u

如果不是邻居：

D(v)=\infty

循环步骤

重复下面过程：

第一步：找最小临时节点

在所有不属于 ${N}^{'}$ 的节点中，找 $D(w)$ 最小的节点 $w$ 。

把它加入 ${N}^{'}$ 。

意思是：当前已知距离最小的临时节点，可以确定为最短路径。

第二步：用新节点更新它的邻居

对每个不在 ${N}^{'}$ 中、并且是 $w$ 的邻居的节点 $v$ ，更新：

D(v)=min(D|(v)D(w)+c(w|v))

如果通过 $w$ 更近，就更新：

p(v)=w

第三步：直到所有节点都加入 ${𝒂𝒃}^{'}$

最后得到从源点到所有节点的最短路径。

十二、Dijkstra 怎么生成转发表？

Dijkstra 算出来的是从源点到各个节点的最短路径。也就是先有表再走，每次都是选择一个路径最短的节点再摊开到相邻路径最短最后算出到各点的距离，也就是所谓贪心的算法

但是转发表需要的是：

去某个目的地，下一跳是谁。

所以要从最短路径中找：

从源点出发的第一个节点。

例如从 $u$ 到 $z$ 的最短路径是：

u\to x\to y\to z

那么在 $u$ 的转发表里：

目的｜下一跳 z ｜ x

虽然最终目的地是 z，但从 u 发出去的第一跳是 x。

十三、Dijkstra 的复杂度

普通实现下：

O({n}^{2})

因为每次都要在临时节点中找最小 $D(w)$ 。

如果用更高效的数据结构，比如堆，可以做到：

O(nlogn)

更准确地说，常见实现是：

O(ElogV)

普通 Dijkstra 是 $O({n}^{2})$ ，可优化到 $O(nlogn)$ 或更高效形式。

总结就是：

链路状态路由中，每个路由器先通过 LS 分组获得全网拓扑，然后以自己为源点运行 Dijkstra。Dijkstra 每次贪心选择当前距离最短的临时节点加入确定集合，再松弛它的邻居，最终得到到各目的节点的最短路径，并由此生成转发表。实现上通常可以用邻接表，配合优先队列效率更高。

十四、LS 的消息复杂度

链路状态算法需要把每个节点的链路状态分组扩散给全网。

如果有 $n$ 个节点，每个节点都要广播自己的 LS 信息。

所以消息复杂度大致是：

O({n}^{2})

核心记：LS 需要全网泛洪链路状态信息，消息开销较大。

十五、LS 可能出现路由振荡

Dijkstra 可能路由振荡。

如果链路代价和当前流量有关，比如：某条链路流量越大，代价越高。

那么路由器可能这样反复变化：

大家发现路径 A 代价低，于是都走 A。

A 上流量变大，代价升高。

大家又改走路径 B。

B 流量变大，代价升高。

大家又改回 A。

这就会导致：路由结果来回震荡。

所以实际网络中链路代价不能过于敏感地跟瞬时流量变化，否则不稳定。

第五章 第1节-第2节