目录
第三章 数据链路层
3.1 数据链路层的设计问题
3.1.1 提供给网络层的服务
3.1.2 成帧
3.1.3 差错控制
3.1.4 流量控制
3.2 差错检测和纠正
3.2.1 纠错码
3.2.2 检错码
3.3 基本数据链路层协议
3.3.1 一个乌托邦式的单工协议（协议1）
3.3.2 无错信道上的单工停-等式协议（协议2）
3.3.3 有错信道上的单工停-等式协议（协议3）
3.4 滑动窗口协议
3.4.1 基本概念
3.4.2 1位滑动窗口协议（协议4）
3.4.3 回退N协议（协议5）
3.4.4 选择重传协议（协议6）
数据链路层是基于物理层不可靠的传输向上层提供可靠的传输，它提供的是相邻两个节点之间可靠的数据传输。
本章主要涉及网络模型中第二层（即数据链路层）的设计原则。实现通过一条通信信道连接起来的两台机器，实现可靠有效的完整信息块（称为帧）通信的一些算法。解决通信线路中出错的情况、关于有限的数据传输率、发送时间和接受时间存在的非零延迟等问题。
数据链路层使用物理层提供的服务在通信信道上发送和接受比特。完成一些功能：
（1）向网络层提供一个定义良好的服务接口。
（2）处理传输错误。
（3）调节数据流，保证慢速的接收方不会被快速的发送方淹没。
为实现这些目标：数据链路层从网络层获得数据包，并将之包装成包含：
帧头+有效载荷（存放数据包）+帧尾的帧（frame）
数据链路层的工作核心就是帧的管理。
最主要的服务是将数据从源机器的网络层传输到目标机器的网络层：
数据链路层可以设计成向上提供各种不同的服务。实际提供的服务因具体协议的不同而有所差异。一般情况下，数据链路层通常会提供以下3种可能的服务：
（l）无确认的无连接服务。
源机器向目标机器发送独立的帧，目标机器不对这些帧进行确认。不需建立逻辑连接。适用于错误率低或者实时通信（语音传输）的情况。
(2）有确认的无连接服务。
源机器向目标机器发送独立的帧，目标机器会对这些帧进行确认。不需建立逻辑连接。适用于不可靠的信道（无线系统，WiFi）。
(3）有确认的有连接服务。
源机器和目标机器在传输任何一个数据之前要建立一个连接，保证目标机器按照正确的顺序接受每一个帧。适用于长距离且不可靠的链路（卫星信道，长途电话）。
为检测错误和纠正错误，数据链路层将比特流拆分成多个离散的帧，为每个帧计算一个称为校验和的短令牌，并将该校验和放在帧中一起传输。为拆分比特流需要解决两个问题：
（1）帧的边界问题：如何识别帧的边界；
（2）帧的透明传输（填充）问题：如果帧的数据中出现和边界一样的 flag 该如何防止被识别为边界
1. 四种成帧方法
（1）Character count（字节计数法）
用头部的一个字段来标识该帧中的字符数：
问题：因为一个传输错误，就会全弄混。很少被使用。
（2）Flag Bytes with byte stuffing（字节填充的标志字节法）
发送方使用标志字节（FLAG）作为开始和结束；使用转义字节（ESC）表示其后的字节为数据字节而不是标志字节或转义字节。接收方将收到的数据中的转义字节删除后再传递给网络层。
（3）Starting and ending flags,with bit stuffing（比特填充的标志比特法）
使用“01111110”表示帧的开始和结束（帧的边界问题解决），并且在数据中，若遇到5个连续的比特1，就在其后填入一个比特0（帧的填充问题解决）。接收方除了将首尾的“01111110”删除外，还要将数据中所有5个连续比特1其后的比特0删除。
相较于方法（2），帧长度增幅更少，降低了传输数据内容。
（4）Physical layer coding violation（物理层编码违禁法）
使用“不会出现在常规数据中”的冗余比特作为边界。好处是除了开始和结束的填充外，不再需要填充额外的数据。
为确保所有帧按照正确顺序传递给目标机器的网络层：
发送方发送反馈信息来确保传递可靠。
引入计时器来防止硬件故障或通信信道出错等原因丢失某一帧使发送方持续等待确认。
通过序号保证每一帧按照顺序且不会被接收方重复接收。
具体的确认方式在后面通过协议的形式来讲
发送方发送帧的速度超过了接收方能够接收这些帧的速度，而导致丢帧。
解决方法：
基于反馈的流量控制（链路层）。
基于速率的流量控制（网络层）。
推断出被发送的数据是什么。适用于错误发生很频繁的信道，因为再次传输仍可能出错。
海明码
1）海明码的生成
2）海明码的接收
推断是否发生错误。适用于高度可靠的信道，错误偶尔发生时，只需重传整个数据块即可。循环冗余校验码（CRC,Cyclic Redundancy Check，也称作多项式编码）。注意有一定的误判率。
步骤：（以下面算式为例讲解）
①收发双方商定一个比帧短且头尾都是1的01串叫做生成多项式，如下的10011
②帧的后面附上生成多项式长度减一个0后，作为被除数对生成多项式模2除，得到商和余数，如10011长度为5，所以附上了4个0
③若帧与余数合并以后在接收方被生成多项式整除，那么认为传递的过程没有出错
模2除原则：列竖式的方式同除法，但是模2除法中加法无进位，减法无借位，即加减皆等同于异或，而商0还是1由被除数首位决定，首位是1商1，否则商0
组成帧的四个字段：kind、seq、ack和info。前三个包含控制信息，称为帧头，最后一个可能包含了要被传输的实际数据。
不需考虑任何错误情况：数据单向传输，双方总是就绪，数据处理时间不计，缓存空间无限大，通信信道永不丢帧。
这是一个完全不现实（理想化）的协议，“乌托邦”协议。
发送过程是一个无限的while循环，它尽可能快速地把数据放到线路上。无差错控制或者流量控制方面的限制。接受过程一直等待一个未损坏的帧到达。（发送速率和接收速率必须一样快）
单向数据传输，发送方网络层一直有无限的数据要发送，信道不会出错，从不损坏或丢失帧，发送方需等待接收方确认帧返回后才发送下一帧。如果接收方不反馈应答信号，则发送方必须一直等待，然后就陷入等待接收方确认信息的过程中，因而传输效率低。
信道存在噪音。需要计时器与序号配合，需要超时重传机制。
滑动窗口（sliding window）：为了便于理解，可以认为数据是一条传送带，而滑动窗口中的数据是当前准备处理的数据。一旦窗口的第一条数据被确认处理结束，窗口就会继续向后滑动以处理后面的数据。下面是发送方的发送窗口形象化的表示：
捎带确认（piggybacking）：暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术。捎带确认通常与累计确认一同使用，更好的利用了信道的可用带宽。
期望确认：收到数据帧以后向发送方发送期望对方发送的下一帧的序号。
累计确认（cumulative acknowledgement）：当n号帧的确认到达，n-1号帧、n-2号帧等都会自动被确认。
否定确认（NAK）：接收方检测到错误时发送的否定确认，实际是一个重传请求，在NAK中指定了要重传的帧。
发送窗口（sending window）：发送方总维持着一组序号，分别对应于允许它发送的帧，我们称这些帧落在发送窗口。
接收窗口(receiving window):接收方维持着的一个窗口对应于一组允许它接受的帧。
（发送窗口大小=1，接收窗口大小=1）
当接收窗口大小为1时，可保证帧的有序接收，但效率较低。
源站发送单个帧后必须等待确认，在目的站的确认到达源站之前，源站不能发送其他数据帧。这是因为发送窗口大小仅为1，必须用来保存当前未确认的帧以超时重传。
发送方必须在内存中保存所有的帧，因此如果最大窗口的尺寸为n，则发送方需要n个缓冲区才存放未被确认的帧。
（发送窗口大小>1，接收窗口大小=1）
发送方按照顺序向对方发送帧，在收到对方的确认以后窗口向后滑动，若当前窗口中的第一个帧出现超时，那么回退到这个帧重新发送所有的帧。
而因为接收窗口大小为1，除了数据链路层必须要递交给网络层的下一帧外，接收方拒绝接受任何帧。如果在计时器超时以前，发送方的窗口已被填满，则管道将变为空闲，最终，发送方将超时，并且按照顺序重传所有未被确认的帧，从那个受损或者丢失的帧开始。
一般使用累计确认。
（发送窗口大小>1，接收窗口大小>1）
发送方按照窗口的顺序依次发送帧给接收方，而接收方检查该帧是否可以落在接收窗口内，即以前没有接收过且该序号在窗口可接收的范围内，如果可以那么不管这一帧是否为网络层所期望的下一个数据包都接收该帧并暂存于缓冲区内。该帧会一直保存在数据链路层中直到所有序号比它小的帧已经按顺序递交给网络层，它才能被传递给网络层。
辅助计时器：在发送方的计时器超时之前，没有出现需要发送的反向流量，则发送一个单独的确认帧，而发送的时间间隔由辅助计时器决定，因此辅助计时器的超时间隔应该明显短于数据帧关联的计时器的间隔。
除ACK，选择重传还有否定确认，当接收方发现坏帧丢弃时，立刻发送一个NAC给发送方告知该帧未收到让它重传，以防超时。
选择重传和回退N实际是带宽使用效率与数据链路层缓存空间之间的权衡。
