期末速通（？）⚓︎

约 9562 个字预计阅读时间 48 分钟

注意

说是「速通」，但鉴于我说话罗里吧嗦的坏习惯，笔记篇幅可能又会拖的很长，请见谅🙏

概述⚓︎

Internet⚓︎

网络 (network)：由若干链路和节点互连形成

互联网(internet)：若干网络通过路由器互连形成，网络的网络

因特网(Internet) 是世界上最大的互联网。

三个阶段：
因特网服务提供者(Internet Service Provider, ISP)
因特网已发展成为基于 ISP 的多层次结构的互连网络
标准化工作
- 面向公众：其任何一个建议标准在成为因特网标准之前都以 RFC 技术文档的形式在因特网上发表
- RFC（请求评论，Request For Comments）：任何人都可以从因特网上免费下载 RFC 文档（http://www.ietf.org/rfc.html），并随时对某个 RFC 文档发表意见和建议
管理机构：

电路交换、分组交换和报文交换⚓︎

电路交换：
- 计算机之间的数据传送是突发式的，当使用电路交换来传送计算机数据时，其线路的传输效率一般都会很低，线路上真正用来传送数据的时间往往不到 10% 甚至 1%。
分组交换：
- 发送方：构造并发送分组
- 交换节点：缓存并转发分组
- 接收方：接受分组，还原报文
- 优点：
  - 没有建立连接和释放连接的过程
  - 分组传输过程中逐段占用通信链路，有较高的通信线路利用率
  - 交换节点可以为每一个分组独立选择转发路由，使得网络有很好的生存性
- 缺点：
  - 分组首部带来了额外的传输开销
  - 交换节点存储转发分组会造成一定的时延
  - 无法确保通信时端到端通信资源全部可用，在通信量较大时可能造成网络拥塞
  - 分组可能会出现失序和丢失等问题
报文交换：
- 分组交换的前身
- 报文被整个地发送，而不是拆分成若干个分组进行发送
- 交换节点将报文整体接收完成后才能查找转发表，将整个报文转发到下一个节点
- 因此相比分组交换带来的转发时延要长很多，需要交换节点具有的缓存空间也大很多

三种交换方式的对比：

若要连续传送大量的数据，并且数据传送时间远大于建立连接的时间，则使用电路交换可以有较高的传输效率；然而计算机的数据传送往往是突发式的，采用电路交换时通信线路的利用率会很低
报文交换和分组交换都不需要建立连接（即预先分配通信资源），在传送计算机的突发数据时可以提高通信线路的利用率
将报文构造成若干个更小的分组进行分组交换，比将整个报文进行报文交换的时延要小，并且还可以避免太长的报文长时间占用链路，有利于差错控制，同时具有更好的灵活性

定义和分类⚓︎

「计算机网络」一词没有精确统一的定义。不同阶段的不同定义反映当时计算机网络技术的发展水平。

现阶段计算机网络的一个较好的定义：计算机网络主要是由一些通用的、可编程的硬件互连而成的，而这些硬件并非专门用来实现某一特定目的（例如，传送数据或视频信号）。这些可编程的硬件能够用来传送多种不同类型的数据，并能支持广泛的和日益增长的应用。

可编程的硬件：不限于计算机，而是包括了智能手机、具有网络功能的传感器以及智能家电等智能硬件，这些硬件一定包含有 CPU
各类应用：基于数据传送实现各种各样的应用，包括今后可能出现的各种应用

分类：

交换方式：电路 / 报文 / 分组交换（见前一节）
使用者：
- 公用网：因特网
- 专用网：军队、铁路、电力、银行
传输介质：
覆盖范围：
- 广域网（WAN）：几十到几千千米
- 城域网（MAN）：5-50 km
- 局域网（LAN）：~1 km
- 个域网（PAN）10 m
拓扑结构：
- 总线型
- 星型
- 环型
- 网状型

性能指标⚓︎

速率：数据的传送速率（即每秒传送多少个比特），也称为数据率 (data rate) 或比特率 (bit rate)
- 基本单位是比特 / 秒（bit/s，可简记为 b/s，有时也记为 bps (bit per second)）
- 常用单位：
  - 千比特 / 秒（kb/s 或 kbps）= 10³ bps
  - 兆比特 / 秒（Mb/s 或 Mbps）= 10⁶ bps
  - 吉比特 / 秒（Gb/s 或 Gbps）= 10⁹ bps
  - 太比特 / 秒（Tb/s 或 Tbps）= 10¹² bps
带宽：表示网络的通信线路所能传送数据的能力，即在单位时间内从网络中的某一点到另一点所能通过的最高数据率
- 单位：同「速率」
- 数据传送速率 = min[ 主机接口速率，线路带宽，交换机或路由器的接口速率 ]（短板效应）
吞吐量：在单位时间内通过某个网络或接口的实际数据量，常被用于对实际网络的测量，以便获知到底有多少数据量通过了网络
- 受网络带宽的限制
时延：数据从网络的一端传送到另一端所耗费的时间，也称为延迟或迟延；数据可由一个或多个分组、甚至是一个比特构成
- 发送时延 = 分组长度（b）/ 发送速率（b/s）
  - 发送速率 = min[ 主机接口速率，线路带宽，交换机或路由器的接口速率 ]
- 传播时延 = 信道长度（m）/ 信号传播速率（m/s）
- 排队时延和处理时延不方便计算
时延带宽积：传播时延和带宽的乘积
- 也称为以比特为单位的链路长度，这对我们以后理解以太网的最短帧长是非常有帮助的
往返时间(round-trip time, RTT)：从发送端发送数据分组开始，到发送端收到接收端发来的相应确认分组为止，总共耗费的时间
- 可使用 ping 命令查看
利用率
- 链路利用率：某条链路有百分之几的时间是被利用的（即有数据通过）；完全空闲的链路的利用率为零
- 网络利用率：网络中所有链路的链路利用率的加权平均
- 根据排队论可知，当某链路的利用率增大时，该链路引起的时延就会迅速增加
- 当网络的通信量较少时，产生的时延并不大，但在网络通信量不断增大时，分组在交换节点（路由器或交换机）中的排队时延会随之增大，因此网络引起的时延就会增大
- 令 $D_0$ 表示网络空闲时的时延，$D$ 表示网络当前的时延，那么在理想的假定条件下，可用下式来表示 $D, D_0$ 和网络利用率 $U$ 之间的关系：
  
  \[ D = \frac{D_0}{1 - U} \]
- 一些大型 ISP 往往会控制信道利用率不超过 50%；如果超过了就要进行扩容，增大线路的带宽
丢包率：在一定的时间范围内，传输过程中丢失的分组数量与总分组数量的比率
- 分为接口 / 节点 / 链路 / 路径 / 网络丢包率
- 分组丢失主要有以下两种情况：
  - 分组在传输过程中出现误码，被传输路径中的节点交换机（例如路由器）或目的主机检测出误码而丢弃
  - 节点交换机根据丢弃策略主动丢弃分组
- 丢包率可以反映网络的拥塞情况：
  - 无拥塞时路径丢包率为 0
  - 轻度拥塞时路径丢包率为 1%~4%
  - 严重拥塞时路径丢包率为 5%~15%

体系结构⚓︎

OSI 标准失败的原因

专家没有实际经验，完成标准时没有商业驱动力
协议实现过分复杂，运行效率很低
标准的制定周期太长，产品无法及时进入市场
层次划分不太合理，有些功能在多个层次中重复出现

TCP/IP 体系结构：

体系结构分层的必要性

计算机网络是个非常复杂的系统，“分层”可将庞大复杂的问题转化为若干较小的局部问题（高内聚低耦合）。

物理层：
- 采用什么传输介质（物理层之下）
- 采用什么物理接口
- 采用什么信号表示比特 0 和 1
数据链路层：
- 标识网络中各主机（主机编址，例如 MAC 地址）
- 从比特流中区分出地址和数据（数据封装格式）
- 协调各主机争用总线（介质接入控制）
- 以太网交换机的实现（自学习和转发帧）
- 检测数据是否误码（差错检测）
- 出现传输差错如何处理（可靠传输和不可靠传输）
- 接收方控制发送方注入网络的数据量（流量控制）
网络层：
- 标识网络和网络中的各主机（网络和主机共同编址，例如 IP 地址）
- 路由器转发分组（路由选择协议、路由表和转发表）
运输层：
- 进程之间基于网络的通信（进程的标识，例如端口号）
- 出现传输差错如何处理（可靠传输和不可靠传输）
应用层：
- 通过应用进程间的交互来完成特定的网络应用
- 进行会话管理和数据表示

专业术语：

实体：解决通过应用进程的交互来实现特定网络应用的问题
- 对等实体：通信双方相同层次中的实体
协议：控制两个对等实体在“水平方向” 进行“逻辑通信”的规则的集合；协议三要素：
- 语法：定义所交换信息的格式
- 语义：定义通信双方所要完成的操作
- 同步：定义通信双方的时序关系
服务：
- 在协议的控制下，两个对等实体在水平方向的逻辑通信使得本层能够向上一层提供服务
- 要实现本层协议，还需要使用下面一层所提供的服务
- 协议是“水平”的，而服务是“垂直”的
- 实体看得见下层提供的服务，但并不知道实现该服务的具体协议；下层的协议对上层的实体是“透明”的
- 在同一系统中相邻两层的实体交换信息的逻辑接口称为服务访问点（SAP），它被用于区分不同的服务类型
- 帧的“类型”字段、IP 数据报的“协议”字段，TCP 报文段或 UDP 用户数据报的“端口号”字段都是 SAP
- 上层要使用下层所提供的服务，必须通过与下层交换一些命令，这些命令称为服务原语
- 对等层次之间传送的数据包称为该层的协议数据单元(protocol data unit，PDU)
- 同一系统内层与层之间交换的数据包称为服务数据单元(service data unit，SDU)

物理层⚓︎

物理层接口有以下特性：

机械特性：
- 形状和尺寸
- 引脚数目和排列
- 固定和锁定装置
电气特性：
- 信号电压的范围
- 阻抗匹配的情况
- 传输速率
- 距离限制
功能特性：规定接口电缆的各条信号线的作用
过程特性：规定在信号线上传输比特流的一组操作过程，包括各信号间的时序关系

传输介质⚓︎

传输介质(transimission media)：计算机网络设备之间的物理通路，不包含在计算机网络体系结构中（物理层之下）。

导向性传输介质⚓︎

同轴电缆(coaxial cable)
- 分类：
  - 基带同轴电缆（50 Ω）：用于数字传输，在早期局域网中广泛使用
  - 宽带同轴电缆（75 Ω）：用于模拟传输，目前主要用于有线电视的入户线
- 同轴电缆价格较贵且布线不够灵活和方便；随着技术的发展和集线器的出现，在局域网领域基本上都采用双绞线作为传输介质
双绞线(twisted pair)
- 绞合的作用：
  - 减少相邻导线间的电磁干扰
  - 抵御部分来自外界的电磁干扰
光纤(fiber optics)
- 光纤通信利用光脉冲在光纤中的传递来进行通信
- 由于可见光的频率非常高（约为 108MHz 量级），因此一个光纤通信系统的传输带宽远大于目前其他各种传输介质的带宽
- 剖面图：
- 当光从高折射率的介质射向低折射率的介质时，其折射角大于入射角
- 如果入射角足够大，就会出现全反射，即光碰到包层时，就会反射回纤芯
- 光在光纤中传输的方式是不断地全反射
- 多条光波在多模光纤中不断地全反射
- 分类：
- 25000~30000GHz 的带宽光纤的通信容量很大
- 常用的三个光波波段的中心波长分别为
  - 850nm：衰减较大，但其他特性较好
  - 1300nm：衰减较小
  - 1550nm：衰减较小
- 优点：
  - 通信容量非常大
  - 抗雷电和电磁干扰性能好
  - 传输损耗小，中继距离长
  - 无串音干扰，保密性好
  - 体积小，重量轻
- 缺点：
  - 切割光纤需要较贵的专用设备
  - 目前光电接口还比较昂贵

非导向性传输介质⚓︎

无线电波
微波
红外线
- 设备：电视 / 空调遥控器
- 红外通信已被淘汰
激光
可见光

传输方式⚓︎

串行传输和并行传输⚓︎

同步传输和异步传输⚓︎

同步传输

收发双方时钟同步的方法：
- 外同步：在收发双方之间增加一条时钟信号线
- 内同步：发送端将时钟信号编码到发送数据中一起发送（例如曼彻斯特编码）
异步传输
- 字节之间异步，即字节之间的时间间隔不固定
- 字节中的每个比特仍然要同步，即各比特的持续时间是相同的

单向通信、双向交替通信和双向同时通信⚓︎

编码与调制⚓︎

基本概念⚓︎

码元(symbol)：在使用时间域的波形表示信号时，代表不同离散数值的基本波形。

常用编码方式⚓︎

双极性不归零编码（NRZ）：编码效率高，但存在同步问题

接收方如何判断码元？
- 需要给收发双方再添加一条时钟信号线
- 发送方通过数据信号线给接收方发送数据的同时，还通过时钟信号线给接收方发送时钟信号
- 接收方按照接收到的时钟信号的节拍，对数据信号线上的信号进行采样
- 对于计算机网络，宁愿利用这根传输线传输数据信号，而不是传输时钟信号
双极性归零编码：
- 在每个码元的中间时刻信号都会回归到零电平
- 接收方只要在信号归零后采样即可
- 归零编码相当于将时钟信号用“归零”方式编码在了数据之内，这称为“自同步”信号
- 然而，归零编码中大部分的数据带宽，都用来传输“归零”而浪费掉了
曼彻斯特编码：
- 码元中间时刻的电平跳变既表示时钟信号，也表示数据
- 正跳变表示 1 还是 0，负跳变表示 0 还是 1，可以自行定义
- 问题：带宽开销增大了一倍
差分曼彻斯特编码（又称为 NRZI(NRZ Invert)）：
- 码元中间时刻的电平跳变仅表示时钟信号，而不表示数据
- 数据的表示在于每一个码元开始处是否有电平跳变：无跳变表示 1，有跳变表示 0
- 在传输大量连续 1 或连续 0 的情况下，差分曼彻斯特编码信号比曼彻斯特编码信号的变化少
- 在噪声干扰环境下，检测有无跳变比检测跳变方向更不容易出错，因此差分曼彻斯特编码信号比曼彻斯特编码信号更易于检测
- 在传输介质接线错误导致高低电平翻转的情况下，差分曼彻斯特编码仍然有效

基本的带通调制方法和混合调制方法⚓︎

基本的带通调制方法：

混合调制方法：

因为载波的频率和相位是相关的，即频率是相位随时间的变化率，所以载波的频率和相位不能进行混合调制
通常情况下，载波的相位和振幅可以结合起来一起调制，例如正交振幅调制 QAM

正交振幅调制 QAM-16：

12 种相位
每种相位有 1 或 2 种振幅可选
可以调制出 16 种码元（波形），每种码元可以对应表示 4 个比特（$\log_2 16=4$）
每个码元与 4 个比特的对应关系采用格雷码(Gray code)，即任意两个相邻码元只有 1 个比特不同

信道的极限容量⚓︎

造成信号失真的主要因素⚓︎

码元的传输速率：传输速率越高，信号经过传输后的失真就越严重
信号的传输距离：传输距离越远，信号经过传输后的失真就越严重
噪声干扰：噪声干扰越大，信号经过传输后的失真就越严重
传输媒体的质量：传输媒体质量越差，信号经过传输后的失真就越严重

信道上传输的数字信号，可以看做是多个频率的模拟信号进行多次叠加后形成的方波
如果数字信号中的高频分量在传输时受到衰减甚至不能通过信道，则接收端接收到的波形前沿和后沿就变得不那么陡峭，每一个码元所占的时间界限也不再明确。这样，在接收端接收到的信号波形就失去了码元之间的清晰界限，这种现象称为码间串扰
如果信道的频带越宽，则能够通过的信号的高频分量就越多，那么码元的传输速率就可以更高，而不会导致码间串扰
然而，信道的频率带宽是有上限的，不可能无限大，因此码元的传输速率也有上限

奈氏准则⚓︎

奈氏准则 (Nyquist's Theorem)

理想低通信道的最高码元传输速率 = 2W Baud = 2W 码元 / 秒

W：信道的频率带宽（单位为 Hz）
Baud：波特，即码元 / 秒

使用奈氏准则给出的公式，就可以根据信道的频率带宽，计算出信道的最高码元传输速率
只要码元传输速率不超过根据奈氏准则计算出的上限，就可以避免码间串扰
奈氏准则给出的是理想低通信道的最高码元传输速率，它和实际信道有较大的差别；因此，一个实际的信道所能传输的最高码元传输速率，要明显低于奈氏准则给出的上限值

波特率与比特率的关系：

当 1 个码元只携带 1 比特的信息量时，波特率与比特率在数值上是相等的
当 1 个码元携带 n 比特的信息量时，波特率转换成比特率时，数值要乘以 n

不可以无限制地提高信息的传输速率，因为在实际的信道中会有噪声。噪声是随机产生的，其瞬时值有时会很大，这会影响接收端对码元的识别，并且噪声功率相对于信号功率越大，影响就越大。

香农公式⚓︎

香农公式 (Shannon's Theorem)

带宽受限且有高斯白噪声干扰的信道的极限信息传输速率为： $$ C = W \log_2 (1 + \frac{C}{N}) $$

$C$：信道的极限信息传输速率（单位为 b/s）
$W$：信道的频率带宽（单位为 Hz）
$S$：信道内所传信号的平均功率
$N$：信道内的高斯噪声功率
$S/N$：信噪比，使用分贝（dB）作为度量单位 = $10 \log_{10} \left( \dfrac{S}{N} \right)$

信道的频率带宽 $W$ 或信道中的信噪比 $S/N$ 越大，信道的极限信息传输速率 $C$ 就越高
实际信道不可能无限制地提高频率带宽 $W$ 或信道中的信噪比 $S/N$
实际信道中能够达到的信息传输速率，要比香农公式给出的极限传输速率低不少，这是因为在实际信道中，信号还要受到其他一些损伤，例如各种脉冲干扰和信号衰减等，这些因素在香农公式中并未考虑

在信道的频率带宽 $W$ 一定的情况下，根据奈氏准则和香农公式，要想提高信息的传输速率，就必须采用多元制（更复杂的调制技术），并努力提高信道中的信噪比。

自从香农公式发表后，各种新的信号处理和调制方法就不断出现，其目的都是为了使码元可以携带更多个比特，进而可以尽可能地接近香农公式给出的传输速率极限。

信道复用技术⚓︎

基本原理⚓︎

复用(multiplexing)：在一条传输媒体上同时传输多路用户的信号
当一条传输媒体的传输容量大于多条信道传输的总容量时，就可以通过复用技术，在这条传输媒体上建立多条通信信道，以便充分利用传输媒体的带宽
尽管实现信道复用会增加通信成本（需要复用器、分用器以及费用较高的大容量共享信道），但如果复用的信道数量较大，还是比较划算的

常用技术⚓︎

频分复用（FDM）：所有用户同时占用不同的频带资源并行通信
时分复用（TBM）：所有用户在不同的时间占用同样的频带
波分复用（WDM）
- 根据频分复用的设计思想，可在一根光纤上同时传输多个频率（波长）相近的光载波信号，实现基于光纤的频分复用技术
- 目前可以在一根光纤上复用 80 路或更多路的光载波信号，因此这种复用技术也称为密集波分复用 DWDM
- 铺设光缆的工程耗资巨大，应尽量在一根光缆中放入尽可能多的光纤，然后对每一根光纤使用密集波分复用技术
码分复用（CDM）
- 常称为码分多址 (code division multiple access, CDMA)，它是在扩频通信技术的基础上发展起来的一种无线通信技术
- 每个用户可以在相同的时间使用相同的频带进行通信
- 最初用于军事通信，这种系统发送的信号有很强的抗干扰能力，其频谱类似于白噪声，不易被敌人发现；随着技术的进步，CDMA 设备的价格和体积都大幅度下降，因而现在已广泛用于民用的移动通信中
- 将每个比特时间划分为 m 个更短的时间片，称为码片(chip)；m 的取值通常为 64 或 128（为了简单起见，在后续的举例中假设 m 的取值为 8）
- CDMA 中的每个站点都被指派一个唯一的 m 比特码片序列
  - 某个站要发送比特 1，则发送它自己的 m 比特码片序列
  - 某个站要发送比特 0，则发送它自己的 m 比特码片序列的反码
- 如果有两个或多个站同时发送数据，则信道中的信号就是这些站各自所发送一系列码片序列或码片序列反码的叠加
- 为了从信道中分离出每个站的信号，给每个站指派码片序列时，必须遵循以下规则：
  - 分配给每个站的码片序列必须各不相同，实际常采用伪随机码序列
  - 分配给每个站的码片序列必须相互正交，即各码片序列相应的码片向量之间的归一化内积为 0
- 令向量 A 表示站 A 的码片向量，向量 B 表示站 B 的码片向量；两个不同站 A 和 B 的码片序列相互正交，就是向量 A 与向量 B 的归一化內积为 0，即：
  
  \[ A \cdot B = \frac{1}{m} \sum_{i=1}^m A_i B_i = 0 \]

数据链路层⚓︎

链路 (link)：从一个节点到相邻节点的一段物理线路（有线或无线），中间没有任何其他的交换节点
数据链路 (data link)：当在一条链路上传送数据时，除需要链路本身，还需要一些必要的通信协议来控制这些数据的传输，把实现这些协议的硬件和软件加到链路上，就构成了数据链路
- 计算机中的网络适配器（俗称网卡）和其相应的软件驱动程序就实现了这些协议；一般的网络适配器都包含了物理层和数据链路层这两层的功能
帧(frame)：数据链路层对等实体之间在水平方向进行逻辑通信的 PDU（协议数据单元）

三个问题⚓︎

封装成帧和透明传输⚓︎

封装成帧：数据链路层为上层交付下来的 PDU 添加帧首部和帧尾部，使之成为帧
- 帧的首部和尾部中包含有一些重要的控制信息
- 帧首部和尾部的作用之一就是帧定界
  - 但并不是每一种数据链路层协议的帧都包含有帧定界标志（比如以太网 V2 的 MAC 帧）
- 为了提高传输帧的效率，应当使帧的数据载荷的长度尽可能地大于首部和尾部的长度
- 考虑到对缓存空间的需求以及差错控制等诸多因素，每一种数据链路层协议都规定了帧的数据载荷的长度上限，即最大传送单元(maximum transfer unit，MTU)
透明传输：使数据链路层对上层交付的 PDU 的内容没有任何限制，就好像数据链路层不存在一样
- 面向字节的物理链路使用字节填充的方法实现透明传输
- 面向比特的物理链路使用比特填充的方法实现透明传输

差错检测⚓︎

帧在传输的过程中可能出现误码
- 比特在传输过程中可能会产生差错（称为比特差错），比特 1 可能变成比特 0，反之也有可能
- 在一段时间内，传输错误的比特数量占所传输比特总数的比率称为误码率(bit error rate，BER)
- 提高链路的信噪比，可以降低误码率；但在实际的通信链路上，不可能使误码率下降为零
接收方根据发送方添加在帧尾部中的检错码，可以检测出帧是否出现了误码
- 奇偶校验：
  - 奇校验是在待发送的数据后面添加 1 个校验位，使得添加该校验位后的整个数据中比特 1 的个数为奇数
  - 偶校验是在待发送的数据后面添加 1 个校验位，使得添加该校验位后的整个数据中比特 1 的个数为偶数
  - 在所传输的数据中，如果有奇数个位发生误码，则所包含比特 1 的数量的奇偶性会发生改变，可以检测出误码
  - 在所传输的数据中，如果有偶数个位发生误码，则所包含比特 1 的数量的奇偶性不会发生改变，无法检测出误码（漏检）
  - 在实际使用时，奇偶校验又可分为垂直奇偶校验、水平奇偶校验以及水平垂直奇偶校验
- 循环冗余校验(cyclic redundancy check，CRC)：
  - 数据链路层广泛使用这一漏检率极低的技术，因为虽然计算比较复杂，但非常易于用硬件实现
  - 基本思想：
    - 收发双方约定好一个生成多项式 $G(X)$
    - 发送方基于待发送的数据和 $G(X)$，计算出差错检测码（冗余码），将冗余码添加到待发送数据的后面一起传输
      
      冗余码计算步骤：
      1. 构造被除数：待发送数据后面添加生成多项式最高次数个 0
      2. 构造除数：生成多项式各项系数构成的比特串作为除数
      3. 做二进制模 2 除法：相当于对应位进行逻辑异或运算
      4. 检查余数：余数的位数应与生成多项式最高次数相同，如果位数不够，则在余数前补 0 来凑足位数
    - 接收方收到数据和冗余码后，通过 $G(X)$ 来计算收到的数据和冗余码是否产生了误码
      
      具体步骤：
      1. 构造被除数：接收到的信息作为被除数
      2. 构造除数：生成多项式各项系数构成的比特串作为除数
      3. 做二进制模 2 除法：相当于对应位进行逻辑异或运算
      4. 检查余数：余数为 0，可认为传输过程无误码；余数不为 0，可认为传输过程产生了误码
  - 生成多项式：

奇偶校验、循环冗余校验等差错检测技术，只能检测出传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。要想纠正传输中的差错，可以使用冗余信息更多的纠错码（例如海明码）进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。

在计算机网络中，通常采用之后介绍的检错重传方式来纠正传输中的差错，或者仅仅丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务还是不可靠传输服务。

海明码

目标：以奇偶校验为基础，如何找到出错位置，提供 1 位纠错能力。

下面以 (15, 11) 海明码为例来理解海明码的编码过程：

假设有一个 11 比特的数据 01011001101（如右图所示），将其按顺序放入数据位
校验位为 2 的幂次方位（记为 p1, p2, p4, p8）；每个校验位对数据位的子集做校验，缩小定位错误的范围
- 海明码缺省为偶校验（也可以使用奇校验）
子集的选择与校验位计算
定位错误与纠正（假如第 7 位出错）
- 组 1 和组 2 的校验结果可以定位错误所在的列
- 组 3 和组 4 的校验结果可以定位错误所在的行

可靠传输⚓︎

不可靠传输服务：收到有误码的帧，直接丢弃，其他什么也不做；未收到发送方发送的帧，也不进行任何处理
可靠传输服务：实现发送方发送什么，接收方最终都能正确收到
一般情况下，有线链路的误码率比较低，因此为了减小开销，并不要求数据链路层向其上层提供可靠传输服务；即使出现了误码，可靠传输的问题由其上层处理
无线链路易受干扰，误码率比较高，因此要求数据链路层必须向其上层提供可靠传输服务
传输差错（前面三种情况出现在数据链路层的上层，最后一种出现在数据链路层及其下层）：
- 误码（比特差错）：前面刚介绍过
- 分组丢失：输入队列快满了，主动丢弃收到的分组
- 分组失序：分组到达顺序与发送顺序不同
- 分组重复：路由器繁忙，分组在输入队列中等待较长时间，导致发送端超时重发，最终接收端收到多个相同分组
可靠传输服务并不局限于数据链路层，其他各层均可选择实现可靠传输
可靠传输的实现比较复杂，开销比较大，是否使用可靠传输取决于应用需求

停止 - 等待协议

实现原理：
- 接收方收不到数据分组，就不会发送相应的 ACK 或 NAK；如果不采取措施，发送方就会一直处于等待接收方 ACK 或 NAK 的状态
- 为解决上述问题，发送方可在每发送完一个数据分组时就启动一个超时计时器(timeout timer)
- 若到了超时计时器所设置的超时重传时间(retransmission time-out，RTO)，但发送方仍未收到接收方的 ACK 或 NAK，就重传之前已发送过的数据分组；一般可将 RTO 设置为略大于收发双方的平均往返时间 RTT
- 为了避免分组重复这种传输错误，必须给每个分组带上序号；对于停止 - 等待协议，由于每发送一个数据分组就停止等待，只要保证每发送一个新的数据分组，其序号与上次发送的数据分组的序号不同就可以了，因此用一个比特来编号就够了（0/1）
- 若接收方收到重复的数据分组，则将其丢弃，并再发送一个确认分组；其中确认分组需要编号，避免发送方搞错确认分组对应的数据分组，所用比特数量与数据分组所用比特数量一样
注意事项
- 使用超时重传机制后，就可以不使用否认机制了，这样可使协议实现起来更加简单；但如果点对点链路的误码率较高，使用否认机制可以使发送方在超时计时器超时前就尽快重传
- 停止 - 等待协议属于自动请求重传(automatic repeat request，ARQ) 协议，即重传的请求是发送方自动进行的，而不是接收方请求发送方重传某个误码的数据分组
信道利用率：
- 若出现超时重传，对于传送有用的数据信息来说，信道利用率还要降低
- 在 RTT 相对较大的情况下，为了提高信道利用率，收发双方不适合采用停止 - 等待协议，而可以选择使用回退 N 帧（GBN）协议或选择重传（SR）协议

回退 N 帧协议(go-back-N, GBN)：

采用流水线传输可以显著提高信道利用率
此时发送方不能无限制地连续发送数据分组，否则可能会导致网络中的路由器或接收方来不及处理这些数据分组，进而导致数据分组的丢失，这实际上是对网络资源的浪费
因此回退 N 帧协议除了采用流水线传输方式，还利用发送窗口来限制发送方连续发送数据分组的数量，这属于连续 ARQ 协议
采用 $n$ 个比特给分组编序号，序号范围是 $0 \sim (2^n - 1)$（本例假设采用 3 个比特给分组编序号）
发送方需要维护一个发送窗口 $W_T$（范围为 $1 < W_T \le (2^n - 1)$），在未收到接收方确认分组的情况下，发送方可将序号落入 $W_T$ 内的所有数据分组连续发送出去（本例取 $W_T = 5$）
接收方需要维护一个接收窗口 $W_R$，只有正确到达接收方（无误码）且序号落入 $W_R$ 内的数据分组才被接收方接收；$W_R$ 的取值只能是 1，这一点与停止 - 等待协议是相同的
接收方每正确收到一个序号落入接收窗口的数据分组，就将接收窗口向前滑动一个位置，这样就有一个新的序号落入接收窗口；与此同时，接收方还要给发送方发送针对该数据分组的确认分组
发送方每收到一个按序确认的确认分组，就将发送窗口向前滑动一个位置，这样就有一个新的序号落入发送窗口，序号落入发送窗口内的数据分组可继续被发送
在回退 N 帧协议的工作过程中，发送方的发送窗口和接收方的接收窗口按上述规则不断向前滑动（因该类协议又称为滑动窗口协议）

无差错的情况超时重传、回退 N 帧的情况

在无传输差错的情况下，回退 N 帧协议的信道利用率比停止 - 等待协议的信道利用率有显著提高；提高的程度取决于发送窗口的大小。

一个数据分组的差错就可能引起大量数据分组的重传
在信道质量较差（容易出现误码）的情况下，回退 N 帧协议的信道利用率并不比停止 - 等待协议的信道利用率高

接收方采用累积确认的方式：

接收方不必对收到的每一个数据分组都发送一个确认分组，而是可以在收到几个序号连续的数据分组后，对按序到达的最后一个数据分组发送确认分组
接收方何时发送累积确认分组，由具体实现决定
确认分组 ACKn 表明序号为 n 及之前的所有数据分组都已正确接收

优点：
- 减少向网络中注入确认分组的数量
- 即使确认分组丢失，也可能不必重传数据分组
缺点：不能向发送方及时准确地反映出接收方已正确接收的所有数据分组的数量

问题

若 $W_T$ 超过取值范围（例如 $W_T = 8$），会出现什么情况？