HNU 计算机网络期末考试考点复习
HNU 计算机网络期末考试考点复习
🎉🎉 Happy New Year 2024! 🎉🎉
考点纵览
教材：《计算机网络：自顶向下方法（原书第 7 版）》
| 章节 | 内容 | 详细 |
|---|---|---|
| Chapter 1 | 网络核心 | 分组交换、电路交换 |
| Chapter 2 | 电子邮件 | SMTP、POP3 |
| Chapter 2 | DNS | DNS 的查询机制 |
| Chapter 3 | 可靠数据传输 | rdt、流水线、GBN、SR |
| Chapter 3 | TCP | TCP 连接、往返时间、超时、流量控制 |
| Chapter 3 | 拥塞控制 | 原因与代价 |
| Chapter 4 | IPv4 网际协议 | 数据报格式、IPv4 分片、编址、NAT |
| Chapter 5 | 路由选择算法 | Link-State 算法、Distance-Vector 算法 |
| Chapter 5 | 自治系统内路由 | OSPF |
| Chapter 5 | BGP | 边界网关协议 |
| Chapter 5 | ICMP | 因特网控制报文协议 |
| Chapter 6 | 差错检测 | 奇偶校验、CRC |
| Chapter 6 | 随机接入协议 | CSMA、CSMA/CD |
| Chapter 6 | 地址解析协议 | ARP、发送数据报到子网之外 |
第一章：计算机网络和因特网
网络的核心：分组交换机和链路构成的网状网络。
分组交换
分组交换中的时延：
- 处理时延，$d_{proc}$ ，检查分组首部和决定将该分组导向何处。
- 排队时延，$d_{queue}$，分组在链路上等待传输。
- 传输时延，$d_{trans} = \frac{L}{R}$，长度为 $L$ 比特的分组在传输速率为 $R \text{bps}$ 的链路上发射所需要的时间。
- 传播时延，$d_{prop} = \frac{d}{s}$，分组在距离为 $d$，传播速率为 $s$ 的链路上传输所用时间。
因此，总时延
\[d_{total} = d_{proc} + d_{queue} + d_{trans} + d_{prop} \\ = d_{proc} + d_{queue} + \frac{L}{R} + \frac{d}{s}\]对于端到端时延
\[d_{end-end} = N(d_{proc} + d_{trans} + d_{prop})\]需要乘上链路的总数 $N$。
电路交换
电路交换中有两种复用（multiplexing）：
- 频分复用（Frequency-Division Multiplexing, FDM）
- 时分复用（Time-Division Multiplexing, TDM）
电路交换的总时延
\[d_{total} = t_{创建电路} + t_{文件传输}\]对比
对于分组交换：
- 不适合实时服务，由于端到端时延是可变的和不可预测的。
- 提供了更好的共享带宽，相比于电路交换支持更多的并发用户。
- 成本更低，实现更加简单有效。
电路交换反之。
第二章：应用层
Internet 中的电子邮件
需要注意的是，应将电子邮件放于与 Web 同等的地位。
电子邮件系统主要有 3 个组成部分：用户代理（user agent）、邮件服务器（mail server）和简单邮件传输协议（SMTP）。
SMTP
简单邮件传输协议（SMTP）是因特网电子邮件的核心。SMTP 限制了邮件的体部分只能采用 7 比特 ASCII 表示，因此现在邮件传送之前，应该先对其进行编码使之符合要求。SMTP 使用 25 号端口，运行在 TCP 连接之上。它是「推」协议，将邮件从用户代理推向邮件服务器，再从邮件服务器把文件推向接收服务器。如果接收服务器没有开机，则邮件将会停留在发送服务器上，并不会在中间某个邮件服务器中留存。
POP3
第三版邮局协议（POP3）使得用户可以从邮件服务器上拉取邮件，即 POP3 将邮件服务器上的邮件传送至用户代理。工作阶段如下：
- 特许（authorization）
- 事务处理
- 更新
注：IMAP（因特网邮件访问协议）、HTTP 均可实现拉取邮件的操作。
DNS
DNS（Domain Name System，域名系统）提供主机名到 IP 地址转换的服务，工作于 UDP 之上，提供非可靠服务，端口 53 号。它是
- 一个分布式 DNS 数据库
- 一个使主机能查询分布式数据库的应用层协议
DNS 服务器通常是运行 Berkeley Internet Name Domain（BIND）软件的 UNIX 机器。
分布式层次数据库
- 根 DNS 服务器：有 13 台，从 A 到 M。
- 顶级域（Top-Level Domain, TLD） DNS 服务器：com、org、net 等顶级域和所有国家和地区的顶级域，都有 TLD 服务器或者集群。
- 权威 DNS 服务器：大型机构拥有，比如大学和大企业。
需要注意的是，本地 DNS 服务器（Local DNS Server）不属于 DNS 服务器的层次结构中。
迭代查询（Iterative query）和递归查询（Recursive query）
理论上任何 DNS 查询都既可以是迭代查询也可以递归查询，但是一般来说，从请求主机到本地 DNS 服务器的查询是递归的，其余的查询都是迭代的。
迭代查询：此种查询方式带来的负担小，所有的结果都是直接返回给发起查询的主机。
递归查询：一层一层地返回结果。
第三章：运输层
可靠数据传输
rdt1.0
无比特差错，无分组丢失。完全可靠信道。发送端只通过 rdt_send(data) 接受来自较高层的数据，并通过 make_pkt(data) 产生一个包含该数据的分组，并将其发送至信道中。接收端通过 rdt_rcv(packet) 从底层信道中接收一个分组，并用 extract(packet, data) 解包，从中取出数据，并将数据传送至较高层。
rdt2.0
有差错检测和重传，但是不能纠错。停等协议（stop-and-wait），发送方发送一个分组之后，需要等待接收方发送 ACK（肯定确认）或者 NAK（否定确认），才会继续发送。接收方的状态仍然只有一个，接收分组，并判断是否受损，回答 ACK 或者 NAK。
如果 ACK 或者 NAK 受损了呢？
- 请重复一遍？你说什么？导致回答含糊不清。
- 增加足够多检验和比特，使发送方可以检验差错，甚至可以纠正差错。对于会产生差错但不会丢失分组的信道来说，此种方法可以解决问题。
- 收到含糊不清的 ACK 或者 NAK 分组时，直接重传当前数据分组。引入「冗余分组」。但是无法事先知道接收到的分组是新的还是一次重传分组。
rdt2.1
为了解决以上问题，设计了 rdt2.0 的修订版 rdt2.1，增加了序号（sequence number）放在将要发送的数据分组的一个新字段中。通过「期望接收的序号」和实际接收到的分组的序号来判断是否出现了差错。
rdt2.2
rdt2.2 与 rdt2.1 的不同之处在于 rdt2.2 的接收方必须包括由一个 ACK 报文所确认的分组序号，发送方也必须检查收到的 ACK 报文的确认的分组序号。
rdt3.0
rdt3.0 可以在具有比特差错和丢包的信道上工作。使用基于时间的重传机制，即选择一个合适的时间值，用来判定可能发生了丢包。如果在这个时间内没有收到 ACK，则认为已经丢包，直接重传该分组，即使该分组有可能实际上没有丢失。因此引入了冗余数据分组（duplicate data packet），此问题可以用 rdt2.2 中的序号来解决。由于分组序号在 0 和 1 之间交替，因此 rdt3.0 有时候也被称为比特交替协议。
如果用「滑动窗口」的视角来看 rdt 协议的话，由于一次只传输一个分组，因此滑动窗口的大小是 1（详见下一小节）。
Pipelining 流水线可靠数据传输
导致 rdt3.0 性能较差的原因是停等协议。解决该问题的方式是不使用停等协议，允许发送方发送多个分组而无需等待确认，将这些分组填充到一个流水线中，因此得名。由于没有等待确认，所以流水线传输需要另外的差错检测和恢复方式。
回退 N 步（Go-Back-N, GBN）
在 GBN 协议中，允许发送方发送多个分组而不需要等待确认，但是需要保证未确认的分组数不超过最大允许数量 $N$。
基序号（$base$）是最早未确认的序号。下一个序号（$nextseqnum$）是最小未使用序号。于是序号范围被分成了四段：
| 已确认 | 未确认 | 还未发送 | 不可用 |
|---|---|---|---|
| $[0, base - 1]$ | $[base, nextseqnum - 1]$ | $[nextseqnum, base + N - 1]$ | $[base + N, …)$ |
其中把 $N$ 看成窗口长度，随着协议的运行，窗口在序号空间内向前滑动，因此又称为「滑动窗口协议（sliding-window protocol）」。
GBN 使用累积确认，对序号为 $n$ 的分组的收到确认，表示接收方已经收到序号为 $n$ 及其之前序号的所有分组。在其他情况下，分组将会丢弃。GBN 接收方将会丢弃所有失序的分组，数据必须按顺序交付。
选择重传（Selective Repeat, SR）
由于单个分组的差错可能导致 GBN 重传大量分组，但是很多分组根本没有必要重传。SR 接收方不管是否乱序。
TCP
什么是 3 次握手和 4 次挥手？ TCP 连接的建立与断开。
TCP 的差错恢复机制是所谓「选择确认（selective acknowledge）」，应当被理解为 GBN 协议和 SR 协议的混合体。
拥塞控制
注意与「流量控制」区分开：流量控制是一个速度匹配服务，使发送方的速率和接收方应用程序的读取速率相匹配。
TCP 发送方因为 IP 网络的拥塞被遏制，于是有「拥塞控制（congestion control）」。
TCP 拥塞控制算法
每次确认就增加一个 $MSS$，每个 $RTT$ 之后拥塞窗口 $cwnd$ 翻一番，呈指数级增长。当 $cwnd$ 到达慢启动阈值 $ssthresh$ 之后，进入拥塞避免阶段。当收到 3 个冗余的 ACK 的时候（此时发送方一共发送了 4 个 ACK），进入快速恢复阶段：$ssthresh$ 减为 $cwnd$ 的一半（TCP Reno），线性增长；$sshthresh$ 直接减为 $1$（TCP Tahoe），进入慢启动。
「加性增，乘性减」。
第四章：网路层之数据平面
IPv4 数据报分片
由于并不是所有的链路层协议都能承载相同长度的网络层分组，因此需要对数据报进行分片。一个链路层帧能够承载的最大数据量叫做最大传送单元（MTU）。
IP 报文首部 20 字节，在分片的时候应该先去除。例如一个 4000 字节的数据报，去除掉 20 字节的 IP 首部之后，剩余 3980 字节的有效数据，由路由器转发到一条 MTU 为 1500 字节的链路上。此时该数据报中 3980 字节就要被分成 3 个独立的片（注意向上取整）。
IPv4 编址
点分十进制记法，各字节之间以句点隔开。
一般而言，路由器有多少个端口，就有多少个子网，IP 编址会对这个子网分配一个地址，例如 223.1.1.0/24，其中「/24」表示子网，叫做子网掩码，意思是 32 比特中从左往右的 24 个比特全部为 1。
分类 IP 编址：
| 类别 | 开头 | net-id | host-id |
|---|---|---|---|
| A 类 | 0 ~ 127 | 8 位 | 24 位 |
| B 类 | 128 ~ 191 | 16 位 | 16 位 |
| C 类 | 192 ~ 223 | 24 位 | 8 位 |
| D 类 | 224 ~ 239 | 多播地址 | \ |
| E 类 | 240 ~ 255 | 保留至今后使用 | \ |
CIDR 无类别域间路由选择
将子网寻址概念一般化，表示为 $a.b.c.d/x$。此处参见 IP 编址例题。
DHCP
即插即用，动态主机配置协议。该协议可以自动为新到达的主机分配 IP 地址。
- DHCP 服务器发现：通过 DHCP 发现报文，向广播地址发送。
- DHCP 服务器收到一个 DHCP 发现报文之后，向客户端做出响应：推荐 IP 地址、网络掩码、租用期等。
- DHCP 请求：新到达的客户主机从提供的服务器中选择一个，并向该服务器提供 DHCP 请求报文，回显配置的参数。
- DHCP ACK：服务器用 DHCP ACK 报文对请求报文进行响应，证实所要求的参数。
NAT
网络地址转换（NAT），解决 IPv4 地址不足的问题，但是 NAT 破坏了端到端的数据传送（即主机应该彼此直接对话）。
第五章：网络层之控制平面
第六章：链路层和局域网
链路层的数据服务：
- 差错检测，纠正
- 共享广播信道，多路访问
- 链路层编址
- 可靠数据传输，流量控制
在链路层中，把任何运行链路层协议的设备都叫做「节点（node）」；把沿着通信路径连接相邻节点的通信信道称为「链路（link）」。
对比运输层协议和链路层协议，
- 运输层协议：在端到端的基础上为两个进程之间提供可靠的传输；流量控制在端到端的基础上提供。
- 链路层协议：两节点之间提供可靠传输；流量控制在相邻节点。
差错检测与校验
奇偶校验
最简单的方法就是使用单个「奇偶校验位（parity bit）」。例如：
| $d$ 比特数据 | 校验比特 |
|---|---|
| 0111 0001 1010 1011 | 1 |
对于奇校验方案，选择最后一个校验比特，使得整个 $d + 1$ 比特中 $1$ 的总数是奇数； 对于偶校验方案，选择最后一个校验比特，使得整个 $d + 1$ 比特中 $1$ 的总数是偶数。
检验和
Internet checksum。将数据的字节作为 16 比特数，对其求和；然后对得到的和取反码，任何的溢出都回卷；最后将得到的反码与上面的所有 16 比特数相加，通过判断是否结果为全 1 来验证是否有差错。
CRC 循环冗余检测
Cyclic redundancy check 编码，也称为多项式编码。将要发送的比特串看作系数是 0 和 1 的一个多项式，对该比特串的操作可认为是对多项式的算术运算。
有一 $d$ 比特的数据 $D$，发送节点要将它送到接收节点。双方必须先协商一个 $r + 1$ 比特模式，叫做「生成多项式（generator）」，表示为 $G$，要求最高位（最左边）是 1。
| $d$ 比特 | $r$ 比特 |
|---|---|
| $D$：被发送的数据比特 | $R$：CRC 比特 |
其中 CRC 比特 $R$ 的比特数量 $r$ 由生成多项式 $G$ 的最高次幂来决定。例如，一个生成多项式 $G = 1001$，那么最高次幂是 $3$，因此 $r = 3$。
在此基础上，可以通过下列公式来计算 CRC 比特 $R$：
\[R = \text{remainder}\frac{D \cdot 2 ^ r}{G}\]在实际操作的时候，可以使用竖式除法来进行运算，最后取 $r$ 位的余数。所有将要被发送的数据是 $D + R$，一共 $d + r$ 位，注意不要漏掉。
随机接入协议
CSMA 载波侦听多路访问
CSMA 在 ALOHA 协议的基础上做了优化。
- 说话之前先听：载波侦听，carrier sensing，如果来自另一个节点的帧正向信道上发送，节点则等待到检测到一小段时间没有传输后才开始传输。
- 如果与他人同时开始说话，停止说话：碰撞检测，collision detecting，当传输的时候侦听信道，如果检测到另一个节点正在传输干扰帧，就停止传输。
CSMA/CD 具有碰撞检测的载波侦听多路访问
具有碰撞检测的 CSMA 的时空图。
使用二进制指数后退算法（binary exponential backoff algorithm），用于解决等待时间较长的问题。当传输一个帧时，该帧经历了一连串的 $n$ 次碰撞后，节点随机地从 ${0, 1, 2, …, 2 ^ n - 1}$ 中选择一个 $K$ 值。因此一个帧经历的碰撞越多（$n$ 越大），则 $K$ 选择的间隔越大。一个经历了 $n$ 次碰撞的帧的节点等概率选择任何一个 $K$ 值的概率都是
\[P = \frac{1}{2 ^ n}\]对于以太网（Ethernet），一个节点等待的实际时间是
\[T = K \cdot 512 比特时间\]即是 $K$ 乘上发送 512 比特进入以太网所用的时间。例如 100Mbps 的以太网，512 比特时间是 $5.12 \text{ms}$，然后乘以 $K$，以此类推。
地址解析协议
ARP
地址转换协议（Address Resolution Protocol, ARP）用于转换网络层地址（因特网的 IP 地址、域名）和链路层地址（MAC 地址）。
每台主机或路由器中存有一个 ARP 表，包含 IP 地址到 MAC 地址的映射关系。例如下面这个：
| IP 地址 | MAC 地址 | TTL |
|---|---|---|
| 222.222.222.221 | 88-B2-2F-54-1A-0F | 13:45:00 |
| 222.222.222.223 | 5C-66-AB-90-75-B1 | 13:52:00 |
发送方需要构造一个 ARP 分组，包括发送和接收 IP 地址及 MAC 地址。ARP 的查询分组和响应分组都有相同的格式，但是
- 查询 ARP 报文是在广播帧中发送的
- 响应 ARP 报文是在标准帧中发送的
ARP 表是自动建立的，无需管理员配置，即插即用。需要注意的是，可以把 ARP 看成是跨越链路层和网络层边界的协议。
发送数据报到子网之外
当主机 A 与主机 B 在同一个子网中时，数据报可以直接交付对方；当主机 A 与主机 B 不在同一个子网中时，不能直接交付。ARP 不能跨网段使用，只在局域网中使用。