1.数据链路层基本概念  

1.链路：两个结点间的物理通道

2.数据链路：两个结点间的逻辑通道

3.帧：链路层的协议数据单元，封装网络层数据报

4.数据链路层使用物理层提供的服务的基础上为网络层提供服务，最基本的就是将本机的网络层交付的数据报可靠的传输到对方主机的网络层。将物理层提供的可能出错的物理连接改造成逻辑上无差错的数据链路（对网络层而言）

功能：

①为网络层提供服务：无确认无连接，有确认无连接，有确认有链接（有连接一定有确认）

②链路管理：连接的建立、维持和释放

③组帧

④流量控制：点对点（相邻接点），传输层的流量控制为端对端（两个主机间）

⑤差错控制

5.信道利用率 = (L / C) / T

L：T时间内发送的数据量

C：数据传输速率

T：发送周记

6.信道吞吐率 = 信道利用率 * 发送方的发送速率

2.组帧

封装成帧：为数据报增加尾部和首部（作用：帧定界）组成帧，数据报为帧的数据部分

帧同步：接收方可以从他们收到的二进制比特流中分辨出帧的开始和结束

透明传输：不管传输的是什么样的比特流，链路层都能传输；由此引申出，若传输的数据中含有和某些控制信息一样的数据时，要采取措施使得接收方不会因此而影响接受

2.1.字符计数法

取每个帧的第一个字符为计数字符，标记该帧中一共有几个字符

缺点：若计数字符的传输出现了问题，则无法区分后续帧

2.2.字符填充法

使用转义字符，发送帧时，在除了真正表示帧开始和帧结束的前面不加转义字符外，该帧中碰见的所有的控制信息前都加上该转义字符。接收端收到数据时，碰到转义字符就知道后面跟着的是数据，而不是控制信息

2.3.零比特填充法

开始和结束的标志为01111110，因此，发送方在发送的数据中每累计碰到5个连续的1时，就在后面加上0

性能优于字符填充法

2.4.违规编码法

用编码中不会用到的两种方式分别标记开始和结束

例如：曼彻斯特编码——高低为1，低高为0，则可以采用高高为开始，低低为结束

3.差错控制

3.1.检错编码

3.1.1.奇偶检验码

奇校验码——添加校验元（0或者1）使得数据中1的个数为奇数

偶校验码——添加校验元（0或者1）使得数据中1的个数为偶数

例如：采用偶校验：01101 则添加1；011011 则添加0

缺点：仅能测出奇数位出错的情况，且只知道错了，不知道哪错

3.1.2.CRC循环冗余码

1.基本概念

双方约定生成多项式为 r + 1 位

①发送方先将d位的数据先加上 r 位的0，与该生成多项式进行异或运算，得到的余数就为 r 位FCS，将其加入到要发送的d位数据之后，形成最终的d + r位数据

②接收方接到d + r位数据后，除以生成多项式，若余数为0，则没出错；余数不为0，则出错丢弃

2.例如发送数据为1101 0110 11，采用CRC校验，生成多项式是1001 1，则最后发送的数据是

①1101 0110 11加生成多项式的位数 - 1位的0，得到1101 0110 1100 00

②1101 0110 1100 00与1001 1进行异或得到CRC1110

③将发送的数据加上CRC，得到最后结果1101 0110 1111 10

3.2.检错编码（海明码）

1.概念

任意两个编码的比特值不同的总位数的最小值为码距（000、001的海明距离为1）

检验d位错：码距 ≥ d + 1

纠正d位错：码距 ≥ 2d + 1

2.工作流程

例：数据为1100

①确定校验码位数r

(1)设数据有m位，校验码为r位

m = 4

(2)检验码有2 ^ r种取值（二进制）

(3)2 ^ r ≥ m + r + 1 （m + r为每位发生错误的情况，1为数据没有出错的情况）（暴力穷举）

满足该不等式的r = 3→总位数为7

②确定校验码和数据的位置

将校验码放在2 ^ n的位置，数据则按序填充

③求出具体校验码

（1）每个校验码负责校验表中与自己的二进制含有相同位置1的数据（包括自己）

x4负责校验1XX：7，6，5，4

x2负责校验X1X：7，6，3，2

x1负责校验XX1：7，5，3，1

（2）采用奇/偶校验，设采用偶校验

x4：7、6、5为110→x3为0

x2：7、6、3为110→x2为0

x1：7、5、3为100→x1为1

④检错并纠错

（1）检错

若接受数据为1110 001：

x4负责校验1XX：7，6，5，4→0、1、1、1        ×

x2负责校验X1X：7，6，3，2→0、0、1、1        √

x1负责校验XX1：7，5，3，1→1、0、1、1        ×

（2）纠错（满足偶校验）

x4、7、6、5、4→x4 0 1 1 1→x4 = 1

x2、7、6、3、2→x2 0 0 1 1→x2 = 0

x1、1、0、1、1→x1 1 0 1 1→x1 = 1

x4、x2、x1 所表示的二进制数为101，即5，因此，5出错

4.滑动窗口

滑动窗口能进行流量控制（确认机制）、可靠传输（发送方自动重传）

4.1.停止等待协议

发送窗口 = 1（交替用帧0，帧1标识），接收窗口 = 1（交替使用ACK0，ACK1），

1.无差错情况：发送端发一个帧，接收端接受到后返回一个确认帧，发送端接受到确认帧后再发送下一个帧

2.有差错情况：

①数据帧丢失：设置一个计时器，设置当超过某一时间（大于RTT）还未收到确认帧，则发送端重新传送该帧

(1)发送该帧后，需要保存副本

(2)确认帧和数据帧必须编号

②确认帧丢失：超时重传该帧，当接收端收到该帧的时候重新返回确认帧，并且把该帧丢弃

③确认帧迟到：丢弃确认帧

缺点：信道利用率太低

4.2.后退N帧协议

1.发送窗口最大为(2 ^ n) - 1，接收窗口为1（增加序号范围）

2.如果超时，重传所有已经发送但是未确认的帧（发送方需要缓存多个分组）

3.采用累计确认（偶尔捎带确认）的方式，返回确认帧ACKn即表示n号数据及其之前的所有数据都已经收到

4.接收方只会按序接收，若收到正确但不是所期待的帧，则直接丢弃，并返回最近收到的按序接收的帧的确认帧（防止最近一个确认帧丢失）（接收方不需要缓存）

总结：虽然提高了信道利用率（连续发送帧），但是效率依然不高（重传时需要重传已经发送的帧）

4.3.选择重传协议

1.发送窗口 = 接收窗口 = 2 ^ ( n - 1)

发送方：

2.接收到ACKn后，将序号n改为已收到。若n为此时发送窗口的下界，则发送窗口向前移动到未确认的最小序号处（逐一确认，后退N帧是累加确认）

3.每个帧都有独立的超时计时器，若超时，则重传该帧（区别于后退N帧协议的所有帧，选择重传协议仅重传出错帧）

接收方：

4.接收方收到接收窗口序号内的帧。若是下界，则返回该帧的ACK，接收窗口向前移动到未收到数据的最小序号处；若不是下界，则返回该帧的确认帧，并将该帧缓存（接收方有缓存），直到该帧及该帧之前的所有序号都接收到的时候，接收窗口向前移动到该帧下一位（逐一确认，后退N帧是累加确认）

1.若收到的是比下界更小的帧，则返回该帧的确认帧（可能是上一次传送的确认帧丢失，重新告诉发送方该帧已经接收）

2.若收到的是比上界更大的帧，则直接丢弃

注：此处的上下界是指对接收窗口而言，并非单纯数值意义上的大小关系，即若此时接受窗口序号为6、7、0、1，接收窗口的下界为6，上界为1（可以理解为循环队列，按序接收到数据帧后，就循环向后移动）