# 网络层

# 概述

网络层的作用: 将分组从一台主机移动到另一台主机;

为了实现这个目的, 需要两种网络层功能:

转发: 在路由器上, 将从输入链路传入的分组, 移动到适当的输出链路上;
路游选择: 在整个网络范围中, 用『 路游选择算法 Routing Algorithm 』计算出, 分组从发送方到接收方所要走的最佳路径;

每台路由器都有一个『 转发表 forwarding table 』

发送到路由器的分组会有一个首部字段, 其用以指示该分组的输出链路;
路由器将该首部字段的值, 作为索引在转发表中查询到对应的输出链路. 之后路由器就可以正确地转发该分组了;

转发表中的值由『 路由选择算法 』计算得出. 这张表揭示了『 路由选择 』和『转发』之间的关系.

『 分组交换机 』是对分组交换设备的通用称呼, 其根据某个首部字段的值, 对分组进行转发:

链路层交换机 link-layer switch: 基于 "链路层" 的首部字段的值做转发决定;
路由器 router: 基于 "网络层" 的首部字段的值做转发决定;

2020-06-11-12-50-18

在『 因特网 』网络体系结构中, 网络层提供给上层一种『 尽力而为服务 best-effort service 』

对于因特网而言, 这基本上就等于没有服务, 网络层基本上不提供给运输层任何服务;
但是除了因特网结构, 还有其他网络结构, 例如下图 👇 中的 ATM 结构. 在 ATM 结构中, 网络层提供服务;

2020-06-11-14-08-08

尽力而为服务的『好处』是:

网络层不提供可靠的传输服务, 使得网络核心实现简单, 造价低廉;
运行方式灵活, 可以适应多种应用. 主机端根据需求, 自己负责需要的连接服务 ( 运输层, 应用层 )

# 路由器工作原理

在计算机网络的语境中, 经常互换『转发』和『交换』这两个词.

# 路由器组成部分

2020-06-11-14-13-15

上图中将路由器分成了 4 个组成部分:

输入端口;
交换结构;
输出端口;
路由选择处理器;

# 输入端口

输入端口主要执行三个功能:

物理层功能: 将一条物理输入链路与路由器相连;
链路层功能: 对远端传来的链路层数据进行处理;
查找转发功能: 通过搜算转发表, 用输入分组的首部字段找到对应的『输出端口』. 然后把该分组发送进入『交换结构』;
- 转发表是由『路由选择处理器』计算和更新的;
- 『路由选择处理器』通过一条『独立总线』将『转发表』复制给『输入端口』
- 输入端口保存了一份『转发表副本』, 这样转发决策就可以在输入端口本地做出了;

2020-06-11-15-13-24

# 交换结构

交换结构位于路由器的核心部位, 通过它就可以将分组实际地从输入端口『交换 / 转发』到输出端口;

2020-06-11-15-23-24

交换实现的方式有很多种, 下面介绍三种:

经内存交换:
- 最早的路由器就是传统的计算机, 交换的操作是在 CPU 的控制下完成的. 一个分组到达输入端口后, 会通过 interrupt 中断的方式向 CPU 发出信号. CUP 之后会把该分组复制到内存中, 然后 CPU 通过分组的首部查找对应的输出端口, 最后把分组再写入输出端口所用的内存中;
- 现代使用内存交换的路由器, 把『输出端口的查找』和『将分组储存进对应的内存位置』交给『输入端口』处理.
经总线交换:
- 输入端口通过一条『共享的总线』直接将分组传输给输出端口;
- 单一总线每次只能传输一个分组, 如果同时多个分组到达路由器, 其他的就要等待. 所以路由器的交换带宽受限于总线传输速率;
经互联网络交换:
- 通过使用更复杂的互联网络, 可以克服单一总线带来的带宽限制;
- 采用互联网络的路由器可以同时转发多个分组;

# 输出端口

输出端口取出存放在『输出端口内存』中的『分组』, 并将其发送到『输出链路』上;

同输入端口一样, 输出端口也实现了『物理层』和『链路层』的功能;

2020-06-11-15-44-53

# 路由选择处理器

路由选择处理器, 执行『 路由选择协议 』维护『 路由选择表 』以及连接的『 链路状态信息 』, 并且为路由器计算『 转发表 』除此之外, 它还执行网络管理功能.

这些内容的具体细节在后面讲.

# 网际协议: 因特网中的转发和编制

网络层中有三个重要组件:

IP 协议: 定义了编址与转发的规则;
路由选择协议: 计算出分组传输的路径;
ICMP 协议: 报告数据报中的差错, 和对某些网络层信息请求进行相应;

2020-06-11-16-05-41

这一章, 我们讲『 IP 协议 』也称为『 网际协议 Internet Protocol 』

版本上可以分为 IPv4 和 IPv6 这两种;
下面的内容先默认采用 IPv4, 在章节最后会讲解 IPv6;

IP 协议是网络层主要协议，它对数据提供『尽力而为 Best-Effort Service 』的服务. 主要功能包括：

分组的分段和重组;
无连接数据报传输;
数据报路由;

# 数据报格式

2020-06-11-16-22-07

IPv4 数据报中的关键字段如下:

版本: 表示数据报的 IP 协议版本 ( E.g. IPv4 / IPv6 )
首部长度: 数据报中可以包含一些可变数量的选项, 所以首部长度是不固定的, 通过它可以确定『有效载荷』从哪里开始;
服务类型: 根据需求不同, 数据报也可以分成很多种类型 ( E.g. 实时数据报, 非实时数据报, etc. )
数据报长度: 数据报的总长度;
标识, 标志, 片偏移: 与 IP 分片相关的字段, 用以组装数据报;
寿命: 表示数据报生存时间;
协议: 表示该数据报, 在接收端应该被交给哪个『运输层协议』;
首部校验和: 用以检验 IP 数据报中的比特错误;
源 & 目的 IP 地址: 表示源主机和目的主机的 IP 地址;
选项: 一些可选设置;
数据: 有效载荷, 大多数情况下是运输层的报文段, 但也可以承载其他类型数据, 如 ICMP 报文;

# IP 数据报分片

链路层协议能够承载的『帧的长度』是有限制的, 一个链路层帧能够承载的最大数据量叫『 最大传送单元 Maximum Transmission Unit, MTU 』

为了让链路层能传输大数量的数据报, 路由器会将数据报『切分』成较小的数据报. 然后再一个个地封装进『帧』中. 被切分出的较小数据报被称为『切片』

切片在到达目的端运输层之前需要进行组装, IPv4 设计者为了让『网络核心』尽量保持简单, 把切片组装的工作放在了『端系统』中, 而不是路由器.

IPv4 数据报中的首部字段『 标识, 标志, 片偏移 』用于让接收方网络层组装数据报:

标识:
- 在发送端生产数据报时, 会为其加上『标识号』
- 当某路由器需要对数据报分片时, 每一个切片都具有与『初始数据报』相同的『标识号』
- 接收方网络层, 通过『标识号』来判断哪些数据报是一个较大数据报的『切片』.
标志:
- 通过将切片的『标志』设置为 0 来表示这是被切分的数据报的最后一片;
- 其他的切片的『标志』设置为 1
片偏移:
- 通过『偏移量』来表示当前切片在初始数据报中的位置;
- 接收方通过它可以有序地组装切片, 同时还可以判断是否有切片丢失;

🌰 下面是一个例子, 将一个 4000 字节的数据报在路由器上被切分成 3 个独立的切片:

初始数据报的『标识』是 777;

2020-06-11-16-40-31

# IPv4 编址

主机与物理链路之间的边界叫做『接口 interface 』
路由器与多条物理链路相连. 因此 路由器有多个接口;

IP 协议要求每台主机和路由器的接口, 都要拥有自己的『 IP 地址 』

一个 IP 地址是与一个接口相关联的, 而不是与主机或路由器;

每个 IPv4 地址:

长度为 32 比特, 由 4 个字节组成, 字节间由 . 分隔开;
共有 $2^{32}$ 约 40 亿个可能的 IP 地址;
IP 地址按照『 点分十进制记法 dotted-decimal notation 』书写, 也就是每个字节都用它的十进制形式书写:
- E.g. 193.23.216.9
- 上面地址的二进制格式为: 11000001 00100000 11011000 00001001

# 分类编址 & 无类别域间路由选择

因特网中的每台主机和路由器上的接口都有唯一的 IP 地址, 这些地址不是随意分配的.

在之前, IP 协议中采用『 分类编制 classful addressing 』的编址方案:

IP 地址由两个部分组成:

网络号: 用于识别主机所在的网络;
主机号: 用于识别该网络中的主机;

根据 网路号的长度, 将 IP 地址分成如下几类:

A 类地址:
- 网络号长度为 8 比特, 固定以 0 开头 ( 类别位 ) ;
- 地址范围：1.0.0.1 — 126.155.255.254
- 保留给政府机构;
B 类地址:
- 网络号长度为 16 比特, 固定以 10 开头;
- 地址范围：128.0.0.1 — 191.255.255.254
- 分配给中等规模的公司;
C 类地址:
- 网络号长度为 24 比特, 固定以 110 开头;
- 地址范围：192.0.0.1 — 223.255.255.254
- 分配给任何需要的人;
D 类地址:
- 不区分网络地址和主机地址;
- 称为广播地址, 用于多点广播 Multicast;
- 第 1 个字节前四位固定为 1110;
- D 类地址范围：224.0.0.1 — 239.255.255.254
E 类地址:
- 不区分网络地址和主机地址;
- 为将来使用保留. 主要用于 Internet 试验和开发;
- 第 1 个字节前四位固定为 1111;

2020-06-12-10-07-21

IP 地址还有如下规定:

主机号字节全为 1 的 IP 地址用于当前网络的『 广播地址 』给这个地址发数据, 所属网络中所有的主机都能收到;
主机号字节全为 0 的 IP 地址表示『 当前网络本身 』这个地址是不可以分配给主机;
0.0.0.0 地址被用于表示一个无效的，未知的或者不可用的目标 ( 后面讲 ) ;
A 类地址中:
- 127.0.0.0 - 127.255.255.255 是保留地址, 用以『 环回测试 Loopback Test 』使用, 也就是主机发送通信给自身时使用的地址;
  - 这些地址不会出现在网络中;
  - 127.0.0.1 代表当前主机;
  - 当主机向环回地址发送分组时, 分组不会被入网络层之下, 经过运输层, 网络层后就又被传回来了;
- 10.X.X.X 是私有地址, 即不能应用在互联网上，而被用在局域网络中的地址;
  - 一般在中大型公司的内网中会使用 10.X.X.X 作为 IP 地址;
B 类地址中:
- 172.16.0.0 - 172.31.255.255 是私有地址;
- 169.254.X.X 是保留地址 ( 这里不讲 )
C 类地址中:
- 192.168.X.X 是私有地址;
  - 作为小型局域网使用的 IP 地址;

抛去上面 👆 提到的这些『私有地址』和『保存地址』, 每个分类中可以支持的『 最大网络数 』和『 最大主机数 』如下:

2020-06-12-11-12-44

『 分类编址 』有一个很大的缺陷就是, 网络号与主机号划分的粒度太大, 导致地址空间的利用率太低

🌰 一个 C 类子网所能容纳的最大主机数为 254 个, 这对于很多企业来说太小了, 但是对于家庭来说又太大了;
🌰 一个 B 类子网能容纳的最大主机数为 65,534 个, 对于中小型企业来说又太多了;

为了解决这个问题, 就又引入了『子网 subnet 』的概念:

将原先的『主机号』从左向右划分出来一部分作为『 子网号 』
- 划分后, IP 地址就从『两级结构』变成了『 三级结构 』
- 子网的网络地址格式采用『 斜线记法 slash notation 』例如, 223.1.1.0/24, 其中 /24 表示『网络号 + 子网号』所占的位数;
但是发送端发送分组时, 并不知道『目的主机』所属的网络是否进行了子网划分:
- 目的主机的『 IP 地址』和发送的『数据报首部』, 都不包含任何和『子网划分』相关的信息;

为了正确找到目的主机所属的网络, 引入了『 子网掩码 network mask 』的概念:

子网掩码是一个 32 位的二进制码, 需要与目标 IP 地址组合起来使用. 可以用来辨别『目的 IP 地址』所属的『网络地址』
一个子网的『网络号 + 子网号』与子网掩码对应的位, 都设置为 1, 剩下的位的值设置为 0
- 也就是 1 的位数等于『斜线记法』格式的网络地址 / 后面的数字;
当属于这个子网的目标 IP 地址, 与子网的子网掩码进行『和 AND 』运算, 的出来的结果就是『目的主机所属的网络地址』

2020-06-12-14-53-48

对于没有划分子网的分类网络, 也都有自己的默认子网掩码:

A 类地址默认子网掩码: 255.0.0.0
B 类地址默认子网掩码: 255.255.0.0
C 类地址默认子网掩码: 255.255.255.0

在使用了子网划分后, 路由器中的『 路由表 』:

包含以下三个内容:
- 目的网络地址;
- 子网掩码;
- 下一跳地址;
缺点: 因特网主干路由器上的路由表中项目数急剧增长;

一个更好的分址策略是『 无分类域间路由选择 Classless Interdomain Routing, CIDR 』

CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念;
地址格式采用『 斜线记法 slash notation 』 a.b.c.d/x, x 表示地址中网络部分的位数;
分类编址概念中的『网络号』和『子网号』组合在一起, 在 CIDR 中被称为『 网络前缀 network-prefix 』
- 采用 CIDR 后, IP 地址又从『三级结构』变成了『 二级结构 』但是是无分类的;
- IP 地址由『网络前缀』和『主机号』这两个部分组成;
CIDR 把网络前缀都相同的连续的 IP 地址组成一个『 CIDR 地址块 』
- 只要知道 CIDR 地址块中任何一个地址，就可以知道这个地址块的『起始地址（最小地址）』和『结束地址 ( 最大地址 ) 』以及地址块中的『地址数』
- 🌰 128.14.35.7/20 代表其中的前 20 位是网络前缀，而前缀后面的 12 位是主机号:
  - 起始地址: 10000000 00001110 00100000 00000000
  - 结束地址: 10000000 00001110 00101111 11111111
  - 地址数: $2^{(32 - 20)} = 4096$

一个 CIDR 地址块中包含多个网络地址, 所以在路由表中就利用 CIDR 地址块来查找目的网络:

这被称为『 路由聚合 route aggregation 』或者『 路由摘要 route summarization 』
它使得路由表中的一个项目可以表示原来传统分类地址的很多个路由。路由聚合也称为『 构成超网 』这有利于减少路由表的长度;
路由表中项目, 改成由『网络前缀』和『下一跳地址』组成:
- 路由器接收到『数据报』后, 将首部中的『目标主机 IP 地址』与路由表中的『网络前缀』做匹配, 然后选择匹配成功的路由;

2020-06-12-15-43-11

🌰 上图示例中:

Fly-By-Night-ISP 只需要向外界通告, 它接收所有目标地址前 20 位于 200.23.16.0 的前 20 为相匹配的数据报;
外部也不需要知道在数据块 200.23.16.0/20 内部还有其他 8 个子网, 外部只要一股脑地把所有匹配的数据报都传过来就行;

# DHCP 动态主机配置协议

一个组织获得一个『网段』后, 就可以给组织内的主机和路由器的『接口』逐个地分配『 IP 地址』了;

地址地分配可以让网络管理员手动设置;
但更多地是使用『 动态主机配置协议 Dynamic Host Configuration, DHCP 』来完成;
- DHCP 可以自动给连入网络的接口分配 IP 地址. 网络管理员也可以通过设置 DHCP 让指定地某些接口每次都被分配到相同 IP 地址.
- DHCP 又被称为『 即插即用协议 plug-and-play protocol 』因为它让一个主机自动地连接进一个网络;
- DHCP 协议广泛应用于会有主机频繁加入 / 离开的网络. E.g. 学校, 公司的无线局域网, 家庭网络, etc.

DHCP 是一个『 客户-服务器协议 』

需要提供一个『 DHCP 服务器』, 或『 DHCP 中继代理』它知道 DHCP 服务器的地址;
『新来的主机』需要向『 DHCP 服务器』请求自己的『 IP 地址』;

2020-06-12-16-08-19

🌰 上图 👆 中『 DHCP 服务器』连接在子网 223.1.2/24 上, 一台具备『 DHCP 中继代理』服务的路由器, 为连接在子网 223.1.1/24 和 223.1.3/24 的主机提供 DHCP 服务;

获取 IP 地址的四步骤:

对于一台新到来的主机, 想要请求 DHCP 服务器获取 IP 地址需要经历 4 步:

DHCP 服务器发现:
- 新到的主机刚开始并不知道 DHCP 服务器的 IP 地址;
- 这时, DHCP 客户生成包含『 DHCP 发现报文 』的数据报;
- 使用『广播目的地址』255.255.255.255 并使用 0.0.0.0 作为『源地址』
- 然后将数据报传递给链路层, 链路层会将这个分组广播给所有连入该子网的主机;
DHCP 服务器提供:
- DHCP 服务器收到 DHCP 发现报文后, 用一个『 DHCP 提供报文 』向客户做出响应. 仍旧使用『广播目的地址』255.255.255.255;
- DHCP 提供报文中包含『收到的发现报文的事务 ID 』『向客户推荐的 IP 地址』『网络掩码』『 IP 地址租用期』
DHCP 请求:
- 可能在子网中有多个 DHCP 服务器, 新来的主机可能同时收到多个 DHCP 提供报文;
- 客户需要在这些响应回来的 DHCP 提供报文中选择一个, 并向选中的 DHCP 服务器发送一个『 DHCP 请求报文 』以作为响应;
DHCP ACK:
- DHCP 服务器用『 DHCP ACK 报文 』作为对客户的响应;
- 客户接收到后, 就可以在租用期内使用分配的 IP 地址了;

2020-06-12-16-10-38

# 网络地址转换

因为 IP 地址的数量是有限了, 随着因特网中主机数量的增多, 很难让每台主机都有一个全球唯一的 IP 地址. 所以需要将 IP 地址分为:

全局 IP 地址: 必须是全球唯一的;
私有 IP 地址: 只要在同一个域里保持唯一便可，在不同域里可以重复;

下图 👇 是私有 IP 地址的可选范围:

2020-06-12-17-05-30

但是『私有 IP 地址』只能在同一网络中作为唯一标识, 当主机要发送 / 接收分组到外部的『全球因特网』中时, 『私 IP 有地址』就不可以用作『源地址』, 或『目的地址』了

需要使用『 网络地址转换 Network Address Translator, NAT 』服务, 它是用以在『私有 IP 地址』和『全局 IP 地址』之间进行转换;

2020-06-12-17-12-06

NAT 运行在路由器上, 在 NAT 路由器内部有一张自动生成的用于地址转换的『 NAT 转换表 』当有数据报经过路由器转发时, 路由器会根据『转换表』修改『目的地址』或者『源地址』

2020-06-12-17-16-06

🌰 例子：

2020-07-18-23-09-11

2020-07-18-23-09-25

# 因特网控制报文协议

『 因特网控制报文协议 ICMP 』用来在主机和路由器间来彼此沟通网络层的信息. 最常见的用途是『 差错报告 』

🌰 假如路由器不能为某个分组找到转发的路径, 该路由器就会向源主机发送一个 ICMP 报文以示错误;

从网络层次上来讲:

ICMP 协议位于 IP 协议之上;
ICMP 报文是作为 IP 数据报的有效载荷承载的;
接收方会将 ICMP 报文从 IP 数据报中分解出来, 然后传递给 ICMP 协议层处理. 只不过我们把 ICMP 协议层也算在网络层之中;

ICMP 报文格式

报文首部有『类型字段』和『代码字段』, 通过不同值的组合, 表示不同的报文类型;
为了能确认引发差错的数据报, ICMP 报文数据部分包含, 引发这次 IMCP 报文生成的 IP 数据报的首部, 和有效载荷的前 8 个字节内容;

2020-06-12-21-46-51

下图 👇 是一些常见的『 ICMP 消息类型』, 及对应的类型值和代码值:

2020-06-12-21-41-20

2020-06-12-21-49-31

# IPv6

因为 IPv4 的 32 比特长度的 IP 地址不够用, 所以为了应对更大的 IP 地址空间需求, 就开发出了 IPv6 协议. 同时 IPv6 的设计者也顺便改进强化了 IPv4 的很多方面.

# IPv6 的地址表示

IPv4 的地址长度为 32 位, 而 IPv6 的地址长度为 128 位. 这个地址长度甚至可以给地球上每一粒沙子都赋予唯一的 IP 地址;

128 位比特被分为 8 组, 每组 16 个比特, 用 16 进制表示. 每组之间用 : 冒号隔开

2001:3CA1:010F:001A:121B:0000:0000:0010

IPv6 地址中可能会出现很多 0, 为了书写简便, 有如下的简写规则:

忽略前导 0
忽略全 0:
- 前后两个 : 合并为 ::
- 但是注意一个地址最多只能有一个双冒号;

2020-06-13-11-23-59

# IPv6 数据报格式

2020-06-12-22-01-48

版本: 标识 IP 版本号;
流量类型: 和 IPv4 中服务类型相似, 用以指出一个流中某些数据报的优先级;
流标签: 用于标识一条数据报的流;
有效载荷长度: 作为一个无符号整数, 表示数据报有效载荷的长度;
下一个首部: 标识数据报中的内容（有效载荷）需要交付给哪个协议 ( E.g. TCP / UDP ) 该字段使用与 IPv4 首部中协议字段相同的值;
跳限制: 转发数据报的每台路由器将对该字段的内容减 1，如果跳限制计数到达 0 时，则该数据报将被丢弃;
源地址 & 目的地址
数据: 有效载荷部分;
分片 / 重新组装: IPv6 不允许数据报在中间路由器上被 "分片 / 重组". "分片 / 重组" 操作只能在 "源 / 目的地主机" 上执行:
- 如果路由器接收到的 IPv6 数据报太大, 则只能丢弃;
- 并且向发送方发送一个『分组太大』ICMP 差错报文;
- 发送方收到 ICMP 报文后, 将数据报拆分成更小的数据报重新发送;
首部校验和
选项

下图 👇 展示了 IPv4 和 IPv6 数据报的首部字段的对比:

2020-06-12-22-09-06

# 路由选择算法

主机通常直接与一台路由器相连接, 该路由器即为该主机的『 默认路由器 』, 又称『 第一跳路由器 』

将源主机的默认路由器称作『 源路由器 』
把目的主机的默认路由器称作『 目的路由器 』

可以用『图 graph 』来形式化描述路由选择问题.

$G = ( N , E )$ 表示一个 $N$ 个结点和 $E$ 条边的集合. 其中每条边是取自 $N$ 的一对结点。

在网络层路由选择的环境中，图中的 "结点" 表示 "路由器"
连接这些结点的 "边" 表示这些路由器之间的 "物理链路"

2020-07-18-23-59-37

上图 👆 中, 一条边还有一个值表示它的 "费用". 通常, 费用表示链路的物理长度, 传输速度, 金融上的搭建费用.

对于 E 中的任一条边 $(x, y)$ 我们用 $c(x, y)$ 表示结点 x 和 y 的边的费用;
如果两个节点不相邻, 之间没有边存在, 则 $c(x, y) = \infin$
$(x, y)$ 属于 $E$ , 结点 y 也被称为结点 x 的『邻居 neighbor 』

在图中为各条边指派了费用后，路由选择算法 "目标" 就是, 找出从源到目的地间的 "最低费用路径"

如果有多条路径费用相同, 则最低费用路径也就是『 最短路径 sbortest path 』，即在源和目的地之间的具有最少链路数量的路径.

根据算法是 "全局式" 还是 "分散式" 可以分类为:

全局式路由选择算法 global routing algorithm:
- 以所有结点之间的连通性及所有链路的费用为输入, 计算出最低费用路径;
- 具有全局状态信息的算法常被称作『 链路状态算法 Link Slate, LS 』
分散式路由选择算法 decentralized routing algorithm:
- 以迭代、分布式的方式计算出最低费用路径. 没有结点拥有关于所有网络链路费用的完整信息，每个结点仅能获得与其直接相连 "链路 / 节点" 的信息;
- 『 距离向量算法 Distance-Vector, DV 』采用的是分散式路由选择算法;

根据算法是 "动态" 还是 "静态" 可以分类为:

静态路由选择算法:
- 路由的变化通常是人工干预进行调整. 例如, 人为手工编辑一台路由器的转发表.
动态路由选择算法:
- 能够当网络流量负载或拓扑发生变化时改变路由选择路径;

根据算法是 "负载敏感的" 还是 "负载迟钝的" 进行划分:

负载敏感算法 load-sensitive algorithm:
- 链路费用会动态地变化以反映出底层链路的当前拥塞水平;
负载迟钝算法 load-insensitive algorithm:
- 某条链路的费用不明显地反映其拥塞水平;
- RIP, OSPF, BGP 算法都是负载迟钝的;

# 链路状态路由选择算法

在『 链路状态算法 Link Slate, LS 』中，网络拓扑和所有的链路费用都是已知的. 实践中, 通过让每个结点向网络中所有其他结点广播链路状态分组来完成.

每个 "链路状态分组" 包含当前节点所连接的链路的特征和费用;
结点广播的结果是所有结点具有了该网络的等同的、完整的视图;
每个结点都能够像其他结点一样，运行 LS 算法并计算出相同的最低费用路径;

『 Dijkstra 算法 』( "迪杰斯特拉" 算法 ) 是一种链路状态算法:

该算法计算从某结点 ( 源结点，称之为 $u$ ) 到网络中所有其他结点的最低费用路径;
其是一个迭代算法;
$D(v)$ : 到算法的本次迭代，从源结点到目的结点 $v$ 的最低费用;
$p(v)$ : 在从源到 $v$ 的最低费用路径中, $v$ 的前一个节点;
$N'$ : 从源到 $v$ 的最低费用路径已确知时, 所有节点构成的集合;

2020-07-18-23-57-26

2020-07-18-23-59-37

考虑这个例子, 计算出从 $u$ 到所有可能目的地的的最低费用路径. 下图 👇 展示了每一次迭代结束时该算法的各个变量的值:

2020-07-19-00-01-47

在初始化步骤，从 $u$ 到与其直接相连的邻居 $v$ , $x$ , $w$ 的当前已知最低费用路径分别初始化为 2, 1 和 5
在第一次迭代中，我们观察那些还未加到集合 $N'$ 中的结点，并且找出在前一次迭代结束时具有最低费用的结点. 那个结点便是 $x$ ，其费用是 1, 将其加入到集合 $N'$ 中. 然后执行上面算法中第 12 行代码;
之后继续迭代;

当 LS 算法终止时，对于每个结点，我们都得到从源结点沿着它的最低费用路径的前一结点, 对于每个前一结点，我们又有它的前一结点，以此方式我们可以构建从源结点到所有目的结点的完整路径.

# 距离向量路由选择算法

『 距离向量算法 Distance-Vector, DV 』是一种迭代的、异步的和分布式的算法.

用 $d_x(y)$ 表示从结点 $x$ 至结点 $y$ 的最低费用路径的费用. 则可以有『 Belloman-Ford 方程 』:

d_x(y) = min_v \{ c(x,v) + d_v(y) \}

$min_v$ 表示遍历 $x$ 的所有邻居;
从 $x$ 到 $y$ 的最低费用是对所有邻居 $v$ 的 $c( x, v) + d_v(y)$ 的最小值;

在『距离向量算法』中:

$D_x(y)$ , 表示对集合 $N$ 中是所有结点, 估计从 $x$ 到 $y$ 的最低费用路径的费用;
$D_x = [D_x(y) : y ∈ N]$ , $D_x$ 被称为结点 $x$ 的『 距离向量 』其保存了从 $x$ 到在 $N$ 中的所有其他结点 $y$ 估计的最低费用;

每个结点 $x$ 维护了下列信息:

从 $x$ 到每个邻居 $v$ 的费用, 即 $c(x, v)$
结点 $x$ 的距离向量, 即 $D_x = [D_x(y) : y ∈ N]$ , $N$ 集合包含了图中所有的结点;
每个邻居 $v$ 的距离向量, 即 $D_v = [D_v(y) : y ∈ N]$

DV 算法应用了 Belloman-Ford 方程, 其基本思想如下:

初始化时, 每个结点计算它自己的距离向量;
然后每个结点再向它的所有邻居发送其距离向量;
在接收到邻居节点的距离向量后, 每个结点再重新计算它的距离向量, 然后再发送给邻居;
如此反复;

2020-07-19-00-23-35

2020-07-19-10-08-16

# 层次路由选择

随着时间的推移，因特网的规模越来越大，几百万几千万的路由器互联在一起. 如果让每个路由器都知道如何到达其他路由器, 那么路由表将非常大. 耗费时间, 耗费流量;

而且有些网络不想让外部知道自己的布局细节, 和使用的具体路由选择协议.

基于上述两个原因，因特网将整个互联网划分为许多较小的『 自治系统 Autonomous System, AS 』

如果两个自治系统需要通信，它们可能各自采用不同的路由选择协议, 所有需要一种在两个自治系统之间的协议:

一个自治系统内部所使用的路由选择协议称为『 内部网关协议 interior gateway protocal, IGP 』
- 自治系统内部的路由选择称为『 域内路由选择 』
自治系统之间使用的路由选择协议称为『 外部网关协议 exterior gateway protocal, EGP 』
- 自治系统之间的路由选择称为『 域间路由选择 』

2020-07-19-10-31-14

网关 ?

网关可以让两个使用不同协议的网络互联, 是一种充当 "转换" 功能的计算机系统或设备。

在讨论自治系统通信时, 可以理解为 "路由器" 的同义词.

# 因特网中的路由选择

在因特网中, 通过『 路由选择协议 』来确定数据报在源与目的地之间采用的路径.

# 自治系统内部的路由选择: RIP

『 路由选择信息协议 Routing Information Protocol, RIP 』是一种『 内部网关协议 』使用『 距离向量算法 』