计算机网络-拥塞控制

1、计算机网络原理第六章拥塞控制徐 晶技大学电子信息与通信学院互联网技术与工程2015年12月华http:/xujing/TCP 设计:问题及解决方案基于不可靠IP的复杂协议设计的-2-No.问题及解决方案1连接建立建立: 三次握手终止: 四次握手2超时定时器问题采用Jacobson/ Karels算法估计RTT3分组乱序到达基于窗口的缓存管理4流量控制通过AdvertisedWindow通告实现基于窗口的流量控制5拥塞控制6协议扩展TCP首部的Seq和AdvertisedWindow字段扩展7傻瓜窗口症状Nagle 算法: 基于ACK自计时TCP可靠传输的新Too many TCP connec

2、tions bringtoo much traffic to theermediate router-3-拥塞当网络负载持续大于其承载能力则发生拥塞拥塞现象的体现持续的分组丢失分组时延不断增加-4-拥塞控制和资源分配拥塞控制和资源分配是同一事物的两个方面.用户的观点主机到主机, 端到端协议网络的观点多个流竞争资源资源: 交换机或路由器的缓存, 链路的带宽拥塞: 过多的分组竞争同一条链路, 队列溢出导致分组丢弃如何在竞争的用户之间合理有效的分配资源?-5-拥塞控制和资源分配拥塞控制和资源分配是同一事物的两个方面.如果网络承担积极主动角色资源分配预先进行网络资源分配, 例如, 调度哪一个虚电路占用

3、物理链路如果网络承担消极拥塞控制角色允许发送方想发多少数据就发多少数据, 当拥塞发生时进行恢复-6-第6章资源分配:-7-第6章. 拥塞控制及资源分配问题: 资源分配6.1 资源分配中6.3 TCP 拥塞控制6.6 总结-8- 网络模型分组交换网无连接流会话开始时无资源预留流可以有不同粒度的定义(进程到进程, 源主机到目的主机, 等.)服务模型最大努力交付: 所有分组采用相同的方式处理9资源分配机制的分类以路由器为中心vs.以主机为中心以路由器为中心: 路由器决定什么时候转发分组, 丢弃哪些分组, 通知主机允许的发送速率以主机为中心: 端主机观测网络状态以路由器为中心和以主机为中心并不完全相互

4、排斥基于预留方式 vs. 基于反馈方式基于预留方式: 事先预留资源, 如果资源无法获得则流基于反馈方式: 端主机在未预留任何容量的情况下发送数据显式或隐式反馈基于窗口方式 vs. 基于速率方式基于窗口方式: 采用与可靠传输相同的窗口机制基于速率方式: 接收方或网络控制速率10网络负载和拥塞分组丢弃膝盖吞吐量缓慢增加时延开始快速增大kneecliff拥塞悬崖吞吐量开始快速减少直至为负载0 (拥塞)时延趋近于无穷大负载时延吞吐量拥塞控制和避免增加路由器的缓存无法避免拥塞避免拥塞的方式源端减少负载 短期流量工程 长期不断增加链路的容量 长期kneecliff拥塞Load拥塞控制拥塞控制吞吐量拥塞控制

5、行为基于主机的拥塞控制-13-基于路由器的拥塞控制第6章拥塞控制及资源分配-14-策略路由器主机章节基于主机的拥塞控制FIFO排队TCP 拥塞控制6.2, 6.3基于路由器的拥塞控制主动队列管理(AQM)TCP 拥塞控制资源分配和拥塞避免资源预留提供QoS6.5第6章. 拥塞控制及资源分配问题: 资源分配6.1 资源分配中6.3 TCP 拥塞控制6.3.1 累次增加/成倍减少6.3.2 慢启动6.3.3 快速重传和快速恢复6.6 总结-15-TCP 拥塞控制TCP源端调整发送速率以避免网络过载考虑网络的可用容量两个基本问题如何察觉网络拥塞?以超时作为网络拥塞的标志如何调整发送速率?一个Cong

6、estionWindow 变量TCP-16-17TCP拥塞窗口每一个TCP的发送方一个拥塞窗口给定时间内允许传送的最大数据量 (未确认的)自适应拥塞窗口分组丢失时减少: 退让成功传送时增加: 乐观的探索总是努力找到合适的传送速率Tradeoff优点: 不需要专门的网络反馈机制缺点: 持续在“合适”的速率上下波动18接收窗口vs. 拥塞窗口流量控制避免快速发送方使慢速接收方过载拥塞控制避免多个发送方使网络过载不同的概念, 但是采用类似的机制TCP 流量控制: 接收窗口TCP 拥塞控制: 拥塞窗口发送方TCP窗口 =min 拥塞窗口, 接收窗口 196.3.1累次增加/成倍减少(AIMD)如何自适

7、应变化?累次增加: 分组成功传送, 将窗口大小增加一个最大数据段大小 (MSS)成倍减少: 一旦分组丢失, 则将拥塞窗口减半减小拥塞窗口的速度比加大窗口要快得多!窗口过大 (导致分组丢失) 比 窗口过小 (使得吞吐量减少) 危害大的多AIMD: TCP稳定的必要条件20TCP “锯齿”窗口大小丢失减半t21新的数据流如何启动?慢启动(较小的CWND)避免网络过载窗口大小丢失减半t但是, 从头开始时需要一个很长的时间!6.3.2 慢启动问题从头开始时, 累次增加需要很长的时间才能延续接采用一种更快速的方法解决方案初始时设臵 拥塞窗口 为一个分组以指数方式有效增加窗口大小直到分组丢失-22-23慢

8、启动与TCP锯齿窗口大小丢失减半t指数 “慢启动”这种称呼（”慢”）是因为最初TCP无拥塞控制机制- 源端启动时发送整个AdvertisedWindow- 导致拥塞!累次增加vs. 慢启动-24-25TCP的两种丢弃超时分组n丢失, 超时定时器超时何时? n 是窗口的最后一个分组, 或者所有发送分组均丢失超时后, 大的CWND会导致更严重的分组丢失以较小的CWND重新开始三个重复的ACK分组n丢失, 但是分组 n+1, n+2, 等到达如何检测? 接收方多次通过ACK表示期望接收分组n何时? 收到分组n后续分组收到三个重复的ACK后, 发送方快速重传分组n倍数减少后累次增加三次重复ACK-26

9、-6.3.3 快速重传原始重传等待超时时会有很长一段时间连接无效知道第一个分组丢失观测重复ACKs分组丢失乱序到达解决方案快速重传: 如果源端收到三个重复的ACKs则不需要等待超时而快速重传-27-快速恢复先前, 快速重传后慢启动快速恢复去除快速重传与累次增加之间的慢启动阶段设臵 CongestionWindow 为先前的一半(成倍较少)cwnd拥塞避免慢启动在稳定状态下, CongestionWindow 在最优窗口大小附近振荡Time-28-TCP拥塞控制示例-29-TCP的发展RFC 793 (1981)基于简单滑动窗口的流量控制机制.Tahoe (1988)慢启动, 拥塞避免, 快速重

10、传.Reno (1990)快速恢复.新版Reno (1995)对快速重传进行了修订.-30-TCP的发展Sl ow start + co ng esti on a vo id an SW S a vo id a nce / Na gl e,DSACKL arg er in it i al win d owNe wRen oBa si csRT Oca lcu la t io n,de la yed ACKRF C 28 83RT O0 7 / 20 0 0RF C 79 3RF C 11 22RF C 13 23RF C 20 18RF C 29 88RF C 33 90RF C 37 820

11、 9 /19 8 11 0 /19 8 90 5 / 19 9 21 0 / 1 99 61 1 / 20 0 01 0 / 20 0 20 4 / 20 0 4RF C 25 810 4 / 19 9 9RF C 30 420 1 / 20 0 1RF C 35 170 4 / 20 0 3SAC K-blo ss recoRF C 31 68F u ll spe ci f i ca t io n ofL im it e d T ra nsm itSl ow start,0 9 / 20 0 1con ge st io n avoi da nce ,F R / F RECN-31-TCP R

12、eno及扩展TCP Reno最流行的TCP实现集成AIMD, 慢启动, 快速重传和快速恢复其他扩展选择性ACK机制: TCP SACK显式的拥塞通知: ECN基于时延的拥塞避免: TCP Vegas-32-第6章. 拥塞控制及资源分配问题: 资源分配6.1 资源分配中6.3 TCP 拥塞控制6.3.1 累次增加/成倍减少6.3.2 慢启动6.3.3 快速重传和快速恢复6.6 总结-33-拥塞控制拥塞是不可避免的ernet中不会预先进行资源分配基于主机vs.基于路由器的拥塞控制TCP 拥塞控制采用分组丢失作为拥塞的判别标示发送方采用CongestionWindow 适应网络累次增加, 成倍减少慢启动, 缓慢开始重启-34-TCP 设计: 问题及解决方案-35-No.问题及解决方案章节1连接建立建立: 三次握手终止: 四次握手5.2.32超时定时器问题采用Jacobson/ Karels算法估计RTT5.2.63