数据链路层

数据链路层的功能
为网络层提供服务：

• 链路管理 ：数据链路的建立、维持和释放。
• 寻址：保证每一帧都能正确到达目的站。

保证数据传输的有效、可靠：

• 帧定界：将物理层的比特封装成帧，确定帧的开始和结束。
• 透明传输 ：指不管数据是什么样的比特组合，都应当能在链路上传输。
• 差错检测：能对物理信道传输的比特流检测出差错。
• 流量控制：控制发送方的发送数据速率使接收方来得及接收。

帧的概念

链路和帧
链路（物理链路）(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。
一条链路只是一条通路的一个组成部分。

数据链路（逻辑链路）(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。

现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。
一般的适配器都包括了数据链路层和物理层这两层的功能。

数据链路层传送的是帧
常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。

帧的封装(帧定界)
封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。
首部和尾部的一个重要作用就是进行帧定界。

常用成帧方法
1.字节/字符填充的定界符法
(让每一帧用一些特殊的字节作为开始和结束标志。)
2.比特填充的标志法(也称零比特填充法)

透明传输

字节填充法

如果数据部分出现EOF，就会出现问题

解决方案：
发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。
接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。
如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。

零比特填充
以01111110作为一帧的开始和结束标志F字段
在发送端，只要发现有 5 个连续 1，则立即填入一个 0。
接收端对帧中的比特流进行扫描。每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除。

差错检测

出错情况：在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1。帧（包括发送帧和响应帧）出错或者帧（包括发送帧和响应帧）丢失。

误码率：在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。

差错检测编码分类
纠错码：前向纠错技术：发现错误，从错误中恢复出正确

• 纠错码需要较多的冗余位，信道利用率不高。
• 适用无线网络

检错码： 只能发现错误，不能从错误中恢复，但可采用重传。

• 适用局域网
• 循环冗余码(CRC)。

海明码
海明距离
两个码字(codeword)的海明距离 : 两个码字之间不同位的数，也就是异或（非进位加法）的结果中，1的个数。
例： 10001001 和10110001 的海明距离为？

# 非进位加法（二进制）：1+1=0,1+0=1,0+1=1,0+0=0

	1 0 0 0 1 0 0 1
+	1 0 1 1 0 0 0 1
-------------------------
	0 0 1 1 1 0 0 0
	
# 1 的个数为3

解析：10001001 和10110001 的海明距离为3

海明距离与检错的关系
海明距离为d+1的编码能检测出d位差错

奇偶校验码
校验位的值取“0”还是“1”，取决于整个码字的总的“1” 的个数。（奇数还是偶数）

原理：如果是奇校验加上校验位后,编码中1的个数为奇数个。如果是偶校验加上校验位后,编码中1的个数为偶数个。

例： Data: 1011010（7位原码）
Even: 1011010 0 （7 + 1位 偶校验）
Odd: 1011010 1 （7 + 1位 奇校验）

海明距离与纠错的关系
海明距离为2d+1的编码，能纠正d位差错。
如果一个码字有d位发生差错，距离原来的码字距离最近的可以直接恢复为该码。
当接收到码字后，先比对是否合法，如果不合法，则恢复为海明距离最短的合法码字
例：
一个系统有4个合法码字： 0000000000, 0000011111, 1111100000 和 1111111111
码字之间最短海明距离是 5=2*2+1，所以可纠正2位错误
例：发送： 0000011111
接收： 0000000111（不合法，海明距离依次为[]）
收方纠正后: 0000011111
练习：发送：0000000000
接收： 0000000111
收方纠正后： 0000011111

纠1位错，需要多少位冗余位？
要传输的数据（原码字）是 m 位，冗余位 r ，总长度 n

海明纠错码
每一个码字从左到右编号，最左边为第1位
校验位和数据位
凡编号为2的乘幂的位是校验位，如1、2、4、8、16、…
其余是数据位，如3、5、6、7、9、…
每一个校验位设置根据：包括自己在内的一些位的集合的奇偶值(奇数或偶数)。
计算过程移步：https://blog.csdn.net/lycb_gz/article/details/8214961

纠1位错的海明码的基本方法
发送方：根据校验集合填充校验位。
接收方：根据校验集合判定校验位是否出错，出错的位编号累加到累加器上，所有的校验位都检查完成后，通过读取累加器的值来确定码字中出错的那一位的编号。

循环冗余检验 CRC
循环冗余检验的原理
信息位：发送端要发送的数据
冗余位：发送端在向信道发送信息位之前，先按照某种关系加上一定的冗余位
发送与接收的过程：

• 发送时：信息位+冗余位构成码字发送；
• 接收时：收到码字后查看信息位和冗余位，并检查它们之间的关系（校验过程），以发现传输过程中是否有差错发生。

CRC码又称为多项式码。任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。
长度为最高次幂+1

例如：
假设系统使用的生成多项式为G(x) = X⁴+X+1 (10011)
要发送的码为1101011011（长度为10）
对应的多项式为X⁹+X⁸+X⁶+X⁴+X³+X+1，设为 M(x)

首先将发送码字的多项式乘上生成多项式的最大阶：
T(x) = X⁴ M(X)

乘上多少阶等于向左移动多少位
再将移位后的码字按照（模2运算法则）计算如果有余数，则将码字减去余数
最后得到的码字就是可以发送的码字

当这个码字到达接收方时：
如CRC码在接收端能被10011整除，则说明接收正确。

数据链路层可靠传输协议

停止等待协议（肯定确认重传请求ARQ（也叫PAR））
每次发送帧的时候都会启动一个定时器

注意:
在发送完一个帧后，必须暂时保留已发送的帧的副本。
发送帧和确认帧都必须进行编号。
超时计时器的重传时间应当比数据在传输的平均往返时间更长一些。

停止等待协议的优点是简单，但缺点是信道利用率太低。

信道利用率计算公式：
RTT（来回时间）T_D （发送数据时间） T_A（接收数据时间）

如果忽略处理时间：假设
信道传输速率是： b bps
每帧的大小是： k bits
来回时间是： R sec
则信道的利用率是：k/(k + bR）
如何优化？
使用滑动窗口技术

滑动窗口（连续 ARQ 协议）

发送方有一个发送窗口，存放依据发送未被确认的数据，当数据确认后，滑动到下一个数据
接收方有一个接收窗口，存放期望接收的数据，当期望的数据接收后、滑动到下一个期望接收的数据

使用滑动窗口技术，批量发送数据，就是发送方可以利用等待接收方的确认数据的时间，继续发送数据直到接收到接收方发送的确认数据，再这段时间里发送的数据称为一个窗口。

发送过程图解：

发送方可连续发送多个帧，不必每发完一个帧就停顿下来等待对方的确认。
由于信道上一直有数据不间断地传送，这种传输方式可获得很高的信道利用率。

如何计算最大的窗口数量？
设窗口数量为 W
假设信道的传输利用率达到100%，W * k /（k + bR）= 1
即可得到W的值（b为传输速率（带宽），R 为RTT往返时间，k为每个数据包bit大小）

还有一种计算W值得方法，也是信道利用率 100%：
W = 2 * 时延带宽积 + 1

但是利用率100 % 一般不可能达到。实际的W值会比计算出来的W值小

累积确认
接收方一般采用累积确认的方式。即不必对收到的分组逐个发送确认，而是对按序到达的最后一个帧发送确认，这样就表示：到这个帧为止的所有帧都已正确收到了。

小结
滑窗技术可以批量收发数据，提高了信道利用率。
发送窗口对应着已经发送但还未被确认的帧。

• 滑动条件：收到了帧的确认。

接收窗口对应着期待接收的帧。

• 滑动条件：收到了期待接收的帧。

窗口数的确认跟带宽-延迟积正相关。

解决发送帧出错的协议

Go-back-N（回退 N帧）
如果发送方发送了前 5 个分组，而中间的第 3 个分组丢失了。这时接收方只能对前两个分组发出确认。发送方无法知道后面三个分组的下落，而只好把后面的三个分组都再重传一次。
这就叫做 Go-back-N（回退 N），表示需要再退回来重传已发送过的 N 个分组。

选择重传协议
连续发送W个数据帧，其中有一帧出错，但其后续帧被成功发送
接收窗口存储差错帧后继的所有正确帧
发送方只重传差错帧
接收方接收重传帧，按正确顺序将分组提交网络层

你一定要做自己，做自己喜欢的事，然后把自己交给命运

本章启航思维导图

数据链路层

数据链路层基本概念

• 结点：主机、路由器
• 链路：网络中两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤和微波。分为有线链路、无线链路。
• 数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路。
• 帧：链路层的协议数据单元，封装网络层数据报。数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。

数据链路层功能概述

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

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

封装成帧

• 封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结東。
• 首部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确定帧的界限）。
• 帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。

透明传输

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

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

• 组帧的四种方法：1.字符计数法，2.字符（节）填充法，3.零比特填充法，4.违规编码法

组帧的四种方法

字符计数法

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

字符填充法

零比特填充法

违规编码法

上述四种组帧方式的总结

• 由于字节计数法中 Count字段的脆弱性（其值若有差错将导致灾难性后果）及字符填充实现上的复杂性和不兼容性，目前较普遍使用的帧同步法是比特填充和违规编码法。

链路 (link) 是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分。

数据链路 (data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。

1. 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。(网卡工作在数据链路层)
2. 一般的适配器都包括了数据链路层和物理层这两层的功能。（路由器的接口也是工作在数据链路层）

也有人采用另外的术语。这就是把链路分为物理链路和逻辑链路。

物理链路就是上面所说的链路。

逻辑链路就是上面的数据链路，是物理链路加上必要的通信协议。

早期的数据通信协议曾叫做通信规程 (procedure)。因此在数据链路层，规程和协议是同义语。 

在数据链路层，探讨的是如何将一段数据传递给另外一个节点的接口。在传递的时候变成电信号，光信号，还是无线信号，我们并不关心这个，因为这是物理层需要做的事情。

数据链路层像个数字管道 

---

常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。

 数据链路层不必考虑物理层如何实现比特传输的细节。甚至还可以更简单地设想好像是沿着两个数据链路层之间的水平方向把帧直接发送到对方。

 三个基本问题

---

数据链路层协议有许多种，不管是哪种数据链路协议，但有三个基本问题则是共同的。这三个基本问题是：

• 封装成帧
• 透明传输
• 差错控制

1.封装成帧

---

分组：当一台端系统向另外一台端系统发送数据时，通常会将数据进行分片，然后为每段加上首部字节，从而形成计算机网络的专业术语：分组。这些分组通过网络发送到端系统，然后再进行数据处理。

• 封装成帧 (framing) 就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。（网络层给你了数据包，网卡就要将其封装一下，加上头和尾部，从网络层给到数据链路层的ip数据报大小是有限制的，叫做最大传输单元，以太网是1500个字节，如果超过了这个大小，那么网络层的IP数据包就要分片）（封装成帧的意思就是给网络层的数据包加上头和尾，有头有尾代表一个完整的数据）
• 首部和尾部的一个重要作用就是进行帧定界。

 举例：用控制字符进行帧定界的方法举例

---

当数据是由可打印的 ASCII 码组成的文本文件时，帧定界可以使用特殊的帧定界符。

控制字符 SOH (Start Of Header) 放在一帧的最前面，表示帧的首部开始。另一个控制字符 EOT (End Of Transmission) 表示帧的结束。

ASCII表里面有非打印的字符，这些字符不是键盘输入的，都是一些控制字符。 

2. 透明传输

---

如果数据中的某个字节的二进制代码恰好和 SOH 或 EOT 一样，数据链路层就会错误地“找到帧的边界”。当作无效帧丢弃就产生错误了。 

解决透明传输问题

解决方法：字节填充 (byte stuffing) 或字符填充 (character stuffing)。

发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)。

接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。

如果转义字符也出现在数据当中，那么应在转义字符前面插入一个转义字符 ESC。当接收端收到连续的两个转义字符时，就删除其中前面的一个。

封装成帧加上头和尾，传输的时候加上转义字符，接收的时候去掉转义字符，加头和尾的过程叫做封装成帧，插入转义字符和去掉转义字符的过程叫透明传输。

不同链路协议解决的透明传输的方法不一样，这个转义字符到底是啥，完全由数据链路层搞定，但是，所有的数据链路层都要解决这个问题。

透明

指某一个实际存在的事物看起来却好像不存在一样。

“在数据链路层透明传送数据”表示无论发送什么样的比特组合的数据，这些数据都能够按照原样没有差错地通过这个数据链路层。

透明传输是指不管所传的数据是什么样的比特组合，都能在链路上传输，当所传输的数据中的比特组成恰巧与链路层的某个控制信息完全一致时，就必须采取适当的措施，这样才不会使控制数据与需要传输的数据混淆，这样才能确保数据链路层的透明传输。

 3. 差错检测

---

链路层数据以帧的形式发送，在发送的过程中，接收方节点的链路层硬件可能会由于信号干扰或者电磁噪音等原因错误的把 1 识别为 0 ，0 识别为 1。这种情况下没有必要转发一个有差错的数据报，所以许多链路层协议提供一种机制来检测这样的比特差错。通过让方节点在帧中包括差错检测比特，让接收节点进行差错检查，以此来完成这项工作。

运输层和网络层通过因特网校验和来实现差错检测，链路层的差错检测通常更复杂，并且用硬件实现。差错纠正类似于差错检测，区别在于接收方不仅能检测帧中出现的比特差错，而且能够准确的确定帧中出现差错的位置。

差错检测和纠正的技术主要有

• 奇偶校验：它主要用来差错检测和纠正

• 校验和：这是一种用于运输层检验的方法

• 循环冗余校验：它更多应用于适配器中的链路层

• 在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。
• 误码率与信噪比有很大的关系。
• 为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。
• 在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。 

帧的数据部分+数据链路层首部来计算帧校验序列，计算完之后将帧校验序列写到FCS一块发出去。接收端收到之后使用帧校验序列来验证里面有没有差错。如果有差错就丢掉了。

在数据链路层是不可靠传输，如果有差错就直接丢弃，不会重传。

数据链路层有没有重传功能，完全看数据链路层协议有没有这个功能。ppp hdlc以太网协议都不具有可靠传输，有错误就直接丢弃，由传输层来实现。

需要注意的是校验的部分是帧的数据部分和数据链路层首部，检擦这些部分在传输过程当作有没有差错。用于校验的部分写到帧的FCS位置。

循环冗余检验的原理

• 在发送端，先把数据划分为组。假定每组 k 个比特。
• 在每组 M 后面再添加供差错检测用的 n 位冗余码，然后一起发送出去。

 冗余码的计算

• 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。
• 得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少 1 位，即 R 是 n 位。
• 将余数 R 作为冗余码拼接在数据 M 后面，一起发送出去。

冗余码的计算举例

• 现在 k = 6, M = 101001。
• 设 n = 3, 除数 P = 1101，
• 被除数是 2nM = 101001000。
• 模 2 运算的结果是：商 Q = 110101，余数 R = 001。
• 把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM + R，即：101001001，共 (k + n) 位。  

 循环冗余检验的原理说明 

假设101001是我们要传输的数据，冗余码需要生成3位二进制，这个时候就需要在原始数据后面加上3个0，然后选一个除数，除数要比冗余码多一位，冗余码是3位，除数就得是4位。

这个除数其实是每种协议提前定义好的，发送端和接受端都知道这个除数。

冗余码的计算

 接收端对收到的每一帧进行 CRC 检验

(1) 若得出的余数 R = 0，则判定这个帧没有差错，就接受 (accept)。

(2) 若余数 R ≠ 0，则判定这个帧有差错，就丢弃。

• 但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。
• 只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。

帧检验序列 FCS

---

算出来的CRC叫做帧校验序列，CRC是一个算法，当然也可以通过其他算法得出帧校验序列，FCS的计算方法除了CRC还有其他算法算出帧校验序列。

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

循环冗余检验 CRC 和帧检验序列 FCS 并不等同。

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

应当注意

---

•  仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受 (accept)。
• “无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。
• 也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。
• 单纯使用 CRC 差错检测技术不能实现“无差错传输”或“可靠传输”。

• 应当明确，“无比特差错”与“无传输差错”是不同的概念。
• 在数据链路层使用 CRC 检验，能够实现无比特差错的传输，但这还不是可靠传输。
• 要做到“无差错传输”（即发送什么就收到什么）就必须再加上确认和重传机制。
• 本章介绍的数据链路层协议都不是可靠传输的协议。

 

 

 

补充

---

1 数据链路层概述

数据链路层在物理层提供的服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。数据链路层在不可靠的物理介质上提供可靠的传输。

该层的作用包括：物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。

有关数据链路层的重要知识点：

• 数据链路层为网络层提供可靠的数据传输；

• 基本数据单位为帧；

• 主要的协议：以太网协议；

• 两个重要设备名称：网桥和交换机。

封装成帧：“帧”是数据链路层数据的基本单位：

透明传输：“透明”是指即使控制字符在帧数据中，但是要当做不存在去处理。即在控制字符前加上转义字符ESC。

2 数据链路层的差错监测

差错检测：奇偶校验码、循环冗余校验码CRC

• 奇偶校验码–局限性：当出错两位时，检测不到错误。

• 循环冗余检验码：根据传输或保存的数据而产生固定位数校验码。