数据链路层

成帧技术

核心要点：拆分比特流，并且要对面能够识别出帧。

字符计数法

将字符的数量放在帧的第一位上作为开头。
缺点：只要发生一次传输错误，就会引起后面所有帧崩溃。

字节填充法

用特殊字节/字符标记帧的开头和结尾。一般是8个字节
如果包含和特殊字符一样的一些字节，那么再在特殊字符前面填充一个特殊的字符ESC

这里要注意哦，比较容易考让你从左侧到右侧

比特填充法

用一串特殊的比特标记开头和结尾。一般含有连续的1或者0，比如01111110
为了防止在传输的内容中出现这一串特殊的比特，我们在每连续的五个1后面都加入一个0。
这样就防止了冲突。

物理层编码违例法

中心思想：在物理层中，某些信号不会出现在传输过程中，比如曼彻斯特编码里面一定有一个上升沿/下降沿，但是我可以使用未曾出现过的编码，比如在里面用一个纯高电平表示帧的开始用低电平表示帧的结束。

差错控制

中心思想：确保所有的帧最终都按正确顺序到达接收方
差错类别：
- 帧丢失
- 帧损坏

错误检测

对于可靠信道而言，使用错误检测然后重传的方法，相比于错误纠正的方法其实成本更低。

EDC码（ERROR-DETECTING-CODE）

奇偶校验码

和数电中的一样，不多赘述。

交错检验码

传输的比特被编码为块，每个块包含个矩阵，每一列都单独运算。
可以根据奇偶校验码等方式计算每一列的奇偶校验码
一次最多可以检测n位的错误（单个突发型错误）

CRC码（重点）

循环冗余检测方法，为了快速的应试，这里不做原理说明。
按例题来说明：
假设要发送的数据是1101011011，生成多项式为10011
生成多项式可得：
计算生成多项式的最高位的幂次：得到是4
在发送数据后加入4个0得到11010110110000
然后做除法运算：
得到余数1110（这个计算的过程，减法的环节其实就是对每一位做异或得到的结果）
我们舍弃商，把余数添加到原始数据的后面得到11010110111110
即为发送数据
如何检测是否误码？
对接收到的数对生成多项式做除法，如果能整除，那么就判断无误，否则有误。

错误纠正

ECC码（ERROR-CORRECTING-CODE)

基本思路：将冗余信息注入待发送的消息中，来纠正某些错误。
包括块编码、系统码、线性码等，其中线性码的线性构造函数主要是XOR异或。

为了实现ECC，我们采用汉明距离来计算两个不同的码字之间的距离。
定义汉明距离：两个码字之间的不同的位数。
一个码组之间的最小汉明距离，决定了这个码组可以纠正的最多的位数。
假设可以纠正的位数是k，最小汉明距离为z那么有:(根据最大相似原理得到)
至于检查错误，如果要检查m位错误的话，最小汉明距离为z，那么有关系:(比最小的汉明距离还小，那不就检测出错误了吗)

计算：纠正一位错误所需检测位位数

设m为消息的位数，r为检测位位数，n = m+r，那么，为了检测一位错误，一共有合法的消息，对于每一个合法消息，都有n个非法的，错误为一位的消息，那么一共就有消息，那么为了保证能够纠错，就一定要有
经过推导可以得到

设计ECC:汉明码

（本文会讲的比较应试，原理方面可以看我的专栏群码系统）讲解
首先，我们根据上文中的公式算出所需增加的检测位数，根据算出他们的位置，然后把每个位数所管的哪些位数通过二进制编码的方式来算出。
然后再根据奇校验/偶校验的方式算出检测位数的值，最终得到汉明码。
下面根据例题来说明：

在这道例题中，我们算出新增校验位一共有4个。因此得到校验码的位置分别为1,2,4,8.
然后我们根据右侧的二进制编码格式，算出b1需要检测哪些二进制码在第一列中为1的位置，即b3,b5,b7,b9,b11，以此类推得到b2,b4,b8需要检测的各自的位置。
本题中采用偶校验，因此，我们需要让它得到偶数个1，从而得到b1,b2,b4,b8为0,0,0,1
即得汉明码。00100001001

关于纠错方面，目前的纠错方法就是根据校验位错误的地方，再加上知道校验位的计算过程，反推出哪些位错了。
比如接收到的结果如下，就可以知道是b5错了

流控制

中心思想：确保发送的帧不会导致接收方堆栈溢出
我们本章所学的，都是基于反馈的流控制。

Stop-and-wait协议

乌托邦单工协议

三个假设：
- 信道单工
- 信道无错
- 接收方无限缓存空间
该假设下，无需任何差错控制和流控制，直接无脑有包就传就行。

单工Stop-and-Wait协议（用于无错信道）

三个假设：
- 信道单工
- 信道无错
- 接收方有限缓存空间
该假设下，无需差错检测，但是需要流控制技术来防止缓存的溢出。
Stop-and-Wait工作过程如下：
1、发送方发送帧，等待
2、接收方返回ACK帧
3、发送发收到ACK帧，继续发下一帧
（可以通过不发ACK帧来停止接收信息）
当出现错误时：当接收方利用CRC检测到错误时或者没收到这个帧时，都直接丢掉这个包，不返回ACK，这时如果发送方的定时器过时，会自动重传这个帧。

PAR协议(Positive ACK with Retransmission)

三个假设：
- 信道单工
- 信道有错
- 接收方有限缓存空间
这个假设带来了新的问题：
1、当ACK帧丢失，那么发送方还会重传，这个包会重复
解决方法：在帧的头部加一个序列号，防止重复
2、ACK帧的到达比定时器归零的时刻还要晚，即已经重发包了才收到ACK，会导致多个ACK的重复
解决方法：给ACK帧也加上序列号，让他知道是对哪个帧做的回复
本协议使用了ARQ机制，即自动请求重传的机制，当接收方利用CRC检测到错误时或者没收到这个帧时，都直接丢掉这个包，不返回ACK或者返回NAK，这时如果发送方的定时器过时，会自动重传这个帧。利用序列号防止ACK或者帧的重复

综上，只需在Stop-and-Wait工作过程的基础上，在帧和ACK中加入序列号即可。

Sliding-Window协议

相比于Stop-and-Wait协议，本协议的优势主要在于：
1、可以并行传输数据包，不用传一个然后就傻等
2、允许一次发送多个数据包
该协议中所有的协议的假设同为以下：
- 全双工数据传输
- 信道有错
- 接收方有限缓存空间
- 使用捎带确认(piggybacking)技术，来解决全双工，过程如下所示
1、当帧到达，开始计时
2、若此时有网络层数据到来，封装成帧，并将ACK加入其中，发送
3、若直到计时器为0前也没有数据到达，那么只发送ACK回复

大小为1的滑动窗口协议

发送窗口：大小为1
接收窗口：大小为1
序列号：n = [0,1]

根据以上这个图来描述，橙色部分为发送方，绿色为接收方。
过程如下：
1、发送方发送序列为0的包，等待接收一个0的ACK
2、接收方接收到序列为0的包，发送序号为0的ACK，然后窗口向前移动
3、发送方收到序列为0的ACK，向前移动并发送序列为1的包
反复循环即可

接下来我们将要拓展滑动窗口的大小，为了实现这个拓展，我们先来搞一点数学：

滑动窗口大小和序列号之间的数学关系

发送方的窗口大小一般是要大于等于接收窗口的大小的，因此，接收窗口大小的上限是由发送窗口决定的。因此我们只讨论发送窗口的大小即可。
对于发送窗口，假设序列空间的大小为n，那么发送窗口的大小范围是
这里的原因解释如下：
序号空间为4， 即:0 1 2 3 0 1 2 3 … , 假设窗口大小为3(大于序号一半)

1. 发送方传012
   
2. 接收方收到，滑动窗口前进至 3,0,1，接收方发回ack
   
3. ack丢失，发送方重传 0,1,2
   
4. 问题来了，此时接收方如何判断是发送方重传的0,1,2还是发送方传了第二个重复序列的0,1,但第一个序列的3丢失了呢？

此时修改窗口大小为序号空间一半，即窗口大小等于2

1. 发送方传0,1
   
2. 接收方收到，滑动窗口移动至2,3，发回ack
   
3. ack丢失，发送方重传0,1
   
4. 接收方看到发送方发0，1,与当前窗口不符，判断重传

Go-Back-N协议

发送窗口：，n为序列空间长度
接收窗口：1

运行逻辑如下所示：
1、发送方窗口同时发送窗口内所有帧，等待ACK
2、接收方每接收一个正确的，就发送ACK和序列码回去。只要接收到一个序列为i的ACK，就说明0~i之间的所有的传输都是正确的
3、但是如果发送窗口中第i个帧错误（丢失或者CRC出错），那么后续传输的所有帧都没用，必须重新从第i个帧重传（这也是它为什么叫做go back N)

关于go-back-N中的错误处理：
如果数据帧受损，接收方丢弃第i帧和后续所有帧，超时之后发送方自动重传。
如果ACK帧受损，如果后续还有帧的话，可能会因为累积ACK而覆盖当前帧的接受，所以基本问题不大。反正如果超时还会重传的

选择重传协议（SR)

主要解决后续帧的重传问题。
首先，窗口大小而言，发送窗口和接受窗口的大小都是
接收方的buffer和窗口大小一样就行，而不是和序列号一样
另外SR不再采用累积ACK

特别的，本课程中，SR是启用累积ACK技术的，为了更好的应对考试，这里需要改为采用累积ACK的形式

运行逻辑：
1、发送方将发送窗口内的数据帧发送出去，并设置定时器A
2、接受方接收窗口内有的数据帧，不论数据是否按序到达。并返回所有正确接收到的数据的ACK
3、接收方窗口向右滑动到第一个未正确接收到的数据帧为止
4、发送方接受所有ACK帧，标记窗口内的包为已成功发送，并向右滑动到第一个未正确接收到ACK帧的数据帧为止。
5、重新发送所有窗口内定时器为0的包，并设置定时器A（所有的未发送过的默认其定时器为0）

其实这个逻辑从整体上来看比较困难，而单从接收方/发送方的角度来看就比较简单了
发送方：把窗口内定时器为0的包全发了，然后设定时器。只要有ACK来了就标记包的状态为已正确发送。然后如果满足窗口移动条件就移动。
接收方：只要正确接收，就返回对应的ACK，然后移动窗口。（没接收到返回NAK）
（NAK的返回逻辑是：收到坏帧或收到的序号不在窗口内）
这个逻辑就很简单了

由于使用了piggybacking技术，那么对于ACK超时定时器的设计，我们需要其满足如下的关系：

其中frame_timer指的是发送方的超时重传定时器的时间

本课程中的运行逻辑(采用累积ACK的)
1、发送方将发送窗口内的未收到ACK的数据帧发送出去，并设置定时器A
2、接收方接受窗口内有的数据帧，不论数据是否按序到达，只返回累积确认的位置(例，假如我收到了0~7，但是第4帧坏了，那么我最多回ACK 3)
3、接收方收到ACK之后，标记前面的都为已接收状态，并滑动窗口，然后重发帧
4、接收方只要收到序列号为4的帧，那么直接回ACK 7
5、反复即可

流控制协议效率分析

为了分析一个协议的信道利用效率，我们首先介绍以下两个时间：
1、RTT时间(round-trip-time)
2、帧传输总时间(frame-transfer-time):接收方收到完整帧的总时间

无错停等协议效率分析

总时间可以由以下公式得到:
其中n是帧的数量，T是总时间，这里选择性的省略了处理时间和ack的发送时间（ack很短，发送时延忽略）
根据计算信道利用率的核心思想：
即得利用率
可以消去n得到：

有错信道停等协议效率分析

假设每个帧错误的概率为p，每个帧发生错误的事件相互独立，设Y为每个帧的重传次数
那么有：每个帧的重传次数为
得到效率为

无错滑动窗口协议

对其进行归一化处理后，使得传输时间为1，传播时间为a
那么当的时候，很显然，发出的包把所有的信道都占满了，然后第一个包才返回回来，此时利用率为100%
当时，
如果考虑piggybacking技术，那么返回的ACK帧也必须考虑其发送时延。也即

最大吞吐量的计算

最大吞吐量等于信道带宽乘以信道利用率

两种数据链路层的实际协议

下面是对PPP（Point-to-Point Protocol）协议和HDLC（High-Level Data Link Control）协议的对比总结，并以表格形式呈现：

特性	PPP (点对点协议)	HDLC (高级数据链路控制)
应用场景	点对点链接	广域网(WAN)，支持多种配置
物理层传输	异步或同步串行传输	同步串行传输
服务类型	无连接不可靠服务	面向连接的可靠传输
功能	流量控制、错误控制、GoBackN ARQ、SR ARQ	流量控制、错误控制、GoBackN ARQ、选择重传ARQ
差错检测方法	CRC	CRC
协议数据单元(PDU)	字节导向	比特导向
帧定界	字节填充法	比特填充法
连接协商	支持，可以动态分配IP地址，支持用户身份认证，可协商数据压缩	不支持相关链路和网络参数的协商，不支持认证

解释：

• 应用场景：PPP主要应用于点对点的直接连接，而HDLC则适用于广域网环境，并且能够适应不同的配置。
  
• 物理层传输：PPP可以在异步或同步环境中操作，而HDLC专门用于同步串行链路。
  
• 服务类型：PPP提供的是无连接的服务，意味着它不保证数据包的顺序或传递；相比之下，HDLC提供面向连接的服务，确保所有帧按序到达目的地。
  
• 功能：两者都提供了流量控制和错误控制机制。此外，它们也都支持GoBackN自动请求重传(ARQ)和选择重传(SR ARQ)策略来处理丢失或损坏的数据帧。
  
• 差错检测方法：两者都使用循环冗余校验(CRC)进行错误检测。
  
• 协议数据单元(PDU)：PPP是基于字节的操作，而HDLC则是基于比特的。
  
• 帧定界：PPP采用字节填充技术来标识帧边界，HDLC则通过比特填充实现这一目的。
  
• 连接协商：PPP的一个显著特点是它可以与多个网络层协议协同工作，并允许在连接建立时进行协商（例如动态IP地址分配、用户身份验证和数据压缩等）。然而，HDLC缺乏这些能力。