Data Link Layer
结点：主机、路由器
帧：链路层的 PDU ，封装网络层的数据报
功能：在有差错的物理线路上提供无差错的数据传输
- 给网络层提供服务：
- 无确认无连接不可靠（快；只检错（CRC）不恢复；适合通信质量好的链路；e.g. IEEE 802.3 以太网）
- 有确认无连接（适合误码率比较高的，e.g. 无线 802.11 (WiFi)）
-
有确认面向连接
- 建立连接
- 每一帧编号；确保恰好收到一次；
-
适用于：长距离不可靠；e.g. 卫星；（可以想象丢失了确认可能导致一个帧被收发多次，因而将浪费带宽。）
-
三个阶段：
- 建立连接：初始化变量、计数器
- 传输数据帧
- 释放连接：释放变量、缓冲区等资源
- 注意：有连接一定有确认！
- 链路管理：连接的建立、维持、释放
- 组帧
- 流量控制（限制发送方）
- 差错控制（帧错/位错）：意义：及时发现，及时解决
1. 封装成帧
拆分比特流以成帧
帧开始）帧首部 + 帧数据（≤MTU） + 帧尾部（帧结束
帧同步：接收方可以从二进制 bit stream 中区分出帧的起始和终止。
1.1 字节计数法
帧首部用 1Byte 表明帧内字符数
- 计数值有可能因为一个传输错误而被弄混
1.2 字节填充的标志字节法
每个帧用标志字节（flag byte）作为开始和结束
- 解决数据中出现 FLAG ： ESC 转义字节
- 数据中出现 ESC ：仍然用 ESC 转义；在接收方，第一个转义字节 ESC 被删除，而留下紧跟在它后面的一个数据字节
- 缺点：只能使用 8 比特的字节；帧只能以8字节为单元
1.3 比特填充的标志比特法
帧的划分可以在比特级完成
每个帧的开始和结束是标志字节：01111110（Ox7E）
- 发送方：在数据中遇到连续5个1，它便自动在输出的比特流中填入一个比特0。
- 接收方：看到 5 个连续比特 1 且后面跟一个比特0，它就自动剔除（即删除）比特 0 。
- 缺点：如果数据中标志字节太多，则帧的长度大幅增加。
- 应用状况：普遍使用
1.4 物理层编码违禁法
选择一段不会在数据部分出现的 bits 作为定界符。
- 4B/5B编码方案：
- 4比特数据映射成5比特编码，剩余的一半码字(16个码字)未使用，可以用做帧定界符。
- 例如: 00110组合不包含在4B/5B编码中，即正常来讲它不可能出现在数据中，于是可做帧定界符。
实现简单，普遍使用。
2. 检错
2.1 奇偶校验
增加1位校验位，可以检查奇数个位错误
- 偶校验：保证1的个数为偶数个
- 奇校验：保证1的个数为奇数个
2.2 Checksum 校验和
2.3 CRC 循环冗余校验
发送方：
- 生成多项式为 n+1 位，原数据后面加 n 个0
- 加 0 后除以生成多项式，余数就是代替补的0的 CRC 校验码
接收方：
- 除以生成多项式，余数为 0 则接受
注意：这属于「无比特差错」的传输，而不是「可靠传输」。
3. 纠错
Codeword： n 位码字， m 个消息位和 r 个校验位，\(n = m + r\)。
Hamming distance：两个码字中不相同的位的个数
原理：空间稀疏：对 r 校验位，可能的报文中只有很少一部分（\(1/2^r\)）是合法的。
Hamming distance 为 d 的编码方案：最短的两个合法的编码之间的距离为d
- 为了检查出 d 个错，可以使用海明距离为 d+1 的编码
- 为了纠正 d 个错，可以使用海明距离为 2d+1 的编码
- 合法码字之间的距离足够远，即使发生了 d 位变化，结果也还是离它原来的码字最近。这意味着在不太可能有更多错误的假设下，可以唯一确定原来的码字。
设计纠错码的要求：
- m 个信息位，r 个校验位，共 n=m+r 位的码字
- 最多错 d 位。
- 有效信息： \(2^m\) 种可能的有效信息；
- 每一个n位纠错码，包括正确的，实际中可能会因为出错变成 \(\Sigma_{k = 0}^d\mathbb{C}_n^k\) 种形式。
- 保证 n 位纠错码能够表示上述所有不同的码字：\(2^m \cdot \Sigma_{k = 0}^d \mathbb{C}_n^k \leq 2^n\)。
- 由上式可解出纠错所需的校验位个数的下界。
3.1 Hamming Code
3.1.1 设计目标
纠正单比特错；令 \(d = 1\) 代入上式有：
校验位的个数 \(r\) 需满足： \(2^r \ge r + m + 1 ~ (= n + 1)\) 。
3.1.2 编码
- 校验位放在 \(2^i\) 的位置；
- 其余数据位顺次填充；
- 如何求校验位？（默认为偶校验）
- 根据校验位位置编号（从1开始）的二进制中1的位置确定其校验的数据位；
- 校验位 + 数据位一起使1的个数为偶数个。
3.1.3 检错 & 纠错
- 每个校验位加上对应的数据位，看是不是偶数个1；是的话记为0，否则记为1
- 其实相当于异或运算的结果！
- 倒序写各个异或运算的结果，即得到出错的1比特的序号！（原理就是每个校验位对应了比特位序号的二进制中的 1 位。）
4. 可靠传输与流量控制
可靠传输：发送端发啥，接收端收啥
数据链路层流控手段：receiver 收不下就不回复确认
对比：传输层流控手段：receiver 给 sender 发送一个窗口公告（告诉它窗口多大，缓冲区多大等）
滑动窗口协议的信道利用率：
- 链路利用率 \(\leq {w \over 1+2BD}\) ；\(BD = { \text{bandwidth} \cdot \text{delay} \over \text{bit size of frame} }\)
4.1 停等协议
问题：效率太低！
（相当于发送、接收窗口大小均为1。）
4.1.1 无差错
ACK确认的意义：receiver 可能 overwhelming
4.1.2 有差错
计时器timer：未收到ACK，timeout，重发（timeout > RTT）
序号SEQ：区分是重发的，还是新帧（数据帧、确认帧，都要编号；1bit编号即可；重复丢弃）
4.2 后退 N 帧 GBN
Sender：
- 从上层收到数据，看在不在窗口内，决定是否发送。
- 收到 ACK：累计确认！收到 n 号 ACK，意味着 receiver 已经收到了 n 号帧和之前的全部帧，于是窗口下界立即滑到 n+1 。
- 超时：重传所有已发送但是未确认的帧！
Receiver：
- 只有正确、按序收到 n 号帧，才给 n 号帧发送 ACK ，并交付上层。
- 其余情况，都丢弃！并发送最近按序接收的帧的 ACK。
窗口大小的设计
- \(W_{Tmax} = 2^n - 1, W_R = 1\) （ n 位比特编序号；接收窗口固定为1）
特点
- receiver 累计确认（偶尔捎带确认）
- receiver 只按顺序接收，否则丢弃；确认最后一个按序正确的。
- sender 连续发送提高了信道利用率！
- sender 一些正确传送的帧也被重传了，效率降低。
4.3 选择重传 SR
Sender：
- 从上层收到数据，看在不在窗口内，决定是否发送。
- 收到 ACK：看是不是窗口中最小序号的未确认帧，决定是否前移。
- 收到 NAK ：只重传出错的帧。
- 超时：每个帧有自己的 timer 。
Receiver：
- 接收窗口内的帧来者不拒（失序的也会缓存）。
- 向前滑动时将一批数据一起交付给上层！
- 收到窗口下界之前的帧，返回 ACK 。
- NAK：出错的帧丢弃，然后传它的 NAK
窗口大小的设计
-
最好发送窗口等于接收窗口（大了溢出，小了没意义。）
-
大小减半： \(W_{Tmax} = W_{Rmax} = 2^{n-1}\) （n 位比特编序号）
-
原因是以下两种情况会混淆：
特点
- receiver 对数据帧逐一确认
- receiver 有缓存
- sender 只重传出错帧
5. 设备
要通过某种方式，拓展以太网，让更大范围内的设备之间能够通信。
冲突域：每个节点都能收到所有被发送的帧。同一时间只能有一方在发。
广播域：网络中能接收任一设备发出的广播帧的所有设备的集合。
5.1 Hub 集线器（物理层设备）
集线器、主干集线器
只能一方发，不能分割冲突域
5.2 Network Bridge & Switch 网桥和交换机 （链路层设备）
对比：集线器把收到的东西向所有其它端口转发出去。
5.2.1 网桥
5.2.1.1 基本特点
根据 MAC 目的地址对帧进行转发和过滤。
- 接收到帧，检查目的 MAC 地址：
- 表中查不到，泛洪；
- 表中能查到，且接收到的端口 ≠ 表中的转发端口，发送；
- 表中能查到，且接收到的端口 = 表中的转发端口，丢弃。
- 分割冲突域
- 过滤通信量；增大吞吐量（速率总和）
- 提高可靠性（不同冲突域不互相影响）
- 互连不同物理层、不同 MAC 子层，不同速率的以太网
5.2.1.2 透明网桥与逆向学习
透明网桥：
- 站点不知道发送的帧要经过几个网桥
- 即插即用，自学习
从发送方的信息「逆向」学习！
转发表 / MAC 地址表：MAC 地址 到 端口 的映射表
5.2.1.3 源路由网桥
5.2.2 交换机
网桥的端口越来越多，变成了交换机。
5.2.2.1 直通式
查完目的地址就立即转发
- 延迟小
- 可靠性低
- 无法支持不同速率端口的交换
5.2.2.2 存储转发式
会检查帧的正确性
- 延迟大
- 可靠性高
- 支持不同速率端口的交换
- 常用！
5.2.2.3 无碎片式
接收到帧的前 64B ，就开始转发。
- 仍可能转发错误帧
- 不支持非对称交换
- 过滤了冲突碎片（< 64B），延迟和转发错帧的情况介于上述两者之间