TCP 拥塞控制 : 为了公平性
原理(拥塞窗口)、原因、算法
算法包括 慢启动 拥塞避免 快速恢复 拥塞发生
拥塞控制
拥塞控制原理
- 拥塞:
- 非正式的定义: “太多的数据需要网络传输，超过了网络的处理能力”
- 与流量控制含义不同
- 流量控制 是为了 让发送端的发送速度和接收端的接受速度匹配，避免接收端接收缓存溢出
- 拥塞 是指 网络拥塞导致发送端发送的分组在路由器缓存溢出。
- 但行为是一致的：都是遏制发送方。
- 拥塞的表现:
- 分组丢失 (路由器缓冲区溢出)
- 分组经历比较长的延迟(在路由器的队列中排队)
- 拥塞控制问题
- 与rdt一样，是网络中前十位的问题
- 如 ：拥塞控制如何在上层应用得到的服务性能中明确的显露出来？如何可用各种方法来避免网络拥塞或对他作出反应？
拥塞原因与代价
代价
- 在分组的到达速率接近链路容量时，分组经历巨大的排队时延
- 发送方必须重传以补偿因为缓存溢出而丢失的分组
- 发送方在遇到大时延所进行的不必要重传会引起路由器利用其链路带宽转发不必要的分组副本
- 当一个分组沿一条路径被丢弃时，每个上游路由器用于转发该分组到丢弃该分组而使用的传输容量最终被浪费掉了
场景见补充
拥塞控制方法
根据网络层是否为运输层拥塞控制提供显示支持
端到端拥塞控制
- 没有来自网络的显式反馈，即网络层不为运输层拥塞控制提供显示支持
- 端系统根据分组丢失和时延推断是否有拥塞
- TCP采用的方法
网络辅助的拥塞控制
- 路由器提供给端系统以反馈信息,即网络层为运输层拥塞控制提供显示支持
- 单个bit置位，显示拥塞情况 (SNA, DECbit, TCP/IP ECN, ATM)
- 显式提供发送端可以采用的速率
- 例子：ATM可用比特率 (略)
TCP拥塞控制概述
- 一种形式受限的拥塞控制 : Timer定时器的RTO在每次重传之后呈指数型增长
- 定时器过期很可能是由网络拥塞引起的，即太多的分组到达路径中的路由器队列中，造成分组丢失或较长排队时延。在拥塞时如果持续重传分组，会使得分组更加严重；于是，TCP采用更文雅的方式，每个发送方的分组都是经过越来越长的时间间隔后进行。
- 下面介绍更复杂的TCP拥塞控制形式。
拥塞感知
发送端如何探测到拥塞 ?
根据《自顶向下》: 发生丢包
先声明：TCP的丢包事件 定义为
要么 1. 出现超时
要么 2. 收到来自接收方的3个冗余ACK(一般收到三个冗余ack时还没超时 因为RTO设置的相对保守)
- 某个segment超时了 : 拥塞
- 超时时间到，某个段的确认没有来
- 原因1：网络拥塞（某个路由器缓冲区没空间了，被丢弃）概率大
- 原因2：出错被丢弃了（各级错误，没有通过校验，被丢弃）概率小
- 一旦超时，就认为拥塞了，有一定误判，但是总体控制方向是对
- 有关某个段的3次冗余ACK：轻微拥塞
- 第1个ACK : 正常ACK. ackno = 3460 , 确认绿色segment
- 2，3，4次ACK：三次冗余ack. ackno = 3460 , 确认乱序到达的蓝色,橙色,灰色segment
- 粉色segment仍然没被确认，其后面的segment却确认了，故粉色segment丢失的可能性很大
- 网络这时还能够进行一定程度的传输，拥塞情况轻于第一种
拥塞控制
拥塞控制中，TCP如何限制Sender发送segment ? –> 通过维护拥塞窗口
- 拥塞窗口 Congestion Window
- cwnd
- TCPSender 维护一个 拥塞窗口
- 在整个过程中保证(流量控制和拥塞控制的联合动作)
- send_window(bytes sent but not acked) <= min {cwnd(拥塞控制),rwnd(流量控制)}
- rwnd : 满足接收方不会缓存溢出
- cwnd : 满足网络可以不拥塞的传输分组
- 本part关注拥塞控制，故假设接收缓存无限大 -> receive_window_size 无限大
- 故 bytes sent but not acked < cwnd
- Sender 发送速率 为 cwnd / RTT byte/s
- send_window(bytes sent but not acked) <= min {cwnd(拥塞控制),rwnd(流量控制)}
- 从而粗略地控制发送方的往网络中注入的速率
- 在整个过程中保证(流量控制和拥塞控制的联合动作)
cwnd变化
通过调节cwnd来控制发送速率,那么TCPSender该怎样确定应当发送的速率呢 ?
- CongWin是动态的，是感知到的网络拥塞程度的函数
- 超时或者3个重复ack，CongWin↓
- 超时：CongWin降为1MSS,进入SS阶段然后再倍增到 CongWin/2（每个RTT），从而进入CA阶段
- 3个重复ack ：CongWin降为CongWin/2,CA阶段
- 否则（正常收到Ack，没有发送以上情况）：CongWin跃跃欲试↑
- SS阶段：加倍增加(每个RTT)
- CA阶段：线性增加(每个RTT)
- 超时或者3个重复ack，CongWin↓
TCP拥塞控制算法
慢启动 slow-start (SS)
连接刚建立, CongWin = 1 MSS
- 如: MSS = 1460bytes & RTT = 200 msec
- 初始速率 = 58.4kbps
- 可用带宽可能>>MSS/RTT
- 应该尽快加速，到达希望的速率
指数性增加CongWin
- 每经过一个RTT， CongWin加倍 <—> 每收到一个ACK时，CongWin加1MSS (这两个概念是一致的)
- 慢启动阶段：只要不超时或3个冗余ack 且 cwnd < sstresh，每经过一个RTT，CongWin *= 2
- 在丢包之前，当cwnd达到sstresh，进入拥塞避免阶段，cwnd线性增长
- ssthresh : 上次发生超时时的窗口的一半
SS总结: 初始速率很慢，但是加速却是指数性的
- SS时间很短，长期来看可以忽略
- 慢启动阶段并不慢
AIMD
- AMID : Additive-Increase , Multiplicative-Decrease
- TCP拥塞控制常被称为加性增，乘性减的拥塞控制方式
cwnd窗口大小随时间：锯齿形
慢启动阶段忽略不计，因为很快
- TCP拥塞控制常被称为加性增，乘性减的拥塞控制方式
加性增
拥塞避免
- 还没发生拥塞
- 当cwnd > ssthresh时，进入拥塞避免
- 一个RTT如没有发生丢失事件 ,将cwnd加1MSS(为了探测)
- 一个RTT如没有发生丢失事件 ,将cwnd加1MSS(为了探测)
快速恢复
不知道该不该放在加性增下面 我觉得应该反正放在这个下面
参考小林coding & 自顶向下 & 郑老师
- 快速重传的拥塞发生 和 快速恢复算法 搭配使用
- 快速恢复算法是认为，你还能收到 3 个重复 ACK 说明网络也不那么糟糕，所以没有必要像 RTO 超时那么强烈。
- 如拥塞发生所说
- cwnd = cwnd/2
- ssthresh = cwnd;
- 然后，进入快速恢复算法如下
- cwnd = ssthresh + 3 （ 3 的意思是确认有 3 个数据包被收到了）；
- 如果再收到重复的 ACK，那么 cwnd 增加 1；
- 如果收到新数据的 ACK 后，把 cwnd 设置为第一步中的 ssthresh 的值
- 原因是该 ACK 确认了新的数据，说明从 duplicated ACK 时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态
乘性减
拥塞发生
发生拥塞时
根据是快速重传还是超时重传区分拥塞发生算法
- 当收到3个重复的ACKs: 不进入慢启动阶段
- cwnd /= 2
- ssthresh = cwnd
- 进入快速恢复阶段 / 或者仅仅就是cwnd线性增长
- 当超时事件发生时: 进入慢启动阶段
- ssthresh = cwnd / 2
- cwnd = 1 MSS，进入SS阶段
- 3个重复的ACK表示网络还有一定的段传输能力
超时之前的3个重复的ACK表示“警报” : 即将发生拥塞
故收到三个重复ACK并不会使得cwnd = 1
总结
- 当CongWin＜Threshold, 发送端处于慢启动阶段（slow-start）, 窗口指数性增长.
- 当CongWin > Threshold, 发送端处于拥塞避免（congestion-avoidance）, 窗口线性增长.
- 当收到三个重复的ACKs (triple duplicate ACK),
- Threshold设置成 CongWin/2
- 进入快速恢复 , CongWin=Threshold+3.
- 当超时事件发生时timeout,
- Threshold=CongWin/2
- CongWin=1 MSS，进入 SS慢启动阶段
状态机
TCP公平性
- 公平性目标:
- 如果 K个TCP会话分享一个链路带宽为R的瓶颈，每一个会话的有效带宽为 R/K
- 如果 K个TCP会话分享一个链路带宽为R的瓶颈，每一个会话的有效带宽为 R/K
- 为什么公平 ?
- 因为拥塞控制算法
- 2个竞争的TCP会话:
- 加性增加，斜率为1, 吞吐量增加
- 乘性减，吞吐量比例减少
