Chapter 3 数据链路层
数据链路层的设计问题
数据链路层在协议栈中的位置
- 向下：利用物理层提供的位流服务
- 向上：向网络层提供明确的服务接口
数据链路层的功能
- 成帧：将比特流划分成“帧”的主要目的是为了检测和纠正物理层在比特传输中可能出现的错误，数据链路层功能需借助“帧”的各个域来实现
- 差错控制：处理传输中出现的差错，如位错误、丢失等
- 流量控制：确保发送方的发送速率，不大于接收方的处理速率
数据链路层提供的服务
成帧
分组与帧的关系
成帧的方式
字节计数法
用于无差错传输的情形
当某个计数字节出错时
帧的边界被破坏，导致一连串的错误。
带字节填充的定界符法
- 定界符 FLAG
- 转移字节 ESC
带比特填充的定界符法
物理层编码违例
核心思想：选择的定界符不会在数据部分出现
差错控制
链路层存在的问题
信道的噪声导致数据传输问题：
- 差错：
- 丢失
- 乱序
- 重复
解决方案
差错检测与纠正、确认重传
- 确认
- 定时器
- 顺序号
流量控制
链路层存在的另一个问题
接收方的处理速率是有限的：
- 接收方的接收缓冲区溢出
解决方案
- 基于反馈的流量控制
- 基于速率的流量控制
差错检测和纠正
概述
-
如何解决信道传输差错问题 增加冗余信息（或称校验信息）的策略
-
目标
保证一定差错检测和纠错能力的前提下，减少冗余信息量
-
考虑的问题
-
信道的特征和传输需求
- 冗余信息的计算方法、携带的冗余信息量
-
计算的复杂度
-
主要策略
-
检错码：在被发送的数据块中，包含一些冗余信息，但这些信息只能使接收方推断是否发生错误，但不能推断哪位发生错误，接收方可以请求发送方重传数据
- 纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误 (定位出错的位置)
问题：纠错编码的最小码距与其检错和纠错能力
典型的检错码
奇偶校验
- 1位奇偶校验：增加1位校验位，可以检查奇数位错误
校验和
主要用于 TCP/IP 体系中的网络层和传输层
-
发送方：进行 16 位二进制补码求和运算，计算结果取反，随数据一同发送
-
overflow 的那位，0 扩展，再加进去
- 接收方：进行 16 位二进制补码求和运算（包括校验和），结果非全 1，则检测到错误
循环冗余校验 CRC
CRC 校验码计算方法
CRC 校验码计算示例
四个国际标准生成多项式
典型的纠错码
设计纠错码
海明码
目标：以奇偶校验为基础，如何找到出错位置，提供 1 位纠错能力
校验位：2 的幂次方位，记为 p1，p2，p4，p8
每个校验位对数据位的子集做校验，缩小定位错误的范围
海明码缺省为偶校验：
- 海明码纠正的实现过程
- 使用海明码纠正突发错误
Reed-Solomon code (RS码)
以有限域运算为基础，提供多位纠错能力
基本的数据链路层协议
定义与假设
物理层、数据链路层和网络层的实现
关键假设
- 分层进程独立假设
- 提供可靠服务假设
- 只处理通信错误假设