计算机网络-数据链路层学习笔记

负责在链路上传递数据帧
处理传输错误
调节数据流

# 链路分类

点对点链路（point-to-point） 使用介质的全部容量
- 专用于两个设备
- 例如，当两个朋友使用座机聊天时，他们使用的是点对点链路
广播式链路（broadcast） 仅使用链路容量的一部分
- 在多对设备之间共享
- 例如，当同两个朋友使用他们的手机时，他们正在使用广播链接（许多手机用户共享广播）

# 数据链路层的两个子层

逻辑链路控制子层（LLC Logical Link Control） 处理点对点和广播链路的所有常见问题
媒体接入控制子层（MAC Media Access Control） 仅处理特定的广播链路问题

# 数据链路设计问题

# 帧

数据链路层接受来自网络层的数据包，并将其封装到帧中发送给物理层；接收则与其相反
封装和去封装的原因：
- 链路层地址通常是不同的
- 每个链路可能使用具有不同帧格式的不同协议

# 向网络层提供的服务

无确认的无连接服务
- 发送帧时没有建立连接 / 恢复错误
- 适合错误率低的场景或实时通信
- 例如以太网
有确认的无连接服务
- 如果需要，帧会进行重传
- 例如 802.11（WIFI）
有确认的有连接服务
- 建立连接
- 卫星信号或长途电话电路

# 成帧

# 字节计数法（Byte count）

头部添加字段用来标记帧的字节数
相对简单，但出错后很难重新同步

# 字节填充的标志字节法（Flag bytes with byte stuffing）

标志字节（flag byte）分隔帧；如果数据中存在标志字节或转义字节，则在其之前填充转义字节（ESC）
例如，A ESC FLAG B ----> A ESC ESC ESC FLAG B
帧会变的更长，但在出错后很容易重新同步

# 比特填充的标志比特法（Flag bits with bit stuffing）

在位级别完成的填充
标志字节为 0x7E，包含 111111（6 个连续的 1）
在传输时，在数据中 5 个 1 之后，添加 0（防止干扰标志字节的识别）
接收时，删除五个 1 后的 0
USB（通用串行总线）所使用

# 物理层编码违禁法（Physical layer coding violations）

使用编码中的冗余比特

# 差错检测

# 差错种类

单比特错误（Single-bit error）数据单元中只有 1 位从 1 变为 0 或从 0 变为 1
突发错误（Burst error）数据单元中的 2 个或更多位从 1 变为 0 或从 0 变为 1

# 差错检测 & 差错纠正

差错纠正比差错检测更困难
在差错检测中，我们只关心是否发生了任何错误
在差错纠正中，我们需要知道被破坏的比特的数目和位置
差错检测使用检错码，差错纠正使用纠错码，使用纠错码的技术也称为前向纠错（FEC Forward Error Correction）
在高度可靠的信道上建议使用检错码，而在错误比较频繁的信道上建议使用纠错码

# 海明距离（Hamming distance）

海明距离是将一个有效码字转换为任何其他有效码字的最小位翻转
编码将 $n$ 位的数据转换为 $n+k$ 位的码字
具有 10 位（ $n=2$ $n = 2$ ， $k=8$ $k = 8$ ）的 4 个码字的示例：
- 0000000000、0000011111、1111100000 和 1111111
- 其汉明距离是 5
具有最小汉明距离 $d_{min}$ $d_{min}$ 的编码界限：
- $d_{min} \geq 2d+1$ 可以纠正 d 错误（上例 2 个错误）
- $d_{min} \geq d+1$ 可检测 d 个错误（上例 4 个错误）

# 线性分组编码（Linear Block Codes）

线性分组编码是将任何码字与任何其他码字进行线性运算的结果为有效码字的编码
线性运算通常选用 XOR 或是模 2 运算

# 纠错码

海明码
二进制卷积码
- GSM 移动电话系统、卫星通信
里德所罗门码和低密度奇偶校验码
- 在数学上较为复杂，广泛应用于实际
- RS 编码：DSL、有线数据、卫星通信、CD、DVD 和蓝光光盘
- LDPC 编码：数字视频广播、10Gbps 以太网、电力线网络、最新版本的 802.11

# 海明码

允许纠正单比特错误
通过使用多个奇偶校验位来实现
要设计一个包含 $m$ 个数据位和 $r$ 个校验位的 $n$ 位编码，并能够纠正所有单个错误，必须有

$(m+r+1)\leq 2^r$

对于 $2^m$ 个合法消息中的每一条都有 $n$ 个非法码字，它们与该消息的海明距离为 1
所以 $2^m$ 个合法消息需要 $n+1$ 个位模式来进行标识。因为位模式的总数为 $2^n$ ，所以必须有

$(n+1)2^m\leq 2^n$

由于 $n=m+r$ ，经过变形变为上式

# 检错码

奇偶（Parity）
校验和（Checksums）
循环冗余校验（CRC）

# 奇偶校验

奇偶校验位等于数据位的模 2 加或 XOR
能检测奇数位比特错误，检测随机错误的概率为 1/2
使用交错校验（Interleaving）能检测突发错误，其本质是发送次序和检验次序不同
$N$ 个奇偶校验位的交错检验可检测高达 $N$ 个的突发错误
每个奇偶校验和在非相邻位上进行
即使出现多达 $N$ 个错误，也不会导致校验失败

# 校验和

校验和将数据分隔为 $N$ $N$ 位字，并添加 $N$ $N$ 个校验位，这些校验位是字的模 $2^N$ $2^{N}$ 和
- 例：16 位 Internet 反码校验和
特性
- 改进的奇偶校验
- 检测最多 $N$ 个突发错误
- 检测随机错误的概率为 $1-2^N$
- 易受系统误差的影响，例如无法检测 0 数据的增加或删除

1's complement 反码
2's complement 补码

如果在传输过程中两个 16 位项顺序颠倒，校验和无法捕获此错误，原因是传统的校验和没有加权，数据项的顺序对计算不重要
可以使用 Fletcher 校验和和 Adler 校验和来解决

# CRC

计算方法：
- 假设 $G(x)$ 的阶为 $r$ ，在帧的低端位加上 $r$ 个 0 位
- 利用模 2 除法，将帧对应的位串与 $G(x)$ 相除，获得余数
- 余数和帧对应的位串模 2 相加
- 验证则相反，如果没有发生错误则余数应该为 0
在循环码中，那些可被 $G(x)$ 整除的 $e(x)$ 错误不会被捕获。
如果生成多项式有多个项且 $x_0$ 的系数为 1，则可以捕获所有单比特错误
包含系数 $x+1$ 的生成多项式可以检测所有奇数位比特错误
所有突发错误，长度 $L \leq r$ 将会被检测到
所有突发错误，长度 $L = r+1$ 将会有 $1-(1/2)^{r-1}$ 的概率被检测到
所有突发错误，长度 $L > r+1$ 将会有 $1-(1/2)^r$ 的概率被检测到
一个好的生成多项式应该：
- 至少拥有两项
- 项 $x_0$ 的系数应为 1
- 应该具有因子 $x+1$

# 基本数据链路协议

# 乌托邦式单工协议 P1

假设没有错误，并且接收方和发送方一样快
单向数据传输

# 无错信道上的单工停 - 等式协议 P2

确保发送方不能超过接收方
接收机在准备就绪时返回一个哑帧（ack），允许它发送下一帧
一次只能输出一帧 —— 称为停 - 等式协议（stop-and-wait）

# 有错信道上的单工停 - 等式协议 P3

ARQ（Automatic Repeat reQuest）也称为 PAR（Positive Acknowledgement with Retransmission）添加了错误控制
接收器确认正确传送的帧并发送 ack
发送方设置定时器并在无应答时重新发送帧
为确保正确性，必须对数据帧和 ack 进行编号，否则，接收方无法从新帧中分辨出重传
对于停 - 等式协议，序号采用 1 位（2 个数字）足矣

# 滑动窗口协议

发送方维护它可以发送的帧窗口
- 需要为可能的重传保留缓冲空间
- 窗口在收到下一次确认时前移
接收方维护它可以接收的帧窗口
- 需要为到达帧保留缓冲空间
- 窗口在帧按顺序到达时前移
确认信息可以被单独附在数据帧上（ack），也可以附在下一个出境的数据帧上。这被称为捎带确认（piggybacking）

# 管道化（Pipelining）

更大的窗口可以使用管道化来实现高效链接
停 - 等式协议（w=1）对于长距离链接而言效率低下
窗口最大帧数量（w）取决于带宽 - 延迟（BD bandwidth-delay）
$w \geq 2BD+1$ 以确保高链路利用率

注意：这里的 BD 已经换算成帧的数量

如果我们直接使用 BDP（bandwidth-delay product），假设 L 是一帧的长度，公式应为

$W \geq 2BDP/L+1$

管道化导致了对于错误 / 缓存的不同选择：
- 回退 N
- 选择重传

# 1 位滑动窗口协议 P4

序列号基于模 2 算法，通过停 - 等式协议在两个方向传输数据
- 借助捎带确认提高效率
- 处理传输错误、流量控制
如果同时发起通信会造成重复传输，效率下降

# 回退 N 协议 P5

接收方仅接受 / 确认按顺序到达的帧：
- 丢弃丢失 / 出错帧之后的帧
- 发送方超时并重传所有未完成的帧
在回退 N 协议中，发送窗口大小必须小于 $2^m$ ，接收窗口的大小始终为 1
其本质就是窗口大小不能超过序号能表示的范围，如果发送窗口大小等于 $2^m$ ，则接收方所有 ack 丢失后无法判断重传帧
对回退 N 进行权衡：
- 对接收方来说较为简单，只需要 1 帧
- 由于大窗口错误而浪费链路带宽，整个窗口将被重传

# 选择重传协议 P6

接收方在接收窗口中的任意位置接收帧
累积 ack（Cumulative ack）表示帧中的最高顺序
NAK（negative ack）导致发送方在超时重新发送窗口之前重新传输丢失的帧
在选选择重传协议中，发送方和接收方窗口的大小不得超过 $2^{m-1}$
如果发送窗口大小 $2^{m-1}$ ，则接收方所有 ack 丢失后无法判断重传帧
对选择性重复进行权衡：
- 由于接收端有缓冲，发送端有多个定时器，因此比回退 N 更复杂
- 更有效地利用链路带宽，因为只重新发送丢失的帧（低错误率）

# 数据链路协议实例

# HDLC

高级数据链路控制（HDLC）是一种面向位的协议，用于点对点和多点链路上的通信
虽然 HDLC 更多的是一个理论问题而不是实际问题，但 HDLC 中定义的大多数概念是其他实际协议（如 PPP、以太网或无线局域网）的基础
HDLC 提供两种常见的传输模式，可用于不同的配置：正常响应模式（NRM）和异步平衡模式（ABM）

# HDCL 帧

信息帧（I 帧）（用于传递数据）
监控帧（S 帧）（用于 ACK 和 NAK）
未编号的帧（U 帧）（用于建立连接）

# SONET 上的数据包

SONET 上的数据包是用于通过 SONET 光纤链路承载 IP 数据包的方法
- 使用 PPP（点对点协议）进行成帧

# PPP

PPP（点对点协议）是跨链路传送数据包的通用方法
- 成帧使用标志字节（0x7E）和字节填充，转义字节（0x7D）
- “无编号模式”（无连接无确认服务）用于承载 IP 数据包
- 使用校验和检测错误

# PPP 中的多路复用

虽然 PPP 是一种链路层协议，但它使用另一组协议来建立链路、验证相关方并传输网络层数据
为使 PPP 功能强大，定义了三组协议：链路控制协议（LCP）、两个身份验证协议（APs）和多个网络控制协议（NCPs）

# ADSL

广泛用于通过本地环路的宽带互联网
ADSL 从调制解调器（用户）到 DSLAM（ISP）
IP 数据包通过 PPP 和 AAL5/ATM 发送
PPP 数据通过 ATM 信元以 AAL5 帧发送：
- ATM 是一个链路层，使用短的固定大小的信元（53 字节）；每个单元都有一个虚电路标识符
- AAL5 是一种通过 ATM 发送数据包的格式
- PPP 帧转换为 AAL5 帧（PPPoA）

计算机网络