TCP协议(下)

拥塞控制

何谓拥塞(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的速率