怎么创建网站教程,苏州电信网站备案,建设工程职称论文查询网站,环保设备网站源码参考资料
https://github.com/ituring/tcp-book
流量控制、窗口控制和拥塞控制的关系
流量控制、窗口控制和拥塞控制的关系如图所示 窗口控制是上层的概念#xff0c;核心思路是基于滑动窗口技术传输数据。而确定发送窗口大小的方法有流量控制和拥塞控制两种
流量控制核心思路是基于滑动窗口技术传输数据。而确定发送窗口大小的方法有流量控制和拥塞控制两种
流量控制指的是根据接收方告知的可接收和处理的最大窗口大小rwnd计算出发送窗口大小swnd。是一种被动控制。拥塞控制则是指调整拥塞窗口大小以在确保不出现网络拥塞的前提下尽可能高效率地传输数据。是一种主动控制。
最后都是比较rwnd和cwnd的大小选择其中较小的值用作swnd。
什么是拥塞控制
拥塞控制的前提是“完全不清楚网络内部的情况”所以需要通过丢包或延迟来获取网络内部情况
最典型的算法是基于丢包的算法也就是以TCP报文段的丢失为契机调整控制方法。如果没有TCP报文段丢失就认为网络比较空困可以提高数据传输量与之相对如果有TCP报文段丢失就认为网络比较拥堵需要减少数据传输量。基于丢包的算法通过反复增减传输数据量完成通信。只要没有TCP报文段丢失就一直增加数据传输量然后根据TCP报文段丢失的出现来判断通信链路的处理极限。其他的拥塞控制算法包括采用RTT的基于延迟的算法还有把基于延迟和基于丢包结合在一起的混合型控制方法。
拥塞控制主要通过以下机制调整cwnd大小
慢启动。在慢启动的过程中cwnd呈指数级增大但是如果发生重传后仍旧按照慢启动的逻辑发送数据包可能会导致再次拥塞拥塞避免。在进行重传时该算法将慢启动阈值ssthreshslowstartthreshold设置为cwnd值的一半当cwnd增大到ssthresh之后再减小每次收到ACK之后拥塞窗口的增大幅度快速恢复。如果发送方以收到重复ACKduplicateACK为契机判断出现了轻度拥寒并进行重传控制快速重传但是如果仍旧按照慢启动的逻辑会导致吞吐量骤降。在发生快速重传后将cwnd减半3。在收到重传报文的ACK之前每收到重复的ACK都让cwnd增加1。收到重传报文之后再进入拥塞避免状态。
拥塞算法的设计思路
拥塞算法要兼顾如下两个方面 提升传输量使其尽可能接近拥塞的临界值 在检测到拥塞之后重新开始传输数据时不过度降低传输量
报文的重传既需要考虑可靠也需要考虑效率判断报文段丢失主要是参考超时或收到重复ACK因此重传控制算法也包括
基于重传计时器的超时控制。确定合适的RTO超时重传时间非常重要。值过大会导致传输效率过低值过小会导致频繁进行不必要的重传。RTO需要根据RTT进行计算但是从数据发送出去开始到收到ACK为止的往返时间RTT非常容易受到网络拥堵情况、链路长短等因素的影响。使用重复ACK
总结TCP拥塞算法的思路
在收到ACK之后如何增大窗口大小正常情况下、发生拥塞时如何确保准确又迅速地进行重传在检测到拥塞时如何调整窗口大小
实现以上思路的拥塞算法
使用慢启动、拥塞避免和快速重传算法的Tahoe使用快速恢复算法的Reno进一步优化了快速恢复算法的NewReno使用新窗口控制思路的Vegas
拥塞控制的基本设计
cwnd指拥塞窗口大小表示发送节点可以一次性发送且不需要等待ACK的最大可发送TCP报文段数量。而rwnd是接收窗口大小表示接收节点可接收的最大TCP报文段数量此上限值会由接收节点通知给发送节点。因此mincwndrwnd表示在同时考虑到发送节点和接收节点的情况下无须等待ACK便可以一次性发送的MSS个数 s w n d m i n ( c w n d , r w n d ) − i n f l i g h t swndmin(cwnd,rwnd)-inflight swndmin(cwnd,rwnd)−inflight TCP拥塞控制算法采用有限状态机finitestatemachine根据情况使用不同的cwnd计算公式见tcp是怎么样工作的p108 Open也就是正常状态。包括Slowstart和Congestionavoidance状态。收到全新ACK时的cwnd计算公式在不同的拥塞控制算法中有所不同。Disorder在Open状态下如果连续收到2次重复的ACK便进入此状态。此时可能发生了轻微的网络拥塞。如果再次收到重复的ACK便迁移到Recovery状态。从Disorder进入Recovery状态时ssthresh和cwnd的计算公式在不同的拥塞控制算法中也有所不同。Recovery在Open状态下如果连续收到3次重复的ACK便进入此状态。此时很可能发生了严重的网络拥塞。在Recovery状态下如果收到全新的ACK则进入Open状态。CWR收到ECN显式拥塞通知后进入此状态。具体运行与Loss状态没有区别。LOSSRTT的值比超时重传时间RTO大也就是说是检测到ACK超时但尚未收到新ACK的状态。此时可能发生了严重的网络拥塞。 一些具有代表性的拥塞算法和相互关系 白底的是基于丢包的算法黑底的是基于延迟的算法灰底的则是混合型算法 拥塞控制算法
拥塞算法要根据效率和可靠性以及网络链路的特性来选择最合适的
NewReno算法
NewReno针对Reno进行了改良通常被当作拥塞控制算法的参考模型。与NewReno的亲和性一般被称为TCP友好性或TCP兼容性。
NewReno及其后的部分基于丢包的拥塞控制算法可以概括为AIMDAdditiveIncrease/MultiplicativeDecrease加法增大/乘法减小。AIMD是拥有以下特点的拥塞控制算法的总称
在Open状态下拥有Slowstart和Congestionavoidance两种子状态。 在Slowstart状态下cwnd呈指数性增大的趋势。在Congestionavoidance状态下cwnd呈线性增大的趋势(additive increase) 在迁移到Recovery状态时以常数因子小于1对cwnd进行缩放multiplicative decrease。
NewReno拥塞算法示例伪代码如下对于NewRenoα1β0.5 NewReno实际上是基于丢包的拥塞控制算法以拥塞事件为契机调整数据发送量从原理上来说是无法避免拥塞的发生的 Vegas算法
Vegas算法根据RTT推算得到的通信链路上的缓存量Diff作为唯一指标来调整数据发送量。Diff cwnd/RTTbase - cwnd/RTT 进入拥塞避免阶段后cwnd和RTT保持稳定是Vegas算法最显著的特征 Veno算法
NewReno等过去的AIMD算法由于无法将随机丢包引起的与拥塞无关的重复ACK与拥塞引起的重复ACK区分开来所以一直存在无线通信发送速率过低的问题。因此Veno使用Vegas算法所引入的Diff来预测拥塞程度来规避这个问题
在处于Congestionavoidance状态且N ≥ βveno时由于通信链路中缓存了较多数据所以每收到2次ACK只会更新1次cwnd值。 当状态往Recovery迁移时的计算公式可用以下伪代码表示。当Nβveno时、由于通信链路中缓存的数据量比较少可以认为重复ACK是因为无线通信中的随机丢包引起的可以控制ssthresh的减小量避免发送速率过低。 BIC算法
BICBinaryIncreaseCongestioncontrol于2004年提出是一个面向长肥管道的基于丢包的拥塞控制算法。
Scalable和HighSpeed都是面向长肥管道的算法但它们都有着RTT公平性RTTfairness较差的问题。所谓的RTT公平性指的是当RTT不同的多个网络流并存时它们之间可以公平地分配带宽的特性。特别是Scalable的RTT公平性极差RTT较小的网络流甚至会独占全部的带宽。这主要是cwnd呈指数级增长两个网络流的cwnd之间的差距不断拉大所造成的结果。
BIC是通过二分搜索binarysearch寻找最佳cwnd的算法。将状态迁移到Recovery之前的cwnd值作为Wmax使用当前的cwnd与Wmax中间的值作为新的cwnd。
YeAH算法
YeAHYetAnotherHighspeed于2007年提出是一个面向长肥管道的混合型拥塞控制算法。YeAH通过分别使用Slow和Fast两种模式可以同时满足以下所有条件
长肥管道下带宽利用率高规避cwnd急剧增长给网络带来的过多负担可以与Reno公平地分享带宽与Reno的亲和性可以与RTT不同的网络流公平地分享带宽RTT公平性在随机丢包方面鲁棒性高即使存在缓冲区较小的链路也可以发挥较高的性能
CUBIC算法
为什么NewReno算法不适用与长肥管道
Reno的缺陷是由于快速恢复阶段的快速重传算法是即使有1个数据包被废弃也会进人重传模式导致数据包发送停止所以当发生连续丢包时吞吐量会大幅下降。针对这一问题NewReno进行了改良即在每次的重传模式下重传多个数据包。开发Reno和NewReno的核心目的就是防止在拥塞发生时拥塞窗口大小变得过小进而避免出现吞吐量过低的情况。
端到端之间的三大时延包括处理时延、队列时延和传播时延。
因链路上的交换机和路由器进行数据包处理而产生的处理时延processingdelay因在链路上各个节点的队列中等待传输而产生的队列时延queuingdelay从信号发送节点到目的地节点所需要的物理上的传播时延propagationdelay。关于传播时延我们通常认为它在无线信号下约为3.33us/kmus是microsecond的缩写表示“微秒”而在光纤中约为5us/km。
在三大时延中处理时延和队列时延可以通过提高通信节点的性能实现进一步的优化而传播时延则只取决于传输距离因此超远程节点间的通信往往无法忽视物理特性所导致的传播时延。这种宽带、高时延的通信环境就被称为长肥管道。
NewReno算法在长肥管道中存在的问题包括
无法有效利用带宽。与在窄带环境下相比在宽带环境下拥塞窗口大小相对于线路传输率wire rate传输链路上的最大数据传输速度进行恢复的时间会被拉长无法有效地利用带宽。发送速率不足Tcp标准通过协商窗口扩大选项来增加拥塞窗口大小RTT增大时通信线路长在拥塞窗口大小不变的情况下通信环境的时延越大吞吐量也就越小。
NewReno算法的基本逻辑时AIMD控制算法即在发生丢包之前缓慢地增大拥塞窗口大小additiveincrease加法增大拥塞发生之后大幅减小拥塞窗口大小multiplicativedecrease乘法减小公式如下 而针对长肥管道提出的算法有HighSpeed与 Scalable逻辑如下
根据拥塞窗口大小调整AIMD控制中的变量α和β。当拥塞窗口大小小于一定的國值时α和β的值与NewReno中的一样而当拥塞窗口大小超过了这个阈值时α和β的值就用拥塞窗口大小的函数来表示。此时拥塞窗口大小越大α的值就越大而对应的β值就越小实现cwnd快速增大和减小之后的快速恢复。
HighSpeed与 Scalable存在的问题
但是HighSpeed与 Scalable也存在如下问题 亲和性问题与旧算法的公平性。当多个tcp流同时使用HighSpeed和NewReno算法时由于HighSpeed的积极性会导致带宽被独占。 RTT公平性。当与RTT不同的网络流共享瓶颈链路时RTT较小的网络流会占据RTT较大的网络流的生存空间。在以下网络链路中RTT较小的网络流独占带宽 BIC如何改善RTT公平性
BIC算法通过加法增大和二分搜索binary search两个阶段来增大拥塞窗口大小。 BIC以发生丢包时的拥塞窗口大小Wmax为目标根据当前的拥塞窗口大小切换阶段。 当拥塞窗口大小较小时使用加法增大的方法快速增大拥塞窗口大小以提高扩展性和RTT公平性。 当拥塞窗口大小变大后通过二分搜索法缓慢增大拥塞窗口大小以避免出现过多的丢包。 当拥塞窗口大小超过Wmax之后会进人Maxprobing最大值搜素阶段。这个阶段拥塞窗口大小的增长函数的曲线与拥塞窗口大小增长到W之前的曲线完全对称同时拥塞窗口大小遵循新的曲线继续增长直到发现下一次丢包。
CUBIC算法要解决的问题
CUBIC的出现解决了一系列问题。其中主要有现有算法与宽带、高时延环境的适应性扩展性这个老问题还有不同RTT的网络流之间吞吐量公平性的问题以及与现有拥塞控制算法的亲和性问题等。
BIC在窄带、低时延的网络环境下会不当地占有带宽。此外由于BIC的拥塞窗口大小的增大算法分为加法增大、二分搜索和Maxprobing等多个阶段所以协议的解析十分复杂而且性能预测和网络设计也十分困难。
CUBIC默认搭载在Linux2.6.19以后的版本中
$ sysctl net.ipv4.tcp_congestion_control
net.ipv4.tcp_congestion_control cubic
$ cat /proc/sys/net/ipv4/tcp_congestion_control
cubicCUBIC通过将BIC拥塞窗口大小的增长函数替换为三次函数cubic function省去了阶段切换实现了算法的简化。
拥塞窗口大小的增大量只由两个连续的拥塞事件之间的时间间隔决定换句话说这意味着“拥塞窗口大小的增大速度与RTT无关”能够提升RTT公平性。
CUBIC使用以“快速恢复开始后的经过时间”为自变量的三次函数近似模拟了BIC中复杂的拥塞窗口大小控制。 拥塞窗口增长函数公式如下 W代表发现丢包时的拥塞窗口大小。C是CUBIC参数t是从快速恢复阶段开始的经过时间。K是决定拥塞窗口大小增大速度的参数通过以下公式计算B代表的是丢包时拥塞窗口大小的减小量。 BBR算法
近些年来路由器等网络设备中的缓冲区存储容量不断增大。包含CUBIC算法在内的那些过去的拥塞控制算法在缓冲区时延增大的情况下出现了吞吐量下降的问题。针对此问题谷歌在2016年9月发布了新的拥塞控制算法BBR。它属于基于延迟的拥塞控制算法以RTT作为指标增减拥塞窗口大小。
网络设备的缓冲区增大好处就是更不容易出现网络去包。这种爆发性网络流量下更不容易出现丢包的特性称为爆发耐性。
如果缓冲区过小就很容易超出缓冲区大小的上限使缓冲区溢出并发生丢包。此时只要到达的网络流TCP网络流使用的是之前介绍的基于丢包的拥塞控制算法吞吐量就会在每次发生丢包时减小。即使拥塞窗口大小很小如果网络流碰巧与其他的网络流同时到达网络设备这种情况同样可以视作爆发性的网络流量也会导致数据包被废弃即使网络流的传输速率很低。
如果增大缓冲区就不容易发生此类问题网络通信也会更加稳定
但是缓冲区增加会导致排队时延增大RTT增大会导致吞吐量降低拥塞窗口不变时
基于丢包的拥塞控制与缓冲区膨胀的关系
随着缓冲区时延的增大数据到达所需要的端到端时延会增大而ACK的到达也会随之推迟最终的结果就是数据的发送间隔变长吞吐量下降。根据缓冲区容量与RTO超时重传时间的大小关系可能会出现数据包在链路上的缓冲区中停留的时间超过RTO导致数据重传的情况。
近些年来随着数据传输可靠性错误少的提升缓冲区溢出成了数据丢包的主要原因。只基于丢包的拥塞控制算法是以丢包作为判断拥塞的指标。因此只要不发生丢包就会一直增大拥塞窗口大小。
一方面如果网络链路上的缓冲区较小就会因缓冲区溢出而频繁发生丢包另一方面随着缓冲区增大不再容易溢出但是发出的数据包会将网络中的各台设备的缓冲区填满带来的影响是RTT增大。
TCP网络流本身会引起缓冲区膨胀缓冲区膨胀又会反过来影响TCP网络流自身。考虑到因为超时而进行重传等情况可以断言基于丢包的拥塞控制算法更容易使时延增大 RTT的增大有可能是三种时延之一增加但是基于延迟的拥塞控制认为链路上RTT增大的原因是队列时延增大导致的。因此此类拥塞控制算法的基本逻辑就是在RTT较小时增大拥塞窗口大小而在RTT较大时减小拥塞窗口大小。
vegas的解决方案和存在的问题
以下是vegas拥塞窗口大小的计算公式 d是往返的传播时延Dt)代表实际测试到的RTT。也就是说w(1)/d是期望吞吐量wt)/D(t)是时刻t的实际吞吐量拿它们的差值与阈值α进行比较然后根据结果来增减wt)的值。
在使用Vegas的情况下RTT、吞吐量完全与缓冲区大小无关并保持一定值不变。
但是由于Vegas的积极性非常低当RTT增大之后它很快就会减小拥塞窗口大小非常容易被基于丢包的拥塞算法抢占
BBR算法的机制
BBR的基本思路是过去主流的基于丢包的拥塞控制算法以发现丢包为契机来判断发生了拥塞的做法过于迟钝因此它将“数据包被缓存之前”也就是“网络带宽被占满但没有缓冲区时延”的状态作为理想状态。
BBR使用RTpropRound-Trippropagationtime往返传播时延和BulBwBottleneckBandwidth.瓶颈带宽两个指标来调节拥塞窗口大小。
RTprop其实就是RTT它是使用ACK计算出来的数值。BtIBw则是瓶颈链路的带宽.使用该指标是因为就算TCP网络流在传输中会经过若干个链路但决定其最终吞吐量的仍然是瓶颈链路的转发速度。 BBR的目标是“inflightBtlBw×RTprop”这一状态其值称为BDPBandwidth-DelayProduct带宽时延积。根据计算此时的数据发送量正好达到BtlBw这一阈值。
BBR监测数据发送量和RTT的值把控两者之间的关系同时调节数据发送速度以在网络最大可处理的范围内提高吞吐量。最终效果是既能充分利用网络带宽又没有缓冲区时延。
