网络层负责将报文段发送到接收主机。它具备两大核心功能：

• 转发：将数据包从路由器的输入链路移动到适当的路由器输出链路。
• 路由：确定数据包从源到目的地的路线。

网络层的组成

网络层可分为两个主要部分：

• 数据平面：确定如何将到达路由器输入端口的数据报转发到路由器输出端口，即负责“转发”。
• 控制平面：确定数据报文从源主机到目标主机的端到端路径，即负责“路由”。

控制平面的两种方式：

• 传统方式：每个路由器的路由算法相互独立，相互作用。

• 新方式：远程控制器在路由器中计算并安装转发表。

路由器模型

路由器是一种实现网络互连的设备，在网络层中提供路由与转发功能。

组成

简单来说，路由器主要由以下软硬件组成：

• 硬件：
  • CPU：运行操作系统，处理路由协议。
  • 交换结构：高速传输数据包，连接输入输出端口。
  • 网络接口：以太网、光纤等，收发数据包。
• 软件：
  • 操作系统：运行专用的嵌入式操作系统，提供路由协议支持、配置管理等功能。

路由器的输入和输出端口可具体分为以下结构：

路由表

路由表是存储在路由器内的数据结构，包含了有关网络之间如何进行路由的信息。

路由表包含如下信息：

当路由器收到一个数据包时，它会提取数据包的目的IP地址，并与路由表中的条目进行比较。最长前缀匹配要求选择与目的IP地址前缀匹配最长的路由表项。

可以理解为更长的前缀表示更具体的路由，因此它的优先级更高。

例如，如下的路由表：

对于IP地址：

• 11001000 00010111 00010110 10100001，最长匹配的前缀为11001000 00010111 00010110，应从0口转发。
• 11001000 00010111 00011000 10101010，最长匹配的前缀为11001000 00010111 00011，应从2口转发。

实际生产中，最长前缀匹配通常使用三元内容可寻址存储器（TCAM）进行匹配。无论表的大小如何，它都可以在一个时钟周期内检索出正确的地址。

交换结构

路由器的交换结构能将数据包从输入链路传输到适当的输出链路。

交换速率定义为数据包从输入端传输到输出端的速率，通常以输入/输出线路速率的倍数进行测量。

交换结构主要有以下三种类型：内存型、总线型、互联网络型。

内存型主要用于第一代路由器，实际上就是受CPU控制的、包含转发功能的小型计算机。这里数据包需要先复制到系统内存，转发速度受内存带宽限制。

总线型结构中，数据包通过共享总线从输入端口转发到输出端口，转发速率仅受到总线带宽的限制，足以为路由器提供足够的速度。

互联网络型利用了并行性：在入口时将数据包转化为固定长度的片段，通过互联结构在出口处重新组装成完整的数据包。

排队现象

如果交换结构比输入端口组合慢，那么输入队列中可能会出现排队和输入缓冲区溢出，进而导致排队延迟和丢包。

输入队列中，排在队首的数据包会阻止队列中其它数据包的转发。

输出队列中，当通过交换机的到达率超过输出线速度时会发生排队。同样，由于拥塞、缺少缓冲区等原因，数据包可能会丢失。因此输出端需要进行优先级调度。

通常，优先级调度方法有以下几类：

• 先来先服务（FCFS）
• 优先级调度
• 时间片轮转
• 加权公平队列（WFQ）

IP协议

IPv4分类编址

在互联网早期，IP地址采用了分类编址。根据IP地址的前几位将其分为 A、B、C、D、E五类。

然而，这种地址分配方式存在较大的缺陷，具体表现为：

• 地址空间浪费：
  • B 类地址提供 65534 个主机位。如果一个组织只有几千台主机，其余地址就被闲置。
  • C 类地址只能容纳 254 台主机。当组织的需求超过这一规模，却又不想使用一个庞大的 B 类地址块时，就会陷入分配困难。
• 分配不灵活：
  • 分类寻址的层次结构固定，无法根据实际需求进行细粒度的划分，导致大块地址被“硬切”，小块需求又常常得不到满足。

为突破这些局限，相继提出了几项关键技术：

• CIDR（无类域间路由）：通过可变长度子网掩码（VLSM）取代固定的分类划分，使得地址块可以按需灵活划分，大幅提升了地址利用率，并简化了路由表的汇总。
• NAT（网络地址转换）：在内部网络使用私有地址，通过在出入口的路由器上进行地址映射，多个终端共享同一个公网 IP，从而在一定程度上缓解了 IPv4 地址匮乏的问题。
• IPv6：直接扩展地址长度至 128 位，提供几乎无限的地址空间（约 $3.4 \times 10^{38}$ 个地址）。

CIDR

CIDR引入了子网掩码（subnet mask）：如果一个CIDR网络的前缀长度是 $n$ 位的话，那么其子网掩码的二进制表示就是 1111 ...（$n$ 个 1）... 0000（32- $n$ 个 0）。

子网掩码的作用是区分网络号和主机号：

• 网络号部分：与子网掩码中 1 对应的比特位
• 主机号部分：与子网掩码中 0 对应的比特位

通常，子网掩码记作 /x，例如：

📝 备注

对于每个子网，主机号全 0 的 IP 为网络地址，全 1 的 IP 为广播地址，不用于设备上网。

例如，将 IP 网络 123.4.4.0/22 划分为规模均衡的 32 个子网：容易得知此时网络中可支持的 IP 总数为 $2^{10}$。若需要划分为规模均衡的 $32 = 2^5$ 个子网，则每个子网支持的 IP 数量应为 $\displaystyle \frac{2^{10}}{2^5} = 2^5$ 个，即每个子网的主机号应有 $5$ 位。即子网的形式为 123.4.x.x/27。

如果两个设备在同一个子网，它们可以直接通信，不用经过路由器转发，只需要使用 MAC地址。

如何获取IP地址？

• 对于网络中的主机，通常通过 DHCP 动态获取 IP地址。
• 对于一个接入网，则将从运营商已有的 IP 空间里分配一部分作为 IP地址。

DHCP

DHCP即动态主机配置协议，用于自动分配IP地址和其他网络配置参数给网络设备。它具备以下特点：

• 可以自动续约。
• 允许重复使用地址。
• 支持有线和无线连接。

📝 备注

DHCP 不仅返回IP地址，还会返回主机第一跳路由器的网关、DNS地址和名字、子网掩码等。

DHCP的流程通常包括以下步骤：

示意图如下：

NAT

NAT全称为Network Address Translation，表示网络地址转换。

它的核心作用是把一个IP地址空间映射到另一个IP地址空间，常见的情形是把局域网内部的私有IP地址转换为公网IP地址（或将公网地址转换回私有地址），从而实现内部设备与外部网络的互联。

使用NAT后，一个本地网络内的所有设备就可以共享同一个公网IP地址。

NAT表

NAT表存储在路由器中，每个条目包含如下内容：

• 内部私有IP地址：局域网中设备的私有IP地址
• 内部端口号：发送数据包的私有网络设备所使用的端口号。
• 外部公有IP地址：路由器在广域网（WAN）侧使用的IP地址，通常是单个IP地址，但也可能有多个。
• 外部端口号：与内部端口号对应的，由NAT分配用于标识特定会话的公有端口号。
• 协议类型：数据包使用的协议（如 TCP、UDP 等）。

地址转换

1. 内网主机向外网发起通信，数据包首先经过NAT路由器。NAT路由器会把数据包的源IP地址和源端口替换为路由器的公网IP地址和分配的公网端口。
2. 外部主机向NAT路由器的公网IP和端口发送响应报文，NAT路由器根据之前记录的映射表，将报文的目的IP地址和目的端口改写回对应的私有IP地址和私有端口，随后将报文转发给内网的目标主机。

在如图所示的NAT网络中，内网主机（10.0.0.1:3345）发起通信，目标地址为128.119.40.186:80。地址转换过程如下：

• 内网主机首先向NAT路由器发送数据包。
  • 源地址：10.0.0.1:3345
  • 目的地址：128.119.40.186:80
• NAT路由器收到数据包后，将源IP地址和源端口替换为路由器的公网IP地址和分配的公网端口，并将该映射关系写入NAT转换表中。
  • 源地址：138.76.29.7:5001
  • 目的地址：128.119.40.186:80
• 外部主机向NAT路由器返回报文。
  • 源地址：128.119.40.186:80
  • 目的地址：138.76.29.7:5001
• NAT路由器将报文的目的IP地址和目的端口改写回对应的私有IP地址和私有端口，并转发给内网的目标主机。
  • 源地址：128.119.40.186:80
  • 目的地址：10.0.0.1:3345

数据报经过 NAT 路由器后，如果 NAT 修改了源 IP 地址或源端口号，可能导致报文段的内容发生变化，因此校验和字段可能会被修改。

路由算法

路由算法的目标：通过路由器网络，确定从发送主机到接收主机成本最低、速度最快、拥堵最少的“最好”路径。

路由算法可分为静态与动态、集中式与分布式。

链路状态路由

在链路状态路由（LS）中，每个路由器通过节点状态广播搜集所有节点信息，构建一致的整个网络拓扑结构。

同时，每个路由器独立运行 Dijkstra 最短路径算法 计算路由各自计算到其它节点的最短路径，形成该节点的路由表。可用以下的伪代码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Initialization: 
    /* 计算u到其他所有节点的最短路径 */
    N' = {u}     
    for all nodes v 
        if v adjacent to u   /* u开始只知道到邻居的距离 */
            D(v) = c[u,v]      /* 不一定是最短路径  */
        else D(v) = ∞ 

Loop 
    find w not in N' such that D(w) is a minimum 
    add w to 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' 

例如，对于上述的网络拓扑结构，以节点 $u$ 为例，初始时 Dijkstra 表：

此时未加入集合 $N$ 的最近节点为 $x$，将其加入集合并更新距离：

接下来未加入集合 $N$ 的最近节点为 $y$，重复操作：

以此类推，可得到最终的 Dijkstra 表：

由此可得出一棵生成树：

据此可得转发表如下：

距离向量路由

距离向量路由使用 Bellman-Ford 算法，核心思想是动态规划。

距离向量

距离向量（Distance Vector）可以表示为一个列表，其中每个条目包含以下信息：

• 目标网络：目标网络或子网的地址。
• 跳数/度量值（常记作Metric）：从当前路由器到达目标网络的代价，通常以跳数、延迟、带宽等度量标准表示。
• 下一跳：到达目标网络的下一跳路由器的地址。

例如，下面就是一个简单的距离向量示例：

距离向量算法

设 $D_x(y)$ 表示 $x$ 到 $y$ 的最短路径，$v$ 为中间节点，则有以下状态转移方程：

即 自己到达目的节点的最短距离 = 所有自己的邻居到达目的节点最短距离和自己与之距离之和的最小值。

例如，在上述的网络拓扑结构中，$u$ 的邻居有 $v, x, w$，则 $u$ 到 $z$ 的最短路径可表示为

路由器在实际工作中，通过周期性地与相邻路由器交换距离向量信息，每个路由器能够逐渐获得整个网络的拓扑信息，并更新其路由表以选择最佳路径。工作流程如下：

• 初始化：每个路由器初始化各自的距离向量，只包含自己的邻居，距离（跳数）设为 0。
• 周期性更新：每个路由器周期性地（例如每30s）将它的距离向量广播给所有相邻的路由器。
• 接收和更新：每个路由器接收到相邻路由器的距离向量后，检查是否有新的或更短的路径。如果有，则更新自己的距离向量和路由表。
• 收敛：经过多次交换和更新后，所有路由器的距离向量和路由表最终会收敛到最优路径。

例如，在如下的网络拓扑中，

消息的稳定性

在距离向量路由算法中，好消息会很快稳定下来。坏消息稳定需要的时间较长。

例如，在如图所示的结构中，$x$ 和 $y$ 之间的成本突然从 $4$ 增加到 $60$：

这将经历如下过程：

• $y$ 发现到 $x$ 的距离变成了 $60$，但是 $z$ 报告 $y$ 它到 $x$ 的距离为 $5$（实际上是经过 $y$ 到 $x$），因此 $y$ 更新到 $x$ 的距离为 $6$。
• $z$ 收到 $y$ 到 $x$ 的距离变成了 $6$，又更新 $z$ 到 $x$ 的距离为 $7$。
• $y$ 只知道 $z$ 到 $x$ 的距离变成了 $7$，又继续更新 $y$ 到 $x$ 的距离为 $8$。
• 这个循环将一直重复，直到 $z$ 发现直接从 $z$ 到 $x$ 成本更低才结束。

📝 备注

也就是说，$y$ 不知道“我从 $z$ 学到的这条路径，实际上也是绕了一圈又回到我这里”。

路由协议

确定了路由算法后，还需要确定路由协议。路由协议是一种用于路由器之间交换网络路由信息的通信规则。它的主要作用是让路由器能够自动学习和维护到达各个目的网络的路径，从而实现数据包的正确转发。

📝 备注

自治系统（AS，Autonomous System）是由一个或多个网络组成的集合，这些网络在统一的管理和策略控制下运行，并对外表现为一个单一的路由实体。

一个自治系统内可能存在域内路由和域间路由。

• 同一个域内的路由器运行相同的路由协议。
• 不同域内的路由器有不同的路由协议。
• 不同的域之间通过网关路由器连接。

每个域运行的域间路由必须学习哪些目的地可以通过哪些域是可达的，并且把可达性在本域内进行广播。

路由协议根据其使用范围的不同，可以分为两大类：

• 内部网关协议（IGP，Interior Gateway Protocol）：在单个组织或自治系统（AS）内部使用的路由协议，常见的IGP协议包括RIP和OSPF。这些协议的主要作用是在一个组织的网络内部传播和更新路由信息，以实现高效的网络通信。
• 外部网关协议（EGP，Exterior Gateway Protocol）：在不同组织或不同自治系统之间交换路由信息。唯一广泛使用的EGP协议是BGP。BGP的设计初衷是为了控制跨组织网络之间的路由信息传递，从而实现 自治系统之间的互联和路径控制。

OSPF协议

OSPF（Open Shortest Path First）是一种基于 链路状态 的内部网关协议（IGP），广泛应用于中大型网络中。它具有以下特点：

• 每个路由器向整个自治系统中的所有其他路由器发送 OSPF链路状态通告（直接通过IP，而不是使用TCP/UDP）。
• 链路的成本指标包括带宽和延迟等。
• 每个路由器都有该自治系统完整的拓扑结构，并使用Dijkstra算法（链路状态路由算法）计算转发表。

BGP协议

BGP协议中，允许每个域向网络中广播自己的存在以及自己可以达到的目的地。BGP为每个AS提供了以下方法：

• eBGP：从相邻的域获取子网可达性信息
• iBGP：将可达性信息传播到所有AS内部的路由器。

每个AS内部可以有多个BGP路由器，但对外通常由一个或多个“BGP 发言人”代表整个AS与其他AS进行路由信息的交换。

“BGP 发言人” 需要同时运行eBGP和iBGP。

BGP发言人之间通过 TCP连接 建立BGP会话，并交换BGP通告路由。该路由信息包含前缀及其路径属性：

• 前缀：正在通告的目的地
• 两个重要属性：
  • AS-PATH：前缀广告通过的AS列表
  • NEXT-HOP：表示下一跳AS的特定内部AS路由器
• BGP消息：
  • OPEN：打开与远程BGP对等端的TCP连接，并对发送BGP对等端进行身份验证
  • UPDATE：通告新路径（或撤回旧路径）
  • KEEPALIVE：在没有更新的情况下保持连接活力；还确认OPEN请求
  • NOTIFICATION：报告之前消息中的错误，也用于关闭连接

每个 AS 在接收到路径信息后，可以根据自身策略决定：

• 是否接受该路由
• 是否将其传播给其他邻居
• 是否作为本地的最佳路径使用

例如，在如下的网络中，

$AS2$ 的路由器 $2c$ 通过 eBGP 接收到了来自 $AS3$ 中路由器 $3a$ 的通告 $(AS3, X)$。表明 $3a$ 承诺将为 $AS2$ 转发所有发往 $X$ 的数据包。

同时，基于 $AS2$ 的策略，它的发言人 $2c$ 接受了 $(AS3, X)$，并通过 iBGP 广播到$AS2$ 中所有的路由器。此外，$AS2$ 的另一个发言人 $2a$ 通过 eBGP 将通告 $(AS2,AS3,X)$ 发送到 $AS1$ 的路由器 $1c$。

实际上，“发言人”可能会收到多个BGP通告。例如图中的路由器 $1c$ 就收到了来自 $2a$ 的 $(AS2, AS3, X)$ 和 $3a$ 的 $(AS3, X)$。此时 $1c$ 将根据所在自治系统的策略选择合适的一个。

热土豆策略：路由器总是选择域内成本最低的本地网关而不考虑域间成本。

例如，上图的 $2d$ 学习到它可以通过 $2a$ 或者 $2c$ 到达 $X$。实际中，$2d$ 选择了 $2a$，因为 $2d$ 和 $2a$ 之间的成本更低。