从零开始的计网学习-数据链路层

写在最前面：本篇文章的主要资料来源为《[公众号蓝蓝考研]计算机网络背诵版》，同时会在遇到重点问题时广泛收集网上资料，使得记录更加详细。本次整理仅用于个人学习。

老规矩，先来看一下数据链路层的考点：

基本概念
差错控制
流量控制
介质访问控制
局域网与广域网
链路层设备

注：数据链路层是计算机网络中很核心的一部分，所以涉及到的知识点很多，考点也多。同时因为数据链路层是既与通信相关，又有很多计网相关的协议，所以属于承上启下的一层。

基本概念

数据链路层的基本概念

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

其中：

节点：主机、路由器等
链路：网络中两个节点之间的物理通道，链路的传输介质有双绞线、光纤、微波等，分为有线链路和无线链路。
帧：链路层的协议数据单元，封装网络层数据报。

数据链路层的功能

组帧

封装成帧与透明传输

封装成帧

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

首部和尾部包含许多控制信息，其中帧定界符的作用就是确定帧的界限。

考虑到差错控制等多种因素，每一种数据链路层协议都规定了帧的数据部分的长度上限，即最大传送单元MTU。

扩展：MTU的相关知识(参考文章：https://info.support.huawei.com/info-finder/encyclopedia/zh/MTU.html)

什么是MTU?

最大传输单元MTU（Maximum Transmission Unit，MTU），是指网络能够传输的最大数据包大小，以字节为单位。MTU的大小决定了发送端一次能够发送报文的最大字节数。如果MTU超过了接收端所能够承受的最大值，或者是超过了发送路径上途经的某台设备所能够承受的最大值，就会造成报文分片甚至丢弃，加重网络传输的负担。如果太小，那实际传送的数据量就会过小，影响传输效率。

**为什么要有MTU?**（MTU的作用）

网络中通常以数据包为单位进行信息传递，那么，一次传送多大的包合适、多大的包最高效就成为一个核心问题之一。如果包大小设置的很大，意味着报文中的有效数据也更多，通信效率更高，但传送一个数据包的延迟也越大，数据包中bit位发生错误的概率也越大。并且如果这个报文丢掉了，重传的代价也很大。如果包大小设置的过小，则意味传输相同的数据量，设备需要处理更多的报文，这样会极大的考验设备的线速转发能力。通过设置MTU来调节网络上数据包的大小，让不同的网络找到最适宜的MTU从而提高转发效率，这就是MTU的作用。

MTU是一个确定的值吗？

MTU是数据链路层的概念，指数据链路层对数据帧长度的限制。不同链路介质类型的网络有不同的默认MTU值，以下是一些常见网络的默认值：

为什么以太网的MTU通常设置为1500

RFC标准定义以太网的默认MTU值为1500。那么这1500的取值是怎么来的呢？

早期的以太网使用共享链路的工作方式，为了保证CSMA/CD（载波多路复用/冲突检测）机制，所以规定了以太帧长度最小为64字节，最大为1518字节。最小64字节是为了保证最极端的冲突能被检测到，64字节是能被检测到的最小值；最大不超过1518字节是为了防止过长的帧传输时间过长而占用共享链路太长时间导致其他业务阻塞。所以规定以太网帧大小为64~1518字节，虽然技术不断发展，但协议一直没有更改。

以太网最大的数据帧是1518字节，这样刨去帧头14字节和帧尾CRC校验部分4字节，那么剩下承载上层IP报文的地方最大就只有1500字节，这个值就是以太网的默认MTU值。这个MTU就是网络层协议非常关心的地方，因为网络层协议比如IP协议会根据这个值来决定是否把上层传下来的数据进行分片，如果单个IP报文长度大于MTU，则会在发送出接口前被分片，被切割为小于或等于MTU长度的IP包。

MTU的示意图

如图所示，IP数据报的长度就是MTU的长度。但是实际上，不同的厂商，甚至同一厂商的不同产品型号对MTU的定义也不尽相同，通常分为以下几种：

MTU用以指示整个IP报文的最大长度（IP头+三层Payload），MTU是一个三层的定义，即MTU = IP MTU。例如在Huawei NetEngine系列路由、CloudEngine系列交换机上，MTU是三层的定义，指IP MTU。
MTU的值等于IP报文与以太帧头的总和，即MTU = IP MTU + 14字节。例如在Cisco部分设备上，MTU是指IP MTU + 以太帧头。
MTU的值等于IP报文与以太帧头、CRC部分的总和，即MTU = IP MTU + 18字节。例如在Juniper部分设备上，MTU是指IP MTU + 以太帧头 + CRC部分。

在实际设置MTU值时，需要特别关注各厂商、产品对于MTU的定义。在本篇文章中以第一章定义为准。

超过MTU的报文如何进行分片？

以太网缺省MTU=1500字节，这是以太网接口对IP层的约束，如果IP层有<=1500字节需要发送，只需要一个IP包就可以完成发送任务；如果IP层有>1500字节数据需要发送，需要分片才能完成发送。

以主机发送一个数据载荷长度为2000字节的报文为例说明其分片的过程（假设出接口的MTU值为1500）。在网络层会对报文进行封装，其结构组成：IP头部20字节+数据载荷长度2000字节，报文封装后，整个报文长度为2020字节。在出接口进行转发的时候，发现IP报文的长度超过了MTU的值1500，因此要进行分片处理，详情见下图。

第一片报文，IP报文头固定20字节，数据载荷可以封装1480字节（MTU值1500字节-IP报文头20字节，数据载荷长度须是8的倍数）；

第二片报文，复制第一片的IP头，IP报文头固定20字节，数据载荷为剩余的520字节（总数据载荷长度2000字节减去第一片中已封装的1480字节）。如果最后一片报文的长度不足46字节，会自动填充至46字节。

所有分片报文在发送至目的主机后，在目的主机进行分片重组，恢复为原报文。在进行重组时，通过IP标志位中的MF用来分辨这是不是最后一个分片，片偏移用来分辨这个分片相对原数据报的位置。通过这几个字段，可以准确的完成数据报的重组操作。

帧同步：接收方应当能从接收到的二进制比特流中区分帧的起始和终止。

组帧的四种方法（即通过不同的方式判断一个完整的帧）

方法一：字符计数法

即在帧首部使用一个计数字段（第一个字节，8位）来标明帧内字符数，表明包含计数字段在内的帧长度。

优点：很简洁明了
缺点：当计数字段发生错误会导致严重错误。因为是一个数据流，一旦一个错了，后续也会出错。

方法二：字符（节）填充法

采取特定的标识字符来标识某一帧的开始和结束，如果数据中有与标识字符相同的字符，则在前面填充转义字符，接收方将转义字符去掉即可得到原数据。

方法三：零比特填法

使用固定的比特模式01111110来标识帧的开始和结束。

在发送时，每次碰到11111就在后面填充一位0
在接收时，先通过01111110找到起始位置，再查找数据中连续的5个1将其后面的0去除得到原数据

扩展：字节填充与零比特填充（参考文章：http://justin955.top/archives/74/ ）

填充的目的

在数据链路层进行封装成帧的过程中，会有帧界定符Flag作为一头一尾用来封装。

PPP协议中使用的是0x7E:01111110作为定界符，即路由器检测到某个字节为0x7E就说明上个帧传输结束，开始下个帧的传输。

那么新的问题出现了：如果我们的数据中存在0x7E，路由器就会把它误认为定界符，那岂不是会导致帧传输出现错误吗？

解决这个问题，我们采用了最简单粗暴的方式，即：对发送的数据进行转义，将会被误解的数据用另一种方式表达，使得数据中不存在会被误解的数据。

两种传输方式–两种填充方法

首先需要知道，在进行数据传输时，常见的有两种传输方式：异步传输和同步传输

在同步传输中，数据以块或帧的形式发送。此传输是全双工类型。在发送者和接收者之间强制性同步。在同步传输中，数据之间没有间隙。与异步传输相比，传输大量数据更加有效和可靠。
在异步传输中，数据以字节或字符的形式发送。该传输是半双工型传输。在该传输中，在数据的起始位和停止位都添加了奇偶校验位。它不需要同步。

注：简记为“同流异字”

异步传输是以字节为单位，逐个字节发送，所以需要以字节为单位进行转换-字节填充
同步传输则是发送整个数据流 ，传输整个比特流，以比特为单位进行转换-(零)比特填充

二者的目的都是为了使得数据中不会出现标识字符，只是实现的方式不同。

方法四：违规编码法

在曼彻斯特编码中，高->低表示1，低->高表示0。那么低-低和高-高就是违规编码。使用违规编码标识帧的开始和结束。

透明传输

透明传输是指不管所传输的数据是什么样的比特组合，都应当可以在链路上传输。

差错控制

差错的原因

差错检测分为检测编码和纠错编码。差错基本上都是由于噪声引起的，注意下面两点：

检错编码可以检测而不能直接定位错误，因此无法纠错、
纠错编码可以完成前向纠错，但是成本很高，甚少使用

噪声的种类

全局性
- 定义描述：由于线路本身的电气特性所产生的随机噪声，是信道固有的，随机产生的
- 解决方法：提高信噪比
局部性
- 定义描述：外界特定的短暂原因所造成的冲击噪声，这是产生差错的主要原因
- 解决方法：利用编码技术解决

差错的种类

位错：0变1,1变0
帧错：丢失、重复、失序

链路层提供的服务种类

通信质量好的网络：无确认无连接服务
通信质量差的网络：有确认无连接服务
无线传输链路：有确认有连接服务

检错编码

奇偶校验码

在待发送的数据后面增加一位检错码，使得数据中的1的个数为奇数或者偶数

缺点：只能检测出奇数个或者偶数个的错误，检错能力为50%

循环冗余编码（CRC校验）

将数据拆分为相同大小的组，每一组加上冗余码后构成帧再发送。

冗余码采用生成多项式与数据相除得到，具体流程如下：

注意：加到数据后面的是余数而不是商。

提醒：使用CRC校验可以实现无错传输，但是不是可靠传输。

纠错编码

海明码是计算机网络中数据链路层的针对帧的位错提出的一种纠错编码方式，下面我们将对其进行详细的介绍。

海明距离（汉明距离）

两个合法编码的对应比特取值不同的比特称为两个码字的汉明距离
在一个有效编码集中，任意两个合法编码的汉明距离的最小值称为该编码集的汉明距离

对于一个n位数据，

使用海明码进行检错：汉明距离为n+1
使用海明码进行纠错：汉明距离为2n+1

海明码的作用

实现双比特检错、单比特纠错

海明码的步骤：4步
（https://blog.csdn.net/Michael__Wu/article/details/114936902 ）

第一步：确定校验码的位数

若数据有m位，检验码有r位，则检验码应该满足：2^r >= m+r+1

第二步：确定校验码和数据的位置

每个校验码应该放置在最终海明码的2的整数次幂的位置

例子：发送数据位101101，即m=6，可得r=4。

第三步：求出校验码的值

每位校验码码位对应的位数的二进制(0001, 0010, 0100, 1000)表示中只有一个1。

因为根据校验码位置确定的原则, P1,P2,P3,P4的位数分别为2^0,2^1,2^2,2^3, 其二进制表示分别为0001, 0010, 0100, 1000。

那么海明码的每一位(p1,p2,d1,p3,d2,d3,d4,p4,d5,d6)对应码位(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)的二进制表示(0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010)中与校验码码位(1, 2, 4, 8)的二进制表示(0001, 0010, 0100, 1000)的1的位置同为1的所有码的码值的异或运算应为0

假设p1,p2,p3,p4的码值分别为x1,x2,x3,x4, 那么应有p1,d1,d2,d4,d5码值的异或运算为0, 即校验码位的码值为0, 同理得出p2,p3,p4的码值分别为0, 0, 1

第四步：检错并纠错

对各位进行奇偶检验，若为奇数，则证明数据出错

将每位校验码所校验的位数再次求奇偶检验，得到新的结果转置得到的二进制值即为出错位数。

注意：无论是差错检验还是纠错检验都是在原数据的基础上加上一些校验码，而后利用算法的性质进行检验。

流量控制与可靠传输协议

流量传输概述

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

可靠传输与流量控制

可靠传输：发送端发送什么，接收端就接收什么
流量控制：控制发送速率，使得接收方有足够的缓冲空间来接收每一个帧

滑动窗口机制

解决可靠传输：发送方自动重传
解决流量控制：在没收到窗口确认的情况下不发送下一个

停止-等待协议

什么是停等协议

停止等待就是指每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组

为什么要有停等协议？

比特出错、丢包问题等
实现流量控制

研究停等协议的前提

以半双工的形式进行
不考虑数据在哪一层进行传输

停等协议的几种情况

情况一：无差错情况

每一帧都会停止等待，所以仅需要1位对帧进行编号。

情况二：有差错情况

帧丢失或出错

ACK丢失

ACK迟到

停等协议的信道利用率

注：这里涉及到了计算问题，要留心。

停等协议的信道利用率很低。

一个例子：

注：没有说确认帧发送时延就不用算。

多帧滑动窗口–后退N帧协议

与停等协议比，后退N帧协议：

需要更大的编码范围
发送方需要缓存多个帧

滑动窗口介绍

发送方的响应事件

接收方的响应事件

后退N帧协议的性能分析

优点：连续发送帧，提高信道利用率
缺点：重传是需要发送已经发送过的帧，传送效率低

选择重传协议

发送方的响应事件

接收方的响应事件

注意：有很多方法实现流量控制，其目的都是为了提高数据的传输效率，保证数据可以高效、可靠、正确的完成传输。要理解不同流量控制协议的不同点及其实现原理。

介质访问控制

介质访问控制：采取一定的措施，使两对节点之间的通信不会发生干扰，分为两种：

静态划分信道
- 信道划分介质访问控制
动态划分信道
- 轮询访问介质控制
- 随机访问介质控制

两种链路类型

点对点链路
- 两个相邻节点的通过链路连接，没有第三者
- 应用：PPP协议，常用于以太网
广播式链路
- 所有主机共享通信介质
- 应用：早期以太网、局域网

扩展：以太网和因特网 https://cloud.tencent.com/developer/news/470680

信道划分介质控制

多路复用：将多个信号组合在一个信道上进行传输，到目的地后在分离为多个信号

本质上是将广播信号转为点对点链路

参考文章：https://blog.csdn.net/suxiaorui/article/details/87096375

频分多路复用（FDM)

所谓频分多路复用就是将我们的信道资源按频率上进行划分，分成一个个频带的子信道，让每个信号只去用其中的某一个频带的子信道。

应用：家里的电视有很多频道，这种电视信号就是这种频分多路复用技术。

频分多路复用的各用户占用不同的带宽资源，用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。

时分多路复用（TDM)

时分复用则是将时间划分为一段段等长的时分复用帧（TDM 帧），每个用户在每个 TDM 帧中占用固定序号的时隙

波分多路复用（WDM)

介质为光纤，原理类似于光的频分多路复用。

码分多路复用(CDM)

广泛应用于无线链路共享 (如蜂窝网,卫星通信等)
每个用户配一个唯一的 m bit码片序列(chipping sequence)，其中“0”用“-1”表示、“1”用“+1”表示，
- 如 S 站的码片序列：(–1 –1 –1 +1 +1 –1 +1 +1)
各用户使用相同频率载波，利用各自码片序列编码数据
编码信号 = (原始数据) × (码片序列)
- 如发送比特 1（+1），则发送自己的 m bit 码片序列
- 如发送比特 0（-1），则发送该码片序列的m bit 码片序列的反码
各用户码片序列相互正交(orthogonal)
令{di}为原始数据序列，各用户的叠加向量为
解码 : 码片序列与编码信号的内积

两个例子：

注：码分复用的计算是很简单的，但是要理解原理。
可以看一下这个文章：https://blog.csdn.net/u011240016/article/details/52705205

随机访问介质控制

所有的用户都可以随机的发送消息，发送消息时占用全部带宽

ALOHA协议

技术特点：

不监听信道
不按时间槽发送
随机重发

冲突检测：

在传输数据发送冲突时，接收方收到错误帧，返回错误信号
发送方在发现超时或者错误后随机时间内重发数据

时隙ALOHA协议：把时间分为若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发送冲突则必须等到下一个时间片开始时刻再发送

CSMA协议

载波监听多路访问协议(CSMA) :在发送帧之前，先监听信道，根据信道状态决定是否发送数据

CS:载波侦听/监听,每- 个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据
MA:多点接入，表示许多计算机以多点接入的方式连接在一根总线上

CSMA/CD协议

与CSMA协议相比多了CD，即碰撞检测。下面介绍该协议的工作原理：

碰撞检测

2. 确定重传时机

最小帧长

CSMA/CA协议

轮询访问介质访问控制

轮询协议

主节点轮流邀请从属节点发送数据

缺点：

轮询开销
等待延时
单点故障

令牌传递协议

局域网

基本概念

以太网与IEEE802.3标准

MAC子层与LLC子层

将数据链路层分为了两个子层：

LLC子层: 逻辑链路控制子层，为网络层提供服务
- 无确认无连接、面向连接、带确认无连接
- 高速传送
- 差错控制
- 给帧加序号
MAC子层:介质访问控制子层，MAC子层的存在屏蔽了不同物理链路种类的差异性
- 数据帧的封装/卸装
- 帧的寻址和识别
- 帧的接收与发送
- 竞争处理
- 比特差错检测