网络层

学习地址：
《计算机网络自顶向下方法》
原书地址：https://www.net.t-labs.tu-berlin.de/teaching/computer_networking/

概念

转发和路由选择

网络层的作用从表面上看极为简单，需要两种重要的网络层功能：

转发：当一个分组到达路由器的一条输入链路时，路由器必须将该分组移动到合适的输入链路。
路由选择：当分组发送方流向接收方时，网络层必须决定这些分组所采用的路由或路径。计算这些路径的算法被称作路由选择算法（routing algorithm）。

转发表（forwarding table）：

路由器通过检查到达分组首部字段的值来转发分组，然后使用该值在路由器的转发表中索引查询。

网络服务模型

网络服务模型（network service model）定义了分组在发送与接收端系统之间的端到端运输特性：

一个分组的需求特性：
- 确保交付：该服务确保分组将最终到达其目的地。
- 具有时延上界的确保交付：在特定的时延上限内交付（如 100ms）
分组流需要提供下列服务：
- 有序分组交付：确保分组以它们发送的顺序到达目的地。
- 确保最小带宽：只要发送主机低于给定比特率的速率传输比特，则满足 确保交付 和 在时延上界内确保交付 的特性。
- 确保最大时延抖动：确保位于发送方发送两个相继分组之间的时间量等于目的地接收到它们之间的时间量
- 安全性服务：使用仅由源和目的主机所知晓的一个秘密回话密钥。

下面表格给出了三种服务模型：

网络体系结构	服务模型	带宽保证	无丢包保证	有序	定时	拥塞指示
因特网	尽力而为	无	无	任何可能	不维护	无
ATM	CBR	保证恒定速率	是	有序	维护	不出现拥塞
ATM	ABR	保证最小速率	无	有序	不维护	提供拥塞指示

虚电路和数据包网络

仅在网络层提供连接服务的计算机网络称为虚电路网络（Virtual-Circuit VC）。

仅在网络层提供无连接服务的计算机网络称为数据报网络（datagram network）。

Internet 是数据报网络。

路由器的工作原理

一台路由器主要由以下 4 个部分组成：

输入端口

输入端口通过以下方式进行处理：

假定转发表已经存在，从概念上来讲表查找是简单的，即我们只是搜索转发表查找最长前缀匹配。

交换结构

主要有三种交换方式：

输出端口

输出端口通过以下方式处理：

Where Does Queueing Occur?

假定需要路由器缓存来吸收流量负载的波动，一个自然而然的问题就是需要多少缓存。

对于缓存长度的经验方法是：

缓存数量（B）应该等于平均往返延时（RTT）乘以链路的容量（C），即 $$B = RTT \cdot C$$
有理论和试验研究表明，当有大量的 TCP 流（N）通过一个链路时，缓存所需要的的数量是 $${\displaystyle B = \frac{RTT \cdot C}{\sqrt{N}} }$$

输出端口排队的后果就是，在输出端口上的一个分组调度程序（packet scheduler）必须在这些排队的分组中选择一个来发送：

这种选择可能是根据简单的原则来定，如先来先服务（FCFS）调度。
或者更加复杂的调度规则，如加权公平排队（WFQ）

类似的，如果没有足够的内存来缓存一个入分组，那么必须丢弃一些分组。已经提出了许多分组丢弃和标记的策略，这些策略统称为主动队列管理（Active Queue Management, AQM）算法：

随机早期检测（Random Early Detection, RED）算法是一种得到最广泛研究和实现的 AQM 算法：

1
2
3
4
5
6
7
void newPacket(Packet p){
	if (queue.length < min_val) queue.push_back(p);
    else if (queue.length > min_val && queue.length < max_val){
        if(randF(queue.length, min_val, max_val)) drop p;
    	else queue.push_back(p);
    }else drop p;
}

其中：min_val 和 max_val 是给定的阈值，randF 按照一定概率返回 true 的函数。

如果交换结构不能快得是所有到达分组无延时地通过它传送，则在输入端口也将出现分组排队，因为到达的分组必须加入输入端口队列中，以等待通过交换结构传送到输出端口。

这种现象叫做输入排队交换机中的线路前部阻塞（Head-Of-the-Line, HOL），即在一个输入队列中排队的分组必须等待通过交换结构发送（即使输出端口是空闲的），因为它被位于线路前部的另一分组所阻塞。

网际协议

Internet 的网络层主要有三个主要组件：

数据报格式

网络层的分组被称为数据报，IPv4 的数据报格式如下：

IP 数据报分片：

因为不同的链路层协议拥有不同的 MTU（Maximum Transmission Unit, 一个链路层帧能够承载的最大数据量），我们可能需要将 IP 数据报中的数据分片称多个较小的数据报，用单独的链路层帧封装这些较小的 IP 数据报，然后向输出链路上发送这些帧。每个这些较小的数据报都称做片（fragment）。
为了让目的主机将这些接收到的片拼接到一起以形成初始的数据报，IPv4 的设计者将以下三个字段放在 IP 数据报的首部中：
1. 标志，flag，flag=0 表示这是最后一个片
2. 偏移，offset，表示相对初始位置的偏移，规定为以 8 字节块为单位。
3. 标识号，ID，标识号相同的属于同一片数据。

IPv4 编址

子网：

在网络拓扑结构中，任意两个路由器或主机的端口之间的部分可以形成一个网络岛，每一个这种网络岛便称为一个子网（subnet）。
IP 编址会为子网分配一个地址，比如：223.1.1.0/24，其中 /24 的记法称作子网掩码，他表示 32 位比特中最左侧的 24 比特定义了子网地址。

CIDR：因特网的地址分配策略被称为无类别域间路由选择（Classless Inter-domain Routing, CIDR），它将子网寻址的概念一般化了。

形式位 a.b.c.d/x 的地址的 x 最高比特构成了 IP 地址的网络部分，并且经常被称作该地址的前缀（prefix，或网络前缀）
一个地址剩余的 32-x 比特可认为是用于区别该组织内部设备的。

在 CIDR 被采用之前，IP 地址的网络部分被限制为长度为 8、16 和 24 比特子网地址的子网分别被称为 A、B 和 C 类网络。

获取一块地址

网络管理员与 ISP(Internet Service Provider) 联系，该 ISP 会从已经分给它的更大的地址块中提供一些地址。
向 ICANN(Internet Corporation for Assigned Names and Numbers) 提起申请（基于 [RFC 2050]）

PostScript：ICANN 除了管理 IP 地址外，还管理 DNS 根服务器，还负责分配域名与解决域名纷争。

获取主机地址

某组织一旦获得了一块地址，它就可以为本组织内的主机与路由器接口逐个分配 IP 地址。

主机地址可以手动配置，也可以通过 DHCP(Dynamic Host Configuration, DHCP) 来完成。

DHCP：

DHCP 允许主机自动获取（被分配）一个 IP 地址，主机还可以得知子网掩码、第一跳路由器（或称默认网关）与它的本地 DNS 服务器地址等。
网络管理员可以配置 DHCP，以使某给定的主机每次与网络连接时能得到一个相同的 IP 地址，或者某主机将被分配一个临时的 IP 地址。
DHCP 是一个客户-服务器协议，它工作流程如下：
1. DHCP 服务器发现：新到来的主机以发送 DHCP 发现报文 广播信号。
2. DHCP 服务器提供：DHCP 收到一个发现报文后，使用 DHCP 提供报文 广播信号进行响应。
3. DHCP 请求：新到达的客户从一个或多个服务器提供中选择一个并向选中的服务器提供一个 DHCP 请求报文 进行响应。
4. DHCP ACK：服务器用 DHCP ACK 报文 证实所要求的参数。

因特网控制报文协议

因特网控制报文协议（ICMP）是被主机和路由器用来彼此沟通网络层信息的协议。它最典型的用途就是差错报告。ICMP 报文有一个类型字段和一个编码字段，并且包含引起该 ICMP 报文首次生成的 IP 数据报的首部和前 8 字节内容。

应用 ICMP 的两个程序：ping，traceroute

路由选择算法

主机通常直接与第一台路由器相连，该路由器即为主机的默认路由器（default router），又称作该主机的第一跳路由器（first-hop router）。我们把源主机的默认路由器称作源路由器（source router），目的主机的默认路由器称作目的路由器（destination router）。

那么路由选择算法：

给定一组路由器以及连接路由器的链路，找到一条从源路由器到目的路由器的最低消耗路径。

链路状态选择算法

全局式路由选择算法（global routing algorithm）用完整的、全局性的网络知识计算出从源到目的地之间的最低费用路径：以所有节点之间的连通性以及链路的费用作为输入。

实践中，具有全局状态信息的算法常被称作链路状态算法（Link State, LS），经常由链路状态广播（link state broadcast）实现（比如 OSPF 路由选择协议），使用 Dijkstra 算法，计算结果给出如下两个变量：

D(v): cost of the least-cost path from the source node to destination v as of this iteration of the algorithm.
p(v): previous node (neighbor of v) along the current least-cost path from the source to v.

通过 p(v) 即可构造从源路由出发到目的路由 v 的路径。

距离向量路由算法

分散式路由选择算法（decentralized routing algorithm）以迭代、分布式的方式计算出最低费用路径。没有结点拥有关于所有网络链路费用的完整信息，而每个结点仅有与其直接相连链路的费用知识即可开始工作。

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

PreScript：首先给出下面的一个方程：

Bellman-Ford 方程：$${\displaystyle d_x(y) = min_{v\in neighbor(x)}{c(x,v), +d_v(y)} }$$，其中 $$d_x(y)$$ 是从结点 x 到 y 的最低费用

在 DV 算法中，每个结点拥有以下的三个路由信息：

For each neighbor v, the cost c(x,v) from x to directly attached neighbor, v
Node x’s distance vector, that is, $$D_x = [D_x(y): y \in N]$$, containing x’s estimate of its cost to all destinations, y, in N
The distance vectors of each of its neighbors, that is, $$D_v = [D_v(y): y \in N]$$ for each neighbor v of x

然后利用 Bellman-Ford 方程，可以得到到目的地址的距离向量。

链路费用改变与链路故障

当运行 DV 算法的结点检测到从它自己到邻居的链路费用发生变化时，他就更新其距离向量，并且如果最低费用发生了变化，向邻居通知其新的距离向量。

一个问题：遇到选择环路 → 无穷计数问题。

增加毒性逆转

避免无穷计数问题：一种称为毒性逆转（poisoned reverse）的技术：

如果 z 通过 y 路由发送一个目的地为 x 的数据报，则 z 将通告 y，它到 x 的距离是正无穷，因此 y 在进行路由选择时永远不会选择经由 z 到 x，从而避免了路由选择环路问题。

局限性：涉及三个或更多结点而不只是两个直接相连的邻居结点的环路问题将无法使用毒性逆转技术检测。

层级路由选择

以上的两个算法在实际应用中会出现 规模 和 管理自治 这两个重要问题。

都可以通过将路由器组织进 自治系统（Autonomous System, AS）来解决，每个 AS 由一组通常处在相同管理控制下的路由器组成：在相同的 AS 中的路由器都全部运行同样的路由选择算法。

在一个自治系统内运行的路由选择算法叫做 自治系统内部路由选择协议（intra-autonomous system routing protocol）。

有一台或多台负责向在本 AS 之外的目的地转发分组的路由器，被称作 网关路由器（gateway router）。

因特网中的路由选择

`RIP` 协议

RIP 协议是一种 AS 内部的路由选择协议，又称作内部网关协议（interior gateway protocol）。AS 内部路由选择协议用于确定在一个 AS 内执行路由选择的方式。

RIP 是一种距离向量协议，在 [RFC 1058] 中定义的 RIP 版本使用跳数作为其费用测度，即每条链路的费用为 1。

RIP 中一条路径的最大费用被限制为 15，因此 RIP 的使用限制在网络直径不超过 15 跳的自治系统内。

路由选择更新信息在邻居之间通过一种 RIP 响应报文（RIP response message）来交换，大约每 30 秒相互交换一次，一台路由器或主机发出的响应报文包含了一个该 AS 内的多达 25 个目的的子网列表，以及发送方到每个子网之间的距离。响应报文又称作 RIP 通告（RIP advertisement）。

每台路由器维护一张称为路由选择表（routing table）的 RIP 表。

`OSPF` 协议

OSPF 协议也是一种 AS 内部的路由选择协议。

OSPF 协议（与 IS-IS 协议）通常都设置在上层 ISP 中，而 RIP 通常设置在下层 ISP 和企业网中。

OSPF 协议的核心是一个使用洪泛链路状态信息的链路状态协议和一个 Dijkstra 最低费用路径算法。

使用 OSPF 时，路由器向自治系统内所有其他路由器广播路由选择信息，而不仅仅向其相邻路由器广播。每当一条链路的状态发生变化时，路由器就会广播链路状态信息。即使链路状态未发生变化。它也要周期性地（至少每隔 30 分钟一次）广播链路状态。OSPF 协议还要检查链路正在运行（通过向相连的邻居发送 HELLO 报文），并允许 OSPF 路由器获得相邻路由器的网络范围链路状态的数据库。

OSPF 协议有以下优点：

安全：能够鉴别 OSPF 路由器之间的交换。使用鉴别，仅有受信任的路由器能参与一个 AS 内的 OSPF 协议。
多条相同费用的路径：OSPF 允许使用多条路径。
对单播与多播路由选择的综合支持：多播 OSPF（MOSPF）提供对 OSPF 的简单扩展。
支持在单个路由选择域内的层次结构：最重要的优点。

`BGP` 协议

BGP(Border Gateway Protocol) 协议是是一种 AS 间的路由选择协议。

BGP 为每个 AS 提供了进行以下工作的手段：

从相邻 AS 出获得子网可达性信息；
向本 AS 内部的所有路由器传播这些可达性信息；
基于可达性信息和 AS 策略，决定到达子网的 “好” 路由。

`BGP` 基础

在 BGP 中，路由器对通过使用 179 端口的半永久 TCP 连接来交换路由选择信息：

位于连接端点的两台路由器称为 BGP 对等方（BGP peers）
沿着连接发送所有 BGP 报文的 TCP 连接称为 BGP 会话（BGP sessions）
跨越两个 AS 的 BGP 会话称为 外部 BGP 会话（external BGP session, eBGP）
在同一个 AS 内部的 BGP 会话称为 内部 BGP 会话（internal BGP session, iBGP）

BGP 使得每个 AS 知道经过其相邻的 AS 可达哪些目的地（CDIR 化的前缀（prefix））

路径属性和 BGP 路由

在 BGP 中，一个 AS 由其全局唯一的自治系统号（Autonomous System Number, ASN）所标识，由 ICANN 地区注册机构分配。

当一台路由器通过 BGP 会话通告一个前缀时，它在前缀中包含一些 BGP 属性（在 BGP 术语中，带有属性的前缀被称为一条路由（route））两个较为重要的属性：

AS-PATH：该属性包括了前缀通告已经通知过的那些 AS。当一个前缀通告传送到一个 AS 时，该 AS 将它的 ASN 增加到 AS-PATH 属性中。
NEXT-HOOP：The NEXT-HOP is the router interface that begins the AS-PATH. 即相邻 AS 网关路由器之间的 IP 地址。

BGP 的路由选择

如果对相同前缀存在两条或多条路由，则 BGP 顺序地调用下面的消除规则，直到留下一条路由：

路由被指派一个本地偏好值作为他们的属性之一，具有最高本地偏好值的路由将被选择。
在余下的路由中，具有最短 AS-PATH 的路由将被选择。
在余下的路由中，具有最靠近 NEXT-HOOP 的路由将被选择。
如果仍剩下多条路由。使用 BGP 标识符来选择路由。

网络层

概念