计算机网络 Chap.3 数据链路层

本系列计算机网络博文基于Bilibili王道的免费考研课程整理而来, 目的在于系统的梳理计算机专业课的基础知识, 并为将来的面试做好充分的准备.

除本系列外, 计算机考研相关还包括数据结构 / 操作系统 / 计算机组成原理的相关内容.

3.1 数据链路层的功能

我们还是得把老图搬过来, 倒腾一下数据链路层的位置:

数据链路层上接网络层, 下接物理层. 因此其主要负责两件事:

• 使用物理层提供的 比特传输 服务
• 为网络层提供服务, 将网络层的 IP数据报(也就是分组) 封装成 帧 .

因此, 数据链路实际上, 为底层的物理层提供了一层额外的封装(就是这个 帧 ) , 它能够使得数据链路层在 物理链路 之上的 逻辑链路 上, 来进一步保证下层的数据传输的正确性.

这之后, 我们来详细一些, 列举一下数据链路层的主要功能:

• 组帧 / 拆帧
  • 帧定界: 让接收方能够确认帧的界限, 对应 组帧
  • 透明传输: 接收方的链路层要能够根据对方发送信息的定界来恢复原始的数据报, 即数据链路层的 服务数据单元 (SDU / Service Data Unit) , 并交付给其网络层. 对应 拆帧
• 差错控制
  • 需要能够发现一个帧内部的 位错误
  • 有 丢弃重传 / 纠错改正 两种策略, 前者简单些, 后者复杂些
• 可靠传输
  • 需要能够发现并解决 帧错误
  • 分为三种: 帧丢失 / 帧重复 / 帧失序
• 流量控制
  • 匹配发送方和接收方的发送 / 接收速率
• 介质访问控制
  • 对于 广播信道(总线型拓扑) , 需要实现介质访问权的分配
  • 对于 点对点信道 , 则通常不需要提供该功能, 因为存在专属介质, 不需要依靠介质的分配和争抢

注意: 差错控制 Vs 可靠传输
差错控制 通常针对的是 帧内部 的错误, 而 可靠传输 针对的是 帧之间 的错误.

这之后的小节中, 我们会对数据链路层实现这一大堆功能的方法进行逐一说明.

3.2 组帧

组帧 , 通常用于达成 帧定界 和 透明传输 的目的. 有四种常见的方案:

• 字符计数法
• 字节填充法
• 零比特填充法
• 违规编码法

3.2.1 字符计数法

字符计数法 的原理是在每个帧的开头加上一个单独的 定长计数段 , 来表示每个帧的长度.

注意: 帧长
帧长, 指的是 计数字段长度和帧的数据部分长度的 总和 .

可知, 使用这种方法的帧的最大长度是有上限的, 其值为 $ 2^{计数字段长度}-1 $ .

除此之外, 该方案的 最大缺陷 在于: 任何一个计数字段出错, 都会导致后续全部的帧都无法正确定界 .

3.2.2 字节填充法

字节填充法 的原理是用两个规定好的字符来 标志一个帧的开始与结尾 . 它们分别叫 SOH(Start of Header) 和 EOT(End of Transmission) , 对应的16进制分别为 $ 01H $ 和 $ 04H $ .

这个方案也有问题, 因为当 数据内本身出现了SOH和EOT时 , 会使接收方 误认为该内容是控制字符 , 导致定界失败.

那咋办呢? 人们引入了一个新的字符叫 转义字符(ESC / Escape Character) , 对应的16进制为 $ 1BH $ .
如果发送方的数据中包含了 特殊字符(SOH, EOT, ESC) , 则需要在对应的字节之前插入一个转义字符, 同时接收方也会进行逆处理, 将数据中的转义字符删除, 并原封不动的保留其下一个字节的内容.

3.2.3 零比特填充法

这种方案的初心跟上一种类似, 只不过开头和结尾使用的定界符相同, 是 $ 7EH $ , 对应的二进制是 $ 0111,1110 $ .

如果理解了上一种方法的问题, 则很容易发现这种方式也面临着同样的问题. 数据本身如果包含完全相同的字节, 就出问题了.

而这个方法中没有引入转移字符, 而是利用了 其规定定界符的特殊性 :

• 发送方对数据进行处理, 每当连续遇到5个1, 就 添加一个0 .
• 接收方对数据进行逆处理, 每当连续遇到5个1, 就 删掉后面的0 .

经过这样的处理, 能够保证数据中一定不会出现跟定界符一样的 六个1连在一块 的情况.

这种组帧方式极为常用, 因为它能够很快速的依赖硬件完成处理. 在当前数据链路层的两个主流协议( HDLC, PPP )中均有所采用.

3.2.4 违规编码法

既然扯到 编码 了, 势必意味着这玩意需要物理层的配合. (不知道读者还记不记得上一章物理层的东西, 笑)

我们以 曼彻斯特编码 为例, 其每一个码元中间是必须要进行一次 跳变 的.
那么, 只需要让物理层在每一帧的前面和后面, 分别插入一个时钟周期的 违规信号(比如中间不跳变) , 就可以很方便地让接收方知道帧的起始位置和结束位置.

3.3 差错控制

差错控制 的目标是 发现并解决一个帧内部的位错误 . 解决方案通常有两种:

• 发现错误后丢弃帧, 并通知发送方重传.
  • 只需要发现错误即可, 检错编码
  • 奇偶校验码 / CRC循环冗余校验码等
• 发现错误并纠正比特错误
  • 需要能够确定是哪一位出了错, 纠错编码
  • 海明校验码

3.3.1 奇偶校验

奇偶校验 指的是通过一个单独的比特位来保证信息中 “1” 的个数为奇 / 偶.

• 奇校验 : 添加该校验位后, 该校验码中总共有奇数个1.
• 偶校验 : 添加该校验位后, 该校验码中总共有偶数个1.

通常而言, 偶校验 要更加常用一些, 因为只需要通过模2加的情况就能简单的得到结果.

• 发送方只需要将 数据的所有位 全部以 异或 的方式相加就能得到偶校验位.
• 接收方只需要将 校验码的所有位 全部 异或 起来, 结果为1说明数据出错, 结果为0说明通过.

注意: 异或?
因为 异或 运算实际上相当于 模2加法 , 因此结果为1就说明有奇数个1相加, 为0则反之.

注意: 奇偶校验的限制
因为奇偶校验只能针对 “1” 数据位总数的奇偶性进行检测, 因此当 偶数个位发生错误时 , 则此时奇偶校验码会失效.

最后, 还请读者明确, 奇偶校验码没有纠错功能, 只有检错功能 .

3.3.2 循环冗余校验

循环冗余校验(CRC / Cyclic Redundency Check) 的核心思路在于通信双方约定一个相同的 除数 , 随后对信息本身运行二进制除法来确定最终的 余数 .

其数据结构分如下两个部分:

• 信息位(K位) : 待校验的信息(也就是数据本身的位数)
• 校验位(R位) : 位数与校验码本身有关, 校验码通常由 生成多项式 给出, 而校验码的位数就是 生成多项式最高次项的次数

我们先捯饬明白一个问题: 生成多项式是什么 ?

生成多项式 是通过一个一元多项式来生成一段二进制的校验码的一种方法. 通过将该多项式各个次数项的系数拼接而成. 我们给个例子

$$ G(x) = x^3 + x^2 + 1 $$

则该多项式可以再写成: $ 1 \times x^3 + 1 \times x^2 + 0 \times x^1 + 1 \times x^0 $ , 进而写成二进制的 $ 1101 $ .

现在的问题是, 怎么除 ?

在循环冗余校验中, 采用的是 模2除 的策略. 其算法为 仅通过最高位判断当前位的商 , 后续低位则使用 异或 计算后顺延到下一次计算中.

我们给个例子, 假设信息位6位, 校验位3位(相当于最初直接将信息位左移3位):

最终得到的三位余数就是最终的 校验位结果 .

发送方计算得到这个校验码之后, 将 信息位 + 校验位 一并传输给接收方. 接收方收到后再次进行与发送方相同的运算, 并验证最终校验位是否为0即可.

注意: 接收方验证是否为0?
读者在这个位置可以类比一下除法的 余数 , 发送方发送给接收方的数据是 信息位 + 校验位 , 换句话说就是把发送方算出的余数加了上去, 再传给了接收方, 因此接收方在算相同的问题时, 只需要检验自己的运算结果是不是0即可.

这里需要额外提一嘴, 循环冗余校验 是具备纠错能力的 , 但具备纠错的条件是校验码能够表示的状态数 ( $ 2^R $ ) 大于本身的数据位数 (K+R) . 因此在计算机网络中一般不常用它来纠错而已.

通常, 循环冗余校验码能够检测出所有:

• 奇数位错误
• 双比特错误
• 小于等于校验位长度的错误

3.3.3 海明校验

海明校验 是对于偶校验的一种扩展. 他着眼于偶校验的校验码长度过短, 导致无法判断指定某位的错误.
那到底需要多少个校验位?

事实上上一节已经给出答案了, 如果校验位数为k, 则它总共能表示 $ 2^k $ 个状态, 这其中应当包括 n+k个信息位出错的情况 以及 正确的情况 . 即:

$$ 2^k \geq n+k+1 $$

我们给个例子:

4位信息位, 因此需要有3位校验码 ( $ 2^3 \geq 4+3+1 $ ) .
随后是海明码的位置规定, 校验位 $ P_i $ 应该放在数据位号为 $ 2^{i-1} $ 的位置上. (即校验位的分布是 1, 2, 4, 8, 16, …)
再将数据位分别填入剩余别的位置上.

这之后进入分组, 我们将 $ P_i $ 与 位置序号第i位为1的数据位分为同一组 .
对同一组的数据进行异或, 得到 $ P_i $ 的值(相当于进行 分组偶校验 )
那怎么纠错呢, 就是验证对应分组的偶校验是否正确, 得到 $ S_1, S_2, S_3, … $ , 这个值标志着哪一位的数据出了错.

请读者明确, 海明码具有 1位纠错 和 2位检错 的能力, 其中两位检错通常是通过前加全体偶校验提供的.

3.4 可靠传输与流量控制 / 滑动窗口机制

可靠传输 的目标是发现并解决 与帧整体相关的错误 , 具体分为三类:

• 帧丢失
• 帧重复
• 帧失序

注意: 差错控制中的丢弃重传
在 差错控制 一节中, 我们提到过有些校验码只具有检错的功能, 而并不能纠错, 这意味着接收方只能丢弃该帧并进行重传. 这种情况下, 问题就回到了可靠传输的 帧丢失 这一类中.

流量控制 的目标是让发送方控制自己的数据传输速度以 能够与接收方的接受速度相匹配 .

那为啥把这俩东西放一块唠呢?
因为这俩目标的实现都跟一个机制相关, 它叫 滑动窗口机制 .

3.4.1 滑动窗口机制

滑动窗口 是针对双方而言的, 它分为 发送窗口( $ W_t $ / Transmit Window) 和 接收窗口( $ W_r $ / Reveive Window) . 它们分别指 发送方当前允许发送的帧 和 接收方当前允许接收的帧 .

注意: 允许发送? 允许接收?
这一部分是笔者自己的理解, 如有错误还请读者谅解
个人认为对于发送 / 接收窗口的定义是有些模糊的, 从笔者的理解, 发送窗口包括了发送方当前 正在或准备传输但没能够接收到确认消息 的帧 , 而接收窗口包括了接收方当前 希望收到但还没有从发送方处收到的帧 .

因此, 发送方暂时不会发送在发送窗口外的帧, 而接收方也会拒绝接受在接收窗口外的帧.

那么, 窗口的 滑动 是如何体现的呢?

在 接收方收到滑动窗口内的帧时 , 会主动先将自己的窗口向后移, 随后通过某种确认方式向发送方确认 我已经收到这个帧了 , 发送方收到该确认消息后 , 也会主动将自己的发送窗口后移, 以达到同步的效果.

这样, 我们就大概明确了 滑动窗口 到底是个啥玩意.
随后我们要探讨的几个协议, 会在以下四个方面有所区别, 但请读者明确, 它们的本质都是滑动窗口机制的延申 .

• 窗口大小
• 确认机制
• 重传机制
• 帧编号

3.4.2 停止等待协议

停止等待协议(SW / Stop and Wait) , 是滑动窗口机制中最为简单的协议.

它的特点如下所示:

• 窗口大小
  • 发送窗口 $ W_t = 1 $
  • 接收窗口 $ W_r = 1 $
• 确认机制
  • 接收方收到第i号帧, 且未检测出差错时, 发回给发送方一个确认消息 $ ACK_i $
• 重传机制
  • 发送方若超时未收到 $ ACK_i $ , 则主动重传该帧
• 帧编号
  • 仅需要1bit对帧进行编号

注意: ACK?
ACK 是 Acknowledge 的缩写, 在此后的协议书写中会经常使用.

在这里我们单独对 帧编号 进行一个说明.

帧的编号需要满足一个条件, 即 窗口长度必须小于等于序号空间大小的一半 .

$$ W_t / W_r \leq 2^{n-1} $$

这个式子在随后的协议中也会看到, 而在停等协议中, n=1就已能够满足该条件.

注意: 窗口长度的限制
这个位置王道的网课上给出的式子为 $ W_t + W_r \leq 2^n $ , 笔者认为这种写法不够严谨.
具体留给各位读者自行评判.

为了写清楚停等协议的具体步骤, 我们得画俩流程图 (草, 这东西真费劲啊)

我们对这种流程图进行一个说明:

• 圈内指的是 当前实体的状态
• 横线上是 当前实体收到的信息
• 横线下是 当前实体会采取的措施

总结一下停等的总体思路:

• 发送方发一个包, 等待接收方确认
• 接收方收到包, 发送确认消息, 等待发送方下一个包

3.4.3 后退N步协议

后退N步协议(GBN / Go Back N) , 比停止等待协议要稍显复杂, 它的特点如下:

• 窗口大小:
  • 发送窗口 $ W_t > 1 $
  • 接收窗口 $ W_r = 1 $
• 确认机制
  • 接收方收到第i号帧, 且未检测出差错时, 发回给发送方一个确认消息 $ ACK_i $
• 重传机制
  • 发送方若超时未收到 $ ACK_i $ , 则主动重传该i号帧
• 帧编号
  • 仅需要1bit对帧进行编号
• 特殊规则
  • 接收方可以 累计确认 . 即连续收到多个数据帧时, 只返回最后一个收到的帧的ACK
  • 如果发送方超时未收到i号帧的ACK, 则重传 i号帧以及其之后的所有帧

意义即接收方能够通过 $ ACK_i $ 表示自己已经收到第i号帧以及其之前的所有帧.

我们同样通过两个流程图来分别说明发送方和接收方的事情:

后退N步的主要想法是让发送方能够 一次发送多个帧 , 而不用发一个等一下这样循环, 提高信道利用率.
但可以预见的是, 如果 信道错误率很高 , 或者 接收方接收速率很慢 的情况下, 发送方需要 频繁的后退 , 这也会导致资源的浪费.

3.4.4 选择重传协议

选择重传协议(SR / Selective Repeat) , 尝试解决GBN的缺点. 它的特点如下:

• 窗口大小:
  • 发送窗口 $ W_t > 1 $
  • 接收窗口 $ W_r > 1 $
• 确认机制
  • 接收方收到第i号帧, 且未检测出差错时, 发回给发送方一个确认消息 $ ACK_i $
• 重传机制
  • 发送方若超时未收到 $ ACK_i $ , 则主动重传该i号帧
• 帧编号
  • 仅需要1bit对帧进行编号
• 特殊规则
  • 接收窗口不能大于发送窗口
  • 接收方逐个确认已收到的分组
  • 发送方只重新发送没有收到ACK的分组
  • 发送方对每个分组均有单独的计时器

注意: 选择重传的机制
王道网课给出的选择重传机制与笔者教材(计算机网络: 自顶向下方法 / Computer Networking: A Top-Down Approach)中的机制并不相同, 甚至可以说是差异明显. 笔者这里给出的是教材中的方法. 如果读者有兴趣, 可以前往 选择重传协议王道网课版 进行王道版本的学习.

3.4.5 三种协议的信道利用率

三种协议唠叨完了, 我们看看它们的优劣, 那自然就要捯饬一下它们对于信道的利用程度对吧.

3.4.5.1 停等协议的信道利用率

我们先从最简单的 停等协议 开始.

可见, 停等协议的一个周期由三部分组成:

• 数据帧传输时延 $ T_D $
• 传播时延: $ RTT $
• 确认帧传输时延 $ T_A $

因此我们能给出这么个式子:

$$ U = \frac{T_D}{T_D + RTT + T_A} $$

注意: 信道利用率的计算前提
我们在本处计算信道利用率时的前提是 理想情况 , 即信道不丢帧, 不产生比特差错的情况. 原因在于如果我们加上那些意外, 整个情况会显得非常复杂 (那不乱套了嘛)

注意: RTT Vs 单向传播时延
事实上, RTT = 2 * 单向传播时延 , 请读者务必注意这个名称问题

3.4.5.2 GBN / SR 的信道利用率

接下来是复杂一些的 回退N步和选择重传协议 , 之所以把他俩放在一块说, 是因为他俩的理想条件是几乎完全一致的, 即发送一帧后对方也能及时接收这一帧并返回ACK.

我们只需要看单个周期内(即灰色框内部)的信道利用率, 其实组成是一致的, 只不过此时的情况在于, 发送方能一次发送多个帧对吧. 进而我们给出这个式子:

$$ U = \frac{N * T_D}{T_D + RTT + T_A} $$

其中, N 是指 发送过程中能够连续发送的数据帧数目 .

相信有些读者读到这已经有点想法了, 那如果我的发送数据的这 $ N * T_D $ 比你的分子还大捏? 你这式子不炸缸了吗?

所以说嘛, 都叫信道利用率了, 还能比1大不成? 算出来大于1直接写1就完了.

3.4.6 额外补充

有三个名词需要读者了解:

• 滑动窗口协议: 指GBN或SR
• ARQ(Automatic Repeat Request / 自动重传请求)协议: 指ST / GBN / SR
• 连续ARQ协议: 指GBN / SR

3.5 信道划分与介质访问控制

首当其冲, 什么是介质访问控制 ?

概念: 介质访问控制
为了应对多个节点共享信道时的 信号冲突 , 对各个节点对传输介质的访问进行控制的过程.

好嘞, 所以说白了就是该怎么应对介质访问冲突对吧, 那我们来慢慢寻思.

3.5.1 时分复用

概念: 时分复用(Time Division Multiplexing, TDM)
将时间分为等长的 TDM帧 , 同时每个TDM帧又被分为等长的 m 个 时隙 . 将m个时隙分别分配给各个用户使用.

时分复用非常公平, 有时候显得有些公平过头了.

• 每个节点最多享受到信道传输速率的 $ \frac{1}{m} $
• 当有节点在它的时隙内不需要发送信息时, 该信道的资源会被浪费.

3.5.2 统计时分复用

概念: 统计时分复用(Statistic Time Division Multiplexing, STDM)
亦称 异步时分复用 , 在TDM的基础上, 动态按需分配时隙.

3.5.3 频分复用

概念: 频分复用(Frequency Division Multiplexing, SDM)
将信道的总频带划分为多个 子频带 , 每个子频带都作为一个子信道. 每对用户使用其中一个子频带进行通信.

上图中出现了两个陌生的玩意:

• 复用器 : 将各个节点发出的信号 复合 后传输到共享信道上.
• 分用器 : 将各个子频带的信号 分离 出来.

注意: 隔离频带
都分频了, 那自然要做一些隔离措施, 防止分用器将本不属于这个子频带的信号分到这个子频带上.
就像跑道之间还要有一条隔离线作为隔离区域对不

FDM看起来非常好, 又公平, 还充分利用了信道带宽对吧. 但它有个非常重要的缺点:
FDM技术只能用于模拟信号的传输 , 因为一般而言, 只有模拟信号才有 频率 这个概念.

3.5.4 波分复用

概念: 波分复用(Wavelength Division Multiplexing, WDM)
将信道按照传输光信号的 波长 来分组. 本质上与频分复用是一个思路.

波分复用主要用于 光纤 .

上面我们提的方式挺完善 吗 ?
要知道互联网不仅仅是一对一, 而经常涉及到一对多的通信. 上面这些方式, 如果要进行一对多的通信, 会显得非常繁琐不是吗?

因此, 码分复用出现了.

3.5.5 码分复用

概念: 码分复用(Code Division Multiplexing, CDM)
各个节点预先获得自己的 码片序列 , 并根据自己的码片序列向接收方传送数据, 接收方能够根据传送数据的特点判断出是属于哪个发送方的.

哎, 这里有个玩意叫 码片序列 , 读者可以把它考虑为一个 多维向量 , 并且这个向量的每个分量都取1 / -1 .
举个例子, 下面就是几个码片序列:

$$ \vec{a} = (1, 1, 1, 1) $$

$$ \vec{b} = (1, -1, 1, -1) $$

通常而言, 发送方会发送 $ \vec{sender} $ 来表示1, 发送 $ - \vec{sender} $ 来表示0 .

注意: 码片序列的正交性
为了让接收方更好的区分不同的发送方, 通常而言, 码片序列之间被规定为 严格正交(即相乘得0) .

好的, 我们现在搞明白了发送方怎么发数据, 那接收方怎么收数据?

这里涉及到一个数学方面的运算, 被称为 规格化内积 .

假设发送方a发了个比特1, b发了个比特0.
接收方应当接收到这两个比特的加和, 即 $ \vec{a} + (- \vec{b}) $ .
此时发送方干这么一件事: 分别用 $ \frac{1}{向量维数} $ 以及 $ \vec{sender_i} $ , 乘上它拿到的这个叠加向量, 即:

$$
\begin{align*}
\frac{1}{m} \space \vec{a} * (\vec{a} + (- \vec{b})) \\
\frac{1}{m} \space \vec{b} * (\vec{a} + (- \vec{b})) \\
\end{align*}
$$

哎嘿, 挺神奇, 是不是上面得1, 下面得-1;
正好对应a发送1, b发送0.