数据链路层的功能： 1.向网络层提供一个定义良好的服务接口。 2.Framing
成帧（边界控制 3.处理传输错误。（错误控制）
4.调节数据流，确保慢速的接收方不会被快速的发送方淹没。（流量控制）
数据链路层从网络层获得数据包，然后将数据包封装成帧（frame）传输，每个帧包含一个帧头、一个有效载荷（用于存放数据包）以及一个帧尾。
#
3.1 数据链路层的设计问题 ## 3.1.1 提供给网络层的服务（通常三种）
对于这里的“连接”与“确认”，都可以用漂流瓶的例子来理解。
### 1. 无确认的无连接服务 #### 定义
源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认（以太网）。
#### 适用场合
第一种是错误率很低的场合，差错恢复过程可以留给上层（例如，在传输控制协议（TCP）和用户数据报协议（UDP）等运输层协议中，通常会实现差错检测和纠正机制）来完成（想起小学二年级的一篇课文，纸船与风筝，小熊能收到松鼠的小船是因为河流只从山上流向山下）；第二种是实时通信，如语音传输，因为在实时通信中数据迟到比数据受损更糟糕。（与下面的长途电话相对应，这里的实时通信默认在同一个地区，都能接收到，泛起的波纹没有消散
### 2. 有确认的无连接服务 #### 定义
向网络层提供服务时，数据链路层没有使用逻辑连接，但其发送的每一帧都需要单独确认。如果一个帧在指定的时间间隔内没有到达，则发送方将再次发送该帧。
#### 适用场合 不可靠的信道，比如无线系统（802.11 WIFI）。
在滴水湖中央放出一艘小船随便飘，小船上有协议，只有岸边的人有对应的协议才能接收它。若小船以光速航行，那么显然无连接比建立连接效率更高。但小船可能种种差错没飘到，这时候发出信号说船沉了。
### 3. 有确认的有连接服务（面向连接的服务） #### 定义
源机器和目标机器在传输任何数据之前要建立一个连接。连接上发送的每一帧都被编号，数据链路层确保发出的每个帧都会真正被接收方收到。它还保证每个帧只被接受一次，并且所有的帧都将按正确的顺序接收。
面向连接的服务相当于为网络层进程提供了一个可靠的比特流。 #### 适用场合
长距离且不可靠的链路，比如卫星信道或长途电话电路。
一个帧可能被收发多次，因此将浪费带宽。（超时又重发 ####
使用面向连接的服务时，数据传输经过的3个不同阶段：
第一个阶段：建立连接，双方初始化各种变量和计数器（记录哪些帧已经/还没有接收到）。
第二个阶段：传输一个或多个数据帧。
第三个阶段：连接被释放，所有的变量、缓冲区以及其他用于维护该连接的资源也被释放。
## 3.1.2 成帧
数据链路层负责检测和纠正错误：将比特流拆分成多个离散的帧，为每个帧计算一个称为校验和的短令牌，并将该校验和放在帧种一起传输，当帧到达目标机器时，要重新计算该帧的校验和。
### 成帧（拆分比特流）的四种方法 #### 1.字节计数 ##### 方法
利用头部中的一个字段来标识该帧中的字符数。 ##### 优点 实现简单 #####
缺点 帧只能以字节为单位，且计数值有可能因为一个传输错误而被弄混。 
#### 2.字节填充（byte stuffing
考虑出错之后的重新同步问题，对第一个方法的传输错误缺点进行改进。 #####
方法
每个帧用一些特殊的字节作为开始和结束。特殊字节通常都相同，称为标志字（flag
type），如FLAG，作为帧的起始和结束分界符。两个连续的标志字节代表了一帧的结束和下一帧的开始。如果接收方丢失了同步，只需搜索两个标志字节就能找到当前帧的结束和下一帧的开始位置。
##### 字节填充
标志字节出现在数据中时，发送方的数据链路层在每个标志字节的前面加入一个转义字节（ESC）进行区分，接收方的数据链路层在将数据传递给网络层之前必须删除转义字节。如果转义字节也出现在数据中，就在转义字节前再填充一个转义字节。
（中间传输的部分也可能出现FLAG，这时候就用转义字符告诉谁是FLAG，如果考虑ESC也正好有的话，概率就太低了扒，那只能无限套娃，再加一个再加一个，摩多摩多）
（PPP协议的简化形式） ##### 缺点
帧可以包含由任意大小单元组成的二进制比特数，但字节填充只能使用8比特的字节。（同字节计数法）如果FLAG出错则（只有）当前数据帧无法成帧。
#### 3.位填充法（bit stuffing
又弥补了字节计数和字节填充只能以8比特的字节为单位的缺点 ##### 方法
每个帧的开始和结束由一个特殊的比特模式，01111110或十六进制0x7E标记。这种模式是一个标志字节。每当发送方的数据链路层在数据中遇到连续5个1，就自动在输出的比特流中填入一个比特0。正文中不会出现6个1。当接收方看到5个连续入境比特1，并且后面紧跟一个比特0，就自动删除比特0。
##### 副作用
一帧的长度要取决于它所携带的数据内容。如果数据中没有标记字节，100个字节被一个大约长100字节的帧所携带；如果数据完全由标志字节组成，每个都得被转义，最后发送的帧的长度变成大概200个字节，帧的长度增幅大约为12.5%，每个字节增加1比特。（省流：太长了，浪费空间
#### 4.物理层违禁编码 ##### 方法
使用物理层的捷径。比特编码成信号通常包含一些冗余比特，这种冗余说明一些信号将不会出现在常规数据中。可以利用这些保留的信号来指示帧的开始和结束，区分帧的边界。
物理层正常为，高低是1，低高是0。用物理层不正常的编码作边界（高高11
低低00）。 ##### 优点
用作分界符的信号是保留不用的，可以通过他们找到帧的开始和结束，而且不需要再填充数据。
## 3.1.3 差错控制（Error Control
晚上送很多小姑娘回家，编号小姑娘1，小姑娘2...叫她们到家了都说一声，如果过了十二点还没说，多半就是掉下水道里了。为了不让小姑娘的家长担心，过了十二点还没到我就要再送一个相同的小姑娘回去顶一下位置。
### 1. 反馈
向发送方提供一些有关线路另一端的反馈信息。接收方返回一些特殊的控制帧，在控制帧中对它所接受到的帧进行肯定或否定的确认。肯定确认：安全到达；否定确认：传输有错误，该帧重传。
### 2. 计时器
用于解决发送的帧或确认帧丢失而发送方无限等待的情况。当发送方发出一帧时，启动计时器。在计时器超时前，该帧应该被正确接收，且确认帧也被传了回来，然后计时器被取消。
### 3. 序号
有的帧被发送多次后（还是送到了，但是超时了，也就是小姑娘超过十二点到了家，没发生啥事，这时候我送的下一个相同小姑娘也到家了，为了区分他们俩，给他们加上编号），接收方将两次或多次接收到同一帧，并多次将它传递给网络层。所以要给发送出去的帧分配序号，这样接收方可以根据帧的序号来区分原始帧和重传帧。
## 3.1.4 流量控制（Flow Control
发送方发送帧的速度超过了接收方能够接受这些帧的速度，发送方该如何处理？
解决方法： ### 1. 基于反馈的流量控制
接收方给发送方返回信息，允许它发送更多的数据，或者告诉发送方接收方的情况如何。
### 2. 基于速率的流量控制
使用这种方法的协议有一种内置的机制，它能限制发送方传输数据的速率，而无需利用接收方的反馈信息
基于速率的方案仅在传输层的一部分中可见，基于反馈的方案（如作为链路层硬件实现的网络接口卡 NIC）可同时出现在链路层和更高的层次。 # 3.2 差错检测和纠正 （Error Detection and Correction 前面说的成帧是数据链路层为了进行边界控制，在数据的基础上添加一些冗余信息；接下来说的纠错码和检错码则是和成帧处于不同层级，二者在物理层进行操作，马上就要传输辣，为了防止出现问题，从而再添加一些冗余信息，达到纠错和检错的目的。 纠错码/前向纠错（FEC）：在每一个被发送的数据块中包含足够多的冗余信息，以便接收方能据此推断出被发送的数据是什么。在错误发生很频繁的信道上使用（比如无线链路），在每一个数据块中加入足够的冗余信息，以便接收方能够计算出原始的数据块；用于有噪声的信道，因为重传的数据块本身也可能像第一次传输那样出错。（小姑娘回家路上随机丢失器官，最后可能面目全非，认不出来是谁，你不知道应该给这家的家长再送一个谁回去，所以在她身上贴很多的名签 检错码：包含一些冗余信息，这些信息只能让接收方推断出是否发生了错误（而推断不出哪个发生了错误），然后接收方可以请求发送方重传。在高度可靠的信道上使用（比如光纤），当偶尔发生错误时只需重传整个数据块。（小姑娘只要不完整了就会发出尖锐的爆鸣声，从而在到达时让家长知道她不完整了，再送一个完整的她来 ## 3.2.1 纠错码（ECC ECC大致分为两类：块码和卷积码 其中块码（block code）指r个校验位是作为与之相关的m个数据位的函数计算获得的。
其他一些概念： 一帧由m个数据位（即信息，小姑娘本身）和r个冗余位（即校验，身上的名签）组成。 系统码（systematic code）：直接发送m个数据位，然后发出r个校验位，不在发送前对他们编码。 线性码（line code）：r个校验位是作为m个数据位的线性函数被计算出来的 线性函数的选择：异或（如海明码）或模2加。 以上名词常叠加使用，如线性系统块码。
数据块的总长度为n（即n=m+r），描述为（n，m）码。一个包含了数据位和校验位的n位单元称为n位码字（codeword） 码率（code rate）：码字中不包含冗余部分所占的比例，用m/n表示。 ### 1. Hamming Code #### （1）海明距离 两个码字中不相同的位的个数。意义在于，如果两个码字的海明距离为d，则需要d个1位错误才能将一个码字转变为另一个码字。
如：0000000000与0000011111海明距离为5 Bounds for a code with distance: 2d + 1 can correct d errors（向下取整 d + 1 can detect d errors 对于上面这个例子，最多可纠正2个错误，检测四个错误
解释： 假设我们有两个码字： 000 编码为 00000 111 编码为 11111 则可纠正两位的错误 在这个场景中，实际上发送的是 00000。为了确保接收方能够纠正传输中的错误，事先知道了其他可能的码字，比如 11111。这个额外的码字 11111 是用来帮助接收方识别并纠正错误的。 在传输过程中，第一个比特发生错误，变为 10000。 在这里，海明距离 d 是4，即我们能够纠正1个错误。纠错的过程是，接收方看到 10000，并意识到它离最近的码字 11111 的距离是4，但它离 00000 的距离是1。因此，接收方能够纠正第一个比特的错误，将 10000 纠正为 00000，即原始的码字 000。 但假如传输过程中变为11100，离00000距离为3，离11111距离为2，则会发生错误。
在一个纠错码中，海明距离 d 表示两个码字之间不同位的数量。如果 d
是奇数，我们可以确保存在一个中间点，离任何一个码字的距离都大于 d/2。如果
d 是偶数，那么中间点就可能是多个，但我们仍然可以通过向下取整确保 t
是整数。 d/2 的意义是，如果两个码字的海明距离小于
d/2，那么它们有可能在纠错的时候被混淆，因为有一部分错误可能会落在一个码字的一半上，而另一部分错误可能会落在另一个码字的一半上。
所以，为了纠正可能发生的错误，我们希望确保两个码字之间的最小距离至少是
d。为了确保这一点，我们可以取纠错能力 t 为 (d - 1) / 2。这样，即使有 d
个错误，我们仍然可以通过查看最近的码字来确定应该对哪些位进行纠正。 ####
（2）海明不等式
每个码字有k个消息位和n个校验位，并且能纠正所有的一位错误。 \[2^n\geq k+n+1\] #### （3）编码（计算校验位
Hamming码采用的是奇偶校验，具体而言，它使用的是偶校验。
校验位下标为2的幂次方，图中\(P_1、P_2、P_3、P_4\)是校验位，\(P_1\)从\(P_1\)开始，校验1位，然后跳过1位，再校验1位，再跳过1位，...,\(P_2\)从\(P_2\)开始，取2隔2，以此类推（\(2^n\)），传输前计算使得都为偶检验。
其实正式一点说是异或，使得最后异或值为0，但是位数比较少就让1是偶数个就行了。
检错（进行校验）：传输过去了，计算校验位时，方法同上，此时每个\(P_x\)和本身的那些位异或，如图3-6对于右边收到的码字中的\(P_0\)，\(P_0\oplus m_3 \oplus m_5 \oplus m_7 \oplus m_9
\oplus
m_{11}=1\)，如果没错，异或结果为0，有错为1，这里很显然由于第五位和\(P_0\)有关，所以出错了。 
对于其他几个也是同样计算，这样可以精准定位到出错的位置。此时将校验位结果倒过来排列，如\(P_8P_4P_2P_1\)（图中为0101，出错的即第5位），可得出错比特位置，将其取反，则可修改过来。
这里用二进制更方便，0001，0010，0011，...，其校验位对应的是1则算上，所以形成了这样的规律。
#### （4）海明距离与海明码
由上述计算过程可知，如四位信息，编码为海明码要加上1，2，4三位，共七位。可自行验证，任意一个信息编码，其相邻的最小海明距离都为3，由海明距离的结论可知，海明码只能修改1位错误。
### 2. 二进制卷积码
在卷积码中，消息包含任意长度的数据流，并且通过将布尔函数滑动应用到数据流来生成一系列输出位。
## 3.2.2 检错码 以下三种都是线性的系统块码。 ### 1. 奇偶 ####
（1）检错原理 检测1是奇数还是偶数，只能检测1位错误，检错效率高于海明码
#### （2）举例 发送1011010： 偶校验（01011010），奇校验（11011010） ###
2. 校验和 #### （1）检错原理
与一组奇偶校验位密切相关。对消息中的数据位进行求和计算，校验和放在消息的末尾，检测错误时求和计算整个收到的码字（包含数据位和校验和），计算结果是0则无错误
#### （2）举例 ### 3. 循环冗余校验（CRC #### （1）算法 
补充：生成多项式的过程为\[1 \cdot x^4 + 0
\cdot x^3 \] #### （2）举例 
#
3.3 基本数据链路层协议 ## 3.3.1 一个乌托邦式的单工协议 ## 3.3.2 停等协议
所谓“停等”，即每发送完一个分组就停止发送，等待对方确认，收到确认的消息再发送下一个分组
### （1）无差错情况 
###
（2）有差错情况 
发送一个帧后，一定要保留它的副本，以便超时重传。 
数据帧和确认帧都要编号， 
###
（3）信道利用率
发送方在一个发送周期内，有效地发送数据所需要的时间占整个发送周期的比率。
\[信道吞吐率 = 信道利用率
\times 发送方发送速率\] ## 3.3.3 滑动窗口协议 ###
