The Data Link Layer

Protocols for achieving reliable（差错控制） and efficient（流量控制） communication 考纲： 3.1.2 成帧（位填充、字节填充） 3.2 错误检测和纠正（CRC） 3.3 基本数据链路协议（停等协议） 3.4 滑动窗口协议（捎带确认、发送窗口、接收窗口、一位滑动窗口协议、回退N、选择性重发协议）

3.1 数据链路层的设计问题

数据链路层使用物理层提供的服务在通信信道上发送和接收比特，它要完成的功能：

  • 向网络层提供一个定义良好的服务接口
  • 处理传输错误
    • 差错控制
      • 发现并解决帧内部的"位错"
        • 数据正确性
        • 确保所有的帧都被递交给目标机器上的网络层exactly once，并且保证正确的顺序
    • 可靠传输：发现并解决“帧错”
  • 调节数据流，确保慢速的接收方不会被快速的发送方淹没（流量控制）
    • 流量控制解决的问题：如果发送方发送帧的速度超过了接收方能够接收这些帧的速度，发送方如何处理
      • 基于反馈的流量控制Feedback-based flow control
        • 接收方给发送发返回信息，允许它发送更多的数据，或者至少告诉发送方自己的情况怎么样
      • 基于速率的流量控制rate-based flow control
        • 仅在传输层的一部分可见

数据链路层从网络层获得数据包，然后将这些数据包封装成帧（frame）以便传输，每个帧包括帧头+净荷域（分组，Payload）+帧尾

  • 帧的长度受硬件的限制
  • 一个分组可能要分成多个帧 image.png image.png

3.1.1 提供给网络层的服务

功能：为网络层提供服务，最主要的服务是将数据从源机器的网络层传输到目标机器的网络层 一般情况下，数据链路层通常提供以下3种可能的服务：

  • 无确认的无连接服务 Unacknowledged connectionless service
    • 源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认
    • 应用场景
      • 错误率低的场合，差错恢复可以留给上层完成
      • 实时通信
      • LAN➡️以太网
  • 有确认的无连接服务 Acknowledged connectionless service
    • 数据链路层仍然没有使用逻辑连接，但其发送的每一帧都需要单独确认，这样发送方可知道一个帧是否已经正确到达目的地。如果一个帧在指定的时间间隔内还没有到达，则发送方再次发送该帧
    • 适用于不可靠的信道：无线系统、local loop、802.11(Wifi)
  • 有确认的有连接服务 Acknowledged connection-oriented service
    • 源机器和目标机器在传输任何数据之前要建立一个连接。连接上发送的每一帧都被编号，数据链路层确保发出的每个帧的会真正被接收方收到。它还保证每个帧只被接收一次，并且所有的帧都按正确的顺序被接收
    • 向网络层进程提供一个可靠的位流/比特流
    • 适用于长距离且不可靠的链路：卫星信道/长途电话电路
    • 占用网络资源

3.1.2 成帧Framing

解决的两个问题：

  1. 帧的边界问题
  2. 帧的透明传输（填充）问题 总结：成帧framing解决了“标识每一帧的起始和结束位置”的问题

Framing method (4种成帧的方法)

  1. 字符计数法（Character count) 思想：利用头部中的一个字段来标识该帧中的字符数，当接收方的数据链路层看到字符计数值时，它就知道后面跟着多少个字节，因此也就知道该帧该在哪里结束 image.png 问题：计数值有可能因为一个错误而被弄混，接收方会失去同步，再也不可能找到下一帧的正确起始位置。即使校验和不正确，接受方知道该帧已经被损坏，它仍然无法知道下一帧从哪里开始。在这种情况下，发送方也无法重传，因为接收方本身并不知道应该跳过多少个字节才能到达重传的开始处

  2. 字节填充的标志字节法（Flag Bytes with byte stuffing） 思想：让每个帧用一些特殊的字节作为开始和结束，这些特殊的字节通常都相同，称为标志字节（flag byte），作为帧的起始和结束标志符 image.png 两个连续的标志字节代表了一帧的结束和下一帧的开始，因此如果接收方丢失了同步，只需搜索两个标志字节就能找到当前帧的结束和下一帧的开始位置 需要解决的问题：当标志字节出现在数据中时，往往会严重干扰到帧的分界 解决方案：字节填充 byte stuffing

  • 发送方的数据链路层在数据中出现的每个标志字节的前面插入一个特殊的转义字节（ESC），只要看它数据中标志字节的前面有没有转义字节，就可以把作为帧分界符的标志字节与数据中出现的标志字节区分开来
  • 接收方的数据链路层在将数据传递给网络层之前必须先删除转义字节
  • 若转义字节也出现在数据中，则同样使用字节填充技术，用一个转义字节来填充，在接收方第一个转义字节被删除，留下紧跟在它后面的数据字节 image.png tips： 还原：看到ESC删除，保留其后的数据 填充：看到ESC、FLAG在其后添加ESC 字节填充法的最大开销（填充数据与原始数据的比值）：100% 开销大
  1. 比特填充的标志比特法/含位填充的首尾界符法（Starting and ending flags,with bit stuffing） 思想：
  • 考虑了字节填充的缺点为：只能使用8比特的字节
  • 比特填充，帧的划分在比特级完成，因而帧可以包含由任意大小的单元（而不是只能以8比特为单元）组成的二进制比特数 规则：每个帧的开始和结束由一个特殊的比特模式：01111110或十六进制0x7E标记，这种模式是一个标记字节
  • 每当发送方的数据链路层在数据中遇到连续5个1，它便自动在输出的比特流中填入一个比特0
  • 当接收方看到5个连续入境的比特1，并且后面紧跟了一个比特0，就自动剔除比特0 image.png
  1. 物理层编码违例法（Physical layer coding violation）
  • Bit “1” 高-低电平对
  • Bit “0” 低-高电平对,
  • 帧的边界（高-高，低-低） 优点：用作分界符的信号是保留不用的，所以很容易通过它们找到帧的开始和结束，而且不需要填充数据

3.2 差错检测和纠正

纠错码

Error-Correcting Codes （纠错码）

检错码

Error-Detecting Codes（检错码）

//见pad

流量控制与可靠传输机制

一个新的视角看待数据链路层的协议

image.png

停止-等待协议（S-W）

王道网课

  1. 滑动窗口机制 发送窗口WT=1W_T=1 接收窗口WR=1W_R=1

  2. 确认机制：若接收方收到i号帧，且没有检测出差错，需要给发送方返回确认帧ACK_i 一些概念： image.png

  3. 重传机制:若发送方超时未收到ACK_i,则重传i号帧 超时重传机制：发出一个帧后，发送方需要启动“计时器”，若计时器超时，就会自动重传

  4. 帧编号

    • 仅需1bit给帧进行"编号"
      • 给帧编号可以判别"重复帧"
      • 接收窗口和发送窗口的距离不超过1 要求：WT+WR≤2n{W_T+W_R} \leq 2^n

  5. S-W实现流量控制 只有接收窗口向后滑动，同时给发送窗口发送ACK，发送窗口才会跟着向后滑动 数据的接受方控制了发送窗口向后滑动的速度

  6. S-W实现可靠传输

  • 数据帧丢失：此时接受方在计时器超时还未收到数据
    • 若计时器超时，就自动重传
    • 重传帧时，重置计时器
  • 确认帧丢失：此时接收方收到重复帧
    • 帧序号落在接收窗口外
      • 丢弃重复帧
      • 返回重复帧的ACK
  • 数据帧有差错：接收方收到数据帧，但检测出差错
    • 将此帧丢弃且不返回ACK
    • 超时未收到ACK，自动重传

为什么S-W不存在“数据帧失序问题” 接收窗口大小为1，接收窗口只会按顺序接收各个数据帧

ppt

实用的停止等待协议Stop-Wait可能出现的四种情况：

  • 正常帧情况
  • 数据帧出错
  • 数据帧丢失
  • 确认帧丢失 image.png

An Unrestricted Simplex Protocol（一种无限制的单工协议/乌托邦式的单工协议） 不需要考虑任何出错的情况 假设条件：

  • 数据只能单向传输
  • 数据链路层之间的通信信道永远不会损坏或者丢失帧
  • 两端的网络层就绪
  • 数据处理时间忽略不计
  • 缓冲区空间无穷大/接收能力无限大 协议由两个单独的过程组成，一个发送过程，一个接收过程
  • 发送过程运行在源机器的数据链路层上
    • 无限的while循环，尽可能快速地把数据放在线路上
      • 从网络层获取一个数据包
      • 利用变量s构造出一个出境帧
      • 通过物理层将发送该帧
  • 接收过程运行在目标机器的数据链路层上
    • 开始等待某些事情的发生
    • 将新到达的帧从硬件缓冲区中删除并放入新变量r中以便后续接收方的代码访问该层
    • 该帧的数据部分传递到网络层

A Simplex Stop-and-Wait Protocol（一种单工的停-等协议） 假设条件：

  • 数据只能单向传输
  • 发送方网络层一直有无限的数据要发送
  • 信道不会出错，从不损坏或丢失帧 抛弃的约束条件：
  • ！！！接收方网络层一直可以接收（需要处理时间）,接收方缓冲空间无限大
  • 讨论：如何避免发送方快速发送，淹没接收方的情况
    • 解决方案：确认机制➡️接收方发送一个响应帧，通知发送方发送下一帧/让接收方给发送发提供反馈信息。接收方将数据包传递给网络层之后给发送方返回一个小的哑帧➡️给发送方一个许可，允许它发送下一帧 发送方首先从网络层获取一个数据包，用它构造一帧，然后发送出去。但是发送方在开始下一轮循环从网络层获取下一个数据包之前必须等待确认帧的到来。 接收方将数据包递交给网络层之后，在进入下一轮循环之前，要先给发送方返回一个确认帧

A Simplex Protocol for a Noisy Channel（有噪声信道的单工协议） 假设条件：

  • 将信道变成有噪音的信道/通信信道可能会出错
    • 数据出错
    • 丢包
  • 解决方案：
    • 增加一个计时器。发送方发出一帧，接收方只有在正确接收到数据之后才返回一个确认帧。如果到达接收方的是一个已经损坏的帧，则将它丢弃/如果数据帧丢失，接收方收不到数据。经过一段时间发送方超时，于是再次发送
    • 增加序列号。让发送方在它发送的每个帧的头部放上一个序号。然后接收方可以检查它接收到的每个帧的序号，由此判断是否为重复帧（1位，0，1 循环使用）
  • 一个肯定确认的重传协议(PAR: Positive Acknowledgement with Retransmission) 或自动重传协议 ARQ: Automatic Repeat reQuest //Timeout image.png

停等协议的补充要点：

  • 实用的 CRC 检验器都是用硬件完成的
  • CRC 检验器能够自动丢弃检测到的出错帧。因此所谓的“丢弃出错帧”，对上层软件或用户来说都是感觉不到的

停止等待协议的效率问题：

  • 信道利用率很低，传播延迟较长
    • 只能有一个没有被确认的帧在发送中 一种提高效率的方法：使用更大的帧
  • 但是帧的最大长度受到信道比特错误率（BER，Bit Error Ratio）的限制，帧越大，在传输中出错的概率越高，将导致更多的重传

滑动窗口协议

Sliding Window Protocols 双向协议

捎带确认piggybacking

全双工数据传输且使用同一条链路来传输两个方向上的数据的进一步优化： 捎带确认：暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术

  • 当到达一个数据帧时，接收方并不是立即发送一个单独的控制帧，而是抑制自己开始等待，直到网络层传递给它下一个要发送的数据包。然后确认信息被附加在往外发送的数据帧上（使用帧头的ack） 优点：
  • 提高了信道的利用率
  • 更好地利用了信道的可用带宽

滑动窗口机制

发送窗口WTW_T:发送方当前允许发送的帧

  • 发送方窗口内的序号代表了那些可以被发送或者是已经被发送但是还没有确认的帧 接收窗口WRW_R：接收方当前允许接受的帧 image.png

由接收方通过“确认机制”控制发送方的窗口向前滑动，从而实现“流量控制” image.png

1位滑动窗口协议

A One-Bit Sliding Window Protocol

在一般情况下，两个数据链路层中的某一个首先开始发送第一帧，初始启动的机器从它的网络层获取第一个数据包，然后根据该数据包创建一帧，并将它发送出去，当该帧到达目的地，接收方的数据链路层检查该帧看它是否为重复帧，如果该帧正是接收方所期望的，则将它传给网络层，并且接收方的窗口向前滑动

确认字段包含了最后接收到的正确帧的序号，如果该序号与发送方当前试图发送的帧的序号一致，则发送方知道存储在buffer中的帧已经处理完毕，于是可以从网络层中获取写一个数据包。如果序号不一致，则它必须继续重复发送同一帧 image.png 出现的问题： 若A和B同时发起通信，则它们的第一帧交错，此时会出现有一半的帧是重复的，类似的情况发生在过早超时的情况，即使有一方明显地首先开始传输也会发生这样的情形,严重浪费了宝贵带宽 image.png

回退N协议GNB

A Protocol Using Go Back N 回退：原本已经发送的帧回退回去重新发送

  1. 滑动窗口机制 发送窗口WT>1W_T \gt 1 接收窗口WR=1W_R=1 image.png

  2. 确认机制 关于确认帧：接收方可以累积确认，即连续收到多个数据帧时，可以仅返回最后一个帧的ACK

  • ACK_i:表示接收方已收到i号帧及其之前的所有帧

  1. 重传机制 关于超时重传：若发送方超时未收到ACK_i,则重传i号帧及其之后的所有帧

  2. 帧编号 要求：WT+WR≤2n{W_T+W_R} \leq 2^n 为了支持以上机制正确允许，至少需要用nbit给帧进行编号 image.png

  3. GBN的特殊规则

  4. 异常情况处理

    • 数据帧的丢失/检测出差错丢弃
      • 收到正确帧的窗口落在接收窗口之外，直接丢弃
      • 当收到接收窗口之外的帧时，返回目前已经正确接收的最后一个帧的ACK
      • 此时若i号帧超时，则需要重传i号帧及其后续所有帧
    • 确认帧丢失
      • 此时第一个被发送的帧i超时，需要重传i号帧及其后续所有帧
      • 当接收方收到一个非法帧时，返回目前已接收的最后一个正确帧ACK

  5. 流量控制 发送方给接送方发送的速率被接收方所控制

  6. 要点

  • 收到一个非法帧时，接收方会将此帧丢弃并返回目前已接收的最后一个正确帧的ACK_i，以提醒发送方后退回(i+1)mod  2n(i+1)\mod2^n 号帧重新发送
    • 非法帧：落在接收窗口之外的帧/检查出错的帧
  • 缺点
    • 如果接收方接收帧的速度很慢，或在信道误码率很高的情况下，可能会导致发送方的发送进度经常需要 “后退”，传输效率低下

选择重传协议 SR

A Sliding Window Protocol Using Selective Repeat

  1. 滑动窗口机制

    • 发送窗口WT>1W_T \gt 1 接收窗口WR>1W_R \gt 1
    • 接收窗口不能大于发送窗口WR≤WTW_R \leq W_T
      • 保证窗口的利用率
      • 实际情况下，通常取WR=WTW_R = W_T

  2. 确认机制

    • 确认帧：接收方收到i号帧，且没有检测出差错，需要给发送方返回确认帧ACK_i
    • 否认帧：接收方收到i号帧，但检测出i号帧有差错，需要丢弃该帧，并给发送方返回否认帧NAK_i

SR协议不支持累计确认，必须一帧一帧确认

  1. 重传机制

    • 超时重传：若发送方超时未收到ACK_i，则重传i号帧
    • 请求重传：若发送方收到否认帧NAK_i，则重传i号帧

  2. 帧编号 要求：WT+WR≤2n{W_T+W_R} \leq 2^n 为了支持以上机制正确允许，至少需要用nbit给帧进行编号

  3. 异常情况处理

    • 数据帧的丢失
      • 超时重传机制：每个帧被发出时设置计时器，若仅i号帧超时，仅需选择重传i号帧，并重置计时器
    • 数据帧差错而被丢弃
      • 请求重传机制：如果接收方收到一个有差错的帧，将此帧丢弃，并返回对应的否认帧NAK_i，主动请求发送方重传i号帧
      • 返回出错数据对应序号的否认帧，主动请求发送方重传对应帧
      • 发送方在计时器超时前即可收到对应的否认帧，可立即触发重传，并重置计时器
    • 确认帧丢失
      • 超时重传，接收方收到重复帧（接收窗口之外），每收到重复帧，接收方就会给发送方发送对应的ACK

描述回退N和选择重传协议的描述并比较优缺点： 回退N：接收方只需要简单丢弃所有到达的后续帧，而且针对这些这些丢弃的帧不返回确认，这种策略对应于接收窗口为1。最终发送方将超时，并且按照顺序重传所有未被确认的帧，从那个受损或者被丢失的帧开始 优点：接收方对缓存空间要求不高 缺点：如果接收方接收帧的速度很慢，或在信道误码率很高的情况下，可能会导致发送方的发送进度经常需要 “后退”，传输效率低下，浪费大量带宽

选择重传：接收方将收到的坏帧丢弃，但接收并缓存坏帧后面的所有好帧。当发送方超时，它只重传那个最早的未被确认的帧。如果该重传的帧正确到达接收方，接收方就可按序将它缓存的所有帧递交给网络层。选择重传对应的接收窗口大小大于1

选择重传策略通常和否定策略结合使用。当接收方检测到错误，它就发送一个否定确认NAK，NAK可触发该帧的重传操作，而不需要等待相应的计时器超时，因此协议性能得以提高 优点：否定策略，协议性能提高，提高了带宽使用率 缺点：对于数据链路层的内存需求很大 image.png

留下你的想法