Skip to content

Chapter 3 数据链路层

数据链路层的设计问题

数据链路层在协议栈中的位置

  • 向下：利用物理层提供的位流服务
  • 向上：向网络层提供明确的服务接口

image-20241009104005888

数据链路层的功能

  • 成帧：将比特流划分成“帧”的主要目的是为了检测和纠正物理层在比特传输中可能出现的错误，数据链路层功能需借助“帧”的各个域来实现
  • 差错控制：处理传输中出现的差错，如位错误、丢失等
  • 流量控制：确保发送方的发送速率，不大于接收方的处理速率

数据链路层提供的服务

image-20241009104551764

成帧

分组与帧的关系

image-20241009105651543

成帧的方式

字节计数法

用于无差错传输的情形

image-20241009111132558

当某个计数字节出错时

image-20241009111155406

帧的边界被破坏，导致一连串的错误。

带字节填充的定界符法
  • 定界符 FLAG
  • 转移字节 ESC
带比特填充的定界符法
物理层编码违例

核心思想：选择的定界符不会在数据部分出现

差错控制

链路层存在的问题

信道的噪声导致数据传输问题：

  • 差错：
  • 丢失
  • 乱序
  • 重复

解决方案

差错检测与纠正、确认重传

  • 确认
  • 定时器
  • 顺序号

流量控制

链路层存在的另一个问题

接收方的处理速率是有限的：

  • 接收方的接收缓冲区溢出

解决方案

  • 基于反馈的流量控制
  • 基于速率的流量控制

差错检测和纠正

概述

  • 如何解决信道传输差错问题 增加冗余信息（或称校验信息）的策略

  • 目标

保证一定差错检测和纠错能力的前提下，减少冗余信息量

  • 考虑的问题

  • 信道的特征和传输需求

  • 冗余信息的计算方法、携带的冗余信息量

  • 计算的复杂度

  • 主要策略

  • 检错码：在被发送的数据块中，包含一些冗余信息，但这些信息只能使接收方推断是否发生错误，但不能推断哪位发生错误，接收方可以请求发送方重传数据

  • 纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误 (定位出错的位置)

问题：纠错编码的最小码距与其检错和纠错能力

典型的检错码

奇偶校验

  • 1位奇偶校验：增加1位校验位，可以检查奇数位错误

image-20241009114706568

校验和

主要用于 TCP/IP 体系中的网络层和传输层

  • 发送方：进行 16 位二进制补码求和运算，计算结果取反，随数据一同发送

  • overflow 的那位，0 扩展，再加进去

image-20241009115051876

  • 接收方：进行 16 位二进制补码求和运算（包括校验和），结果非全 1，则检测到错误

image-20241009115105403

循环冗余校验 CRC

CRC 校验码计算方法

image-20241009115237383

CRC 校验码计算示例

image-20241009115353333

四个国际标准生成多项式

image-20241009115547178

典型的纠错码

设计纠错码

海明码

目标：以奇偶校验为基础，如何找到出错位置，提供 1 位纠错能力

校验位：2 的幂次方位，记为 p1，p2，p4，p8

每个校验位对数据位的子集做校验，缩小定位错误的范围

海明码缺省为偶校验：

image-20241009120850892

  • 海明码纠正的实现过程

image-20241009121323638

  • 使用海明码纠正突发错误

image-20241009121347657

Reed-Solomon code (RS码)

以有限域运算为基础，提供多位纠错能力

基本的数据链路层协议

定义与假设

物理层、数据链路层和网络层的实现

关键假设

  • 分层进程独立假设
  • 提供可靠服务假设
  • 只处理通信错误假设

基本的协议定义

乌托邦式单工协议

无错信道单工停止-等待协议

有错信道单工停止-等待协议

image-20241016110221746