可靠数据传输原理

一、杂记

延时

传输延时：发送端将分组数据报发送到数据链路的时间
传播延时：分组数据报在物理链路中传播的时间
排队延时：分数数据报在网络节点队列中排队的时间

流量强度：I = La/R

R：物理链路的带宽(bps bit peer second)

L：分组长度(bits)

a：分组到达队列的平均速率

I ~ 0：平均排队延时很小(队列等待分组少)

I ~ 1：延时变的很大(队列等待分组增多)

I > 1：数据到达队列的速率超过了队列输出的速率(数据传播速度大于节点的数据处理速度)，平均排队延时将趋向无穷大

网络强度等于1时，网络节点将会挂掉

设计系统时流量强度不能大于1！
节点处理延时：网络节点检查bit级差错，计算下一跳路由等的时间

windows的延时诊断程序

Traceroute诊断程序

提供从源端，经过路由，到目的地的延时测量
- 沿着目的路径，向每个路由器发送3个探测分组
- 路由器 i 将向发送方返回一个分组
- 发送方对发送和回复之间间隔计时
Traceroute原理

利用ICMP(互联网控制报文协议)，ICMP有很多类型的Message

数据报：|IP头 TTL | IP数据报|

TTL(time to live)：生存时间

数据报在经过每个节点时，TTL都减一，当TTL等于0时，数据报不再通过下一跳继续传输，当前节点利用ICMP报文告诉源主机数据无法继续往下一跳传输

丢失

链路的队列缓冲区有限，当分组到达一个满的队列时，该分组将会丢失
丢失的分组可能被前一个节点或源端系统重传，或者根本补重传
- 分组丢失时，由前一个节点进行重传，如果前一个节点提供不可靠的服务(不支持重传)，则通知源端系统进行重传
  
  如果上一个节点提供可靠的服务，则每次传输数据都要等待下一个节点的应答，如果没有应答就一直传，直到由应答为止
- 对于链路层的上层传输层协议，有些应用采用的传输层协议本身就不支持重传，则源端系统也没必要进行重传
- 物理链路(光纤)本身就比较可靠，传输很稳定，在链路层就能够保证数据不丢失，则不需要协议栈来保证可靠；而对于wife等无线网络链路本身不可靠，则需要上层协议栈来保证可靠。以太网就是不可靠的

吞吐量

瞬间吞吐量：一个很短时间内的速率
平均吞吐量：在一个长时间的平均指
整个数据链路上，平均的吞吐量取决于吞吐量最小的一跳
- 瓶颈链路
  
  端到端路径上，限制端到端吞吐的链路
  
  端到端平均吞吐量 = min(R1,R2,…,RN)
- 互联网场景
  
  假设R链路上有N个用户共同使用，则每个连接上的端到端的吞吐量 = min(RC,RS,R/N)
  
  实际上：整个链路RC或者RS经常是瓶颈，他们代表了家庭链路、学校或者公司的接入网链路

UDP

UDP报文段结构

源端口 | 目标端口 ——32bit

长度 | 检验和

应用报文
检验和

提供差错检验功能，检验和用于确定当UDP报文段从源到达目的地移动时，其中的比特是否发生了改变(链路噪音等)。

发送方的UDP对报文段中的所有的16bit字的和进行反码运算，求和时遇到任何溢出都被回卷(高位溢出时，溢出数字在低位相加)

例如：

1000 0000 1001 0001

加 1100 1010 0001 0110

0100 0101 0110 1000

在接收方，所有16bit字(包括检验和)加在一起，如果该分组中没有引入差错，则在接收方该和将是1111 11111 1111 1111

二、可靠数据传输

由于IP协议是不可靠的，无法保证数据的可靠性，则需要TCP在传输层对可靠性进行控制

可靠传输协议rdt(reliable data transfer protocol)

停等式(stop-wait协议)

用有限状态机(Finite-State-Machine FSM)来定义发送方和接收方的状态转化

rdt1.0
- 假设认为下层的传输信道是完全可靠的(实际不可能)
  - 没有比特出错
  - 没有分组丢失
- 发送方和接收方的FSM
  - 发送方将数据发送到下层信道
  - 接收方从下层信道接收数据
rdt1.0中，传输层没有做任何多余的操作，只负责发送和接收即可
rdt2.0
- 假设下层信道可能出错：将分组中的比特翻转
  - 用检验和来检验比特出错
- 问题：如何从差错中恢复？
  - 确认(ACK)：接收方显示告诉发送方分组已被正确接收
  - 否定确认(NAK)：接收方显示告诉发送方分出出现了差错，发送方手法哦NAK后，发送方重新传分组
  基于这种重传机制的可靠数据传输协议称为自动重传请求(Automatic Repeat reQuest，ARQ)协议，ARQ协议中，还需要另外三类协议功能来处理比特差错的情况：
  
  差错检测、接收方反馈、重传
- rdt2.0中的新机制：采用检验和进行差错检测
  - 发送方差错控制编码、缓存(用于重发)
  - 接收方使用编码检错
  - 接收方反馈：控制报文(ACK,NAK)：接收方->发送方
  - 发送方收到反馈进行相应(重发或继续发下一个报文)
像rdt2.0这样的协议，数据报发送出去以后，要等待接收方的反馈以后才能继续发送，在等待期间不能从上层获取更多数据。这种协议称为停等协议(stop-wait)
rdt2.1

发送方：
- 在分组中加入序列号，两个序列号(0,1)就足够了
  
  一次只发送一个未经确认的分组
- 必须检测ACK/NAK是否出错
接收方：
- 必须检测接收到的分组是否是重复的
接收方并不知道发送方有没有收到ACK/NAK反馈

针对rdt2.0的缺陷，在rdt2.0中，如果反馈的既不是ACK，也不是NAK，则发送方则不知道该如何处理了

解决该问题的一个简单办法是在数据分组中添加一个字段(只需1bit)表示分组序号，该序号(用模2运算得到)可以让接收方知道是不是重传的报文。

报文的逻辑序号是不断增加的，但数据分组里面的序号是逻辑序号用2取模得到的(只需要判断当前分组与上一个分组是否为同一个，用0/1即满足)

rdt2.1接收接受到无法解析的反馈时，就继续发送上次发送的分组，接收方接收到分组后，根据分组的序号判断是否为上一个分组，如果为上一个分组，则直接抛弃，同时给发送方一个ACK/NAK的反馈，直到接收方能够正确解析

接收方重复发送的分组称之为冗余分组
rdt2.2无NAK的协议
- 功能同rdt2.1，但只是用ACK(ack要编号)
- 接收方对最后正确接收的分组发ACK，以替代NAK
  
  接受方必须显示地包含被正确接收分组的序号
- 当收到一个重复的ACK(如再次收到ack0)时，发送发与收到NAK采取相同的动作：重传当前分组
  1. 发送方发送一个p0，接收方正确接收，响应ack0
  2. 发送方收到ack0，然后发送下一个p1，接收方错误接收，仍然响应ack0(响应最后正确的一个分组序号)
  3. 发送方又收到一个ack0(冗余ACK)，接收方重复发送p1
rdt3.0

假设下层信道可能丢失分组(数据/ACK)，发送方没法收到响应则一直阻塞

方法：发送方等待ACK一段合理的时间(时间太短会导致成功的被再次发送，浪费带宽)
- 发送方超时重传：如果到时没有收到ACK->重传
- 问题：如果分组(或ACK)只是被延迟了
  - 重传将会导致数据重复，但利用序列号可以处理这个问题
  - 接收方必须指明被正确接收的序列号
  疑问：由于延迟，发送方可能连续收到两个相同ACK怎么办？
- 需要一个倒计数定时器

流水线式

通用协议：滑动窗口(slide window)协议

发送缓冲区：内存中的一块区域，存放来自上层的数据分组

滑动窗口：发送缓冲区内容的一个范围(子集)，后沿指针和前沿指针之间的区域

发送缓冲区和滑动窗口的关系：

发送缓冲区是固定的一块区域，滑动窗口是缓冲区内一块变化的区域

发送缓冲区：

发送缓冲区
- 形式：内存中一个区域，落入缓冲区的分组可以发送
- 功能：用于存放已发送但未确认的分组和待发送的分组
- 必要性：需要重发时可用
发送缓冲区发大小：一次最多可以发送多少个未经确认的分组
- 停止等待协议=1
- 流水线协议>1 ，合理的值，不能太大，链路利用率不能超100%
发送缓冲区的分组
- 未发送的分组：落入发送缓冲区的分组，可以连续发送出去
- 已发送出去，等待接收方确认的分组：滑动窗口内部的分组，发送缓冲区的分组只有得到确认才能删除

滑动窗口：

发送窗口
- 发送方滑动窗口
  - 那些已发送但是未经确认分组的序号构成的空间
- 发送窗口最大值<=发送缓冲区的值
- 一开始：没有发送任何分组
  - 前沿=后沿
  - 前沿与后沿之间为发送窗口尺寸=0
- 每发送一个分组，前沿前移一个单位，最多移动到发送缓存区末端
- 每收到一个分组确认，后沿前移一个单位，最多移动到跟前沿同一处
- 发送窗口真正滑动过程
  
  发送缓冲区不动，分组移动
接收窗口=接收缓冲区
- 接收窗口用于控制哪些分组可以接收
  - 只有收到分组序号落入接收窗口内的才允许接收
  - 若分组序号在接收窗口之外，则丢弃
- 接收窗口尺寸Wr=1，则只能顺序接收(GBN协议)
- 接收窗口尺寸Wr>1，则可以乱序接收
  
  提交给上层的分组，要按序
- 将接收到数据按顺序交给上层应用
接收窗口收到正确的分组时，前沿指针和后沿指针同时向后移动，保证了滑动窗口大小固定=缓冲区大小

GBN(Go-Back N)

在滑动窗口协议的基础上，当发送端缓冲区大小SW>1，但接收端缓冲区大小RW=1时，即为GBN协议

在GBN协议中，对序号为n的分组确认采用累计确认(cumulative acknowledgment)的方式，即表明已正确收到序号为n及以前的所有分组

例子：

发送接收流程：

发送端发送P1，接收端收到P1，数据报解析交给上层服务并同时响应ACK1
发送方收到ACK1然后发送P2，接收端未收到P2
发送端发送P3，接收端收到P2，丢弃P3，响应ACK1
发送端发送P4，接收端收到P4，丢弃P4，响应ACK1
发送方再次收到ACK1，便知道P2没有发送成功，则发送P2，接收方收到P2，响应ACK2
发送端发送P3……
SR(Selective Repeat，SR)

在滑动窗口的基础上，当发送端缓冲区大小SW>1，且接收端缓冲区大小RW>1，即为SR协议

在SR协议中，每个分组发送时，都会启动一个超时定时器，用于超时重传，同时SR协议支持乱序发送

举例：

假设接收端滑动窗口大小=4，等待1-4数据报