旨在理解网络层服务原理和熟悉因特网的网络层协议。

综述

通过学习这一章节，我们需要了解以下两方面内容：

理解网络层服务原理：

网络层服务模型
网络层上的重要功能：转发和选路
路由器工作原理
选路算法

因特网的网络层协议：

IP 协议
ICMP 协议
选路协议：RIP,OSPF,BGP

概念简介

网络层的作用：将报文段从发送主机传送到接收主机。

每一台主机和路由器都运行网络层协议。

路由器：将分组从输入链路转发到输出链路。它运行的协议包括，网络层，链路层，物理层。

发送主机：将传输层报文段封装到网络层分组中，发送给边缘路由器。

接收主机：从边缘路由器接收分组，取出报文段交付给传输层。

网络层的主要功能：

选路：确定分组从源路由器到目的路由器的路径 – 利用各种路由算法来计算转发表。

转发：将分组从输入端口转移到合适的输出端口 – 根据转发表转运分组。
在传输分组之前，两个端系统需要建立连接。
- 传输层连接：进程-进程，连接状态仅仅保存在端系统中，传输层服务在网络边缘实现
- 网络层连接：主机-主机，连接状态保存在源主机，目的主机以及所有中间路由器上（路由器要保存转发表的嘛），网络层服务在网络核心实现。
网络服务模型

定义分组在发送主机与接收主机之间传输时的特性。
- 对单个分组提供的服务
  
  保证交付；具有时延上界的保证交付；
- 对分组流提供的服务
  
  有序交付；保证最小带宽；
  保证最大时延抖动（分组端到端时延的最大差异）；
  
  不同架构的网络提供的网络层服务可能不同，同一个网络也可以提供不同的网络层服务。

虚电路和数据报网络

两种基本的网络类型：

数据报网络：提供网络层无连接服务

虚电路网络：提供网络层面向连接服务

虚电路 Virtual circuits

网络层连接成为虚电路。

虚电路是从源主机到目的主机的一条路径，类似电话电路，每条虚电路有唯一标识（虚电路号），每个分组应该携带虚电路号，表明所属的虚电路。

传输分组前建立虚电路，传输结束后拆除虚电路;

每个路由器为经过它的虚电路维护状态（转发表项 - 进入端口，进入VC号，输出端口，输出VC号），分组携带 VC 号，每一次转发前用新的 VC 号替换分组中的 VC 号 ;

链路及路由器资源（带宽、缓存等）可以分配给虚电路，从而虚电路能提供可预期的网络服务。

**信令协议：**用于 VC 的建立、维护与拆除。

数据报网络

分组携带目的主机地址，路由器按目的地址转发分组；
路由器根据分组的目的地址转发分组，转发表记录目的地址到输出链路的映射；

实际上是存储目的地址的范围到链路的映射；

匹配规则：最长前缀匹配优先；
转发表被选路模块修改，约1～5分钟更新一次；
同一对主机之间传输的分组可能走不同的路径，从而可能重排序；

数据报网络 VS 虚电路网络

数据报网络：

计算机之间交换数据：没有严格的时序要求；
终端具有智能：将复杂的工作（如差错控制）推到网络边缘，以保持网络简单。

虚电路网络：

由电信网发展而来：严格时序和可靠性要求；
终端无智能或很少智能：复杂工作由网络完成，以保持终端简单。

Internet 网络层协议

internet 网络层

IPv4 数据报格式

IP 数据报分片

最大传输单元 MTU

MTU：链路层数据帧可封装数据的上限； $MTU = MAX(data)$

不同链路的 MTU 不同

分组与重组

大 IP 向比较小的 MTU 链路转发时，可以被分片（fragmented）。

大 IP 分片成若干小 IP
IP 分片在到达 目的主机 后重组（路由器只管分不管组装）

IP 首部相关字段用于标识分片以及确定分片的顺序（便于在目的主机重组 IP 分组）

涉及到的字段：总长度、标识、标志和片偏移字段。

标识：每个分片必须携带与原始数据报相同的标识。
标志位：
- MF（more fragments）：最后一个分片的MF=0，其余分片的 MF=1
- DF（don’t fragment）：DF=1 表示不允许对数据报分片
片偏移量（13bits）：指示分片中的数据在原始数据报载荷中的位置（以 8 字节为单位）

分片的处理过程

根据报头长度 H 和输出线路的 MTU 为 M，原 IP 分组的总长度为 L 。

一个最大分片可封装的数据为： $d = \lfloor \frac{M-20}{8} \rfloor * 8 ~ Bytes$

需要的总片数为： $n = \lceil \frac{L-20}{d} \rceil$

将数据报的载荷划分成长度为 d 的若干片段（最后一个分片可能不足 d 字节）。
将原始报头加到每一个分片的前面，修改报头中的以下字段：

$\text{总长度} = d + 20, ~(1 <= i < n)$ ; $ or = L-(n-1)d, ~(i = n)$

最后一个报头的 MF 位置 0，其余报头的 MF 位置 1

偏移量： $F_i = \frac{d}{8} * (i-1), ~~~ 1\le i \le n$
计算头部检查和

IP 编址

接口： 主机 or 路由器与物理链路的边界。

**IP 地址：**32bit 标识主机、路由器的接口。一般采用点分十进制标识（8位一组，转成十进制），例如：127.0.0.1

如何为接口分配 IP 地址？

IP 地址分为两部分，高位比特为网络号，低位比特为主机号。
IP 子网： IP 地址具有相同的网络号，不跨越路由器，可以彼此物理联通的接口。

有类编址

A,B,C 类 IP 地址可以用来给主机或路由器分配网络接口，但也有一些特殊情况。

子网划分

IP 地址：

网络号 NetID - 高位比特
子网号 SubID - 原网络主机号部分比特
主机号 HostID - 低位比特

如何确定是否划分了子网？利用多少位划分子网？

子网掩码：形如 IP 地址。取值：NetID、SubID 全部取 1， HostID 全部取 0

例如：

A 网默认子网掩码：255.0.0.0

B 网默认子网掩码：255.255.0.0

C 网默认子网掩码：255.255.255.0

借用 3 比特划分子网的 B 网的子网掩码：255.255.224.0
对特定主机来说，前 32 位都看成网络号，即其子网掩码为 255.255.255.255
子网地址 + 子网掩码 = 准确确定子网大小
例：将子网 201.2.3.0, 255.255.255.0 划分为等长的 4 个子网。

分析：

C 网，主机号范围只有最后 8 位（一共可以有 256 个不同的主机号）

$256 / 4 = 64$ ，所以将最后 8 位的前两位借为子网号，划分的四个子网如下：
1. 201.2.3.0 子网号(00) 255.255.255.192
  
  该子网的 IP 地址范围为 201.2.3.0 ~ 201.2.3.63
  
  去掉子网 IP 地址(0)和该子网的广播地址(63)，可分配的 IP 地址为：201.2.3.1 ~ 201.2.3.62
2. 201.2.3.64 子网号(01) 255.255.255.192
3. 201.2.3.128 子网号(10) 255.255.255.192
4. 201.2.3.192 子网号(11) 255.255.255.192

一个栗子

其中 0.0.0.0 是一个特殊 IP ，表示所有待选 IP 都没有匹配到，这个特殊 IP 没有网络号。

无类域间路由 CIDR

CIDR (Classless InterDomain Routing)：

消除传统的 A、B、C 类地址界限： $NetID + SubID->Network~Prefix$
融合子网地址与子网掩码，方便子网划分：a.b.c.d/x 其中 x 为前缀长度

例如：200.23.16.0/23

C 类地址前 24 位都是网络号，但这里的 CIDR 地址的前缀只有 23 位。

实际上它是两个 C 类地址的组合：200.23.16.0 和 200.23.17.0 (第24位分别为 0 和 1)
子网 201.2.2.3.64 255.255.255.192 -> 201.2.3.64/26

优点：

提高 IPv4 地址空间分配效率
提高路由效率
1. 将多个子网聚合为一个较大的子网
2. 构造超网（supernetting）
3. 路由聚合（route aggregation）

路由聚合

路由表中符合聚合条件的若干条路由可以合并成一条路由：

这些路由的前缀可以聚合成一个更短的前缀（称地址前缀）
这些路由使用相同的下一跳
路由聚合的过程可以递归进行

若个别路由不满足路由聚合的条件，可以给出一条聚合路由和若干条特定路由。

最长前缀匹配优先：在所有匹配的路由表项中，选择前缀最长的路由表项。（避免路由黑洞现象【数据到达不了目标地址】）

DHCP 协议

一个主机如何获得 IP 地址？

硬编码：静态配置（手动）

默认网关：数据报离开子网时，将要经过的路由器接口。数据报将通过这个路由器进一步转发到其他路径。
动态主机配置协议 DHCP：自动获取（租赁）IP 地址、子网掩码、默认网关地址、缺省路由器、本地 DNS 服务器等配置信息。

即插即用；

允许地址重用（IP 地址采用租赁的形式，当一个主机不用时，归还 IP ，这个 IP 就可以分给其他主机使用）；

可以续租；

DHCP 工作过程：

主机广播 “DHCP discover” 报文

寻找子网中的 DHCP 服务器
DHCP 服务器用 “DHCP offer” 报文进行广播响应

给出推荐的 IP 地址及租期、其它配置信息
主机用 “DHCP request” 报文广播请求 IP 地址

主机选择一个 DHCP 服务器，向其请求 IP 地址
DHCP 服务器用“DHCP ack” 报文发送IP地址

响应客户的请求，确认所要求的参数
DHCP 服务器使用 UDP 端口 67，客户使用 UDP 端口 68

DHCP 的实现：

在应用层实现
请求报文封装到 UDP 数据报中

封装：DHCP 应用层 -> UDP 传输层 -> IP 网络层-> Eth 链路层 -> Phy 物理层
IP 广播 -> 链路层广播（e.g. 以太网广播）

网络地址转换 NAT

动机：

IP地址支持许多用户同时上网
仅为公共可访问的节点分配公用IP地址（减少需要的公用IP地址数）
网络内部节点对外是不可见的（安全考虑）

NAT 实现：

外出的数据报: 将数据报中的（源IP地址，源端口号）替换为（NAT IP地址，新端口号）
NAT 转换表：记录每个（源IP地址，源端口号）与（NAT IP地址，新端口号）的转换关系
进入的数据报: 取出数据报中的（目的IP地址，目的端口号）查找NAT转换表，然后用转换表中对应的（IP地址，端口号）进行替换

16比特端口号:

允许一个 NAT IP 地址同时支持65535个对外连接

NAT的使用有争议:

路由器应当只处理三层以下的报头（端口号在传输层）
违反端到端原则（节点介入修改IP地址和端口号）

NAT 妨碍 P2P 应用程序：需要 NAT 穿越技术

方案一：静态配置 NAT ，将特定端口的连接请求转发给服务器。

方案二：利用 UPnP 互联网网关设备协议自动配置。可以学习 NAT 公共 IP 地址，并在 NAT 转换表中增删端口映射。

方案三：中继（如 Skype）NAT 内部客户- 中继 - NAT 外部客户；中继服务器桥接两个连接的分组。
地址短缺问题应该由 IPv6 解决

互联网控制报文协议 ICMP

ICMP 协议支持主机或路由器：差错或异常报告；网络探询；

两类 ICMP 报文：

差错报告报文
1. 目的不可达
  
  路由器无法为一个数据报找到路由或主机无法交付一个数据报，然后丢弃数据报
2. 源抑制
  
  拥塞控制的一种方法：警告源节点，在路径中的某处出现了拥塞，源节点必须放慢(抑制)发送过程
3. 超时/超期
  
  TTL = 0 或
  
  目的结点在规定的时间内没有收到一个分组的所有分片
4. 参数问题
  
  路由器或目的节点发现数据报首部中的字段值出错(二义性)，丢弃该数据报
5. 重定向
  
  路由器发现这个 IP 数据报不应该由自己转发，则向源主机发送重定向报文，请求重定向
网络探询报文
1. 回声（Echo）请求与应答报文（Reply）
2. 时间戳请求与应答报文

由于 ICMP 报文可能需要经过几个网络才能到达源节点，ICMP 报文被封装在IP包中传输。

ICMP 通常被认为是 IP 协议的一部分，因为 IP 协议使用 ICMP 向源节点发送错误报告。

Ping 利用 ICMP 报文测试目的主机是否活跃，以及去往目的主机的路径是否正常：

源主机发送 Type=8，Code=0 的 Echo Request 报文

若目的主机收到，发送 Type=0，Code=0 的 Echo Response 报文
源主机计算并报告 RTT

若源主机连续几次超时（收不到Echo Response），向调用者报告目的不可达

不产生 ICMP 差错报文情形：

对于携带 ICMP 差错报文的数据报，不再产生 ICMP 差错报文
对于分片的数据报，如果不是第一个分片，则不产生 ICMP 差错报文
对于具有组播(也称多播)地址的数据报，不产生 ICMP 差错报文
对于具有特殊地址(如 127.0.0.0 或 0.0.0.0 )，不产生 ICMP 差错报文

ICMP 报文格式：

IPv6

动机：

32 位 IPv4 地址空间已经分配殆尽
改进首部格式：快速处理、转发数据报；支持 QoS；

IPv6 与 IPv4 不兼容，但与其它所有因特网协议都兼容。

IPv6 数据报格式

固定长度的 40 字节基本首部
不允许分片

IPv6 地址

128 位，使用冒号十六进制表示，每 16 位以十六进制的形式写成一组，组之间用冒号分隔，如 8000:0:0:0:0123:4567:89AB:CDEF

地址表示的零压缩技术：可将连续的多组 0 压缩为一对冒号，如以上地址可表示为：``8000::0123:4567:89AB:CDEF`

IPv6定义了三种地址类型：

单播地址：一个特定的网络接口（一对一通信）
多播地址：一组网络接口（一对多通信）
任播地址（anycast）：一组网络接口中的任意一个（通常是最近的一个）

IPv6 vs. IPv4

与IPv4固定头相比，IPv6的基本头中去掉了以下一些字段：

IHL：IPv6的基本头总是40字节长
与分片相关的字段：IPv6路由器不负责分片
头校验：计算校验和太花时间；现在的网络非常可靠，并且链路层和传输层上往往又都有校验和

IPv6基本头中增加了：

流标签：支持对数据包区分处理

改变了以下字段的作用：

Type of Service：代之以 Traffic Class
总长度：代之以载荷长度
Protocol：代之以Next header，允许任意扩展选项

IPv6 数据包如何穿越 IPv4 网络？

报头转换

IPv4/IPv6节点（如路由器 B）在将数据报传递给 IPv4 路由器（如路由器 C）之前，将 IPv6 报头转换成 IPv4 报头
缺点：报头转换不完全，有信息丢失。
建立隧道
IPv6/IPv4 边界路由器将 IPv6 包封装到一个 IPv4 包中，送入 IPv4 网络，目的边界路由器取出IPv6包继续传输。
优点：保留原始数据报的全部信息。

路由算法

路由算法也就是解决选路问题的算法。

选路问题：给定一组路由器和连接路由器的链路，寻找一条从源路由器到目的路由器的最佳路径。

学过数据结构之后我们知道，计算机网络中的路由器网络可以抽象成图模型。

顶点：路由器
边：链路
边权：链路费用（可以是带宽的倒数、拥塞程度等）
关键问题：源到目的的最小费用路径 == 最短路径问题

路由算法的分类

静态路由：

手工配置；路由更新慢；优先级高；
动态路由：

路由更新快，能定期更新且及时响应链路费用或网络拓扑变化。
全局算法：

所有路由器掌握完整的网络拓扑和链路费用信息。

e.g. 链路状态（LS ）路由算法。
分布式算法：

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

邻居间信息交换、运算的迭代过程；

e.g. 距离向量（DV）路由算法。

链路状态（Link State）路由算法

基于图的最短路径算法 – Dijkstra 算法，得到源点到其他所有顶点的最短路径。

所有节点（路由器）掌握网络拓扑和链路费用
计算一个结点（源）到所有顶点的最短路径
迭代：经过 k 次迭代后，得到到达 k 个目的结点的最短路径

// Dijkstra 算法
Initialization:
    N’ = {u}      // N’为已找到最短路径的节点集合，初始时只有u
    for all nodes v    //标记源节点u到各个节点v的路径代价D(v)
      if v adjacent to u
          then D(v) = c(u,v)   //c(u,v)为链路(u,v)的代价
      else D(v) = ∞

   Loop
     find w not in N’ such that D(w) is a minimum  //下一条最短路径
    add w to N’     //将找到最短路径的节点加入N’
    update D(v) for all v adjacent to w and not in N’ :
       D(v) = min( D(v), D(w) + c(w,v) )    //更新到相关节点的路径代价
    until all nodes in N'

震荡现象： 若 A 是目的地，则下面这种情况下，最短路径循环变化，有可能一个数据报永远也到达不了 A。

解决办法：引入路由延迟更新算法。

距离向量（Distance Vector）路由算法

基于 bellman-ford 算法，得到源点到所有点的最短路径。

特点：对每个路由器来说，只需要知道其邻居及其链路费用即可。

$D_x(y)$ ：从结点 x 到结点 y 的最小费用估计

x 维护距离向量 DV： $DV = \{D_x(y):y\in N\}$

结点 x：

已知到达每个邻居的费用 c(x,v)
维护其所有邻居 v 的距离向量： $DV = \{D_v(y):y\in N\}$

核心思想：

每个节点不定时的将自身 DV 估计发送给邻居
当 x 接收到最新的 DV 估计时，根据 B-F 方程更新自身的距离向量估计：

$D_x(y) <- ~~min_v \{c(x,v) + D_v(y) ~for ~each~node~y\in N\}$
$D_x(y)$ 将最终收敛于实际最小费用 $d_x(y)$

无穷计数问题：好消息传播快，坏消息传播慢。

消除无穷计数问题：

毒性逆转：
定义最大度量：

定义一个最大的有效费用值，如 15 跳，16 跳表示无穷大。

无穷计数不会真正的无穷下去，会在有限的步数内反应网络状态。比如上图中的 R1,R2 已经不可达了。

层次路由

将任意规模的网络抽象成一张图，这样计算路由过于理想化。

在实际（大规模）网络中不可行：

路由表几乎无法存储；

路由计算过程的信息交换量巨大，会淹没电路。

考虑网络管理自治性的问题：每个网络的管理可能都期望自主控制内部路由算法。

自治系统 AS（autonomous systems）

聚合路由器为一个区域：自治系统。

同一个 AS 内的路由器运行相同的路由协议（算法）。

自治系统内部路由协议
不同的 AS 内的路由器可以运行不同的 AS 内部路由协议

网关路由器：

在 AS 边缘
通过链路连接其他的 AS 网关路由器

互连的 AS：

转发表由 AS 内部路由算法与 AS 间路由算法共同设置。

举个栗子：

热土豆路由协议：选择最近的网关路由器。

路由协议

Internet 采用层次路由。

AS 内部路由协议也称内部网关协议IGP（Interior Gateway Protocols），

最常见的有:

路由信息协议 RIP（Routing Information Protocol）：较低层ISP和企业网中使用
开放最短路径优先协议 OSPF（Open Shortest Path First）：较顶层 ISP 中使用

外部网关协议 EGP（Exterior Gateway Protocols），目前只有： BGP（Border Gateway Protocol）

RIP

RIP 采用距离矢量选路算法：

距离度量：跳步数（MAX = 15 hops），每条链路一个跳步。
RIP 响应报文（RIP通告）
距离向量封装在RIP响应报文中传输；
每个报文携带一个目的子网列表（最多包含25个子网），以及到每个目的子网的最短距离；
RIP 响应报文的发送：
相邻路由器之间大约每 30 秒交换一次 RIP 响应报文
RIP 报文封装在 UDP 报文中发送，使用 UDP 端口 520

RIP是一个应用层协议，其路由表示利用一个称作 route-d（daemon）的应用层进程进行管理。

RIP：是应用层协议，但完成的是网络层功能。

RIP 链路的失效和恢复：

经过该邻居的路由不可用：需要重新计算路由
向邻居发送新的通告
若转发表改变，邻居再依次向外发送通告
链路失效信息能否快速传播到全网？

可能发生无穷计数问题，但因为规定了最大跳数，故而可以在有限时间内收敛到正确状态。
毒性逆转技术 用于预防乒乓环路。

RIP 认为 15 跳步以内有效，16跳步及以上则认为网络不可达。所以 RIP 适用于小规模的自治系统，超过 15 跳的自治网络就不再适用了。

OSPF （Open Shortest Path First）

特点：

开放，公众可用；

采用链路状态路由算法：

LS 分组扩散（通告）
每个路由器构造完整的网络（AS）拓扑图
利用 Dijkstra 算法计算路由

OSPF 通告中每个入口对应一个邻居；

OSPF 通告在整个 AS 范围内泛洪，其报文直接封装到 IP 数据报中。

与 OSPF 及其相似的路由协议： IS-IS 路由协议。

BGP – 自治系统间的路由选择

用于确定跨越多个 AS 的源和目的对之间的路径。