什么是数据链路

  • 数据链路层处理关注两台相邻（adjacent）机器实现可靠有效的完整信息块（称为帧）通信的算法，而不像物理层那样只关注单个比特传输
  • 沿着通信路径连接相邻节点的通信信道就是链路
  • 相邻指两台机器通过一条通信信道连接起来，通信信道在概念上就像一条线路（比如同轴电缆、电话线、无线信道）
  • 信道像一条线路的本质特性使得信道上传递的比特顺序与发送顺序完全相同

一个链路的性质（property）和局限性（limitation）

  • 基本属性
    • 信道上传递的比特顺序与发送顺序完全相同
  • 局限
    • 通信电路偶尔会产生错误
    • 只有有限的数据速率
    • 在比特发送时间和接收时间之间有一个非零延迟（propagation）

数据链路层设计问题

数据链路层使用物理层提供的服务在通信信道上发送和接收比特

数据链路层的要完成的功能

  • 向网络层提供一个定义良好的服务接口
  • 处理传输错误
  • 调节数据流，确保慢速的接收方不会被快速的发送方淹没

数据包和帧的关系

  • 数据链路层从网络层获得数据包，然后将这些数据包封装成帧（frame）以便传输
  • 每个帧包含一个帧头、一个有效载荷（用于存放数据包）、一个帧尾
  • 帧的管理构成了数据链路层工作的核心

可靠性（reliability）是网络的总目标

  • 这个目标的实现需要各层次紧密配合
  • 在数据链路层的错误控制（error control）和流量控制（flow control）等同样可以在传输层和其他协议中寻觅到类似的踪迹
  • 实际上在许多网络中，这些功能最常出现的地方是上层，数据链路层只要做很少的一点工作就已经“足够好”

提供给网络层的服务

数据链路层的功能是为网络层提供服务，最主要的服务是将数据从源机器的网络层传输到目标机器的网络层

  • 在源机器的网络层有一个实体（称为进程），它将一些比特交给数据链路层，要求传输到目标机器
  • 数据链路层的任务就是将这些比特传输给目标机器，然后再进一步交付给网络层

3 种可能的服务

无确认的无连接服务

  • 源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。采用这种服务，事先不需要建立逻辑连接，事后也不用释放逻辑连接。若由于线路的噪声而丢失了某一帧，数据链路层并不试图去检测或恢复丢帧
  • 错误率很低的场合，比如以太网
  • 实时通信，比如语音传输

有确认的无连接服务

  • 没有使用逻辑连接，但发送的每一帧都需要单独确认。发送方可以知道一个帧是否已经正确到达目的地。如果一个帧在制定的时间间隔内还没有到达，则发送方将再次发送该帧
  • 不可靠的（错误率高的）信道，比如无线系统（802.11 WiFi）

有确认的有连接服务

  • 确保发出的每个帧都会真正被接收方收到，还保证每个帧只被接收一次，并且所有的帧都将按正确的顺序被接收
  • 相当于为网络层进程提供了一个可靠的比特流
  • 长距离且不可靠的链路，比如卫星信道、长途电话网络

确认

确认（acknowledgement）只是一种优化手段

  • 数据链路层提供确认只是一种优化手段，永远不应该成为一种需求
  • 在很多情况下，恢复留给更高层
    • 例如，网络层可以发送一个数据包，然后等待该数据包被确认。如果在计时器超时之前，该数据包的确认还没有到来，那么发送方只要再次发送整个报文即可

这个策略的麻烦在于可能导致传输的低效率。链路层对帧通常有严格的长度限制，由硬件所决定；此外还有传播延迟。但网络层并不清楚这些参数，网络层可能发出了一个很大的数据包，该数据包被拆分并封装到多个帧中，且部分在传输中被丢失，那么这个数据包可能要花很长时间才能传到接收方

相反的，如果每个帧都单独确认和必要时重传，那么出现的差错就能更直接并且更快地被检测到

在可靠信道上，比如光纤，重量级数据链路协议的开销可能是不必要的；在无线信道上，由于信道内在的不可靠性，这种开销还是非常值得的

面向连接的服务

源机器和目标机器在传输任何数据之前要建立一个连接；连接上发送的每一帧都被编号，数据链路层确保发出的每个帧都会真正被接收方收到；它还保证每个帧只被接收一次，并且所有的帧都将按正确的顺序被接收

当使用面向连接的服务时，数据传输必须经过三个不同的阶段

  • 建立连接，双方初始化各种便利和计数器，这些变量和计数器记录了哪些帧已经接收到，哪些帧还没有接收到
  • 真正传输一个或多个数据帧
  • 连接被释放，所有的变量、缓冲区以及其他用于维护该连接的资源也随之被释放

成帧（frame）

对于数据链路层来说，通常的做法是将比特流拆分成多个离散的帧，为每个帧计算一个校验和，并将其放在帧中一起传输

如何使接收方发现一个新帧的开始，同时所使用的信道带宽要少

  • 字节计数法（Byte Count）
  • 字节填充的标志字节法（Flag bytes with byte stuffing）
  • 比特填充的标志比特法（Flag bits with bit stuffing）
  • 物理层编码违禁法（Physical layer coding Violations）

字节计数法

  • 利用头部中的一个字段来标识该帧中的字符数
  • 问题：可能因为一个传输错误而混淆

字节填充的标志字节法

  • 用标志字节（flag byte）作为帧的起始和结束分界符
  • 两个连续的标志字节代表了一帧的结束和下一帧的开始
  • 标志字节出现在数据中，在前面加入一个特殊的转义字节（ESC）
  • 转义字节也出现在数据中，也在前面加入一个特殊的转义字节（ESC）

比特填充的标志比特法

  • 只能使用 8 比特的字节
  • 帧的划分可以在比特级完成，因此帧可以包含由任意大小单元组成的二进制比特数
  • 每个帧的开始和结束由一个特殊的比特模式，01111110 或 0x7E 标记
    • 每当发送方数据链路层在数据中遇到连续五个 1，它便自动在输出的比特流中填入一个比特 0
    • 类似字节填充，在数据字段的标志字节之前插入一个转义字节到出境字符流中
    • 比特填充还确保了转换的最小密度，这将有助于物理层保持同步。USB（通用串行总线）采用了比特填充技术
    • 接收方看到5个连续入境比特 1，并且后面紧跟一个比特 0，它就自动删除比特 0
  • 比特填充和字符填充的一个副作用是帧的长度增加了

物理层编码违禁法

  • 冗余意味着一些信号将不会出现在常规数据中。例如，在 4B/5B 线性编码模式下，4 个数据位被映射成 5 个信号比特，通过这种方法确保线路上的信号有足够跳变。这意味着 32 个可能的信号中有 16 个是不会被使用的。我们可以利用这些保留信号来指示帧的开始和结束
  • 使用编码违禁法来区分帧的边界的优点在于，因为这些用做分界符的信号是保留不用的，所以很容易通过它们找到帧的开始和结束，而且不再需要填充数据

成帧方法的综合

许多数据链路层协议为安全起见综合使用了这些方法。以太网和 802.11 使用了共同的分界模式，即用一个定义良好的比特模式来标识一帧的开始，该比特模式称为前导码（preamble）

前导码之后是头的长度字段（即计数），这个字段将被用来定位帧的结束处

差错控制

如何确保所有的帧最终都被传递给目标机器的网络层，并且保持正确的顺序

  • 三种方法：确认（acknowledgment）、计时器（timer）、序号（sequence number）

确认

  • 接收方返回一些特殊的控制帧，在这些控制帧中，对于它所接收到的帧进行肯定或否定的确认（ACK / NACK）
  • 问题：控制帧被丢失

计时器

  • 当发送方发出一帧时，通常还要启动一个计时器。
  • 该计时器的超时值应该设置得足够长，以便保证在正常情况下该帧能够到达接收方，并且在接收方进行处理后再将确认返回到发送方
  • 在计时器超时前，该帧应该被正确地接收，并且确认帧也被传回来。此时计时器被取消
  • 如果帧或确认被丢失，则触发计时器，重传该帧

序号

  • 重传引入了重复帧（duplicate frames），为了区分重复帧，需要给发送出去的帧分配序号，这样接收方可以根据帧的序号来区分原始帧和重传帧
  • 用于序号的比特取决于任何时候可能重复的帧的数量

流量控制

流量控制处理发送方的速度以匹配接收方的速度。通常这是一个动态过程，因为接受速度取决于诸如负载、可用的缓存空间等变化因素

  • 目的是为了防止快速发送方淹没慢速接收方

基于反馈的流量控制（Feedback-based flow control）

  • 接收方给发送方返回消息，允许它发送更多的数据，或至少告诉发送方自己的情况
  • 可同时出现在链路层和更高的层次
  • 协议规定了发送方什么时候可以发送下一帧，通常在没有得到接收方许可（隐式或显示）之前禁止继续发送帧

基于速率的流量控制（Rate-based flow control）

  • 使用内置机制限制发送方传输数据的速率
  • never used in data link layer 仅在传输层可见

网络接口卡（NIC, Network Interface Cards）

差错检测和纠正

在数据中加入足够的冗余（redundancy）以便能够检测（并纠正）数据错误

针对错误处理由两种基本策略（都是在发送的数据中加入冗余信息）

  • 纠错码（error-correcting code）
    • 在每一个被发送的数据块中包含足够多的冗余信息，以便接收方能据此判断出被发送的数据是什么
    • 使用纠错码的技术通常也称为前向纠错（FEC, Forward Error Correction）
  • 检错码（error-detecting code）
    • 包含一些冗余信息，只能够让接收方推断出是否发生了错误，然后接收方可以请求发送方重传

传输错误非常普遍

  • 在高度可靠的信道上（比如光纤）：使用检错码
    • 偶尔发生错误时只需重传整个数据块
  • 错误发生频繁的信道上（比如无线链路）：使用纠错码
    • FEC 被用在有噪声的信道上，因为重传的数据本身也可能像第一次传输那样出错

错误模型

在第一种错误模型中，偶尔出现的极端热噪声快速淹没了信号，引起独立的单个比特错误

在第二种错误模型中，传输错误往往呈现突发性而不以单个的形式出现

  • 这种错误源自物理过程，比如无线信道上的一个深衰落（deep fade）、有线信道上的瞬态电气干扰、信号衰减（signal attenuation）

两种错误模型实际上造成的问题以及处理方式有不同的权衡

纠错码也会出现在物理层，特别是有噪声干扰的信道，同时还会出现在更高的层次，特别是实时流媒体应用和内容分发应用

检错码更经常被用在数据链路层、网络层和传输层

差错编码是应用的数学，应该从可靠的来源获得性质更优良的编码，而不是自己设计编码方案

纠错码

以下所有编码都将冗余信息加入到待发送的信息中

  • 海明码（Hamming codes）
  • 二进制卷积码（Binary convolutional codes）*
  • 里德所罗门码（Reed-Solomon codes）*
  • 低密度奇偶校验码（Low-Density Parity Check codes）*

一个帧由 $m$ 个数据位（即信息）和 $r$ 个冗余位（即校验位）组成

  • 在块码（block code）中，$r$ 个校验位是作为与之相关的 $m$ 个数据位的函数计算获得的，就好像在一张表中找到 $m$ 位数据对应的 $r$ 个校验位
  • 在系统码（systematic code）中，直接发送 $m$ 个数据位，然后发出 $r$ 个校验位，而不是在发送前对它们进行编码
  • 在线性码（line code）中，$r$ 个校验位是作为 $m$ 个数据位的线性函数被计算出来的。异或（XOR）或模 2 加是函数的流行选择，意味着编码过程可用诸如矩阵乘法或简单逻辑电路完成

令数据块的总长度为 n (n=m+r)，将此描述 (m,n) 码

一个包含了数据位和校验位的 $n$ 位单元称为码字（codeword）

码率（code rate）则定义为码字中不包含冗余部分所占的比例：$m/n$

海明距离（Hamming distance）

两个码字中不相同的位的个数称为海明距离

  • 如果两个码字的海明距离为 $d$，则需要 $d$ 个 1 位错误才能将一个码字转变成另一个码字
  • 为确定有多少个不同位，只需要 XOR 两个码字，并计算结果中 1 的个数

$$ 10001001 \oplus 10110001 = 00111000$$

  • XOR（$\oplus$）：相同为 0 ，不同为 1

给定计算校验位的算法，完全可以构建一个完整的合法码字列表，然后从这个列表中找出两个具有最小海明距离的码字。这个距离就是整个编码的海明距离

在大多数数据传输应用中，所有 $2^m$ 种可能的数据报文都是合法的；但是，根据校验位的计算方法，并非所有的 $2^n$ 种可能的码字都会被用到

块码的检错和纠错特性和它的海明距离有关

  • 检测 $d$ 个错误：需要海明距离为 $d+1$ 的编码方案
  • 纠正 $d$ 个错误：需要海明距离为 $2d+1$ 的编码方案

在给定 $m$ 的情况下，纠正单个错误所需要的校验位数的下界为：$ (m+r+1) \leq 2^r $

海明码（Hamming codes）

2 的幂次方为是校验位，其余位是数据位

  • (11,7) 海明码，7 个数据位，4 个校验位

若要查看数据 $k$ 位上的校验位，必须将 $k$ 改写成 2 的幂之和

  • 11 = 1+2+8 （校验 1、2、8 就可确定 11 位是否出错）
  • 校验结果不是全零，则意味着检测到了一个错误
  • 8、4、2、1 的校验结果是 0101，因此第 5 位发生了错误

海明码还被用在纠错存储器中

二进制卷积码（Binary convolutional codes）*

  • 唯一不属于块码的编码
  • 编码器处理一个输入位序列，并生成一个输出位序列
  • 编码器有内存，决定当前输出的以前输入位称为代码的余数长度（constraint length）
  • 卷积码由它们的速率和约束长度来标识
  • 已经被广泛应用于实际部署的网络中，GSM 移动电话系统、卫星通信、802.11
  • 软判决解码（soft-decision decoding）*
    • 带有一位不确定性的工作方法，把 -0.1V 看成很可能是 0，把 0.9V 看成很可能是 1
  • 硬判决解码（hardd-decision decoding）*
    • 在执行纠错之前就决定了每个位是 0/1

里德所罗门码（Reed-Solomon codes）*

  • 实际上被定义成一个在有限域上操作的多项式
  • 强大的纠错性能，尤其针对突发错误
  • 被用在 DSL、线缆上的数据通信、卫星通信、CD、DVD、蓝光光盘
  • 里德所罗门码结合卷积码，对单个错误和突发错误都有良好的保障

低密度奇偶校验码（LDPC, Low-Density Parity Check codes）*

  • 比较适用于大块数据，具有出色的纠错能力
  • 用于数字视频广播、万兆以太网、电力线网络、802.11

检错码

以下都是线性的系统块码

  • 奇偶（Parity）
  • 校验和（Checksums）
  • 循环冗余校验（CRC, Cyclic Redundancy Checks）

奇偶

单个奇偶校验位

  • 具有单个校验位的编码具有海明距离 2，因为任何 1 位错误都将使得码字的奇偶校验码出错，这意味着奇偶校验码可以检测出 1 位错误
    • 偶校验：1 的个数为偶数，校验位为 0
    • 奇校验：1 的个数为奇数，校验位为 0

交错奇偶校验位（interleaving）

  • 以不同于数据位发送的次序来计算校验位
    • 将 $n$ 列中的每列计算检验位，按 $k$ 行发送全部的数据，发送次序是从上到下发送每一行，行内数据通常按从左到右的次序发送
    • 在最后一行，发送 $n$ 个校验位，$k$ 行
  • 对 $nk$ 长度的数据块使用了 $n$ 个校验位就能检测出一个长度小于等于 $n$ 的突发错误
  • $n+1$ 的突发错误将被遗漏

校验和

校验和（checksum）指与信息相关的一组校验位，不管这些校验位是如何计算出来的

  • 一组奇偶校验位是校验和的一个例子

校验和通常放置在消息的末尾，作为求和功能的补充。通过对整个接收到的码字（包含数据位和校验和）进行求和计算就能检测出错误

  • 如果计算结果是零，则没有检测出错误

例子

  • 16 位的 Internet 校验和，作为 IP 协议的一部分用在所有 Internt 数据包中

循环冗余校验

数据链路层广泛使用，也称为多项式编码（polynomial code）

  • 允许我们确认正确收到帧/丢弃不正确的帧

检测

  • 所有一位错误
  • 所有两个独立的比特错误
  • 奇数个位发生错误
  • 长度小于 $r$ 的突发错误
  • 大多数突发错误

常用的三个生成多项式（generator）

位移寄存器

基本数据链路层协议

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

  • 由一个模块上的网络层递交给数据链路层的数据通过另一个模块上的数据链路层递交到网络层
  • 远程网络层对等体应接收发送方生成的相同的消息（例如，如果数据链路层添加了控制信息，则在消息传递到网络层之前必须删除标头信息）
  • 网络层可能会确保它发送的所有消息将被正确传送（例如，没有丢失/损坏）。任何错误可能会导致数据和控制帧丢失
  • 网络层可以按照发送的顺序将消息发送到远程对等体

关键假设

  • 物理层、数据链路层、网络层都是独立的进程，他们通过来回传递消息进行通信
  • 机器 A 希望用一个可靠的、面向连接的服务向机器 B 发送一个长数据流
  • 假定 A 要发送的数据总是已经准备好，不必等待数据生成
  • 假设机器不会崩溃（只处理通信错误）

帧序号总是在 $ [0, \rm MAX_{SEQ}]$ 范围内

乌托邦式的单工协议（Utopian Simplex Protocol）

假设

  • 数据只能单向传输（单工 simplex）
  • 发送方和接收方的网络层总是处于准备就绪状态
  • 数据处理的时间忽略不计
  • 可用的缓存空间无穷大
  • 数据链路层之间的通信信道永远不会损坏/丢失帧

无错信道上的单工停-等式协议（Simplex Stop and Wait Protocol for an Error-Free Channel）

假设

  • 不再假设接收方可以无限地快速处理入境数据
  • 发送方发送一帧，等待对方确认到达后才继续发送（停-等式协议，stop-and-wait）
  • 确认帧的内容（content）不重要
  • 通信信道不会出错，数据流量是单工的，从发送方传到接收方，但帧可以在两个方向上传送
    • 一个半双工的物理信道就足够了（一次只在一个方向上发送，流量严格交替）

有错信道上的单工停-等式协议（Simplex Stop-and-Wait Protocol for a Noisy Channel）

假设

  • 通信信道可能会出错，帧可能损坏/丢失
  • 简单的解决
    • 增加一个计时器（timer），在一定时间内没收到确认就重传该帧

特殊场景

  • A 传输帧 1
  • B 接收 A1
  • B 生成 ACK
  • ACK 丢失
  • A 的计时器超时，重传帧 1
  • B 收到重复的 A1（又递交给了它的网络层）

延迟也可能导致重复帧

序号（sequence number）

  • 让发送方在它所发送的每个帧的头部放上一个序号。然后接收方可以检查它所接收到的每个帧的序号，由此判断帧的新旧

序号的字段长度

  • 唯一不明确的地方在于一帧和它的前/后一帧，而不是它的前一帧和后一帧，因此1位序号就足够了
    • 0 变 1，1 变 0

ARQ

  • 在一个协议中，发送方在发送前移到下一个数据之前必须等待一个肯定确认，这样的协议称为自动重复请求（ARQ, Automatic Repeat reQuest），也称为带有重传的肯定确认（PAR, Positive Acknowledgement with Retransmission）
    • 只在一个方向上传输数据

效率问题（Efficiency Problem）

  • 停-等协议的问题是发送方只能有一个未确认帧
  • 例子，长肥网络（Long Fat Network）
    • Short frame length: 1000 bit frames
    • High bandwidth: 1 Mbps channel （satellite）
    • Long transit time: 270 ms propagation delay
    • 帧需要 1 ms 发送（$1000 {\rm bit}/10^6{\rm bps}=1 {\rm ms}$），利用传输延迟，发送方在 541 ms 之前都不会收到确认。信道利用率很差
    • 我们可以使用更大的帧，但是帧的大小被信道的错误率限制。帧越大，越可能在传输过程中损坏

性能评估（Performance Evaluation）

  • $F$ = frame size (bits)
  • $C$ = channel capacity (Bandwidth in bits/second)
  • $I$ = propagation delay plus processor service time (second)
  • Time to transmit a single frame = $F/C$
  • Total Delay = $2I$

在停-等协议中，信道在 $F/C$ 内忙碌，在 $2I$ 内空闲

如果 $F < 2CI$ 的话，信道利用率 = $F/(F+2CI) < 50%$

如果网络的带宽延迟积明显大于 $10^5$ 位（$\sim 12$ kB），则被认为是长肥网络（LFN）

滑动窗口协议

假设

  • 在两个方向上同时传输数据
    • 每个方向使用一条独立的链路进行单工数据传输
      • 逆向信道带宽几乎完全被浪费了
    • 使用同一条链路来传输两个方向上的数据
      • 使用帧头部的 kind 字段，区分数据帧和确认帧

捎带确认（piggybacking）

  • 暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术
  • 主要好处：更好地利用了信道的可用带宽
  • 问题：为捎带一个确认，数据链路层应该等网络层传递给它下一个数据包多久？

滑动窗口协议

  • 3 个双向协议
    • 1 位滑动窗口协议（A One-Bit Sliding Window Protocol）
    • 回退 N 协议（A Protocol Using Go Back N）
    • 选择重传协议（A Protocol Using Selective Repeat）
  • 不同
    • 效率（efficiency）、复杂性（complexity）、缓冲区需求（buffer requirements）

任何一个出境帧都包含一个序号，范围从 0 到某个最大值。序号的最大值通常是 $2^n-1$，这样序号证号可以填入到一个 $n$ 位的字段中

  • 停-等式窗口协议使用 $n = 1$，限制序号只能是 0 / 1

发送 / 接收窗口

  • 所有滑动窗口协议的本质是在任何时刻发送方总是维持着一组序号，分别对应于允许它发送的帧。称这些帧落在发送窗口（sending window）
  • 接收方也维持着一个接受窗口（receiving window），对应于一组允许它接收的帧
  • 发送窗口和接受窗口不必拥有同样的上下界，甚至也不必有同样的大小
    • 有些协议中，这两个窗口有固定的大小，但在其他协议中，它们可以随着帧的发送和接收而增大（grow）或者缩小（shrink）

滑动窗口协议的例子

停等式滑动窗口协议

  • 最大序号（MaxSeq）= $2^n - 1, n \geq 1 $
  • 窗口大小（window size）= 1

协议有效

  • 所有帧以正确的顺序传送
  • 易于实现
  • 只需要很少的缓冲空间
  • 停-等式导致信道利用率差

大小为 1 的滑动窗口

  • 3 位序号，$[0, 7]$
  • 发送方窗口
    • 由于当前在发送方窗口内的帧最终有可能在传输过程中丢失或损坏，所以发送方必须在内存中保存所有这些帧，以便满足可能的重传需要
    • 因此，如果最大的窗口尺寸为 $n$，则发送方需要 $n$ 个缓冲区来存放未被确认的帧。如果窗口在某个时候达到了它的最大尺寸，则发送方的数据链路层必须强行关闭网络层，直到有一个缓冲区空出来为止
  • 接收方窗口
    • 接收方的数据链路层窗口对应于它可以接收的帧。任何落在窗口内的帧被放入接收方的缓冲区；任何落在窗口外面的帧都将被丢弃
    • 当收到一个帧，且其序号等于窗口下边界时，接收方将它传递给网络层并将整个窗口向前移动 1 个位置
    • 所有情况下，接收方都要生成一个确认并返回给发送方
    • 窗口大小为 1 意味着数据链路层只能按顺序接收帧，对于大一点的窗口就不成立

1 位滑动窗口协议

确认字段包含了最后接收到的正确帧的序号

特殊情况

  • （序号, 确认, 包号）
  • *表示网络层接受了一个包
  • （a）正常情况，每一帧到来后都带给网络层一个新的数据包，没有任何重复
  • （b）异常情况，即使没有传输错误，也会有一半的帧是重复的
    • B 在发送自己的帧之前等待 A 的第一帧

回退N协议（go back n）

管道化策略（Pipelining Strategies）

允许多个帧同时传输

  • 发送方不等待每个帧被确认。相反，它发送了许多帧，并假定它们将到达。每帧仍然必须被确认
  • 提供更高效的传输带宽使用，但错误处理更为复杂

问题和解决

问题

  • 如果发送了 20 个帧，第 2 帧发生了错误
    • 3~20 帧如何处理？重传（retransmission）？

接收方窗口大小的策略

  • 回退 N（go back n）
  • 选则重传（selective repeat）

（a）回退 n —— 接收窗口大小为 1

  • 损坏帧/丢失序号：丢弃后续帧
  • 丢弃的帧没有确认返回

（b）回退 n 帧的情形

  • 接收方的窗口比较大
  • 发送方意识到问题，继续发送后续的帧直到 2 号帧的计时器超时
  • 然后退回到 2 号帧，从这里重新发送 2 号、3 号、4 号帧等

选则重传 —— 接收窗口大于 1

  • 将坏帧丢弃，接收并缓存后续的好帧
  • 只确认顺序收到的最后一个帧
  • 否定确认（NAK, negative acknowledgement）: 触发该帧的重传，无需等待计时器超时

带宽与缓存

这两种不同方法恰好是带宽使用效率和数据链路层缓存空间之间的权衡

  • 无论哪种情况，发送方都需要缓冲区空间，直到收到确认后才能释放
  • 为已发送的每个未被确认的帧设置一个计时器
  • 必须能够启用 / 禁用网络层，因为如果有许多未被确认的帧，可能无法处理更多的发送数据
    • 组织网络层向下传数据，因为缓冲区已满

最大序号与发送窗口大小

任何时候，可以发送的帧的最大个数不能等同于序号空间大小

  • 对回退 n 协议，可以发送的帧最多为 $\rm MAX_{SEQ}$ 个
    • 发送窗口大小为 $2^n - 1$

累计确认（cumulative acknowledgement）

当 $n$ 号帧的确认到达，$n-1$ 号帧、$n-2$ 号帧等都会自动被确认

计时器（timer）

所有未发生的超时时间构成一个链表

  • 指向下一个超时值
  • 超时对应的帧
  • 剩余滴答数

选择重传协议（selective repeat）

允许接收方接收并缓存坏帧或丢失帧后面的所有好帧

发送 / 接收窗口

  • 发送方和接收方各自维持一个窗口，该窗口分别包含可发送或已发送但未被确认的和可接受的序号
  • 发送方的窗口大小从 0 开始，可以增大到某一预设的值
  • 接收方的窗口大小总是固定不变，等于预先设定的最大值
    • 接收方为其窗口内的每个序号保留一个缓冲区
    • 帧只能被保存在数据链路层中，直到所有序号比它小的帧都已经按顺序递交给网络层后，它才能被传递给网络层

非顺序接收

  • （a）窗口大小为 7 的初始情形
  • （b）发出 7 个帧并接收 7 个帧，但未确认
  • （c）窗口大小为 4 的初始情形
  • （d）发出 4 个帧并接收 4 个帧，但未确认

问题的本质在于：

  • 当接收方向前移动它的窗口后，新的有效序号范围与老的序号范围有重叠
  • 因此，后续的帧可能是重复的帧（如果确认丢失），也可能是新的帧（确认正确接收）

最大序号与接收窗口大小

  • 选择重传的最大窗口大小是 ${\rm(MAX_{SEQ}}+1)/2$
  • 接收窗口大小 $(2^n-1 + 1)/2$

窗口大小

缓冲区与计时器

接收方所需的缓冲区数量等于窗口的大小

需要的计时器数量等于缓冲区的数量

  • 每个缓冲区都有一个相关联的计时器。当计时器超时，缓冲区的内容就要被重传

计时器时间

  • 在某些情形下，从一帧发送出去开始算起，到该帧经传播抵达目的地、在那里被处理，然后它的确认被传回来，整个过程所需要的时间（几乎）是个常数
    • 发送方可以把计时器的事件设置为恰好略大于正常情况下从发送一帧到接收到其确认之间的时间间隔
    • NAK 没什么作用
  • 其他情况下这段时间的变化非常大
    • 逆向流量零散/没有逆向流量
    • NAK 可以加快丢失帧或损坏帧的重传速度
    • 可变时间？

逆向流量很轻，确认会被延迟

  • 依赖反方向上的数据帧来捎带确认信息
  • 如果在一个方向上有很大的流量，而另一个方向上根本没有流量，那么当发送方的窗口达到最大值后协议将被阻塞
  • 解决
    • 辅助计时器，超时则发送单独的确认帧

更加有效的策略来处理错误

  • 否定确认（NAK），实际上是一个重传请求，指定了要重传的帧
    • 接收到一个受损的帧
    • 到达的帧并非期望的（可能出现丢帧）
  • 如果 NAK 丢失 / 损坏，不会有实质性的伤害，因为发送方最终会超时，并重传帧

性能（performance）

数据链路层协议实例

通过广域网中的 SONET 光纤链路发送数据包，这些链路被广泛用于连接一个 ISP 网络中位于不同位置的路由器，并构成了通信网络的骨干网，其中包括电话系统

运行在 Internet 边缘的电话网络本地回路上的 ADSL 链路，这些链路把成千上百的个人和企业连接到 Internet 上

SONET上的数据包（Packet over SONET）

SONET 是物理层协议

  • IP （Internet Protocol）
  • 点到点协议（PPP, Point to Point Protocol）
  • SONET（Synchronous Optical Network）

PPP 特性

单独的帧，错误检测

  • 一种成帧方法。它可以毫无歧义地区分出一帧的结束和下一帧的开始

链路控制协议（LCP, Link Control Protocol）

  • 一个链路控制协议。它可用于启动线路、测试线路、协商参数，以及当线路不再需要时关闭线路

网络控制协议（NCP, Network Control Protocol）

  • 一种协商网络层选择的方式。协商方式独立于网络层协议，所选择的方法是针对每一种支持的网络层都有一个不同的网络控制协议

PPP 和 HDLC

  • PPP 帧格式的选择类似 HDLC 帧格式（高级数据链路控制协议, High-level Data Link Control），但是是面向字节而不是面向比特的
  • PPP 默认不提供可靠的数据传输（LCP 的一部分），实际上很少使用；HDLC 提供了可靠的数据传输

点到点通信

与外部世界的所有连接都通过一个或两个具有点到点租用线路的路由器连接到远程路由器

PPP 帧格式

  • HDLC 标志字节 0x7E（01111110）
  • 地址（address）字段（11111111），表示所有站点都接收该帧
  • 控制（control）字段（00000011），默认值表示无编号帧
  • 协议（protocol）字段
    • 通告 payload 字段中包含什么类型的数据包
    • 以 0 开始的编码定义为 IPv4、IPv6 以及其他可能用到的网络层协议，比如 IPX 和 AppleTalk
    • 以 1 开始的编码被用于 PPP 配置协议，包括 LCP 和针对每个网络层协议而设置的不同 NCP
    • 默认大小为 2 个字节，可以通过 LCP 协商减少到 1 字节
  • 有效载荷（payload）字段，可变长度，无 LCP 协商采用默认长度 1500，必要时填充技术
  • 校验和（checksum）字段，通常占 2 字节，但可以协商使用 4 字节

状态机

PPP 链路建立到释放

  • 链路的初始状态为死（DEAD）
  • 一旦进入打开（OPEN）状态，双方就可以进行数据传输。IP 数据包被承载在 PPP 帧中通过 SONET 线路传输

对称数字用户线（ADSL, （Asymmetric Digital Subscriber Loop）

以 Mbps 速率将百万家庭用户连接到Internrt上，使用的是与普通老式电话服务相同的本地回路

典型的 ADSL 设备配置

ADSL 协议栈

  • ADSL 物理层，基于正交频分复用（OFDM）
  • 异步传输模式（ATM, Asynchronous Transfer Mode），是一种链路层
    • 面向连接
    • 映射成一系列信元（cell），映射过程称为分段（segmentation）和重组（reassembly）
  • ATM 适应层 5（AAL5, ATM Adaptation Layer 5）

运载 PPP 数据的 AAL5 帧

总结

  1. 将原始比特流转换为帧流：字节计数（character count）、比特填充（bit stuffing）、字节填充（character stuffing）
  2. 错误检测和纠正：奇偶校验（parity）、校验和（checksum）、CRC
  3. 流量控制：保持发送方和接收方的速度
  4. 数据链路层协议：滑动窗口（sliding window）
  5. 规范和验证：正确性（correctness）、完整性（completeness）、可达性分析（reachability analysis）、失败案例（failure cases）