＜计算机网络自顶向下＞ 可靠数据传输的原理

可靠数据传输（rdt：Reliable Data Transfer）的原理

• rdt在应用层，传输层和数据链路层都很重要
• 是网络TOP10问题之一
• 信道的不可靠特点决定了可靠数据传输rdt的复杂性
• rdt_send: 被上层（如应用层）调用，以将数据交付给下方的发送实体
• udt_send： 被rdt调用，用一将分组放到不可靠的信道上传输到接收方
• rdt_rcv: 放分组通过信道到达接收方的时候调用（修改下层的错误，传递给上层正确的信息）

• 下面将渐增的开发rdt的发送方和接收方（上层和下层的接口都定下来以后，如何安排本层协议实体需要做那些动作，安排那些时空资源来向上层提供可靠的服务）
  • 条件；只考虑单项数据传输（但是接收方有可能会返回给发送方控制信息一类的东西，所以控制信息是双向流动的）
  • 双向的数据传输问题实际上黑丝两个单项数据传输问题的综合
  • 使用FSM（有限状态机）来描述发送方和接收方（在某一状态的时候，下一个状态只由下一个事件唯一确定

    把可靠传输依靠下层信道比作一个团队领导依靠小弟，下面小弟越没用领导的工作就越复杂，所以需要先假设他们可靠程度高一点，渐增的设计领导的工作这样更加容易一点而不是毫无头绪的直接从头设计领导工作，rdt同理

Rdt1.0： 在可靠信道上的可靠数据传输

• 下层信道是完全可靠的
  • 没有比特出错
  • 没有分组丢失
• 发送方和接收方的FSM
  • 发送方将数据发送到下层信道
  • 接收方从下层信道接收数据
• 总的来说rdt1.0要做的就是封装和解封装

Rdt2.0： 具有比特差错的信道

• 下层信道可能会出错，将分组中的比特翻转
  • 用校验和来检测比特差错
• 从差错中恢复的办法
  • 确认(ACK)：接收方显式的告诉发送方分组已经被正确接受
  • 否定确认(NACK): 接收方显式的告诉发送方发生了差错：发送方收到NAK以后重传分组
• rdt2.0中的新机制：使用差错控制编码来进行差错检测
  • 发送方差错控制编码、缓存
  • 接收方使用编码检错
  • 接收方的反馈，控制报文（ACK.NAK）：接收方->发送方
  • 发送方收到反馈相应的动作

• rdt2.0致命的缺陷
  • ACK和NACK也有可能出错
  • rdt2.1引入序号可以解决这一点

Rdt2.1：有序号

• 处理重复：发送方在每个分组中加入序号，如果ACK/NAK出错，发送方重传当前分组

• 如果序号重复的话，接收方丢掉重复分组，再发一次ACK

• 这是stop and wait (停等协议）：发送方发送一个分组（一次只发送一个分组），然后等待接收方的应答 

• 发送方

  • 在分组中加入序列号，0和1两个序号即可（因为一次只发送一个未经确认的分组）

  • 必须检查ACK/NAK是否出错（需要checksum）

  • 状态数变成了两倍：必须记住当前分组的序列号是0还是1

• 接收方

  • 必须检测接收到的分组是否是重复的

    • 状态会指示希望收到的分组的序号为0还是1

    • 注意：接收方并不知道发送方是否正确收到了ACN/NAK——没有安排确认的确认

 rdt2.2：无NAK的协议

• 功能同rdt2.1，单只使用ACK（ack要编号）
• 接收方对最后正确接受的分组法ACK，以替代ACK
  • 接受方必须显示的包含被正确接收分组的序号
• 当收到重复的ACK（如：再次收到ACK0）的时候，发送方与收到NAK采取相同的动作：重传当前分组
• 为后面的一次发送多个数据单位做准备
  • 一次能够发送多个，每一个的应答都有：ACK, NACK太麻烦了
  • 使用对前一个数据单位的ACK代替本数据单位的NAK
  • 确认信息减少一半，协议处理简单
• 2.2和2.1的唯一区别就是2.2没有NAK

Rdt3.0：具有比特差错和分组丢失的信道——超时重传机制

• 下层信道可能会丢失分组（数据或者ACK）
  • 会死锁：发送的时候分组丢失（比如队列满了包丢失等等）比如发送p1包到接收方，p1中间没了，发送方等待AK，接收方等待p1
  • 机制还不够处理这种状况（下面列出来的只是帮助回忆之前的机制）
    • 检验和
    • 序列号
    • ACK
    • 重传
  • 方法：发送方等待ACK一段合理的时间
    • 发送端超时重传，如果导师没有收到ACK->重传
    • 问题：如果分组（或ACK）只被延迟了

      • 重传将会导致数据重复，但利用序列号一已经可以处理这个问题
      • 接收方必须指明被正确接收的序列号

    • 需要一个倒计数定时器（设置为比正常往返稍微多一点点的时间）
  • 链路层的timeout时间是确定的（往返延迟分布比较集中），传输层timeout时间是适应式的（往返延迟分布比较分散）

    链路层（数据链路层）定时器设置固定： 链路层通常负责在相邻节点之间进行数据传输，其定时器设置一般较为固定。这是因为在局域网或广域网等较小范围内的链路上，往返延迟相对较低且相对稳定，数据包的传输时间相对可预测。因此，链路层的定时器一般采用固定的超时时间，以适应这种相对稳定的网络环境。 传输层定时器设置适应性强： 传输层负责在端到端的通信中提供可靠的数据传输服务，其定时器设置一般需要更加灵活和适应性强。在互联网等大范围网络中，往返延迟可能会受到多种因素的影响，如网络拥塞、路由器处理延迟、数据包丢失等，导致数据包的传输时间波动较大，难以准确预测。因此，传输层通常采用自适应的超时时间设置策略，如 TCP 中的拥塞控制算法（如慢启动、拥塞避免）和快速重传机制，以根据网络状况动态调整超时时间，从而提高数据传输的效率和可靠性。

  • 过早超时（延迟的ACK）也能够正常工作；但是效率较低，一半的分组和确认是重复的，所以设置一个合理的超时时间也是比较重要的

• rdt3.0的性能
  • stop and wait效率太低，信道的容量比较大，包发出去要好久才能到目标主机，特别费时间，比如下面的例子，花了1G的钱仅仅可以得到270kbps有效带宽，所以要一次发送多个包

slide window（滑动窗口）协议

发送端有一个缓冲区（发送缓冲区），发送方把一个分组发送完毕了以后，仍然将那个分组留在缓冲区以便检错重发或者超市抽放。接收端也有一个缓冲区。这个缓冲区是为了平衡发送速率与用户接受速率（一般后者是比前者要慢的）

• 发送缓冲区
  • 形式：内存中的一个区域，落入缓冲区的分组可以发送
  • 功能：用于存放已发送但是没有得到确认的嗯组
  • 必要性：需要重发的时候可用
• 发送缓冲区中的分组
  • 未发送的：落入发送缓冲区的分组，可以连续发送出去
  • 已经发送出去的，等待对方确认的分组；发送缓冲区的分组只有得到确认才能删除
• 发送缓冲区窗口，是发送缓冲区的子集，用于存放已经发送但是未确认的分组的范围。没发送一个分组，发送缓冲区窗口向前滑动一个单位，前沿滑动的极限就是发送缓冲区的大小后沿滑动的极限就是滑动缓冲区的最前方（后沿滑动是因为收到ACK）。实际上是分组在动窗口不动（这里说窗口动是指相对滑动）
• 发送缓冲区的大小：一次最多可以发送多少个未经确认的分组
  • 停止等待协议=1（sw=rw=1）
  • 流水线协议>1，这里必须要合理的值，不可以很大，链路利用率不可以超过100%

Pipeline（流水线或者是管道化）协议

连续发送多个未经确认的分组，要用多个比特来表示分组序号。假如序号由n个比特表示，那么序号的空间为2^n。

• sw>1， rw=1是GBN协议（Go-Back-N 累计确认协议）
  • 接收缓冲区窗口等于1，只有落在接收缓冲区中的分组才能被接收，假如缓冲区已经满了，但是有新的分组到来，把这个新来的分组丢弃然后返回接收窗口最高位的分组的ACK确认信息（带有序号），因为接收窗口此时大小就是1所以直接返回最后收到的分组序号的ACK（这个协议只能顺序的一个一个接收分组）这里比如收到ACK2，就代表2及以前所有分组都收到了，是累计确认（收到的分组都会放在缓冲队列，只要没接收就还在里面，处理到这个分组的时候溢出或者前面又没收到的直接拒收）

             一个计时器，超时就重传 

• sw>1, rw>1是SR协议（Selective Repeat 选择重传协议）
  • 对于正确到来的分组，需要给这个分组确认然后接收窗口向前滑动一格，滑动到接收窗口的最大值大小。要是接接收窗口里面最左边有分组没有收到，不可以向右边滑动。GBN协议不一样，SR协议是每次收到哪个发哪个的确认信息，而GBN协议之只要没收到新的一直发到来的最高序号的分组确认是。SR是非累积确认也就是独立确认（SR协议下，内容正确但乱序的包会缓存下来，并发送相应确认），整个窗口的分组全部确认了以后会一起解封装然后有序地接收

•  正常情况下的两个窗口互动
  • 发送窗口 
    • 有新的分组落入发送缓冲区范围，发送->前沿滑动
    • 来了老的低序号分组的确认->后沿向前滑动->新的分组可以落入发送缓冲区的范围
  • 接收窗口
    • 收到分组，落入接收窗口范围内，接收
    • 是低序号，发送确认给对方
  • 发送端上面来了分组->发送窗口滑动->接收窗口滑动->发确认
  • 也就是说发送方有了新的分组发送进入推动发送窗口向前滑动，发送窗口向前滑动意味着接收窗口一会可以向前滑动，接收窗口向前滑动发送确认给发送端代表发送窗口也可以向前滑动，发送窗口滑动使得发送缓冲区有新的分组可能落到发送缓冲区范围之内（这就是一个连续的过程） 

• 异常情况下SR的两个窗口活动
• 发送窗口
  • 有新分组落入发送缓冲区范围，发送->前沿滑动
  • 超时重发机制让发送端将发送窗口中的所有分组发送出去
  • 来了老分组的重复确认->后沿不向前滑动->新的分组无法落入缓冲区的范围（此时如果发送缓冲区有新的分组可以发送）
• 接收窗口
  • 收到乱序分组，没有落入到接受串口范围内，抛弃
  • （重复）发送老分组的确认，累计确认

• 异常情况下SR的两个窗口活动
  • 发送窗口
    • 新分组落入发送缓冲区范围，发送->前沿滑动
    • 超时重发机制让发送端将超时的分组重新发送出去
    • 来了乱序分组的确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围（此时入如果发送缓冲区有新的分组可以发送）
  • 接收窗口
    • 收到乱序分组，落入到接收窗口范围内，接收
    • 发送该分组的确认，单独确认

• GBN协议和SR协议的异同
  • 相同点
    • 发送窗口>1
    • 一次可以发送多个未经确认的分组
  • 不同点
    • GBN:接收窗口尺寸=1
      • 接收端只能顺序接收
      • 发送端从表现来看，一旦一个分组没有发成功：如0,1,2,3,4:；假如1没有发送成功，234都发送过去了，要把这个从1开始重新发送

• GBN和SR优缺点以及适用范围

•  窗口的最大尺寸（这里我没明白，有人可以回答一下吗）