[网络协议]计算机网络-数字链路层-CRC、分组码、选择重传协议、滑动窗口协议

数据链路层的功能

数据链路层在物理层提供的服务的基础上通过执行数据链路层协议向网络层提供服务,其最基本的服务就是将从源机器网络层来的数据可靠地传输到目标机器网络层。

帧同步

由差错控制码产生的校验和可以检查出一个帧在传输中是否发生了错误。一旦检查出错误,就通常采用反馈重发的方法来纠正错误。发送方只有等收到接收方已正确接收的反馈信息后才能认为该帧已正确传送完毕,从而不再保留该帧。

1. 帧丢失 ：物理信道可能丢失帧,包括数据帧或者传递反馈信息的帧,这使发送方永远也收不到接收方已正确接收的反馈信息而无限地等待下去。为了避免出现这种情况,通常引入计时器(timer)。计时器超时(timeout)后还未收到接收方确认正确接收的返回信息时,可认为传出的帧已出错或丢失,因而要重新发送。在正常情况下,若在计时器未超时前已收到确认信息,则可将计时器清零。
2. 重复发送：同一帧被重复发送多次,就存在接收方两次或多次收到同一个帧,并将它交给上一层(即网络层)的危险。为了防止这种情况发生，有必要对发送的帧编号,即给每个帧一个序号,从而使得接收方能从该序号来区分是新发送的帧,还是已被接收但发送方又重新发送来的帧,从而决定是不是交给网络层。

流量控制

流量控制实际上是控制发送方的数据流量,使其发送速率不要超过接收方所能处理的速率。在这个过程中需要通过某种反馈机制使发送方知道接收方是否能来得及处理。

差错控制

1. 差错检测与矫正

概括地说,传输中的差错都是由噪声所引起的。

1. 随机热噪声: 信道所固有的,持续存在的;随机热噪声所引起的差错称为随机错,造成某些码元的差错是孤立的,与前后码元没有关系。
2. 冲击噪声:由于外界短暂的特定原因所造成的。冲击噪声是传输中产生差错的重要原因。这种差错呈突发状态,称为突发错误。
   突发长度：从突发错误发生的第一个码元到发生错误的最后一个码元间所有码元的个数。

误码率： $$P_e=\frac{发生差错的码元数}{接收的总码元数}$$

2. 差错控制编码

要发送的数据,称为信息位或信息码元,在向信道发送之前,先按照某种关系加上一定的冗余位或监督位,构成一个码字再发送。接收方收到码字后查看信息位和冗余位,并检查它们之间的关系(校验过程),以发现传输过程中是否有差错发生。
$$码字（k+r位）=信息位（k位）+冗余位/监督位（r位）$$
编码效率R：它是码字中信息位所占的比例。
$$R=\frac{k}{k+r}$$
编码效率越高,即R越大,则信道中用来传送信息码元的有效利用率就越高。

检错码：检测错误的码。
纠错码：纠正错误的码。

码长:码字中码元的数目
码重:码字中非0数字的数目;对于二进制码来讲,码重W就是码字中1的数目,例如对于码字10100而言,码长n=5,码重W=2。
码距:两个等长码字之间对应位不同的数目,有时也称作这两个码字的汉明距离,例如码字10100与11000之间的码距d=2。
最小码距：在码字集合中全体码字之间距离的最小数值,表示为d_min。对于二进制码字而言,两个码字之间的模2相加,其不同的对应位必为1,相同的对应位必为0。因此,两个码字之间模2相加得到的码重就是这两个码字之间的距离。

3. 差错控制方式

1. 前向纠错：接收方检测出有差错时,就设法通知发送方重发,直到收到正确的码字为止。这种方法只需要用检错码,但必须有双向信道,就有可能将差错通知给发送方,同时发送方要有数据缓冲区存放已发出去的数据,以便出现差错时可重新发送。
2. 自动请求重发：接收方不但能发现差错,而且能确定错误码元的位置,从而可以加以纠正。
   必须用纠错码,不需要反向信道来传递请求重发的信息,发送方也不需要存放以备重发的数据的缓冲区。
   由于纠错码一般要比检错码使用更多的冗余位,编码效率更低, 纠错的设备也比检错的设备复杂得多，在单向传输或对实时要求特别高(不需要重发,实时性较好)的场合应用。
3. 混合纠错：接收方具有纠错和检错的能力:当码字中的差错个数在纠正能力以内时,直接进行纠正;当码字中的差错则检出差错,请求发送方重发来纠正差错。

1. 奇偶校验码

奇偶校验码:通过增加冗余位使得码字中1的个数保持奇数或偶数。
码据：d=2。在奇偶校验码中,若两个数中有奇数位不同,则它们相应的校验位就不同;若有偶数位不同,则虽校验位相同,但至少有两位数据位不同。因而任意两个码字之间至少有两位不同。
特点：

1. 根据码距和纠/检错能力的关系,它只能发现奇数位出错,不能发现偶数位出错,而且也不能确定发生错误的位置,不具有纠错能力。
2. 开销小,适用于校验一字节长的代码,故常被用于存储器读写检查或按字节传输过程中的数据校验

2. 循环冗余码 CRC

CRC在发送方编码和接收方校验时都可以利用一个事先约定的生成多项式G(x)来进行。k位要发送的信息位可对应于一个k-1次多项式K(x),r位冗余位对应于一个r-1次多项式R(x)。由k位信息位后面加上r位冗余位组成的n=k+r位码字则对应于一个n-1次多项式:
$$T(x)=x^r?K(x)+R(x)$$

由信息位产生冗余位的编码过程,就是已知K(x)求R(x)的过程,在CRC中可以通过找到一个特定的 r 次多项式G(x)来实现(r+1位)。用G(x)去除x·K(x)得到的余数多项式就是R(x)。
由于R(x)是G(x)除x·K(x)的余数多项式,因此必然有
$$x?K(x)=G(x)?Q(x)+R(x)$$即：$$x?K(x)/G(x)=R(x)$$
用“/”来表示求余数多项式的除法,该除法为模2除法。
例：

模2加法与模2减法均为异或运算。

模2除法：

3.分组码

分组码是一组固定长度的码组,可以表示为(n,k),通常用于前向纠错。
一般说来,信息位为k位,增加r位冗余位,构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同位置的一位错这两种情况,则要求：
$$2^r\ge n+1或者2^r\ge k+r+1$$

2^r需表示包含冗余位在内的每一位的错误与否的情况，同时包含无错的一种情况。

关于码距的详细介绍，可见 https://blog.csdn.net/qq_44675969/article/details/108554556

数据链路协议

1. 停等协议

这个协议规定发送方每发送一帧后就要停下来,等待对方已正确接收的确认(acknowledgement,ACK)帧返回后才能继续发送下一帧。
由于停等协议规定只有一个帧完全发送成功才能发送新的帧,因而只用一位二进制数(0或1)编号就能够进行区分。此外,确认帧ACK也应加上序号以表示是确认哪一帧。

2. 顺序接受的管道协议

为了提高信道的实际有效利用率,需要允许发送方不等确认帧返回就再连续发送若干帧。


回退n：在发送方未收到前面帧的确认信息且计时器已经超时，不得不又重发后面的n帧。

3. 选择重传协议

选择重传协议在某帧出错时减少了后面所有帧都要重传而造成的浪费。但对接收方提出了更高的要求,即要有一个足够大的缓冲区来暂存未按正确顺序接收到的帧。凡是在一定范围内到达的帧,即使未按顺序,也要接收下来。

4. 流量控制的滑动窗口协议

对发送方发送速度的控制以及受发送缓冲区大小的制约等因素都要求对发送方已发出但尚未经确认的帧的数目加以限制。这个数目就称为发送窗口的大小。落在这个窗口内的帧号就是等待接收方返回的ACK帧的帧号。
由于帧号只有有限的位数,因此一定时间后就会反复循环。

停等协议可以看成是发送窗口的大小等于1的滑动窗口协议的特例。

1. 回退n协议：
   若帧号位数为m,则对回退n协议来说,必须使发送窗口的大小小于或等于2^m-1;
2. 选择重传协议：