拥塞控制
何谓拥塞(Congestion)
- 非正式定义 : 大量发送主机发送了太多数据,亦或者发送速度过快以至于网络无法处理
- 具体表现 :
- 分组丢失(路由器缓存溢出)
- 分组延迟过大(在路由器缓存中排队)
- 拥塞控制 VS 流量控制
- A top-10 problem
拥塞的成因和代价
场景1
- 两个senders,两个receivers
- 一个路由器,无限缓存
- 没有重传
- 拥塞时分组延迟太大
- 达到最大throughput
场景2
- 一个路由器,有限buffers
- Senders重传分组
- 情况a : Sender能够通过某种机制获得路由器buffer信息,与空闲才发λin>λout(goodput)
- 情况b : 丢失后才重发 : λ’in>λout
- 情况c : 分组丢失和定时器超时后都重发,λ’in变得更大
- 拥塞的代价:
- 对给定的"goodput",要做更多的工作(重传)
- 造成资源的浪费
场景3
question : 随着λin和λ’in不断增加会怎样?
- 四个发送发
- 多跳
- 超时/重传
- 拥塞的另一个代价:
- 当分组被drop时,任何用于该分组的"上游"传输能力全被浪费掉
拥塞控制的方法
端到端拥塞控制
- 网络层不需要显式的提供支持
- 端系统通过观察loss,delay等网络行为判断是否发生拥塞
- TCP采取这种方法
网络辅助的拥塞控制
- 路由器向发送方显示地反馈网络拥塞信息
- 简单的拥塞指示(1bit) : SNA,DECbit,TCP/IP ECN,ATM
- 指示发送发应该采取何种速率
案例 ATM ABR 拥塞控制
- ABR : available bit rate
- “弹性服务”
- 如果发送方路径"underloaded" 使用可用带宽
- 如果发送方发送路径拥塞,将发送速率降到最低保障速率
- RM(Resource Management) cells
- 发送方发送
- 交换机设置RM cell 位(网络辅助)
- NI bit : rate 不许增长
- CI bit : 拥塞指示
- RM cell 由接收方返回给发送方
- 在RM cell 中有显式的速率(ER)字段 : 两个字节
- 拥塞的交换机可以将ER置为更低的值
- 发送方获知路径所能支持的最小速率
- 数据cell中的EFCI位 : 拥塞控制的交换机将其设为1
- 如果RM cell 前面的data cell 的EFCI位被设为1,那么发送方在返回的RM cell 中置CI位数
拥塞控制的基本原理
- Sender限制发送速率
LastByteSent - LastByteAcked <= CongWin
- CongWin
- 动态调整以改变发送速率
- 反映所感知到的网络拥塞
question 1 : 如何感知网络拥塞?
- Loss事件=timeout 或 3个重复 ACK
- 发生loss事件后，发送方降低 速率
question 2 : 如何合理地调整发送速率?
- 加性增 —乘性减: AIMD
- 慢启动: SS
加性增 —乘性减: AIMD
- 原理：逐渐增加发送速率，谨慎探测可用带宽，直到发生loss
- 方法: AIMD
- Additive Increase: 每个RTT 将CongWin增大一个MSS——拥塞避免
- Multiplicative Decrease: 发生loss后将CongWin减半
TCP慢启动 : SS
- TCP连接建立时,CongWin=1
example:
MSS = 500 byte,
RTT = 200 msec
初始化速率 initial rate = 20k bps- 可用带宽可能远远高于初始速率
- 希望快速增长
- 原理 : 当连接开始时,指数性增长
- 核心算法
initialize: Congwin = 1;
for (each segment ACKed)
Congwin ;
until (loss event ORCongWin > threshold);- 指数性增长
- 每个RTT将CongWin翻倍
- 收到每个ACK进行操作
- 初始化速率很慢,但是快速攀升
Threshold变量
question : 何时应该由指数性增长切换为线性增长(拥塞避免)?
answer : 当CongWin达到loss事件值的1/2时
- 实现方法
- 变量Threshold
- Loss事件发生时,Threshold被设为Loss事件前CongWin值的1/2
Loss事件的处理
- 3个重复ACKs
- CongWin切到一半
- 然后线性增长
- Timeout事件 :
- CongWin直接设为1个MSS
- 然后指数增长
- 达到threshold后,再线性增长
- 二者比较
- 前者表示网络还能够传输一些segment
- 后者表明拥塞更为严重
拥塞控制总结
- When CongWin is below Threshold, sender in slow-start phase, window grows exponentially.
- When CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly
- When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Threshold
- When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS
- 当CongWin低于阈值时，发送器处于缓慢启动阶段，窗口呈指数级增长。
- 当CongWin高于阈值时，发送方处于拥塞避免阶段，窗口线性增长
- 当出现三重重复ACK时，Threshold设置为CongWin/2，CongWin设置为Threshold
- 发生超时时，阈值设置为CongWin/2，CongWin设置为1 MSS
拥塞控制算法
例题
TCP性能分析
TCP throghput : 吞吐率
- 给定拥塞窗口大小和RTT，TCP的平均吞吐率是多少?
- 忽略掉Slot start
- 假定发生超时时CongWin的大小为W，吞吐率是W/RTT
- 超时后，CongWin=W/2，吞吐率是W/2RTT
- 平均吞吐率为：0.75W/RTT
未来的TCP
举例：每个Segment 有1500 个byte, RTT 是100ms，希望获得 10Gbps的吞吐率
- throughput = WMSS8/RTT, 则 W=throughputRTT/(MSS8)
- throughput=10Gbps, 则W=83,333
- 窗口大小为83,333
- 吞吐率与丢包率(loss rate, L)的关系
- 高速网络下需要设计新的TCP
TCP的公平性
- TCP协议具备公平性
- 如果 K 个TCP Session共享相同的瓶颈带宽 R，那么每个Session的平均速率 为R/K
- 公平性与UDP
- 多媒体应用通常不使用TCP， 以免被拥塞控制机制限制速率
- 使用UDP：以恒定速率发送， 能够容忍丢失
- 产生了不公平
- 研究：TCP friendly
- ** 公平性与并发TCP连接 **
- ** **某些应用会打开多个并发连接
- Web浏览器
- 产生公平性问题
- 例子：链路速率为 R，已有 9 个 连接
- 新来的应用请求 1 个TCP，获得 R/10的速率
- 新来的应用请求11 个TCP，获得 R/2的速率
