文章目录

• 概述
• • 运输层和网络层
  • 因特网运输层
• 多路复用与多路分解
• UDP
• • 报文段结构（segment structure）
  • 检验和（check sum）
• 可靠数据传输原理
• • 可靠数据传输协议
  • • 完全可靠信道的可靠数据传输：rdt1.0
    • 具有比特差错信道的可靠数据传输 rdt2.0
    • 具有比特差错信道的可靠数据传输 rdt2.1
    • 具有比特差错信道的可靠数据传输 rdt2.2
    • 具有比特差错的丢包信道的可靠数据传输 rdt3.0
  • 流水线
  • 回退N步（GO-Back-N）
  • 选择重传(Selective Repeat)
  • 可靠数据传输机制
• 拥塞控制原理
• • 原因与代价
  • 控制方法
• TCP
• • 连接
  • 报文段结构
  • 往返时间估计与超时
  • 可靠数据传输
  • 流量控制
  • 连接管理
  • 拥塞控制
  • • 核心思想
    • 控制机制
    • 相关演化
    • 公平性
    • 网络辅助拥塞控制
  • TCP小结

概述

运输层和网络层

1. 运输层协议为运行在不同主机上的应用进程之间提供逻辑通信。

   

2. 通信过程

3. 网络层协议IP

   • 尽力而为服务（best-effort）：不保证交付，不保证按序，不保证完整性
   • 不可靠服务
   • 每台主机有一个IP地址

因特网运输层

1. 多路复用（multiplexing）

2. 多路分解（demultiplexing）

   

3. TCP：可靠数据传输、拥塞控制

   • 四元组标识：源IP，目的IP，源端口，目的端口

4. UDP：不可靠服务，流量不可调节

   • 二元组标识：目的IP，目的端口

多路复用与多路分解

1. 多路分解：处理来自不同套接字的数据，给他们加上头部

2. 多路复用：利用头部信息交付到正确的套接字

   • 要求：

     • 套接字具有唯一标识符
     • 报文段可以指示所要交付到的套接字

   

3. 无连接的多路复用与多路分解

   • UDP套接字：由目的IP地址和目的端口号构成的二元组标识

4. 面向连接的多路复用与多路分解

   • TCP套接字：由源IP地址，源端口号目的IP地址和目的端口号构成的四元组标识

   

UDP

1. 尽力而为服务：可能丢包，不保证按序交付

2. 无连接

   • 接收方和发送方之间无需握手
   • 没有建立连接所需的时延（RTT）

3. 头部更小

4. 实现简单

5. 无拥塞控制

6. 适用范围：要求最小的发送速率，不希望过分延迟传送，可以容忍数据丢失

   

报文段结构（segment structure）

头部由四个部分组成：

• 源端口号
• 目的端口号
• 长度：包括首部在内的UDP报文段长度
• 检验和：用于差错检验

检验和（check sum）

• 步骤如下：

  1. 将所有数据相加
  2. 如果有进位，则舍弃进位之后再加1，此操作成为回卷
  3. 上述结果取反码，得到检验和

• 检验过程：

  • 将所有数据项相加（报文段+检验和）
  • 如果某一位是零，则一定出现错误

• 特点：

  • 只能检验奇数位错误
  • 无法纠错

可靠数据传输原理

可靠数据传输协议

完全可靠信道的可靠数据传输：rdt1.0

• 发送端：接收来自较高层的数据，产生分组，发送至信道

• 接收端：从底层信道接收分组，取出数据，传送给较高层

  

• 特点：

  • 无须担心差错
  • 接收方的接收速率 = = =发送方的发送速率

具有比特差错信道的可靠数据传输 rdt2.0

1. 停等协议（stop-and-wait）：发送者发送一个包，等接收到接收端的相应之后再发送下一个包

2. 自动重传请求协议（automatic repeat request，ARQ）

   • 差错检验：检测何时出现比特差错
   • 接收方反馈：肯定确认（ACK）和否定确认（NAK）
   • 重传：接收方收到有差错的分组时，发送方开始重传

3. 发送端：

   • 等待接收来自上层的数据，产生分组，带上检验和，发送
   • 等待接收来自接收端的ACK或NAK
     • ACK :开始等待数据
     • NAK:重传上一个分组，等待接受ACK或NAK

   

4. 接收端：

   • 当分组到达时，要么回复NAK，要么回复ACK

   

5. 问题：当ACK或NAK出错

   • 陷入无限请求确认的死循环
   • 增加足够的检验和
   • 只重传当前数据分组
     • 无法事先知道收到的分组是新的还是之前的

6. 问题解决：增加分组序号（sequence number）

具有比特差错信道的可靠数据传输 rdt2.1

• 在rdt2.0的基础上增加分组序号

  • 停等协议中使用一位编码即可

• 发送端：需要指明目前正发送的分组

  

• 接收端：需要指明当前希望收到的分组

  

• 问题：所需的ACK和NAK会造成冗余开销

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

• 在rdt2.1的基础上去掉NAK

  • 接收端的ACK需要加上序号

• 发送端：若接收到两个ACK（一个冗余），则说明接收方没有正确接收到被确认两次的分组之后的分组

  

• 接收端：若出错，发送对上一个分组的ACK

  

具有比特差错的丢包信道的可靠数据传输 rdt3.0

• 也称作比特交替协议：alternating-bit protocol

• 基于时间的重传

  • 时间不好确定
  • 可能出现冗余数据分组
    • 通过序号解决->rdt2.2

• 倒数计时器

• 发送方要求

  • 每发送一个分组，就启动一个定时器
  • 可以响应定时器中断
  • 可以终止定时器

• 有限状态机

  

• 执行示意图
  

• 问题：停等协议，效率不够高

  • 解决：流水线，允许发送方发送多个分组而无需等待确认

流水线

允许在未收到确认的情况下发送多个分组

• 增加序号范围：正在传输中的分组必须有唯一序号
• 发送方和接收方需要设置缓存
  • 发送端：至少需要缓存已发送但没有确认的分组
  • 接收端：或许需要缓存那些已经正确接受的分组
• 差错恢复：处理丢失、损坏或延时过大的分组
  • GBN：go-back-n
  • SR：selective repeat

回退N步（GO-Back-N）

• 也称为滑动窗口协议：sliding-window protocol

• 使用到的技术：适用序号、累计确认、检验、超时重传

• 允许发送多个分组而无需等待确认

  • 采用累计确认

• 限制：未确认的分组数不能超过最大允许数 N N N

  • N N N常称为窗口长度

• 基序号：base number

• 下一个序号：nextseqnum

• 四个分组：

  • 已被确认：[0,base-1]
  • 可用未被发送：[nextseqnum,base+N-1]
  • 发送未被确认：[base,nextseqnum-1]
  • 不可用：[base+N,~]

  

• 发送方必须响应：

  • 上层调用时：检查发送窗口是否已满
    • 已满：将数据返还给上层，提示稍后重试
    • 未满：将数据加头部形成分组之后发送，更新相关变量
  • 收到一个ACK：
    • 收到ACK(n)：n及之前分组均已得到确认
  • 超时：
    • 重传已发送但未被确认的分组
    • 收到ACK, 仍有已发送未被确认的分组，重新启动计时器
    • 收到ACK, 没有已发送未被确认分组，停止计时器
  • 需要维护窗口的上下边界、nextseqnum在窗口中的位置

  

• 接收方：

  

  • 按序收到分组n, 返回ACK（n）
  • 其他情况下，丢弃收到的分组，返回最近按序到达的相应ACK
  • 只需要维护下一个按序接收的分组序号

• 举例

• 问题：存在大量没有必要的重传

选择重传(Selective Repeat)

• 发送方仅重传怀疑出错的分组
• 接收方需要逐个确认正确收到的分组
  • 失序分组被缓存
  • 确认时不必管是否按序到达

• 发送方：

  • 从上层受到数据：检查下一个可用于该分组的序号
    • 序号位于发送方窗口内：打包并发送
    • 不在发送窗口内
      • 缓存数据
      • 返回给上层
  • 超时：每个分组都拥有自己的逻辑定时器
    • 超时后只能发送一个分组
  • 收到ACK：
    • 若该序号在窗口内，将那个分组标记为已接受
    • 该分组序号等于send_base，则窗口基序号向前移动到具有最小序号的未确认分组处
    • 窗口移动并由序号落在窗口内的未发送分组，则发送这些窗口内的分组

• 接收方：

  • 序号在[rcv_base，rcv_base+N-1]内的分组被正确接收：收到的分组落在接收方窗口内，会送一个ACK
    • 该分组以前没收到过，则缓存他们
    • 该分组序号等于接收窗口的基序号（rcv_base）,则改分组及以前缓存的序号连续的分组都会交付给上层
  • 序号在[rcv_base-N, rcv_base-1]内的分组被正确接收：产生一个ACK,即使该分组之前被确认过
  • 其他情况：忽略该分组

• 举例

  

• 问题：

  • 发送方和接收方的窗口不一致问题，导致无法判断是一个新分组还是一次重传
  • 解决：窗口长度不许小于等于序号空间大小的一半

  

可靠数据传输机制

机制	用途和说明
检验和check sum	检测传输分组中的比特错误
定时器timer	用于重传分组，因为分组可能丢失。当一个分组延时但没有丢失时，或一个分组已被接收而其对应的ACK丢失时，接收方可能会接收到一个分组的多个冗余副本
序号sequence number	用于为从发送方流向接收方的分组按顺序编号。所接收到的分组序号间的空隙可以使接收方检测出丢失的分组；具有相同序号的分组可以使接收方检测到一个分组的冗余
确认ACK	接收方告诉发送方一个或一组分组已经被正确接收
否定确认NAK	接收方告诉发送方某个分组没有被正确接收
窗口流水线window+pipeline	发送方限制，只能发送序号落在窗口范围内的分组。通过允许在没有得到确认的情况下一次发送多个分组，发送方的利用率相较于停等协议有了很大的提高。

拥塞控制原理

网络十分拥塞导致路由器缓存溢出丢包

原因与代价

• λ i n \lambda_{in} λin​：主机A的发送速率
• λ o u t \lambda_{out} λout​：接收方接收速率
• λ i n ′ \lambda_{in}^{'} λin′​：初始数据+重传数据，供给载荷
• R R R：链路容量

1. 两个发送方和一台具有无限大缓存的路由器

   

   • 发送速率在0-R/2之间：接收方吞吐量=发送方发送速率

   • 发送速率超过R/2：吞吐量只能达到R/2

     • 此时时延会趋近无穷

   • 代价：分组会经历巨大的排队时延

     

     

2. 两个发送方和一台具有有限缓存的路由器

   

   • 性能依赖于重传方式

   • 代价：

     • 发送方必须执行重传以补偿因为缓存溢出而丢失的分组

       

     • 发送方在遇到大时延所进行的不必 要重传，导致路由器需利用其链带宽来转发不必的分组

     

3. 4个发送方和具有有限缓存的多台路由器及多条路径

   

   • 当流量很小时，链路并未得到充分使用，仍有较大空间，所以 λ i n \lambda_{in} λin​的增大会导致 λ o u t \lambda_{out} λout​的增大

   • 当供给载荷趋于无穷，R2的空闲缓存会立即被B-D的分组沾满，而A-C连接在R2的吞吐量趋于零

   • 每当有一个分组在第二跳路由器上被丢弃时，第一条所做的工作全部是”劳而无功“的

   • 代价：当一个分组沿一条路径被丢弃时，每个上游路由器用于转发该分组到丢弃该分组而使用的传输容量最终被浪费

     

控制方法

• 端到端

  

  • 网络层不提供现实支持
  • 端系统需要通过对网络行为的观察来判断
    • 分组丢失
    • 时延
    • 超时
    • 冗余ACK

• 网络辅助

  

  • 路由器向发送方提供关于网络中拥塞状态的显式反馈信息
  • 直接网络反馈：由路由器发送给发送方，采用阻塞分组
  • 经由接收方的网络反馈：路由器标记或更新从发送方流向接收方的分组中的某个字段, 收到标记分组后，接收方通知发送方存在网络拥塞
    • 至少经过一个RTT

TCP

连接

• 面向连接：发送数据之前相互握手
  • 点对点：单个发送方与单个接收方之间的连接
  • 三次握手
• 最大报文段长度：maximum segment size
  • 报文段里应用层数据的最大长度，不包括TCP首部
• 两端都具有发送缓存和接收缓存

报文段结构

• 首部20字节
  • 32b的序号字段
  • 32b的确认号字段
  • 16b的接收窗口字段：指出接收方愿意接受的字节数
  • 4b的首部长度字段：指示TCP首部长度
  • 可选与变长的选项字段：协商MSS
  • 6b标志字段：
    • ack：确认字段有效
    • rst、syn、fin：连接的建立和拆除
    • psh：接收方应立即将数据交给上层
    • urg：紧急数据，TCP必须通知接收端的上层实体
• 序号和确认号：可靠传输服务
  • 序号：建立在传送的字节流上，该报文段首字节的字节流编号
  • 确认号：累计确认，只确认该流中至第一个丢失字节为止的字符

往返时间估计与超时

• 应该大于该链接的往返时间（RTT）

• 加权公式估算往返时间

  

• 设置和管理重传超时间隔

可靠数据传输

确保一个进程从其接受缓存中独处的数据路是无损坏无间隙非冗余的按序数据流

1. 发送方：

   • 从上层接收到数据
   • 定时器超时
   • 收到ACK(y)

2. 超时间隔加倍：

   • 相对解决由于网络拥塞引起的定时器超时

3. 快速重传

   • 利用冗余ACK
   • 三个ACK启动快速重传

   

4. GBN到SR

   • TCP使用累计确认
   • 发送方仅需要维护已发送但未被确认的字节的最小序号和下一个需要发送的字节序号
   • 重传至多一个报文
   • 改进：跳过重传那些已被选择性确认过的报文

流量控制

• 速度匹配：发送方的发送速率要让接收方来得及读取
  • 消除发送方使接收方缓存溢出的可能性
• 方法：
  • 发送方维护一个接收窗口rwnd，指出接收方还有多少可用的缓存空间
  • LastByteRead：B从缓存中读出的最后一个字节编号
  • LastByteRcvd：从网络中到达的并放入B接收缓存中的数据流的最后一个字节编号
  • LastByteRcvd-LastByteRead ≤ \leq ≤RcvBuffer
  • rwnd=RcvBuffer-[LastByteRcvd-LastByteRead]

连接管理

建立连接三次握手

1. 客户端向服务器端发送特殊的报文段：SYN报文
   • 不包含应用层数据；
   • SYN置1
2. 服务器为该连接分配缓存和变量，向客户端发送允许连接的报文段：SYNACK
3. 客户端收到SYNACK之后，给该连接分配缓存和变量，向服务器发送另一个报文段，SYN=0，同时时可以携带数据

关闭连接四次挥手

1. 客户端发送特殊报文段FIN=1,
2. 服务器发送确认
3. 服务器发送自己的终止报文段，FIN=1
4. 客户端发送确认

状态图

• 客户端

  

• 服务器端

  

拥塞控制

核心思想

• 出现丢失报文段意味着拥塞，因此当丢失报文段时应该降低TCP发送方速率
• 一个确认报文段指出该网络正在向接收方交付发送方的报文段，因此，当对先前未确认报文段的确认到达时，可以增加发送方速率
• 带宽探测
  • 收到ACK表明网络不拥塞，增加速率
  • 发现丢包表明网络拥塞，减小速率
  • 从丢包时的速率后退，再次开始探测，看拥塞开始速率是否发生变化
• TCP拥塞控制：AIMD
  • 慢启动：必须
  • 拥塞避免：必须
  • 快速恢复：推荐

控制机制

1. 慢启动 slow start
   • 以窗口初始值开始，指数增长
2. 拥塞避免 congestion avoidance
   • 线性增加
3. 快速恢复 fast recovery
   • 保留一定数目的段

相关演化

1. 回顾
2. 吞吐量
3. 经高带宽路径的TCP

公平性

• 瓶颈链路：对于每条连接，相对于瓶颈链路的传输容量自己总是很充足

• 公平：K条连接，瓶颈链路速率为R，若每天连接的平均传输速率接近R/K，认为公平

  • 即每条连接可以得到相同份额的链路带宽

• 假设如图的两条链接具有相同的MSS和RTT（他们拥有相同的拥塞窗口长度，则会拥有相同的吞吐量），TCP一直按照CA模式运行

  

  • 我们应追求平等带宽共享和全带宽利用率曲线的交点

    

  • 沿平等带宽共享共享曲线在波动，最终收敛到该状态

• 理想中

  • 只有TCP连接穿过瓶颈链路
  • 所有的连接具有相同RTT
  • 对于一个主机-目的地只有一条TCP连接与他关联

• 实际中，当有多条连接共享一个共同的瓶颈链路时

  • 具有较小RTT的连接能够更快抢到可用带宽，即较快地打开拥塞窗口
  • 具有较大RTT的连接会享用更高的吞吐量

• 公平性和UDP

  • 媒体：不想传输速率被扼制，即使偶尔丢包
  • UDP：不公平，无拥塞控制，不调整速率

• 公平性和并行TCP

  • 当一个应用使用多条并行连接时，会占用较大的带宽

网络辅助拥塞控制

• 明确拥塞通告（Explicit Congestion Notification, ECN）：允许网络明确向TCP的发送方和接收方发出拥塞信号

• 在网络层，IP数据报首部的服务类型字段中的2b被用于ECN

• 流程

  

  • 接收主机中的TCP接收到了一个数据报中的ECN拥塞指示
  • 接收主机中的TCP在接收方到发送方的TCP ACK报文段中设置ECE，通知发送方的TCP收到拥塞指示
  • TCP发送方通过减半拥塞窗口对ACK做出反应，并在下一个传输的从发送方到接收方的报文段首部对CWR进行设置

• 其他运输层协议也可以利用网络层发送ECN信号

  • DCCP, Datagram Congestion Control Protocol：低开销、控制拥塞类似UDP不可靠服务
  • DCTCP：为数据中心网络设计的TCP版本

TCP小结

• 特点：面向连接、可靠传输、全双工、字节流
• 首部：20B，源端口、目的端口、序号、确认号、接受窗口、标志字段、选项
• 连接管理：三次握手四次挥手
• 可靠传输：序号、确认号、重传（超时、3个冗余ACK）
• 流量控制：rwnd
• 拥塞控制
  • 发送方根据感知到的拥塞程度设置cwnd限制发送速率
  • AMID
  • 慢启动、拥塞避免、快速恢复