可靠传输

发表于 更新于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

可靠传输

可靠传输的概念

  • 差错检测技术只能做到无差错接受
    • 凡是接受的帧（即没有丢弃），我们能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错
  • 错误帧呗接收方丢弃
    • 有些纠错码技术可以恢复轻微的误码，但实际计算开销太大
  • 可靠传输
    • 必须能以某种方式恢复被丢弃或丢失的帧
    • 链路层、传输层、应用层都可以提供
  • 基本机制
    • 确认（ACK）：协议发给它的对等实体的消息，告知它已收到刚才的帧
      • 可以是一个控制帧，即无任何数据的头部
      • 也可以将一个ACK捎带在一个恰好要发向对方的数据帧中
    • 超时（TIMEOUT）
      • 发送方收到一个确认，表明帧发送成功；如果在合理的一段时间后未收到确认，那么它重发 (retransmit) 原始帧
      • 等待一段合理时间的这个动作称为超时 (timeout)
    • 自动请求重发（ARQ）
      • 使用确认和超时实现可靠传输的策略

停等算法

基本思想

  • 当发送方传输一帧后，在传输下一帧之前等待一个ACK；如果在某段时间之后ACK没有到达，则发送方超时，重发原始帧

重复帧问题：Sender超时重传，但是Receiver误以为是下一帧，重复接收

  • 包含1比特序列号的停等算法
    • 序号值取0或1，每帧交替使用

缺点

  • 只允许链路上有一个未确认的帧，这可能远远低于链路的容量
  • 例如：RTT=90ms的1.5Mbps链路
    • 链路带宽积 = $ 1.5Mbps * 90ms / 2 = 8KB $
    • 每次只能发一帧，造成明显的浪费

滑动窗口算法

基本原理

  • 保持管道满载，提升传输速率的方法
    • 增加单位时间传输数据帧的数目
  • 并发传输数据
    • 允许多个在途传输 (未收到ACK) 的数据帧
    • 通过窗口大小 (window) 限制在途传输的数据帧个数
  • 每个数据帧赋予一个序列号 (Sequence Number, SeqNum)
    • 匹配数据帧与对应的ACK，假设SeqNum能无限大

发送方

  • 维护三个状态变量
    • 发送窗口大小 (Send Window Size, SWS)：能够发送但未确认的帧数的上界
    • 最近被确认过的帧的序号 (Last Acknowledgement Received, LAR)
    • 最近发送的帧的序号 (Last Frame Sent, LFS)
  • 操作
    • 收到 ACK：更新 LAR（右移），若窗口运行，则发送新的帧，更新 LFS
      • 即保证 $ LFS - LAR SWS$
    • 为每帧设置定时器，若收到ACK前超时，重传该帧
    • 必须能缓存SWS个帧

接收方

  • 维护三个状态变量

    • 接收窗口大小 (Receive Window Size, RWS)：能够接受的无序帧数目上界
    • 最大的可接收帧的序号 (Largest Acceptable Frame, LAF)
    • 最后确认接收的帧的序号 (Last Frame Received, LFR)

  • 操作

    • 收到帧：$ LFR SeqNum LAF $，帧在接收窗口内，接收；否则，丢弃

    • 接受数据帧后，将收到的最大连续数据帧的SeqNum作为ACK回复

当数据帧丢失时

  • 方案一：回退N机制(Go-Back-N)恢复丢包
    • 接收方只对连续收到的数据帧回复ACK
      • 例如收到 2 3 4 6 7，则对帧4回复ACK
    • 发送方，由于接收不到新的ACK，超时后重传LAR+1与LFS之间的数据帧
      • 例如上例中重传 5 6 7
  • 方案二：选择确认机制(Selective Acknowledgments) 回复丢包
    • 接收方准确地确认每个已接受的数据帧，发送方根据这些信息更快重传
    • 传输效率更高，但实现更复杂

窗口大小

  • 发送方 SWS
    • 可根据一段给定时间内链路上有多少待确认的帧来选择
    • 依据给定的延迟与带宽的乘积
  • 接收方 RWS
    • RWS=1：接收方不缓存任何错序到达的帧
    • RWS = SWS：接收方能够缓存发送方传输的任何帧
  • 序号大小有限
    • 序列号在大小有限的首部字段中，如3bit可用序号0~7
    • 序列号必须可重用，能回绕
      • 能够区别同一序列号的不同次发送
      • 可用序列号的数目必须大于所允许的待确认的帧的数目
        • 例如停等算法中只允许一个待确认的帧，用2个序列号
  • 当 SWS = RWS时
    • $ (SWS + RWS) MaxSeqNum$
      • \(MaxSeqNum = 2^n\)，n为使用的bit数
    • 即 $SWS = RWS ^{n-1} $
      • 发送窗口大小不能大于可用序列号数的一半

滑动窗口算法的优点

滑动窗口是一种高效的可靠传输机制

  • 可靠传输
    • 基于确认和超时重传机制，在不可靠链路上可靠传输
  • 高效传输
    • 通过并发提升传输性能
  • 按序传送
    • 接收方将连续的数据交给上层，缓存不连续 (乱序到达)的数据
  • 流量控制 (flow control)
    • 接收方能够控制发送方使其降低速度的反馈机制
    • 通信双方通过设定Window大小表达自己的发送/接收能力