【计算机网络】王道考研笔记整理（3）数据链路层

第三章 · 数据链路层

3.1 数据链路层的功能

3.2 组帧

3.2.1 字符计数法

3.2.2 字节填充法

3.2.3 零比特填充法

3.2.4 违规编码法

3.3 差错控制

3.3.1 奇偶校验码

3.3.2 CRC 校验码

3.3.3 海明校验码

3.4 可靠传输与流量控制

3.4.1 滑动窗口机制

3.4.2 停止 - 等待协议

3.4.3 后退 N 帧协议

3.4.4 选择重传协议

3.4.5 三种协议的信道利用率分析

3.5 介质访问控制

3.5.1 信道划分

3.5.2 随机访问

3.6 局域网和 IEEE802

3.6.1 局域网的基本概念和体系结构

3.6.2 以太网和 IEEE802.3

3.6.3 VLAN 的基本概念与基本原理

3.6.4 IEEE802.11 无线局域网

第三章 · 数据链路层

3.1 数据链路层的功能

数据链路层使用物理层提供的“比特传输”服务，为网络层提供服务，将网络层的 IP 数据报（分组）封装成帧，传输给下一个相邻结点。

以下是数据链路层的常见功能，也是本章节之后会涉及到的所有内容。

3.2 组帧

本节我们主要讨论不同的组帧编码方式。

3.2.1 字符计数法

字符计数法的原理是在每个帧开头，用一个定长计数字段表示帧长。注意，这里的帧长是计数字段长度加上帧的数据部分长度的和。

这种方法的缺点在于任何一个计数字段错误，后面所有的帧都会无法定界。

3.2.2 字节填充法

字节填充法的原理是在每个帧的开头和结尾分别添加一段控制字符。

但问题在于可能会将数据部分中某一段当作控制字符，因此，使用这种编码需要在数据部分出现控制字符时，在前面加上一段转义字符。这样，机器识别的时候，当识别到转义字符时，就会认为后一段是数据部分，并忽略转义字符的内容。从而避免将数据的一部分当作控制字符。

3.2.3 零比特填充法

这种编码方式和字节填充法类似，也是在每一帧的开头结尾添加一段特殊比特串。

但问题也一样，可能在数据部分出现和特殊比特串一样的数据段。由于特殊比特串中间有 6 个连续的 1，因此，采用的解决方法是对于数据部分，从左往右扫，每当出现 5 个连续的 1 时，就会在后面插入一个 0。这样就永远不可能出现 6 个连续的 1，而接收方在接收数据时也可以用类似的方法将数据部分复原，实现透明传输。

注意：HDLC 和 PPP 组帧协议使用的就是零比特填充法。

3.2.4 违规编码法

这种编码方式需要物理层配合使用，比如说在物理层传输比特串时使用的是曼彻斯特编码，上跳 0 下跳 1，时间周期中间一定会变化，那么就可以在帧的开头结尾加上一个时钟周期的编码。这段编码的中间不发生变化，也就是违规的曼彻斯特编码。

当遇到违规的曼彻斯特编码时，就可以很方便地确定帧的界。

3.3 差错控制

差错控制主要目的是发现并解决一个帧内部的“位错误”。常用的有两种解决方案：一种是接收方在发现比特错误后，丢弃帧，由发送方重传帧；另一种是由接收方发现和纠正比特错误。

第一种解决方案使用的编码方式被称为检错编码，本节主要讨论奇偶校验码和 CRC 校验码。

第二种解决方案使用的编码方式被称为纠错编码，本节主要讨论海明校验码。

3.3.1 奇偶校验码

奇偶校验码的原理如下图所示：

工业上常见的是偶校验法，因为偶校验的硬件实现比较简单，只需要将所有信息位做异或运算得到的就是偶校验位。但问题在于，无法检验出偶数位错误，并且没有纠错能力。

3.3.2 CRC 校验码

CRC 校验码全称为循环冗余校验码，具体原理如下图所示：

【例题】如何求 CRC 码？

注意这里的余数产生使用的是模 2 除法，而不是我们常用的十进制除法！！！

最终得到校验位是 001，因此，CRC 码为 101001001。

除了计算 CRC 码，我们还需要知道如果接收方收到的编码除以除数得到的结果不是 0，那么我们是可以根据不同的余数情况判断收到的编码中哪一位出现了问题。只不过，对于不同的除数，得到的余数和编码中位数的对应关系是不同的！比如下图就是除数为 1101 时，不同余数对应出错的编码位：

3.3.3 海明校验码

这部分在计算机组成原理中已有，这里不再赘述。

3.4 可靠传输与流量控制

可靠传输与流量控制的具体功能在第一节中已经提过了，这两者都与滑动窗口机制紧密相关。本节，我们从滑动窗口开始说起，并讨论与之息息相关的三种协议。

3.4.1 滑动窗口机制

如下图所示，发送窗孔表示发送方当前允许发送的帧，接收窗口表示接收方当前允许接收的帧。

若此时，发送方发送 A,B,C,D 这四个帧，由于 A,B 落在接收窗口范围内，因此会被接收，而 C,D 因为落在接收窗口范围外，则会直接丢弃。接着，接收方可以通过“确认机制”控制发送方窗口向右滑动，从而实现“流量控制”。

之后，我们将提到的一些协议在下图中的四个方面都有所不同，也是我们讨论的中心。

3.4.2 停止 - 等待协议

上图是停止 - 等待协议中的一些机制。这里主要对帧编号这一点做一定的解释：无论是停止 - 等待协议还是之后将提及的后退 N 帧协议和选择重传协议，我们判断需要 n bit 来给帧编号，都使用的是条件 Wt + Wr <= 2^n。这里可以求得 n = 1。

假如此时，接收方没有收到数据帧，那么发送方会因为长时间没有收到确认帧而选择重新发送数据帧 Data0。等到接收方收到数据帧 Data0，并且发送方收到确认帧之后，接收窗口和发送窗口才会右移。

假如此时，接收方发出的确认帧丢失，那么发送方也会因为长时间没有收到确认帧而选择重新发送数据帧 Data0。但是，此时接收方已经移动到帧序号为 1 处，当收到数据帧 Data0 时，容易判断收到的是重复帧，所以直接丢弃，并发送重复帧的 ACK 给发送方。等到发送方收到确认帧之后，发送窗口才会右移。

通过上面的例子可以看出，如果没有编号，那么接收方将无法判断“重复帧”。由于接收窗口和发送窗口的距离相差不超过 1，因此使用 1 bit 表示帧序号足矣。

3.4.3 后退 N 帧协议

上图是后退 N 帧协议的一些机制。这里发送窗口的数量并不固定，因此，需要用多少 bit 来给帧编号，是要利用条件计算才能得到的。

正常情况下，GBN 使用特殊规则“累计确认”来依次接收和发送帧数据。假如此时，再一次发送，本来应该发送 3，0，1 但是 0 号帧出现了问题。那么接收方将会返回最后一个接收到的正确的帧，也就是 3 号帧的 ACK。接着，发送方本要继续发送 2，3，0 号帧，但因为收到的 ACK 只到 3 号帧，所以会“后退”到 0 号帧，发送 0，1，2 号帧。

注意：这里的“后退”并不是指滑动窗口后退，只不过是需要重传部分帧，因此看起来比原本应该传的帧有所后退罢了。

3.4.4 选择重传协议

上图是选择重传的一些机制，具体的实现原理和停止 - 等待协议和后退 N 帧协议类似，在此不再赘述。

3.4.5 三种协议的信道利用率分析

停止 - 等待协议的信道利用率比较容易分析：

只要代入公式计算即可。这里确认帧的传输时延一般较短，有时甚至可以忽略。

后退 N 帧协议和选择重传协议的信道利用率计算公式一致：

但要注意信道利用率的最大值为 1，因此，如果通过公式计算得到的结果超过 1，应该取 1。

【注意】这里要额外讲一些术语：

如果题目里出现滑动窗口协议，那么指的是后退 N 帧协议或选择重传协议。

如果题目里出现 ARQ 协议，那么三种协议都有可能。

如果题目里出现连续 ARQ 协议，那么指的是后退 N 帧协议或选择重传协议。

3.5 介质访问控制

在多个节点共享同一个“总线型”广播信道时，可能发生信号冲突。为了减少甚至避免冲突，就需要对介质访问加以控制。本节将讲解不同的介质访问控制技术。

3.5.1 信道划分

信道划分的方式有很多，比如时分复用、频分复用等等。具体的实现思想就是通过将信道按照某一个标准进行划分，从而使得不同的信号不会相互干扰。

1. 时分复用（TDM）

将时间分为等长的 TDM 帧，每个 TDM 帧又划分为等长的时隙，将 m 个时隙分配给 m 个用户使用。

但 TDM 的缺点也十分明显，每对节点最多只能分配到 1/m 个带宽。如果某对节点不发送数据，会导致分配的时隙闲置，信道利用率低。

2. 统计时分复用（STDM）

在 TDM 的基础上，动态按序分配时隙。如果需要时某个节点可以在一段时间内获得所有的信道带宽资源。如果某节点暂不发送数据，可以不分配“时隙”，信道利用率更高。

3. 频分复用（FDM）

频分复用划分的是信道的总频带范围，也就是总带宽。通过将信道的总频带划分为多个子频带，每一个子频带作为一个子信道，每对用户通过一个子信道进行通信。

这种方式的优点在于，充分利用了信道带宽，但缺点是只能使用模拟信号进行传输。

4. 波分复用

波分复用其实就是光的频分复用。光的频率和波长呈负相关，将各节点发出的不同波长的光信号“复合”后传输到光纤上，就成了波分复用。

5. 码分复用

码分复用的内容比较复杂，具体可以参看下图：

我们可以用例子帮助理解：下图展示的就是对于 A,B,C 三个节点之间传输信息的码分序列设置。

而如何将叠加的信号从节点收到的信息中分离出来呢？就使用规格化内积的方式：

3.5.2 随机访问

1. ALOHA 协议

这里我们将通过流程图的形式帮助理解随机访问的过程。ALOHA 协议分为纯 ALOHA 协议和时隙 ALOHA 协议。

上图展示的是纯 ALOHA 协议的流程，特点是一旦准备好数据帧就立刻发送。

例如，在上图中 A,B,C,D 的数据帧准备好就立刻发送，假如出现发送是被或者冲突的情况，就会随机等一段时间后重发。

上图展示的是时隙 ALOHA 协议的流程，特点是我们设置的时隙大小就是传输一个帧的最长时间，并且只有在每个帧的开始才会传输数据帧。

时隙的好处在于避免了用户发送数据的随意性，降低了冲突的概率，增加了信道利用率。

2. CSMA 协议

CSMA 协议即载波监听多路访问协议，在发送数据前，会监听信道是否空闲，只有信道空闲时才会发送数据。

CSMA 协议有很多不同的变种。首先，我们来看 1-坚持 CSMA 协议。它的优点是信道利用率高，一旦信道空闲就会给下一个节点使用。它的缺点是当多个节点准备好数据时，一旦信道空闲，所有节点会同时发送数据，出现冲突的概率大。

在此基础上，衍生出了 非坚持 CSMA 协议。此时当信道并不空闲时，各个准备好的节点会随机推迟一段时间再监听信道，这样使出现冲突的概率降低了。但缺点是信道刚刚恢复空闲时，可能不会被立即利用，导致信道利用率降低。

还有一种 CSMA 协议是 p-坚持 CSMA 协议。它的特点在于当信道空闲时，有一定概率会立刻将数据帧发送到信道上，也有一定概率会推迟一段时间再尝试发送。它属于是 1-坚持 CSMA 协议和非坚持 CSMA 协议的中和。

3. CSMA/CD 协议

CSMA/CD 协议用于早期的有线以太网（总线型）。

上图中展示了 CSMA/CD 协议中的核心内容，下面我们通过流程图理解一下这个协议的步骤：

流程图中的过程其实比较容易理解，但有一个概念比较新颖，叫争用期。这里我们着重解释一下什么是争用期。

考虑广播信道中相距最远的两个节点，争用期 = 2 * 最大单向传播时延（最远两个节点间数据传输的时间）。CSMA/CD 协议没有 ACK 机制，如果发送过程中没有检测到冲突，就判定发送成功。争用期的概念是为了让发送方可以认为，如果在争用期内没有检测到冲突，那么就不可能出现冲突。

或者也可以根据以下步骤，也就是一个简单的行程问题理解争用期的概念：

除此之外，我们还要解释最短帧长的概念。最短帧长 = 2 * 最大单向传播时延 * 信道带宽。如果收到的帧长小于最短帧长，则视为无效帧。

如果发送的帧小于最短帧长，有可能实际上发生了冲突，但因为冲突信息传回来的时间过长，导致认为发送成功。

有最短帧长，就有最长帧长。这是为了避免有的节点长时间占用信道。一般而言，以太网规定最短帧长为 64 B，最长帧长为 1518 B。

刚才我们的流程图展示的是发送方的任务，现在我们来看接收方的任务，这比较简单。

4. CSMA/CA 协议

如果说 CSMA/CD 协议的核心在于冲突检测，那么 CSMA/CA 协议的核心在于冲突避免。CSMA/CA 在发送时不用检测冲突，发送前想办法避免冲突。这种协议更适用于无线网络技术。

在介绍该协议之前，我们要先了解什么是 AP。AP 又称接入点，也就是平时连接的无线 WIFI 热点。之前我们提过，家用路由器 = 路由器 + 交换机 + AP。所有的移动站点都需要和固定站点的 AP 进行通信。

【提问】为什么移动通信不使用 CSMA/CD 协议呢？

【回答】一方面是因为硬件上很难实现“边听边发，冲突检测”——因为接收信号的强度往往远小于发送信号的强度，且在无线介质上信号强度的动态变化范围很大。

另一方面存在“隐蔽站”问题——在无线通信中，并非所有站点都能够听见对方。发送节点处没有冲突不代表在接收节点处不存在冲突。

不考虑隐蔽站的情况下，协议要点如下：

在协议要点中出现的间隔 DIFS 含义解释如下：

为了方便理解上面的协议要点，我们使用时间图帮助理解：

3.6 局域网和 IEEE802

本节主要讨论局域网和 IEEE802 之间的关系。在此之前，我们首先需要了解什么是 IEEE802 委员会。

3.6.1 局域网的基本概念和体系结构

局域网是一种覆盖较小的地理范围，具有较低的时延和误码率，在各节点之间以帧为单位进行传输，支持单播、广播、多播的网络概念。

单播指的是一对一发送帧，如 A->B

广播指的是一对全部发送帧，如 A->BCDE...

多播指的是一对多发送帧，如 A->BCD

局域网分为有线局域网（LAN）和无线局域网（WLAN）。我们需要关注的是不同网络的拓扑结构，传输介值和介值访问控制方式。这些内容均可以通过下图查看。

另外，我们还要了解实现局域网的一些硬件架构：一台计算机和局域网之间的信息传输主要通过网络适配器这个装置完成。具体的内容可以通过下图查看。

3.6.2 以太网和 IEEE802.3

IEEE802.3 将五层参考模型中的数据链路层划分为介质访问控制子层和逻辑链路控制子层。其中，以太网技术的研究范畴包括物理层和介质访问控制子层。

上图展示的是 IEEE802.3 推出的以太网物理层标准。重点要关注的是支持全双工还是半双工。同轴电缆只能半双工。双绞线在速率 < 2.5Gbps 时既可以支持半双工，也可以支持全双工；在速率 >= 2.5Gbps 时只能支持全双工。光纤只支持全双工。另外，在做题时，默认交换机连接的终端都可以全双工，集线器连接的终端都只能半双工。