数据链路层基础
向下：利用物理层提供的位流服务
向上：向网络层提供明确的(well-defined) 服务接口
数据链路层的设计问题
功能：成帧（frame）、差错控制、流量控制
服务：无确认无连接服务（Unacknowledged connectionless）：
接收方不对收到的帧进行确认。适用场景：误码率低的可靠信道；实时通信；网络实例：以太网
有确认无连接服务（Acknowledged connectionless）：
每一帧都得到单独的确认。适用场景：不可靠的信道（无线信道）网络实例：802.11；
有确认有连接服务（Acknowledged connection-oriented）：适用场景：长延迟的不可靠信道；
成帧：
成帧（framing）的方式：字节计数法（Byte count ）、带字节填充的定界符法（Flagbytes with bytestuffing ）、带比特填充的定界符法（Flagbits with bitstuffing ）、物理层编码违例（Physical layer coding violations ）等。
如果包含相同字符，则需要转义字节帮助。
收到ESC，则后一字节无条件成为有效载荷，不予检查；
收到FLAG，则为帧的边界。
缺点：可能浪费大量空间给转义字节
接收方的处理：若出现连续5个1比特−若下一比特为0，则为有效载荷，直接丢弃0比特；若下一比特为1，则连同后一比特的0，构成 定界符，一帧结束。
物理层编码违例
核心思想：选择的定界符不会在数据部分出现
示例：4B/5B编码方案：4比特数据映射成5比特编码，剩余的一半码字（16个码字）未使用，可以用做帧定界符。例如：00110组合不包含在4B/5B编码中，可做帧定界符；
前导码：存在很长的前导码（preamble），可以用作定界符。例如：传统以太网、802.11。
曼切斯特编码/ 差分曼切斯特编码：若中间无跳变，该信号当然可以作为帧定界符。
差错检测和纠正
信道的噪声导致数据传输问题，有差错、丢失、乱序、重复等。
信道传输差错解决的通常策略：增加冗余（校验）信息
在此基础上，减少冗余信息量的主要策略：检错码，纠错码
检错码：基于高可靠性
在被发送的数据块中，包含一些冗余信息，但这些信息只能使接收方推断是否发生错误，但不能推断哪位发生错误，接收方可以请求发送方重传数据
纠错码：定位出错位置
发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。使用纠错码的技术通常称为前向纠错（FEC）。
一些概念阐述：
**码字：**一个包含m个数据位和r个校验位的n位单元。描述为(n, m) 码，n=m+r
**码率：**码字中不含冗余部分所占的比例，可以用m/n表示。
海明距离(Hamming distance)：两个码字之间不同对应比特的数目
检d个错需要d+1位海明码，纠d个错需要2d+1位
其他检错码还有：
奇偶检验(Parity Check)：1位奇偶校验是最简单基础的检错码（奇/偶校验：保证1的数量为奇/偶数）
校验和(Checksum)：主要用于TCP/IP体系中的网络层和传输层
循环冗余校验(Cyclic Redundancy Check，CRC)：数据链路层广泛使用的校验方法
checksum后面还会讲，在这不展开了
CRC校验码计算方法如下：
- 原始数据D为k位二进制位模式。
- 选定一个n+1位的生成多项式G，最高位为1。
- 将D乘以2n（即在D后加n个0），得到k+n位的位模式。
- 用G对该位模式做模2除法，得到n位余数R，即为CRC校验码（不足n位时前面补0）。
四个国际标准生成多项式：
CRC-12 = x12+x11+x3+x2+x+1
CRC-16 = x16+x15+x2+1
CRC-CCITT = x16+x12+x5+1
CRC-32 = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1（以太网、无线局域网）
海明码的检验本质：奇偶校验，例子在ppt上，或者一搜就有
出错的位置编号正好是检验出错的组的位置编号之和
海明码纠正的实现过程：每个码字到来前，接收方计数器清零•接收方检查每个校验位k (k = 1, 2, 4 …)的奇偶值是否正确（每组运算）；若pk奇偶值不对，计数器加k；所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为j，则第j 位出错。例：若校验位p1、p2、p8出错，则第11位变反
RS码：以有限域运算为基础，提供多位纠错能力
RS会将需要编码的流数据重新排列为以Symbol为单位的数据块
对于一个(n, k)RS编码，k为原始数据符号数，n-k为校验符号数
n-k=2t，t表示能够纠正的错误数
基本的数据链路层协议
三个关键假设：分层进程独立假设、提供可靠服务假设、只处理通信错误假设
物理层进程和某些数据链路层进程运行在专用硬件上（网络接口卡）；
数据链路层进程的其他部分和网络层进程作为操作系统的一部分运行在CPU上，数据链路层进程的软件通常以设备驱动的形式存在。
乌托邦式单工协议：完美信道，始终就绪、瞬间完成，完美但不现实
也许完美对我反而是假象……啊不对跑题了
发送方——在循环中不停发送——从网络层获得数据——封装成帧——交给物理层——完成一次发送
接收方——在循环中持续接收——等待帧到达（frame_arrival）——从物理层获得帧——解封装，将帧中的数据传递给网络层——完成一次接收
无错信道上的停等式协议：不再假设瞬间完成，仍然假设半双工、完美信道
停-等式协议（stop-and-wait）——发送方发送一帧后暂停，等待确认（Acknowldgement）到达后发送下一帧——接收方完成接收后，回复确认接收.
有错信道上的单工停等式协议：帧在传输过程中可能被破坏，可能丢失
最简单的一个解决方法：添加计时器，超时重传。可能的问题：ACK丢失，过高延时
additional solution：SEQ，根据帧序号判断是不是新帧
其他方法：自动重复请求，或带有重传的肯定确认：ARQ(Automatic Repeat reQuest)，PAR(Positive Acknowledgement with Retransmission)
发送方：初始化帧序号0，发送帧——等待：正确的确认/错误的确认/超时——正确确认：发送下一帧——超时/错误确认：重发
接收方：初始化期待0号帧——等待帧达到——正确帧：交给网络层，并发送该帧确认——错误帧：发送上一个成功接收帧的确认
停止等待协议的问题是只能有一个没有被确认的帧在发送中，信道利用效率低
一种提高效率的方法：使用更大的帧
滑动窗口协议
停止-等待机制降低了信道利用率：设数据速率记为R，帧长度记为F，往返延迟记为D，则采用停-等协议的线路效率为：F/(F+R·D)
解决办法：流水线协议或管道协议：允许发送方在没收到确认前连续发送多个帧
协议基本思想：窗口机制：发送方和接收方都具有一定容量的缓冲区（即窗口），发送端在收到确认之前可以发送多个帧。
序号使用：循环重复利用有限的序号
流量控制：接收窗口驱动发送窗口的转动
累计确认：不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认
Eg：
发送方实现过程：1. 初始化：ack_expected = frame_expected = next_frame_to_send = 0
- 从网络层接收分组，放入相应的缓冲区，构造帧，物理层发送，开启计时。
- 等待确认帧到达，从物理层接收一个帧，判断确认号是否正确，正确则停止计时器，并从网络层接收新分组。
- 发送新的帧，跳转至3
接收方实现过程：1. 初始化：ack_expected = frame_expected = next_frame_to_send = 0
- 等待帧到达，从物理层接收一个帧，校验和计算， 并判断收到的帧序号是否正确，正确则交给网络层处理，期待帧号增加。
- 返回确认帧，跳转至2。
回退N协议
设计思想：出错全部重发：当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认；发送端超时后，重传所有未被确认的帧。
该策略对应接收窗口为1的情况，即只能按顺序接收帧。
基本原理：当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就重新发送出错帧及其后的N帧。
出错全部重发时，若帧序号为n位，接收窗口WR=1，发送窗口WT≤ 2n－1
实现要点：必须增加序号范围、发送方需要缓存多个分组
发送方必须响应的三件事：
- 上层的调用：检测有没有可以使用的序号，如果有就发送
- 收到ACK：对n号帧的确认采用累积确认的方式
- 超时事件：如果出现超时，就重传所有已发送未确认的分组
协议实现
发送方：
- 窗口尺寸：1<WT≤2n-1，最多连续发送窗口中的WT个PDU
- 窗口滑动：收到期望的ACK(k)：窗口底部移到PDU(k)，窗口顶部向前移动，始终保持窗口里有WT个PDU未确认。
- 窗口滑动后，发送新进入窗口的PDU
- 超时重发：超过T未收到期望的ACK，重发窗口中的PDU（回退整个窗口）
- 超次数失败：超过最大重发次数Nmax仍无正确应答
接收方：
- 窗口尺寸：WR=1
- 按序接收：按照PDU编号依序接收，出错、乱序PDU一律丢弃
- 确认含义：ACK(k)表示对k-1及以前各编号的PDU的确认，同时期望接收第k号PDU
- 确认策略：按序到达的PDU可立即确认，也可延迟确认(收到多帧后一起确认)，但出错或乱序的PDU，确认ACK(k)（期望接收k号PDU）或不应答
选择重传协议
实现思想：若发送方发出连续的若干帧后，收到对其中某一帧的否认帧，或某一帧的定时器超时，则只重传该出错帧或计时器超时的数据帧。
该策略对应接收窗口大于1的情况，即暂存接收窗口中序号在出错帧之后的数据帧。
优点：避免重传已正确传送的帧；缺点：在接收端需要占用一定容量的缓存
在发送过程中，如果一个数据帧计时器超时，就认为该帧丢失或者被破坏；接收端只把出错的的帧丢弃，其后面的数据帧保存在缓存中，并向发送端回复NAK；发送端接收到NAK时，只重传出错的帧。
如果落在窗口内的帧从未接受过，那么存储起来，等比它序列号小的所有帧都正确接收后，按次序交付给网络层。
接收端收到的数据包的顺序可能和发送的数据包顺序不一样，因此在数据包里必须含有顺序号来帮助接收端进行排序。
发送窗口应该小于序号空间的一半。
在SR中，和GBN不同，SR是给每一个PDU设置定时器，发送端只重传出错PDU。接收端在接收到乱序的PDU的时候会进行缓存，当前面的PDU到达以后一起提交给上层
发送方必须响应的三件事：
上层的调用：检测有没有可以使用的序号，如果有就发送
收到ACK：如果收到的是最小序号的ACK，窗口滑动。如果收到其他序号的ACK，进行标记
超时事件：每个PDU都有定时器，哪个超时重传哪个
协议实现基本过程与回退N协议基本类似，其中
发送方：
- 窗口尺寸：1<WT≤2n- 1，最多连续发送窗口中的WT个PDU
- 窗口滑动：与回退N帧协议相同
- 选择重发：收到NAK(k)，重发PDU(k)
- 超时重发：超过T未收到期望的ACK，重发当前超时未应答的PDU
- 超次数失败：超过最大重发次数Nmax仍无正确应答，报告上层失败
接收方：
- 窗口尺寸：1<WR≤2n-1
- 窗口滑动：窗口底部数据上交，窗口向前滑动一步
- 窗口内接收：窗口内的PDU全部接收，存储出错的后续PDU，按序交付；窗口外的PDU一律丢弃
- 确认策略：按序到达的PDU可立即确认，也可延迟确认(收到多帧后一起确认)ACK(k)；出错用否定性确认NAK(k)（期望重发k号PDU）
协议实现
我实在懒得搬过来了，截张图
数据链路协议实例
PPP协议Point-to-Point Protocol)由IETF制定，1994年成为正式标准（RFC1661）是目前使用最多的数据链路层协议之一，具有简单、灵活的特点。
协议为全双工，支持帧的封装，差错检测、填充技术、链路工作状态监测、设置MTU；未实现纠错、可靠传输、流量控制和多点连接
PPP的帧格式（LKJ100题里面关于PPP的好几道，感觉会是一个考点？）
当PPP 用在异步传输时，使用一种特殊的字符填充法；
当PPP 用在同步传输链路时，协议规定采用硬件来完成比特填充（与HDLC的做法类似）
PPPoE：提供了在以太网上的PPP连接
优点：原理简单、安全性高：点对点信道，提供认证机制、提供良好的访问控制和计费功能
使用CS模型，服务器通常是接入服务器
（PPPoE应该不是重点……吧）
PPPoE可分为三个阶段：
- Discovery阶段− 获取对方以太网地址，确定PPPoE会话ID
- Session阶段−PPP协商阶段−PPP报数数据传输
- Terminate阶段− 会话建立以后的任意时刻，发送报文结束会话
