一、定义
借助于物理层，为网络层提供服务。
定义一个合适的传输差错率。
对传输的数据流进行管理，以免快速的发送淹没了慢速的接收端。
传输单元是帧。
二、功能
任务：把网络层的数据组合成帧，加上一定的校验，交给物理层用比特流传输到目的计算机。
为网络层提供了一条可靠的数据链路。
相连：物理介质 的连接。当采用多路复用技术时，也可以是信道的连接，特征是传输的数据是顺序的。
物理链路：无源的点到点的物理连接，中间没有交换节点。没有可靠性保证。
数据链路：包括一条物理连接和配置在两端的硬件和相关的数据链路层协议。
三、数据链路层服务的区分规则
通过有无连接、有无确认来区分。
1. 无确认无连接
接收到数据帧后，不发确认。
数据传输前，不建立链接。
应用场景：传输距离短，可靠信道。例如：局域网。
无确认并非不可靠，其可靠性由上层负责。
2. 有确认无连接
不建立连接。接收到数据帧后，必须发出确认。
应用场景：信号传播延时大（建立连接耗时），线路状态不一定很可靠（确认）。例如：无线通信。
3. 有确认有连接
最可靠的方式。
使用前先建立连接。每帧传输必须得到确认。最后要释放连接。
例如：电话。实时应用，需要面向连接来保证实时。
四、可靠传输
解决三个问题：将传输的信息组合成帧；校验和重发；流量控制。
五、数据帧
保证能识别一个完整的帧，保证一旦出现传输差错导致的前一个帧丢失后，也能识别后一个帧——再同步功能。
1. 字符计数法
每帧的第一个字节记录该帧的长度，即1个计数字节+(n-1)个数据字节。
缺点：一旦帧长度计数出错，就无法再同步。
2. 带字符填充的首尾界符法
用特殊的字符作为帧头和帧尾界符。
面向字符的帧格式，传输的数据都是字符（ASCII, EBCDIC字符）。帧中不允许出现帧界符标志。
在面向字符的串行通信中常使用这种格式。
优点：接收方一旦丢失了一个FLAG，只要继续向下搜索下一个FLAG，就可重新确定帧边界。——再同步能力。
面向字符的帧格式不适宜传输数据中包含二进制数的帧，因为这样的帧可能出现与FLAG相同的字符。（一般FLAG用ASCII字符7EH定义）
解决办法：字符插入方法，对于二进制数中偶然出现的FLAG，在它前面插入一个ESC(ASCII字符1BH)。——字符填充法。
如果要传输1B，则再添加1个1B（去掉1个还有1个）。类似于C语言中的转义符。
3. 带位填充的首尾界符法
在实际应用中，传输的都是二进制比特串，所以更经常使用位填充的首尾界符法。位插入法，也称透明传输。
面向二进制位的同步串型通信中，常使用位填充，如HDLC。
以特殊的位模式01111110为帧标志。
如果由于 干扰，一个帧标志没有正确接收，就继续扫描接收串，一旦扫描到01111110，新的一帧就开始了。
当帧中出现连续的5个1时，插入1个0.
接收时检查连续的5个1后面的位，如果是0就删除，如果是1就结束。
4. 物理层编码违例法
曼彻斯特编码中，连续高电平或低电平，可用作帧界符。因为高-高电平和低-低电平对没有在数据中使用，就称这两种为编码违例，可以用作帧界符。在令牌环网中使用编码违例格式。
六、差错控制
避免帧错误：校验
避免帧丢失：超时和重发
避免帧重复：序号。
1. 确认
接收方收到帧后，如果校验出有问题，接收方可以扔掉，或发送否定性确认。
如果帧正确，就发送肯定性确认。
必须先检测，后发送确认。
2. 差错检测和校正
传输出错的情况：超时，数据中一位或几位因噪声干扰出错。
通常接收方应能检错，甚至 纠错。
纠错码是除m个数据位外，增加r个冗余位作为纠错位，传输总长度为m+r=n。
常用的纠错码是汉明码。
【检错码：校验和】
算法简单，实现容易，但检错强度较弱。如一个位从0变1，另一位从1变0，则分辨不出。
看成二进制整数序列，划分为固定长度（8位，16位，32位等），计算各分段的和，将校验和与数据一起发送。
在接收端重新计算校验和，比较，如果相同则认为正确。
【块校验码BCC】
常用，强度较弱。同校验和，偶数位出错不能检测到。
将所有字符的ASCII码作异或操作。
【循环冗余校验CRC】
把一个K位的帧看成一个K-1次的多项式m(x )
设定一个生成多项式g(x )，r阶。k>r。
取 R(x ) = x^r M(x ) / G(x )
将CRC码接在帧后一起发送。
接收方只要计算CRC，所得余数为0，就正确。
（例子）1101011011
M(x ) = x^9 + x^8 + x^6 + x^4 + x^3 + x + 1
G(x ) = x^4 +ｘ ＋ １ = 10011
Ｔ(x ) = x^4 *M(x ) = 1101 0110 11 0000
CRC = T(x ) / G(x ) = 1110
最后发送的码为： 1101 0110 11 1110
接收方只需要取前面9位，后4位视为CRC, 用原数据减去CRC，一定可以被G(X )整除。（因为CRC就是余数）
3. 重复帧
帧编号。
如果编号已接收过，则认为是重复帧。
重发机制导致了发送方多次发送同一帧，可能产生重复帧。
【帧的格式】
帧类型TYPE
帧序号SEQ_NO
确认号ACK_NO
信息INFO
前三个是帧头内容，接收方会去掉帧头帧尾，取出信息。
七、流量控制
发送方与接收方的速率匹配。
通常接收方的缓冲区达到一定量时，应及时通知发送方，暂停发送，等候通知。——流量控制机制
基本数据链路协议
1. 无限制的单工协议
理想简化：主机A,B的信道是理想信道，信息传输不会出错，没有差错控制。接收方的接收能力无限，不需要流量控制。
只需要简单的帧封装，和上下层的交互。
发送方的数据链路层接口不断询问网络层是否有消息，while(true){…}
如果网络层有信息传输，就把信息传递给数据链路层。数据链路层负责封装帧，然后把帧交给物理层。
接收方等待物理层的事件发生，从物理层取一个帧，解封装，交给网络层。
2. 单工的停-等协议
考虑接收方的处理能力有限，CPU、缓冲区。这就得增加流量控制。
发送方发送一个帧以后，必须停下来，等待接收方处理完后发送回来的确认帧，再发送下一帧。——流量控制。
3. 噪声信道单工协议
发送方发完一帧后，启动定时器，等待确认消息。超时后启动差错控制机制，重发该帧。
问题：效率低。无论是由于接收方收到一个错帧而不发ACK，还是由于帧标志错而导致帧丢失，甚至接收方发送的ACK丢失，发送方的定时器都会超时，而需要一定长的时间才能确认是真的需要重发。
另一个问题是接收方会收到重复帧。
帧序号字段：只需要1个比特，0和1。发送方要记录下一个准备发送的顺序号，接收方要记录下一个期待接收的顺序号。
由于是单工噪声信道，发送和接收过程将严格交替。
应答号字段：仅需要一个比特，接收方期待接收的下一个帧序号。
如果发送方收到的应答号和下一个帧序号相同，则表明发送成功。就停止计时器，从物理层取下一个帧。
如果接收方收到的帧序号和等待的序号相同，就解封装，交给网络层。否则，可能是个重复帧，就不处理。但仍然会向发送方回应确认。
两个问题：
单工通信，不能双向传输，效率低。
如发送方的定时器设定的初值较小，可能出现系统死锁。（实际正确接收的包，被认为丢弃）
4. 双向传输
用四条信道，两条数据，两条应答。信道利用率很低。
用两条信道，一条A到B，一条B到A。接收方采用捎带确认。数据帧和确认帧采用不同的帧格式。
接收到帧后，首先检查格式，如果是数据帧，就给网络层；如果是应答帧，就准备发送下一帧。
捎带确认的方式就是节省了应答帧。不单独发一个确认帧，而是把确认消息附加在数据帧里，可以等待到下一次发送数据时才确认。
5. 滑动窗口协议
收发使用两条信道。
发送窗口、接收窗口
假设发送窗口是5， 接收窗口是3，则发送方可连续发送5个帧，超过5个就停止、等待接收方处理，接收方一次可接收3个，确认一个之后发送方再发送一个。这样，一次发送一批帧是可能的。
两者窗口数相加 是8， 则帧序号可以用3个比特表示。0~7号。
【双向的一位滑动窗口协议】
发送窗口1， 接收窗口1， 则帧序只需要1比特。信道利用率太低。
双向意味着发送方同时也是接收方。既有等待接收的序号，也有等待发送的序号。
发送方发送下一个数据帧之前，必须收到接收方的捎带确认。
凡是接收到一个正确的帧，即使是重复帧，也要发送确认。
每一方发送出去后，就启动计时器。如果是帧的到达，则先判断帧序号是否是等待的帧，如果是则交给网络层，等待的帧序号加1。然后判断应答号是否是上一帧的序号，如果是，说明发送成功，停止计时器，发送下一帧。如果应答号不正确，说明前一个帧没有正确接收，就重发上一帧。
【后退n帧的滑动窗口协议】管道化协议，是一个实用的点对点可靠传输的协议，适合出错较少的情况
发送窗口大于1， 接收窗口为1。总窗口大小是不定的，帧序号的比特数不定。
假设发送窗口为7，则需要3个比特。
每次接收方只等待1个帧序号，其他帧扔掉。如果有一个帧出错了没收到，后面的帧就都收不到。这样，后面N帧全部要重发。——后退N帧。
在发送窗口未满时，允许网络层请求发送。enable_network_layer()。
frame_expected，等待接收的帧号。只有0和1即可。
next_frame_to_send，要发送的下一帧的序号。
ack_expected，滑动窗口期待应答的帧号。
nbuffered，已发送的帧数。
等待事件：
事件1：网络层有消息，
事件2：有帧到达
事件3：帧错误
事件4：超时。
如果已发送的帧数小于最大窗口，允许网络层请求，否则关闭网络层请求接口。
事件1的处理：装配一个数据帧，发送；发送缓冲区数+1， 帧序+1， 启动计时器；准备发送下一帧。
事件2的处理：如果帧是等待接收的帧，就给网络层，等待帧号+1. 如果是一个ACK，如果在已发送的帧序区间，则释放对应的缓冲区，定时器复位，准备接收下一个ACK。如果不在已发送的帧序范围，就说明该帧发送失败，该帧和它后面的帧全部都要重发。——后退N帧。
【选择性重发滑动窗口协议】
一旦帧出错了，不是全部重发，只是重发出错的帧。没有出错的帧，就不重发。可以提高信道效率。但带来的麻烦是，不能随便扔掉不符合的帧，接收方要保存这些收到的帧。因此，接收窗口不能为1，接收窗口和发送窗口都大于1.
例如发送窗口7， 接收窗口7， 则接收方可以保存7个帧。
假设接收完1号帧后，2号帧丢了，接收方仍然可以接收3，4，5，6，7，8号帧，不过应答时ACK都是2，并且收到3号帧时，发送一个否定性确认NAK，确认号为2，表示期待接收2。当发送方定时器超时后，它就发现2号帧发送失败了，重发2号帧，接收方收到2号帧以后，应答时ACK=8，表示这8个帧都收到了。
有一个差错时仅重发一帧，而不是全部重发。
接收方定义了一个辅助计时器，到目前为止多长时间没有发送过确认了，超时时专门发送一个确认帧，以免发送方的定时器超时导致的重发。
定义了一个否定性确认的帧格式。接收方收到一个有问题帧时，发送一个否定性确认NAK。
初始时：
enable_network_layer()
ack_expected=0,
next_frame_to_send=0,
frame_expected=0,
too_far=NR_BUFS,
nbuffered=0,
初始化arrived[]为false。
数据帧的处理包括作为接收方和作为发送方。作为接收方：看帧序是否和等待的帧号相同，如果是，就接收处理，交给网络层。如果不是，如果在接收的窗口之内，就得缓存起来，把arrived[]对应位置1，表示收到。另外，这说明等待的帧丢失了，需要发一个NAK帧告诉发送方丢失了，设置对应标志记录已发送过NAK。
如果接收的是一个NAK，则重发对应帧。
如果接收的是一个ACK，则转动窗口。
详细过程另外总结。
【注意】发送窗口+接收窗口<=2^n，发送窗口>=接收窗口。
八、