数据链路层
参考南京邮电大学的网络技术与应用课与Andrew S. Tanenbaum与David J. Wetherall的计算机网络（第五版）
1.设计问题
数据链路层使用物理层提供的服务在通信信道上发送和接收比特，它的功能主要有
- 给网络层提供一个定义良好的服务接口
- 处理传输错误
- 调节数据流，确保慢速的接收方不会被快速的发送方淹没
1.1成帧
数据链路层主要将物理层传递的原始数据流拆成离散的“帧”，进行纠错和检错等工作
成帧的方法
字节计数法
利用头部的字段来标识该帧的字符数，缺点是当传输错误导致计数值错误，从而会使接收方失去同步（即使想重传也不知道重传的字节），字节计数很少被使用
字节填充的标志字节
考虑了重传问题，每帧使用特殊字节包装了帧的开始和结束，称为标志字节（flag byte），失去同步时就可以搜索两个字节。
在数据中如果出现标志字节就会导致误判，所以发送方会在这些数据中的标志字节前面加上转义字节（ESC），将分界符与数据分开来，接收方会在接收时删除这些转义字节，这种技术叫字节填充，如果数据中出现转义字节，那就转转义
缺点：只能使用8bit的字节，帧大小根据内容而定，若没有标志字节，则帧和数据一样长，若都是标志字节，帧增长两倍
应用：PPP协议
比特填充的标志比特法
这是在比特级成帧的方法，每个帧的开始和结束都有一个特定的比特模式（不一定是8bit），01 11 11 10或11 11 11 10标记，这是标记字节。类似字节填充，比特填充就是在发送方的数据中如果出现连续的5个1，就会在后面填充一个0，这样保证了标志字节是唯一的，只出现在边界。
缺点：帧的长度取决于数据本身，若没有标志字节，则帧和数据一样长，若都是标志字节，由于每个字节都需要转义，帧增长12.5%
物理层编码违禁法
当物理层采用特定的比特编码方法时，利用物理层将比特编码成信号通常包含一些冗余比特，区分帧的开始和结束
1.2差错控制
当接收方知道帧是否出错（通过纠错码和检错码）时，对于无缺认的无连接服务，只需要保存出境帧就可以，但对于可靠的连接服务，还需要接收方对接收情况进行反馈（返回一个控制帧，会对接收帧进行肯定和否定的确认），若错误则重传
考虑一种复杂的情况，那就是因为硬件问题导致帧被完全丢失，这时接收方不会由任何反应，发动方也会永久等待下去，这时就要加入计时器，时长要能保证帧到达接收方，当返回确认帧时计时器取消，当帧或确认帧丢失时，计时器触发，解决方案就是重新发送帧，考虑会出现接收方会多次接收同一帧的情况，发送时需要给帧分配序号，接收方就可以区分原始帧和重传帧
1.3流量控制
处理发送方发送帧的速度超过接收方接收帧的速度时的问题
处理的两种方法
基于反馈的流量控制（feedback-based flow control）
接收方向发送方返回接收信息，允许他发送更多数据，或告诉它自己的情况
基于速率的流量控制（rate-based flow control）
使用这种方法的协议内置的机制，限制发送方的速率
基本上数据链路层的速度都很快，不会丢帧，过载由高层处理
2.差错检错和纠正
在传输过程中数据传输数据与元数据不一致就是传输差错，差错控制就是为了检测这个错误和纠正错误的。虽然是在链路层介绍，但数据可靠性是整个系统关注的问题，纠错码也会出现在物理层或者更高的层次，检错码一般是是链路层、网络层、传输层
每一项技术都适用于不同的位置，在光纤上通常采用检错（误码率低），纠错被用到有噪声的信道上
两种错误模型：单比特错误和突发性错误，原因：有线信道-脉冲干扰，无线信道-脉冲干扰、脉冲衰弱
2.1思想
由于原始数据是独立随机的，需要加入一些数据与原始数据产生约束关系，这些数据相对于原始数据是多余的，在一定程度上会降低传输效率
2.2方式
- 检错重发
- 前向纠错（FEC）
- 混合纠错检错
- 信息反馈
2.3纠错码
- 海明码
- 二进制卷积码
- 里德所罗门码
- 低密度奇偶校验码
2.4检错码
2.4.1奇偶校验码
原理：在传输数据后加监督位，使它有奇数个1或偶数个1
缺点：只能检测出奇数个错，若出错两个位则检测不出
2.4.2循环冗余码
CRC（Cyclic Redundancy Check）比奇偶校验码的方式的检错能力更强
原理：将原有数据$M(k位)$后面添加差错检测的$n$位冗余码，构成帧发出去，发出去（k+n）位
冗余码算法
- 首先进行$M=2^n×M$运算，就是在后面添加n个0
- 然后使用 $M$ 对约定好的n+1位的 $P$ 数据进行模2除运算（异或XOR，相同为0,不同为1），模运算不借位，$P$ 是根据生成多项式 $G(x)$ 而来
- 得到的余数 $R$ 就是FCS（帧检测序列）
- 真正要发送的就是$2^nM+R$
- 接收方使用发送的数据模2除 $P$，余数为0则没有错误
设发送的数据为$C(x)$，则有
$$
C(x)=2^nM(x)+R(x)
$$
特点：
- CRC只能做到无差错接收
- 若要可靠传输，则需要加上确认和重传机制
3.基本数据链路协议
4.MAC
该笔记终止记录
由于书上自下向上开始介绍，内容比较晦涩、难读，我还是基础不好只能与这本书暂时再见了，等我深造时在开启这本书。
换个思路重新学网络，找到了《计算机网络自顶向下方法》开始学习，待我学成，必将开启新篇章！