概述

基本概念

结点：主机、路由器
链路：网络中两个结点之间的 物理通道
- 链路的传输介质主要有双绞线、光纤和微波
- 分为有线链路和无线链路
数据链路：网络中两个结点之间的 逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成了数据链路
帧(frame)：链路层的 协议数据单元(PDU)，封装网络层数据报
三个基本问题：封装成帧、透明传输、差错控制

数据链路层 负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报

功能概述

数据链路层在物理层提供服务的基础上 向网络层提供服务，其最基本的功能是将源自网络层的数据可靠地传输到相邻结点的目标机网络层。其主要作用是 加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为 逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路

功能一：为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务
- 有连接必然有确认
功能二：链路管理，即连接的创建、维持、释放（用于面向连接的服务）
功能三：组帧
功能四：流量控制（限制发送方）
功能五：差错控制（帧错/位错）

帧

封装成帧 就是在一段数据的前后部分添加首部和尾部，这样就形成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束

首部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确认帧的界限）
帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和结束

帧中的语法成分称为域或字段 (field)
帧浓缩了与数据链路层功能实现相关的各种机制
帧提高了数据处理和传输的效率
不同的链路层协议的帧格式可能会存在微小的区别

MTU：最大传输单元（Maximum Transmission Unit）

组帧的四种方法：

字符计数法
带字节/字符填充的标志字节法
带位填充的标志比特法
物理层编码违例法

透明传输

透明传输 是指不管所传数据是什么样子的比特组合，都应当能够在无差错的在链路上传送。因此，链路层就“看不见”有什么东西妨碍数据的传输。

当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取恰当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。

字符计数法

帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数

如果发生传输错误，则可能改变帧长的值，从而导致帧的同步出现问题

带字节/字符填充的标志字节法

每一帧以ASCII字符序列特殊的标志字节 FLAG + Header (SOH) 开始，以 FLAG + Trailer (EOT) 结束

缺点是成帧完全依赖于 FLAG 字符，而且若数据部分出现 FLAG，则接收端就会错误判断边界

字符填充法 可用于解决上述问题。即发送端在数据中所遇到的 FLAG 前再插入一个附加的 ESC，因此只要看到 FLAG 前有没有 ESC，就可以判断它是不是一个帧界符

遇到的 ESC 前面再加上一个 ESC，则接收端则忽略两个连续的 ESC 的前一个
任意比特数的帧不适用，必须是 8位整数倍

带位填充的标志比特法

每一帧使用一个 特殊的位模式“01111110” 作为开始和结束标记，又称为 flag

允许数据帧包含 任意个数 的比特，也允许每个字符采用任意比特的编码

当然这种方法当数据中出现 flag 时会混淆，所以采用 位填充法 解决：

在发送端，扫描整个信息字段，只要连续五个 1，就在其后填入一个 0，即 “逢五 1 插 0”
接收端先找到标志字段确定边界，然后扫描比特流，发现连续 5 个 1 时，就把后面的 0 删除，即 “逢五 1 删 0”

物理层编码违例法

利用物理层信息编码中未用的电信号来作为帧的边界

采用冗余编码技术，如曼切斯特编码，其中：数据 0：低-高电平对；数据 1：高-低电平对

高-高电平对 和 低-低电平对 没有使用，这两种违例编码真号可用作帧界符

在令牌环网中使用编码违例格式

差错控制

差错从何而来？

概括来说，传输中的差错是由于噪声引起的
全局性：由于线路本身电气特性所产生的 随机噪声（热噪声），是信道固有的，随机存在的。

解决方法：提高信噪比来减少或避免干扰（对传感器下手）

局部性：外界特定的短暂原因所造成的 冲击噪声，是产生差错的主要原因

解决方法：通常利用编码技术解决

差错分为：

位错：比特位出错
帧错：丢失、重复、失序

差错控制核心

发送端对传送的数据信息加上与其满足一定关系的冗余码，形成一个加强的、符合一定规律的发送序列。
所加入的冗余码称为 校验码。

接收端利用相同的规律进行检查从而发现错误。

检验码按校验错误能力的不同分为:
- 检错码：可以发现传输中的错误，但不能自动纠正所发现的错误。
  - 奇偶校验码、循环冗余码 CRC
- 纠错码：不仅能发现传输中的错误，还能利用纠错码中的信息自动纠正错误。
  - 海明码
物理层中的编码是针对 单个比特，解决的是比特同步问题；而链路层中针对的是 一组比特，解决的是传输过程中的差错控制。

检错码

奇偶检验码

水平奇偶检验：
在每个字符的 7 位信息码后附加一个校验位 0 或 1 ，使整个字符中“1”的个数构成奇数个（奇校验）或偶数个（偶校验）。

1 位检验 7 位
只能检查出 奇数个比特 错误，检错能力为 50%

垂直奇偶校验：
在发送字符块的末尾附加一个校验字符，且该字符中的第i位是针对所有字符的第i位所进行的校验。

垂直水平奇偶校验：
垂直奇偶校验和水平奇偶校验技术的综合。对每个字符作垂直校验，对整个字符块作水平校验。

CRC 循环冗余码

全称 Cyclic Redundancy Check

工作原理

多项式除法：被除多项式 = 除式 * 商 + 剩余多项式
通信双方约定除式，也就是 生成多项式，发送方将数据处理作为冗余信息发送给接收方
接收方验证所受到的多项式能否为除式所整除，以判断传输过程是否出错

步骤

加 0 ：若生成多项式 $G(x)$ $G (x)$ 的阶为 r，将信息位左移 r 位，即 $x^r M(x)$ $x^{r} M (x)$
- 生成多项式的阶为最高不为 0 位的阶
模 2 除法：求余数 $r(x)$ $r (x)$ ；余数由下式获得：$$ \frac{x^r M(x)}{G(x)} = Q(x) + r(x)$$
- 模 2 除法即异或：同 0 异 1
根据 $T(x) = x^rM(x) + r(x)$ $T (x) = x^{r} M (x) + r (x)$ ，求出最终要发送的数据
- 最终发送的数据 = 要发送的数据 + 帧检验序列FCS

帧检验序列 FCS

在数据后面添加上的冗余码称为 帧检验序列 FCS(Frame Check Sequence)

CRC 是一种常用的 检错方法，而 FCS 是添加在数据后面的 冗余码。
FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的惟一方法

检错

只要接收方将得到的数据模2除生成多项式，得到的余数 R 不为 0，就表示检测到了差错，但是不能确定出错的比特。
一旦出现差错，就丢弃这个出现差错的帧。

注意

CRC 只能做到无差错接受，不代表可靠传输

“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”
要做到可靠传输，必须加上确认和重传机制

纠错码 — 海明码

海明码：发现双 比特错，纠正单 比特错

海明不等式： $2^k \geq k+r+1$

海明码三要素：

添加k位校验位：2^k ≥ n+k+1 [传输n位，分成k组]
检测位的位置：2^i (i=0,1,……) [这一位不与其他组共用]

$C_{1}检测的g_{1}：1，3，5，7，9……$
$C_{2}检测的g_{2}：2，3，6，7，10……$
$C_{4}检测的g_{3}：4，5，6，7，12……$
$C_{8}检测的g_{4}：8，9，10，11，12……$

检测位的取值：所在小组中承担的 奇偶校验任务 有关

流量控制

较高的发送速度 和 较低的接收能力 的不匹配，会造成传输出错。

数据链路层的流量控制是 点对点，而传输层的流量控制是 端到端 的
- 数据链路层：接收方收不下就不回复确认
- 传输层：接收端给发送端一个窗口公告

停止-等待协议

每发送完一个帧就停止发送，等待对方的确认，在收到确后再发送下一帧

特殊的滑动窗口：发送窗口和接收窗口都是一帧

滑动窗口

发送、接收双方保持着一组同样的序列号，各自维持着一个窗口：发送窗口和接收窗口

确认帧到达后，发送窗口向前滑动一格
帧被正确接收，接收窗口向前滑动一格
只有在接收窗口向前滑动时，发送窗口的下限才有可能向前滑动

后退 N 帧协议（GBN）：发送窗口大小 > 1，接受窗口大小 = 1

选择重传协议（SR）：发送窗口大小 > 1，接受窗口大小 > 1

实现流量控制（收不下就不给确认）、可靠传输（发送方自动重传）

链路层服务

无确认的无连接服务(Unacknowledged connectionless service)
有确认的无连接服务(Acknowledged connectionless service)
有确认的面向连接的服务(Acknowledged connection-oriented service)

无确认无连接

源机器向目标机器发送独立的数据帧，而目的机器不对收到的帧作确认。

由于线路上的噪声而造成的帧丢失，数据链路层不作努力去恢复，而将该工作留给上层（通常为传输层）。

事先不存在建立连接，事后也不存在释放。

适用于误码率较低的信道，如大多数的局域网中

有确认无连接

事先不存在建立连接，事后也不存在释放。

源机器向目标机器发送独立的数据帧，但目的机器对收到的每一帧作确认。

若某个确定的时间间隔内未能收到确认帧（超时），则发送方自动重发。

适用于无线通信系统之类的不可靠信道

有确认有连接

传送数据前，事先要建立一条连接。

在连接上所传送的每一帧都要编上号，提供相应的确认和流量控制机制来保证每一帧都只被正确地接收一次，并保证所有帧都按正确的顺序被接收。

数据传输完成之后，需要释放所建立的连接。

真正为网络层提供了可靠的无差错传输服务。
适用于误码率较高的不可靠信道，如某些广域网链路。

数据链路层协议

停-等协议

协议1：一个无限制的单工信道

在这样 理想化 的条件下,数据的传输就非常简单（不需要有流量控制，也不需要有差错控制）。

步骤	发送方	接收方
1	从网络层接受一个分组	等待帧到达事件
2	将分组装入帧的信息域	从物理层接受一个帧
3	将帧传给物理层	从帧中取分组传给网络层
4	返回 1	返回 1

协议2：单工停-等协议

假定信道不会出错，但需要进行 流量控制。在这时引入反馈机制，要求接收端对于收到的每个帧都要给出响应

同时发送端在发出一帧后必须收到该帧的响应后才能发送下一个帧（停-等）。

步骤	发送方	接收方
1	从网络层接受一个分组	等待帧到达事件
2	将分组装入帧的信息域	从物理层接受一个帧
3	将帧传给物理层	从帧中取分组传给网络层
4	等待响应帧，收到后返回 1	回送响应帧并返回 1

由于一次只发送一帧，且该帧一定能正确到达，不会有重发的需要，因此也不需要帧序号。

协议3：有噪信道上的单工协议

假设信道会出错，而且接收端处理能力也有限，即 同时需要差错控制和流量控制

协议要点：
- 采用协议 2 的停-等方式
- 发送方每次只发送一个帧，当这个帧被正确接收后才能发送下一帧，若该帧未在规定的时间内得到确认（超时），则重发该帧；
- 接收端对每个收到的帧进行校验，对正确收到的帧发回确认，错误的帧丢弃；
由于需要区分新、旧两个帧，因此要 使用 1 比特的帧序号
发送完一个帧后，必须保留它的副本，以便重发

发送方

初始化（next_frame_to_send = 0）；
从网络层接收一个分组，放入缓冲区；
使用缓冲区中的分组和 next_frame_to_send 构造一个帧；
将帧传给物理层发送，并启动相关的计时器；
等待事件发生（帧到达，收到坏帧，超时）；
事件发生：
- 帧到达：从物理层接收一个帧，检查帧的 ack 域
  - 若是对所发帧的确认（ack = next_frame_to_send），终止相关的计时器，从网络层接收下一个分组放入缓冲区，发送序号加1，返回3；
  - 若不是对所发帧的确认，返回3；（缓冲区内容和发送序号均不变）
- 其它事件（收到坏帧，超时）：返回3；（缓冲区内容和发送序号不变）

接收方

初始化期待接收的帧序号（frame_expected = 0）；
等待帧的到达；
从物理层接收一个帧，检查帧的seq域：
- 若是期待接收的帧（seq = frame_expected），将帧中携带的分组交给网络层，frame_expected加1，执行 4 ；
- 若不是期待接收的帧（一个重复帧），执行 2；
发回确认帧（确认帧的 ack = 收到帧的 seq）；
返回 2。

滑动窗口协议

捎带确认(piggybacking)：将确认暂时延迟以便可以钩到下一个外发数据帧
推迟确认：当需要发送确认但没有要发送的数据进行捎带时，可以让确认信息推迟一小段时间再发送
自动重复请求 (ARQ)：是应用最广泛的一种差错控制技术，包括：无错接收的 PDU（协议数据单元）的肯定确认、对未确认 PDU（协议数据单元）的自动重传和丢弃。
- 接收方监测到数据中存在差错：发否认帧，立即启动重发；不理会，发送方超时重发

协议4：停止-等待式 ARQ

基本概念

每个待发送帧被赋予一个 序列号 seq
- seq 的取值范围是 0 ~ 2ⁿ - 1（n位字段）
建立缓冲区
- 发送窗口：缓存已发送、待确认的帧
  - 顺序接收来自网络层的分组,成帧,赋予序列号
  - 最多保存W个已经发送、等待确认的帧
  - 窗口达到最大值w时强制关闭网络层
- 接收窗口：缓存待接收的帧(序号)
  - 对进入窗口的顿顺序提交网络层,产生确认
  - 落在窗口外的帧被丢弃

基本工作原理

窗口设置
- 滑动窗口最大值：MAX = SEQ + 1
- 通信双方初始值：seq = 0, ack = 1（期待接收seq = 0）
窗口滑动机制
- A 首先发送数据帧(seq=0, ack=1, A0)
- B 收到 A0,发送捎带确认帧(seq=0, ack=0, BO)
- A 收到对 AO 的确认,滑动窗口,发送帧 (seq=1, ack=0, A1)
特点
- 序列号 seq 和确认值 ack：“0”、“1” 交替
- 滑动窗口长度 W = 1，发送、接收都是 1，收到确认才移动窗口
- 保证按顺序将接收到的正确帧只一次上交网络层

要点

连续出现相同发送序号的数据帧，表明发送端进行了 超时重传
连续出现相同序号的确认帧，表明接收端收到了 重复帧
发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本，以便重发
- 只有确认对方已经收到这个数据帧时，才可以清除这个副本

优缺点

优点：比较简单
缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满

协议5：回退 N 帧协议

接收方的接收策略选择：
- 丢弃错帧，其 后续帧 因不是期望接收帧 也被丢弃（接收窗口为 1）
发送方的重传策略选择：
- 缓存在发送窗口中的 出错帧以及其后续帧全部重发
提高了信道利用率，但是传送效率降低

基本概念

定义序列号 seq 的取值范围和滑动窗口长度 w
发送方连续发送至发送窗口满口
接收窗口为 1,对出错帧不确认（引发超时）
发送方超时重传,从未被确认帧开始

工作原理

累计确认：
- n 号帧的确认到达时，蕴含着：n-1、n-2…n 号帧之前的帧也被确认
- 当采用了累计确认,收到了 n 帧的确认, n 帧之前的帧都可从缓存中删掉。
接收方要做的事：
- 如果正确收到 n 号帧，并且按序，那么回复 ack，并将该帧中的数据部分交付给上层
- 其余情况都丢弃帧，并为 最近按序接受的帧 重发 ack。接收方 无需缓存任何失序帧，只需维护一个信息：expected seq num（下一个按序接收的帧序号）

注意点

接收端 只按序接收 数据帧。
超时事件
- 协议名字为后退 N 帧(Go Back N)，源于出现丢失和超时的时候，发送方的行为。当出现差错必须重传时，要向 回走 N 个帧，然后再开始重传。
- 在每发送完一个数据帧时都要设置该帧的 超时计时器
  - 如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。
  - 但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。
滑动窗口大小：
- 发送窗口： $1 \leq W_{T} \leq 2^n - 1$
- 接收窗口：1

协议6：选择重传协议

可 加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机
选择重传 ARQ 协议可 避免重复传送 那些本来已经正确到达接收端的数据帧。
在接收端要设置具有相当容量的缓存空间
接收窗口 $W_{R} \leq 2^{n-1}$

工作原理

来者不拒（窗口内的帧）
- SR 接收方将 确认一个正确接收的帧，而不管是否按序。
- 失序的帧会被缓存，并 返回接收方一个该帧的确认帧
- 直到所有帧（即序号更小的帧）皆被收到为止，这时候才滑动窗口，然后将数据交付上层
- 如果收到了窗口之前的帧，回复该帧的确认；如果在窗口之后，则丢弃

重点

对数据帧逐一确认，收一个确认一个
只重传出错帧
接收方有缓存

窗口大小

发送窗口最好等于接收窗口
$W_{Tmax} = W_{Rmax} = 2^{n-1}$ $W_{T m a x} = W_{R m a x} = 2^{n - 1}$
- 保证新老窗口不重叠

回退 N 帧 VS 选择重传

回退 N 帧
- 发送方需要较大的缓冲区,以便重传
- 重传帧数多,适于信道出错率较少的情况
- 滑动窗口大小：
  - 发送窗口： $1 < W_{T} \leq 2^n - 1$
  - 接收窗口：1
选择重传
- 接收方需要较大的缓冲区,以便按正确顺序将分组提交网络层
- 重传帧数少,适于信道质量不好的情况
- 滑动窗口大小：
  - 发送窗口： $1 < W_{T} \leq 2^{n - 1}$
  - 接收窗口： $1 < W_{R} \leq 2^{n - 1}$

信道利用率

$信道利用率 = \frac{W * T_f}{T_f + R} = \frac{W * k}{k + bR}$

W 滑动窗口大小， $T_f$ 发送时延，R 传输时延（双程）、k 数据帧长度、b 信道容量（传输速度）

链路利用率

$链路利用率 = \frac{w}{1+2BD}$

假定确认了帧的大小，用带宽延迟积除以帧的大小得到信道上同时存在的帧的数量，称为 $BD$
链路利用率的理论上限为 $w/(1+2BD)$ ，其中 w 最大等于 $1+2BD$
这是一个上限值，它不允许有任何帧的处理时间，并且视确认帧的长度为零