计网-U3 数据链路层
3.1 数据链路层的功能
向上层下层要做的事情
物理链路：传输介质（0层）+ 物理层（1层）实现了相邻节点之间的“物理链路”
逻辑链路：数据链路层基于“物理链路”，添加了实现通信协议的软硬件，实现相邻节点之间逻辑上无差错的“数据链路/逻辑链路”
**==数据链路层向下（使用服务）==**：使用物理层提供的 “比特传输” 服务。
==数据链路层向上（提供服务）==：为网络层提供服务，将网络层的 分组（IP数据报） 封装成帧，传输给下一个相邻节点。
- 帧 = 首部 + 数据 + 尾部
- 首部和尾部包含各种控制信息。
数据链路层实现的功能(5)
之后一小节就是跟一个功能相关。
①封装成帧（组帧）：⭐
组帧即：定义数据格式。
- 帧定界：即如何让 接收方（对面的数据链路层） 能够 确定帧的界限。
- 透明传输：接收方 要能从收到的帧内恢复原始SDU，让网络层“感受不到”将分组封装成帧的过程。（即把帧定阶的附加信息去除，把帧“恢复原貌”）
- （透明性的拓展，其实数据链路层对上层是透明的。）
②差错控制：发现并解决一个帧内部的 “位错误”。
- sol1：接收方 发现比特错后 丢弃帧，发送方 重传帧。（仅需采用 检错编码）
- sol2：接收方 发现并纠正比特错误。（需采用 纠错编码）
③可靠传输：发现并解决“帧错误”。
- eg 帧丢失，帧重复，帧失序。
④流量控制：控制 发送方 发送帧的速率别太快，让 接收方 有时间接收。（or会导致帧丢失）
⑤介质访问控制：
数据链路层使用的信道主要有两种
- “广播信道” 需要实现此功能。因为广播信道在逻辑上是总线型拓扑，多个节点需争抢传输介质的使用权。
- “点对点信道” 不需要实现此功能。点对点信道意味着两个节点之间有专属的传输介质，不用争抢。
3.2 组帧（的方法）(4)
把 网络层 交给的数据打包成帧的过程。
组帧的好处：数据出错，也只需重发出错的帧，无需重发全部数据。
① 字符计数法
在每一个帧的开头，用一个 定长计数字段 ，记录一下帧长。
- 帧长是包括首部分的计数字段的段长度的。即 帧长 = 定长计数字段长度 + 帧的数据部分的长度。
超级无敌大的缺点：任何一个计数字段出错，会导致后续 所有帧 无法定界。（健壮性差）
② 字节填充法
控制字符SOH表示帧的开始，控制字符EOT表示帧的结束。
插入转义字符ESC，防止SOH/EOT和某些数据段歧义。（接收方做的是逆处理）
再次插入一个转义字符，防止转义字符和某些数据段歧义。（接收方做的是逆处理）
原理：（接收方的逆处理）发现转义字符，会把转义字符去除，后面部分就是数据，以此类推。
③ 零比特填充法
HDLC协议和PPP协议使用的组帧方法就是零比特填充法。
以一串特殊比特串（01111110，连续有6个1）表示帧的开始和结束。
解决和上个方法一样的问题：
- 发送方需要对帧的数据部分进行处理：每当遇到了连续的5个1，就填充一个0
- 接收方需要对帧的数据部分进行处理：每当遇到了连续的5个1，就删去后面的0
④ 违规编码法
eg看曼切斯特编码（中间不跳变作为违规信号）
用违规信号，表示帧的开始/结束。（需要网络层的配合，因为涉及到了编码）
适用：仅适用于冗余编码？的编码环境。
回顾
（字节填充法太复杂，字符计数法缺陷大，采用的组帧方法是零比特填充法和违规编码法）
other
无确认的无连接服务：指的是主机发送帧时不需要先建立逻辑连接，目的主机收到帧时也不需要发回确认。
- 如果是帧丢失，也不检测也不回复。
- 适合：①错误率很低的时候。②实时通信（毕竟数据迟到才是最糟的）
3.3 差错控制(2+1)
==发现并解决帧内部的位错误。==
sol1：接收方 发现比特错后 丢弃帧，发送方 重传帧。（仅需采用 检错编码）
- 奇偶校验码
- ORC校验码
sol2：接收方 发现并纠正 比特错误。（需采用 纠错编码）
- 海明校验码
①奇偶校验码（检错编码）
奇校验码：确保整个校验码【（最高一位）校验位+有效信息位】中1的个数为奇数。
偶校验码：确保整个校验码【（最高一位）校验位+有效信息位】中1的个数为偶数。
（校验位首部或者尾部都行）
- 偶校验的实现如下：
- 逐个信息位进行异或运算（相异为1），最终的结果即为偶校验位。
奇偶校验缺点：
- 如果偶数个比特发生错误，数据检测方无法检测出错误。
- 无纠错能力。
回顾
②循环冗余校验码（CRC校验码）（检错编码）
原理
数据发送、接收方 约定一个 除数。
（K个信息位+R个校验位）作为 被除数，添加的校验位是为了保证除法的 余数 为0。
收到数据后，进行除法检查看余数是否为0。
若余数非0说明出错，则进行重传或者纠错。
例题
除数位数 = 生成多项式的最高次幂+1（因为x的0次方也有常数c哈哈哈）
除数内容的确定：由生成多项式确定。
校验位的位数R = 生成多项式的最高次幂
校验位的内容的确定：
- 对移位后的信息码做被除数，用生成多项式做除数，进行模2除，模2减，得到的 R位余数 就是校验位。（模2减，等同于异或运算）
==拓展：出错位置和余数之间的关系：==
检验算得的 余数（n+1位）和 n进制的数，一定没有对应关系！
检验算得的 余数（n位）和 n进制的数可能相对应(因为之后有循环）。
- （eg余数三位）
- 000-正确。001-出错位1(从后往前数)。110-出错位置8。001-出错位置9，形成一个循环…
如果CRC码很短（位数没有超过余数所能表示的范围，即没到一轮循环），就真的是一一对应了！
因此循环冗余校验码是可以有纠错能力的（if信息位不多）
检错纠错能力
- 可以检测出 所有奇数个错误
- 可以检测出 所有双比特的错误
- 可以检测出 所有小于等于校验位长度的连续错误
- 若选择合适的生成多项式，且2^R ≥ K+R-1，则可以纠正单比特错误。
③海明校验码（纠错编码）
基本思想
奇偶校验（单个校验位）只能发现奇数位错误，无法发现是哪一位错误。且无法重传。
==海明码思路==：将信息位分成k个分组，每个分组分别进行偶校验→多个校验位→多个校验位可以标记出错位置。
需要多少校验位：2^k ≥ n+k+1
海明码求解步骤
1.确定海明码的位数。
- n+k，其中（2^k ≥ n+k+1）
2.确定校验位的分布。
- 校验位Pi放在海明位号为2^(i-1)的位置上。（P1，P2，P3…在1，2，4，8..位置）
- 信息位Di按顺序放到其余位置。
3.求校验位Pi的值。
将信息位的位置序号用 k位二进制 表示出来。（十进制→二进制）
将校验位的位置序号Pi 与 位置序号第i位为1的信息位归为一组，进行偶校验。
4.纠错
对P1,P2,P3…所属各分组进行异或==（相当于分组偶校验）==。
求得S1,S2,S3。
S1,S2,S3 = 000，说明无错误。
S1,S2,S3 ≠ 000，其值反映出出错位置。
5.补充
海明码有==1==位纠错能力，==2==位检错能力。
为了区分1位错还是2位错，可以在首部加上一个“全 校验位”，对整体进行偶校验。
回顾
