可靠数据传输原理

TCP和UDP都属于运输层,运输层负责进程之间数据的传输,作为应用层和网络层之间的桥梁。其中TCP(复杂)可靠,而UDP(简单)不可靠,如果不从物理报文结构上作比较,可以认为TCP是实现了可靠传输的UDP。

如果想要了解TCP可靠背后的原理,就有必要了解可靠传输协议。

下面的内容整理自《Kurose,Ross等著 . 计算机网络:自顶向下方法6th》(机械工业2014),在第三章第四节,原作者对不可靠信道上的可靠性传输方法进行了深入阐述,下面誊抄了原书的相关讲解。

可靠服务的模型

rdt_model

上图展示了不可靠信道实现可靠传输的基本模型。

可靠数据传输协议

《Kurose,Ross等著 . 计算机网络:自顶向下方法6th》依次讲解,逐步深入可靠传输原理,下面誊抄了rdt 1.x、rdt 2.x以及rdt 3.x相关基础知识。

可靠信道的可靠数据传输——rdt 1.0

计算机网络(Kurose, KeithW.Ross)rdl-1.0
计算机网络(Kurose, KeithW.Ross)rdt-1.0完全可靠信道协议

Sender和Receiver的FSM如上图。

前提是底层信道完全可靠:

  • 不会产生比特错误;
  • 不会丢失分组。

FSM:

  • Sender将数据发送给底层信道;
  • Receiver从底层信道接受数据。

具有比特差错信道的可靠数据传输——2.x

版本1——rdt 2.0

假设:

  • 分组比特可能受损;
  • 所有传输的分组都将按序被接收,不会丢失。

处理机制:

  • 差错检测:判断分组受损(通过增加发送方的冗余,如CRC校验等);
  • 接收方反馈(ACK和NAK):通知发送方分组是否受损;
  • 出错重传:发送方在得知分组受损后,进行重传。

基于重传的可靠数据传输协议被称为自动重传请求协议 (Automatic Repeat reQuest, ARQ)

计算机网络(Kurose, KeithW.Ross)rdl-2.0
计算机网络(Kurose, KeithW.Ross)rdt-2.0用于具有比特信道差错的协议

在上述协议中,当发送方处于等待ACK或NAK状态时,它不能从上层获得更多数据。这样子的协议被称为停等协议 (stop-and-wait)

版本2——rdt 2.1

问题的引入:ACK和NAK分组可能受损,而rdt 2.0没有考虑该情况。

解决的思路:

  • 增加控制报文:发送方请求接收方重复ACK或NAK分组。但新的控制报文也可能受损,进入一个死循环;
  • 增加足够的检查和比特:使发送方不仅可以检查比特差错,还可以恢复比特差错;
  • 重传当前数据分组:发送方收到损坏的ACK或NAK分组时,重传当前数据分组。这种方法在信道中引入了冗余分组 (duplicate packet)。 同时,需要对数据分组进行编号,以示识别。
计算机网络(Kurose-KeithW.Ross)rdl-2.1-sender
计算机网络(Kurose-KeithW.Ross)rdt-2.1-sender
计算机网络(Kurose-KeithW.Ross)rdl-2.1-receiver
计算机网络(Kurose-KeithW.Ross)rdt-2.1-receiver

版本3——rdt 2.2

针对rdt 2.1的改进:

  • 只使用ACK;
  • 取消NAK,接收方对最后一个正确收到的分组发送 ACK,接收方须
  • 指明被确认的分组的序号;发送方收到的重复的ACK将按照NAK来进行处理,重传正确的分组。
计算机网络(Kurose-KeithW.Ross)rdl-2.2-sender
计算机网络(Kurose-KeithW.Ross)rdt-2.2-sender
计算机网络(Kurose-KeithW.Ross)rdl-2.2-receiver
计算机网络(Kurose-KeithW.Ross)rdt-2.2-receiver

具有比特差错的丢包信道的可靠数据传输——rdt 3.x

版本1——rdt 3.0

假设:底层信道不但可能出现比特差错,而且可能会丢包。

需解决的问题:发送方负责检测和恢复丢包工作(序号、ACK、重传)。

发送方需要:

  • 每发送一个分组时,就启动一个定时器;
  • 设置相应定时器中断;
  • 确认后终止定时器。
计算机网络(Kurose-KeithW.Ross)rdl-3.0-sender
计算机网络(Kurose-KeithW.Ross)rdt-3.0-sender

下图给出没有丢包延迟的情况以及存在丢包的情况下,rdt3.0的运作情况。由于rdt3.0分组序号在0,1间交替,因此也称作比特交替协议

rdt3.0丢包处理
rdt3.0(比特交替协议)正常传输以及丢包处理图解,摘自《计算机网络,自顶向下原理》

不过比特交替协议有一个问题,因为它是一个停等协议,虽然保证了数据可靠性,但是效率极低。考虑以下发送方利用率计算式:

U(sender) = (L/R) / (RTT + L/R)

其中L/R是传输时延,RTT(Round-Trip Time)为往返时延。其中

RTT >> (L/R)

意为着U(sender) -> 0,所以比特交替协议显然无法投入生产环境。所以有流水线可靠数据传输协议。

版本2——rdt 3.0+

流水线

流水线可靠数据传输协议不使用停等方式运行,它允许发送方发送多个分组而无需等待确认。

ccs-labs.org在线演示:http://www.ccs-labs.org/teaching/rn/animations/flow/

流水线传输协议(1)
流水线传输协议(1)

如果发送方可以在等待确认前发送n个报文,则利用率将比等停协议提高n倍。

流水线传输协议(2)
流水线传输协议(2)

流水线技术中,需要对可靠数据传输协议进行以下改进:

  1. 增加序号范围,传输中的每个分组(不包括重传)有一个唯一序号,因为可能存在多个正在传输且未确认的报文;
  2. 协议发送方和接收方两端需要缓存多个分组,发送方至少缓存未确认分组,接受方至少缓存已确认分组;
  3. 所需序号范围取决于差错处理方式:
    1. GBN(Go-Back-N)回退N步
    2. SR(Selective Repeat)选择重传
Go-Back-N

流水处理之回退N步(Go-Back-N)。

ccs-labs.org在线演示:http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/

Go-Back-N特点:

  • ACK(n):接收方对序号n之前包括n在内的所有分组进行确认 – “累积 ACK”;
  • 统一定时器:对所有已发送但未确认的分组统一定时器;
  • 设置一个超时(n):重传分组n和窗口中所有序号大于n的分组;
  • 失序分组:丢弃 (接收方无缓存),重发按序到达的最高序号分组的ACK。
计算机网络(Kurose-KeithW.Ross)rdl-gbn-sender
计算机网络(Kurose-KeithW.Ross)rdt-gbn-sender
计算机网络(Kurose-KeithW.Ross)rdl-gbn-receiver
计算机网络(Kurose-KeithW.Ross)rdt-gbn-receiver

一个运行中的GBN:

计算机网络(Kurose-KeithW.Ross)rdl-gbn-demo
计算机网络(Kurose-KeithW.Ross)rdt-gbn-demo
Selective Repeat

流水处理之选择重传(Selective Repeat)。

ccs-labs.org在线演示:http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/

SR协议发送方和接受方都具有滑动窗口。

发送方事件与动作:

  • 上层数据发送:从上层收到数据,如果下一个可用于该分组的序号在窗口内,则将数据打包并发送;
  • 超时:重传分组n,重置定时器;
  • 收到确认:在 [sendbase : sendbase+N]范围内,标记分组 n 为已接收,如果n是发送窗口基序号sendbase,则将窗口基序号前推到下一个未确认序号。

接收方事件与动作:

  • 分组序号n在[rcvbase : rcvbase+N-1]范围内:发送n的确认ACK(n),如果分组序号失序,则将其缓存,将该分组以及以前缓存的序号连续的分组一起交付给上层,将窗口前推到下一个未收到的分组;
  • 分组序号n在 [rcvbase-N : rcvbase-1]范围内:虽然曾经确认过,仍再次发送n的确认ACK(n);
  • 其他情况:忽略该分组。
计算机网络(Kurose-KeithW.Ross)rdl-sr-demo
计算机网络(Kurose-KeithW.Ross)rdt-sr-demo

可靠数据传输协议小结

校验和、序号、定时器、肯定和否定确认分组 -> rdt 3.0 -> 滑动窗口、流水线(GBN、SR)-> TCP。

可靠数据传输机制及其用途
可靠数据传输机制及其用途

参考

  1. Kurose,Ross等著 . 计算机网络:自顶向下方法6th(Computer Networking – A Top-Down Approach . 6th).  机械工业出版社 . 2014
  2. www.ccs-labs.org – animations – flow
  3. www.ccs-labs.org – animations- gbn_sr

作者: V

Web Dev

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s