数据链路层

数据链路层基本概念

结点：主机，路由器，由边相连的两个节点叫做相邻节点

链路：网络中两个节点之间的物理通道，传输介质主要有双绞线，光纤，微波，分为i有线链路和无线链路

数据链路：网络中两个节点之间的逻辑通道，控制数据传输协议的硬件+软件加到链路上就构成了数据链路

帧：链路层的协议数据单元，封装网络层数据报

数据链路层负责通过一条链路从一个节点向另一个五莲链路直接相连的相邻节点传送数据报。

功能:

为网络层提供服务。无确认无连接服务(不管有没有收到都不重发，实时通信)，有确认无连接服务(没有收到确认信号就重新发送，无线通信)，有确认面向连接服务(事先建立好连接，一定要确认信号)
链路管理，连接的建立，维持，释放(用于面向链接服务)
组帧
流量控制(限制发送方)
差错控制(帧错，位错)

封装成帧

在数据的两端添加首部和尾部，构成一个帧。根据首部h额尾部的标记，从收到的比特流中识别帧的开始和结束。

首部和尾部有很多的控制信息，最重要的作用就是帧定界

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

组帧方法：1.字符计数法。2.字符(节)填充法。3.比特流填充法。4.违规编码法

透明传输：不管所传数据是什么样的比特组合，都应当能够在链路上传送。

字符计数法

帧开头的第一个数字表示帧的长度，如果这个数字错了，就会导致后面所有帧都出错(不常用)

字符填充法

使用SOH作为帧的起始标志，EOT作为帧的结束标志，这里的标志就是某种形式的二进制数字组合。

对于键盘输入的内容，通常都是ASCII码的形式，不会和SOH与EOT标志进行重复，而对于文本文件和图像文件，则会有可能出现与SOH与EOT相同的编码信息，这时候需要ESC转义字符说明这个不是真正的SOH和EOT，对于与ESC相同的转义字符，也只需要在前面加上一个ESC即可。在发送之前使用ESC对SOH，ESC和EOT进行字节填充，之后发送出去，在接收方删除所有的转义字符ESC，接着就可以得到原始的帧了

零比特填充法

使用01111110(2个0，6个1)作为起始标志额和结束标志，具体操作如下：

在发送端，扫描真个信息字段，只要出现连续5个1，就直接填入1个0（不管5个1后面是不是0都要填0）
在接收端收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描，发现连续5个1时，就把后面的0删除（避免出现6个1的情况）

保证了透明传输：在传送的比特流中可以传送任意比特组合,而不会引起对帧边界的判断错误

违规编码法

在曼切斯特编码中，在一个时钟周期内，高-低表示1，低-高表示0，或者与这个相反，不存在高-高，低-低的情况，因此违规编码法就使用了这两个电平信号来定界帧的起始和终止。

组帧方法总结

由于字节计数法中计数字段的脆弱性及i字符填充实现上的复杂性和不兼容性，目前较普遍使用的帧同步法是比特填充和违规编码法

差错控制

$差错产生的原因\begin{cases} 全局性\begin{cases} 线路本身的电气特性产生的随机噪声(热噪声)，固有，随机存在 \\ 解决方案：提高信噪比来较少或避免干扰(传感器下手) \end{cases}\\ 局部性\begin{cases} 外界特定的短暂原因所造成的冲击噪声\\ 解决方案：利用编码技术解决 \end{cases} \end{cases}$

$差错类型\begin{cases} 位错：比特为出错，0变成1，1变成0\\ 帧错(发送1，2，3)：\begin{cases} 丢失：收到1，3\\ 重复：收到1,2,2,3\\ 失序：收到1,3,2 \end{cases} \end{cases}$

对于通信质量好有线传输链路，使用无确认无连接的服务，对于通信质量差的无线传输链路。使用有确认无连接，或有确认面向链接的服务

$差错控制（比特错）\begin{cases} 检错编码\begin{cases} 奇偶校验码\\ 循环冗余码CRC \end{cases}\\ 纠错编码——海明码 \end{cases}$

检错编码——奇偶校验码

$奇偶校验码(n-1位信息元，1位校验元)\begin{cases} 奇校验码——1的个数为奇数 \\ 偶校验码——1的个数为偶数 \end{cases}$

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

检错编码——CRC循环冗余码

准备带传输的有效数据，分成若干组，每组长度为d
每个组都加上冗余码构成帧在发送，首先是要构成d位+r位的FCS，首先将FCS的位置全部补成0，使用生成多项式(一般会直接给出，用二进制的形式，如果是多项式就用他系数作为二进制编码)进行除法(同0异1)，然后得到的余数i玩儿r位的FCS，与d位数据进行拼接
在接收方收到r+d位数据，使用生成多项式进行除法操作(同0异1)，余数为0，则认为正确接收，反之则丢弃
r的长度为多项式的阶，最高幂

FCS的生成及接收端CRC检验都是由硬件实现的，处理速度很快，不会延误数据的传输。

纠错编码——海明码

海明距离：对于两个合法编码的对应比特取值不同的位数成为这两个码字的海明距离(码距)，如果有多组编码，就取任意两组的海明距离中，最小的那一组作为该组的海明距离

比如，001和110的海明距离为3，001,110,111的海明距离为1

要检错d位，则需要d+1位海明码

纠错d位，则需要2d+1位海明码

确定校验码的位数r

假设数据有m位，冗余码有r位，校验码一共有 $2^r$ 种取值，r的取值满足海明不等式 $2^r\geq m+r+1$ ,对应的意思就是，冗余码能纠错的位数，必须大于等于数据和冗余码都发生错误+1
确定校验码和数据的位置

将校验码放在 $2^n$ 的位置上，如下例子所示：
求出校验码的值

如图所示，x4可以管理符合1**类型的数据，其他同理，所以可以得到分组

$\begin{cases} x_4=\{4,5,6,7\}\\ x_2=\{2,3,6,7\}\\ x_1=\{1,3,5,7\} \end{cases}$

分组结束后，组内对应位置的比特为要满足偶校验的要求(一般是用偶校验)，然后就可以求出对应的校验码了，比如x4的组内位110x，有偶数个1，所以x的值应该为0，即x4=0，所以正确的海明码为110,0001

检错与纠错

假设我们收到的结果不是110,0001，而是111,0001可以看到是i第五位发生了错误(序号从左到右递减)

按照3里面的分组，我们检验一下

$\begin{cases} x_4 = \{1110\}->奇数位，错误\\ x_2 = \{1100\}->偶数位，正确\\ x_1 = \{1101\}->奇数位，错误\\ \end{cases}$

检错完成，接下来是纠错

对没一组都进行一个偶校验，同时用x4，x2，x1补上一位，例如

x4 1 1 1 0
x2 1 1 0 0
x1 1 1 0 1
对上面的每一行，使其满足偶校验，可以得到x4,x2,x1的值为1,0,1
101转化位十进制为6，整好错误的是第5位，将其取反,成功解决问题

流量控制方法

停止——等待协议：每发送玩一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。

滑动窗口协议：在发送端的发送窗口包含多个帧，这多个帧可以连续发送，然后在接收端只有一个接收窗口，接收到发送端传来的对应帧，就返回确认信号，发送窗口向右滑动，继续连续发送。

停止——等待协议就是特殊的滑动窗口协议，只是在发送端的发送窗口只有1个帧罢了。

$\begin{cases} 停止等待协议——发送窗口=1,接收窗口=1;\\ 后退N帧协议(GBN)——发送窗口>1,接收窗口=1;\\ 选择重传协议(SR)——发送窗口>1,接收窗口>1;\\ \end{cases}$

可靠传输：发什么，收什么

$滑动窗口解决\begin{cases}流量控制(收不下就不给确认，想发也发不了)\\可靠传输(发送方自动重传)\end{cases}$

停等协议——有差错情况

数据帧丢失或检测到帧错误
1. 每次发送一个帧都会启动一个超时计时器
2. 超时计时器设置的重传时间应该比帧传输的平均RIT更长一些
3. 发完一个帧1后，必须保留他的副本
4. 数据帧和确认帧必须编号
确认帧丢失
1. 发送方未收到确认帧，到达超时时间后，再次重发帧，在接收端替换掉之前的帧，然后重新传递确认帧
确认帧迟到
1. 第一个帧的确认信号在超时计时器时间内没有到达，就会重新发送帧，发送后接收到了帧的确认，接着发送下一个帧，这时候最初发送的帧的确认信号才传递过来，这时就接收h这个确认帧，然后丢弃掉。
信道利用率：

发送方在一个发送周期内，有效地发送数据所需要的时间占整个发送周期的比率：

$信道利用率=\frac{\frac{数据帧长度}{传输速率}}{\frac{数据帧长度}{传输速率}+2\times 单程传播时延}=\frac{数据帧长度}{数据帧长度+2\times单程传播时延\times传输速率}$

信道吞吐率 =信道利用率 $\times$ 发送方的发送速率

后退N帧协议(GBN)

GBN发送方必须响应n三件事

上层调用：上层发送数据时，先要检查滑动窗是否i已满，否加入，是则返回上层。实际中都会将发送内容缓存起来
收到确认帧信号：GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和他之前的全部帧。
超时事件：如果0号帧发送成功，接收方要接收1号帧，但是1号帧发送过程中丢失了，结果2号帧到了，接收方也不收，等到超时计时器时间到后，重新发送1号帧开始的滑动窗口

GBN接收方必要做的事

1. 如果正确收到n号帧，并且是按序接收，就返回给发送放n帧的ACK，并将该帧的数据交付给上层
2. 如果发送方发送1，2，3，4，5，但是接收方只收到1,2,4,5就会吧4，5舍弃掉，然后再次发送2的ACK

重点内容：

累积确认
接收方只按顺序接收帧，不按序就丢弃
确认序列号最大的，按序到达的帧
发送窗口最大为 $2^n-1$ ，接收窗口为1

选择重传协议(SR)

发送方：

上层调用：收到上层数据后，检查下一个可用于该帧的序号是否在滑动窗中，是就发送，不是就缓存或上传
收到一个ACK：加入该帧序号在窗口内，表示SR发送方将那个被确认的帧标记为已接收，如果该帧序号是滑动窗口的下届，窗口向前移动到最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内还未发送，则发送这些帧
超时事件：每个帧都有之际的定时器，一个超时时间发生后只重传一个帧

接收方：

收到的内容就返回ACK，并进行缓存，然后只有当前接收方滑动窗口的下界返回了ACK滑动窗口才会移动，滑动窗口后面的帧，一律不接收

重点内容：

对数据帧逐一确认，收一个确认一个
只重传出错帧
接收方有缓存
发送方和接收方滑动窗口的最大值均为 $2^{(n-1)}$

传输数据使用的两种链路

点对点链路，两个节点建立一条链路相连，没有第三者，应用PPP协议，常用于广域网
广播式链路，所有主机共享传输介质，拓扑结构：总线型，星型(逻辑总线型)

介质访问控制

采取一定的措施，使得两对节点之间的通信不会发生相互干扰的情况

$介质访问控制\begin{cases}静态划分信道——信道划分介质访问控制 \begin{cases} 频分多路复用FDM（Frequence）\\ 时分多路复用TDM（Time）\\ 波分多路复用WDM（Wave）\\ 码分多路复用CDM（Code） \end{cases} \\动态分配信道 \begin{cases} 轮询访问介质访问控制——令牌传递协议\\ 随机访问介质访问控制(重点) \begin{cases} ALOHA协议\\ CSMA协议\\ CSMA/CD协议(重点)\\ CSMA/CA协议(重点) \end{cases} \end{cases} \end{cases}$