可靠数据传输与拥塞控制

1 信道不可靠

  • 出现比特错误
  • 会丢包

2 普通可靠传输-停止等待协议

关键词：校验和、ACK、重传、序号、超时重传

出现比特错误的信道

  • 接收方：需要确认信息是否就是发送方所发送的，并且需要反馈是否有错误给发送方
  • 发送方：需要在发送的信息中添加额外信息以使得接收方可以对接收到的信息是否有错误进行判断，并且需要接收接收方的反馈，如果有错误发生就要进行重传

因而在这种信道上进行传输需要三种功能：

  • 差错检测：发送方提供额外信息供接收方进行校验，接收方进行校验以判断是否有错误发生。网络协议一般采用校验和来完成该任务
  • 接收方反馈：接收方需要将是否有错误发生的信息反馈给发送方，这就是网络协议中最常见的ACK（确认）/NAK（否定的确认）机制
  • 发送方重传：在出现错误时，发送方需要重传出错的分组。重传也是网络协议中极常见的机制。

反馈出现错误

  • 如果收到了受损的反馈，则都认为是出现了错误，就进行重传。但是这时就可能引入冗余的分组，因为被重传的分组可能已经正确的被接收了。
  • 冗余分组可以通过一种简单的机制来解决，这就是分组序列号。被发送的每个分组都有一个序列号，接收方只需要检测该序列号就可以知道分组是否是冗余的。
  • 在引入序列号后，该机制已经可以在这种信道上工作了。有些网络协议中并不会产生否定的确认（即报告发送方出现了错误），它采用的是继续为已经为之发送过ACK的最后一个正确接收的分组发送ACK。当发送方收到冗余的ACK时就知道跟在被冗余ACK确认的分组之后的分组没有被正确接收，这就达到了NAK所要的效果。

出现丢包错误的信道

  • 这种信道是更常见的信道。比特错误的问题已经被校验和、序号、ACK和重传解决了。

  • 丢包问题的解决很简单，对于发送方来说只要在一定时内没有收到分组的ACK就认为分组丢失了，就进行重传即可。当然这可能引入冗余的分组，但是序列号是可以解决冗余分组的问题，因而唯一需要确定的就是所谓的一定的时间内的时间长度。很显然时间长度至少要为“往返时延+分组处理时间”。

停止等待协议机制和性能

  • 停止等待协议机制：校验和、ACK、重传、序号、超时重传
  • 停止等待协议性能：停止等待协议，它的性能很差。任意时刻信道内只有一个分组（或者数据分组或者确认分组）。这就极大的浪费了带宽。

3 流水线可靠数据传输协议

关键词：流水线技术、回退N步、滑动窗口、累计确认、选择重传、超时重传

流水线技术

对停止等待协议的可靠传输协议进行修改修改：不采用停止等待协议，而是允许发送方发送多个分组而无需等待确认。具体的修改包括：

  • 增加分组序号范围，因为每个传输的分组需要有一个唯一的序号，而且同时存在多个未确认的分组
  • 协议的发送方和接收方需要缓存多个分组，发送方至少需要缓存已发送但未确认的分组

流水线的差错恢复有两种手段：回退N步（GBN）和选择重传。

4 GBN回退N步-滑动窗口协议

序号

该协议中，流水线中未被确认的分组数目不能超过N。 GBN协议中发送方两个重要的序号为：

  • 基序号(send_base)：最早未被确认的序号
  • 下一个序号(nextseqnum)：最小未使用的序号

发送方看到的序号分段

  • [0, send_base - 1]：已发送并且收到确认了的序列号
  • [send_base, nextseqnum - 1]：已发送但未收到确认了的序列号
  • [nextseqnum, send_base + N - 1]：可被用于发送新分组的序列号
  • 大于等于send_base + N：不能使用的序列号

滑动窗口

  • 本协议中，已发送但未被确认的分组数目不能超过N。因此N可以看做是从第一个已发送但未被确认的序号开始的长为N的序号窗口，也称为发送窗口。

  • 随着分组被确认，该窗口逐渐滑动，send_base增加，但是其大小不变，因此该协议也称为滑动窗口协议。

发送方事件

  • 上层调用进行发送：当发送数据时，首先判断发送窗口是否已满，只有不满时才会启动发送，如果满了则不能发送或者缓存或者通知调用者，这取决于实现，
  • 收到ACK：如果收到了分组n的ACK，并且分组n的序号在[send_base, nextseqnum - 1]之间，则更新send_base。GBN协议采用累积确认，含义是如果发送方接收到了对分组n的确认，则表明分组n之前的所有分组都已经被接收。
  • 超时事件：GBN协议名字来自该协议对分组丢失或超时事件的处理。如果分组丢失或者指定的时间内仍未收到对已发送但是未收到确认的分组的确认，则发送方重传[send_base, nextseqnum-1]之间的所有分组。实现中可以只为序号为send_base的分组启动一个定时器，如果send_base被更新就重启send_base相关的定时器，如果没有已经被发送但未被确认的分组，则关闭定时器。

接收方事件

接收方接收到分组n时，如果n是按序接收的，即分组n之前的所有分组都已经到达，则发送一个对分组n的确认，并将分组提交给上层。所有其它情况，接收方都丢弃分组，并重传对最后一个按序接收的分组的确认。这种设计简化了接收方接收缓存的设计，同时被丢弃的分组早晚都会被重传，因而可靠性也是有保证的。

GBN协议的接收方只维护了一个期望收到的下一个序号的信息，并保存在expectedseqnum中，在expectedseqnum之前的所有分组都已经被正确接收并提交给了上层。接收方具体的行为如下：

  • 如果收到的分组的序号与expectedseqnum相同，则将分组提交给上层，并更新它的值为下一个期望收到的序号。
  • 如果收到的分组的序号大于expectedseqnum，就丢弃分组。
  • 如果收到的分组的序号小于expectedseqnum，就重传对最后一个按序接收的分组的确认。由于GBN是累积确认的，因此该确认可以确保发送窗口可以向前移动。

5 选择重传

GBN协议存在缺陷，在超时或者分组丢失时它会重传所有的在[send_base, nextseqnum-1]之间的分组，而接收方也会丢弃非按序到达的分组，这也浪费了带宽。

发送方序号

选择重传协议通过让发送方仅重传那些它怀疑在发送方出错的分组来避免不必要的重传。该协议中发送方看到的序号空间与GBN协议完全相同，唯一不同的在于序号空间[send_base,nextseqnum - 1]中的分组包含了一些已经被接收方确认了的分组。

发送方行为

  • 上层调用进行发送：当发送数据时，首先判断发送窗口是否已满，只有不满时才会启动发送，如果满了则不能发送或者缓存或者通知调用者，这取决于实现，
  • 收到ACK：如果收到分组n的ACK，并且n的序号在[send_base, nextseqnum - 1]之间，则将分组n状态更新为已确认，如果n的序号等于send_base，则更新send_base到下一个已发送但未被确认的分组的序号处。
  • 超时事件：该协议使用选择重传，因此每个分组都有一个定时器，如果某个分组的定时器到期了就重传该分组。

接收方序号

该协议中，接收方也需要维护一个长度为N的接收缓存，并且需要维护一个变量rcv_base，它表示接收方期望收到的下一个分组的序号。接收方看到序号空间被划分为：

  • [0, rcv_base - 1]：已经正确接收并且被确认了的序号空间
  • [rcv_base, rcv_base + N -1]：期望接收的序号空间
  • 大于rcv_base + N ：不可用的序号空间

接收方行为

  • 收到了序号在[rcv_base – N , rcv_base -1]之间的分组：产生一个ACK，这是必须的，因为发送方重传了该分组就说明它没有收到对它的ACK，如果不发送ACK，发送方的窗口将不会移动。假设N=5，考虑以下场景
    • 发送方发送了序号为5,6,7,8,9的分组，因此send_base=5
    • 接收方接收了这些分组并且为所有分组都发送了ACK，因此rcv_base=10
    • 所有ACK都丢失
    • 发送方重传分组5
    • 接收方必须发送ACK，否则发送方窗口将不会被更新
  • 收到了序号在[rcv_base, rcv_base + N -1]之间的分组：发送ACK给发送方。如果该分组以前未接收，则缓存它，如果该分组的序号等于rcv_base，则将从rcv_base开始的序号连续的被缓存的接收到的分组提交给上层，同时更新rcv_base为有序接收到的最后一个分组的序号的下一个序号。
  • 接收到其它分组：丢弃分组

注意到接收方必须可以处理序号范围在[rcv_base, rcv_base + N -1]和[rcv_base – N , rcv_base -1]之间的分组，这两个区间的总长度为2N。因此这就意味着序号空间至少要有2N个可用序号值，即序号空间的大小至少要为2N，否则接收方就无法区分一个分组是新的分组还是一个重传。