CUBIC:A New TCP-Friendly High-Speed TCP Variant∗
Sangtae Ha,Injong Rhee Dept of Computer Science North Carolina State University Raleigh,NC27695 {sha2,rhee}@ncsu.edu
Lisong Xu
Dept of Comp.Sci.and Eng.
University of Nebraska Lincoln,Nebraska68588
xu@c.unl.edu
ABSTRACT
CUBIC is a congestion control protocol for TCP(transmis-sion control protocol)and the current default TCP algo-rithm in Linux.The protocol modifies the linear window growth function of existing TCP standards to be a cubic function in order to improve the scalability of TCP over fast and long distance networks.It also achieves more eq-uitable bandwidth allocations amongflows with different RTTs(round trip times)by making the window growth to be independent of RTT–thus thoflows grow their conges-ti
on window at the same rate.During steady state,CUBIC increas the window size aggressively when the window is far from the saturation point,and the slowly when it is clo to the saturation point.This feature allows CUBIC to be very scalable when the bandwidth and delay product of the network is large,and at the same time,be highly stable and also fair to standard TCPflows.The implementation of CUBIC in Linux has gone through veral upgrades.This paper documents its design,implementation,performance and evolution as the default TCP algorithm of Linux. 1.INTRODUCTION
As the Internet evolves to include many very high speed and long distance network paths,the performance of TCP was challenged.The networks are characterized by large bandwidth and delay product(BDP)which reprents the total number of packets needed inflight while keeping the bandwidth fully utilized,in other words,the size of the con-gestion window.In standard TCP like TCP-Reno,TCP-NewReno and TCP-SACK,TCP grows its window one per round trip time(RTT).This makes the data transport speed of TCP∗ud in all major operating systems including Win-dows and Linux rather sluggish,to say the least,extremely under-utilizing the networks especially if the length offlows is much shorter than the time TCP grows its windows to the full size of the BDP of a path.For instance,if the band-width of a network path is10Gbps and the RTT is100ms, with packets of1250byt
es,the BDP of the path is around 100,000packets.For TCP to grow its window from the mid-point of the BDP,say50,000,it takes about50,000RTTs which amounts to5000conds(1.4hours).If aflowfinishes before that time,it verely under-utilizes the path.
To counter this under-utilization problem of TCP,many
even if the protocol makes mistakes infinding the max win-dow,itfinds the next max window near the previous max pointfirst,thus staying at the previous saturation point longer.But the exponential function quickly catches up and its increment becomes very large if the loss do not occur (in which ca,the saturation point has become much larger than the previous one).Becau it stays longer near the pre-vious saturation point than other variants,it can be slug-gish tofind the new saturation point if the saturation point has incread far beyond the last one.BIC-TCP,however, safely reacts fast to reduced capacity becau packet loss occur before the previous max and it reduces the window by a multiplicative factor.This tradeoffis a design choice of BIC-TCP.It is known[31]that available bandwidth in the Internet change over a long time scale of veral hours. Given that packet loss would occur very asynchronously and also proportionally to the bandwidth consumption of a flow under a highly statistically multiplexed environment, fast convergence is a natural conquence of the network en-vironment–something the protocol does not have to force. Thus,although BIC-TCP
may converge slowly under low statistical multiplexing where only a fewflows are compet-ing,its convergence speed is not an issue under typical In-ternet environments.
CUBIC[27]is the next version of BIC-TCP.It greatly sim-plifies the window adjustment algorithm of BIC-TCP by re-placing the concave and convex window growth portions of BIC-TCP by a cubic function(which contains both concave and convex portions).In fact,any odd order polynomial function has this shape.The choice for a cubic function is incidental and out of convenience.The key feature of CU-BIC is that its window growth depends only on the real time between two concutive congestion events.One congestion event is the time when TCP undergoes fast recovery.We call this real time a congestion epoch.Thus,the window growth becomes independent of RTTs.This feature allows CUBIC flows competing in the same bottleneck to have approxi-mately the same window size independent of their RTTs, achieving good RTT-fairness.Furthermore,when RTTs are short,since the window growth rate isfixed,its growth rate could be slower than TCP standards.Since TCP standards (e.g.,TCP-SACK)work well under short RTTs,this feature enhances the TCP-friendliness of the protocol.
The implementation of CUBIC in Linux has gone through veral upgrades.The most notable upgrade is the efficient implementation of cubic root calculation.Since it requires afloating point oper
ation,implementing it in the kernel re-quires some integer approximation.Initially it ud the bi-ction method and later changed to the Newton-Raphson method which reduces the computational cost almost by10 times.Another change to CUBIC after inception is the re-moval of window clamping.Window clamping was intro-duced in BIC-TCP where window increments are clamped to a maximum increment and was inherited to CUBIC for thefirst version.This forces the window growth to be linear when the target mid-point is much larger than the current window size.The authors conclude that this feature is not needed after extensive testing due to the incread stability of CUBIC.CUBIC replaced BIC-TCP as the default TCP algorithm in2006after version2.6.18.The changes and upgrades of CUBIC in Linux are documented in Table1.The remainder of this paper is organized as follows.Section 2gives related work,Section3prents the details of CU-BIC algorithms in Linux,Section4includes the evolution of CUBIC and its implementation in Linux,and Section5 includes discussion related to fairness property of CUBIC. Section6prents the results of experimental evaluation and Section7gives conclusion.
2.RELATED WORK
Kelly propod Scalable TCP(STCP)[25].The design ob-jective of STCP is to make the recovery time from loss events be constant regardless of the window size.This is why it is called“Scalable”.Not
e that the recovery time of TCP-NewReno largely depends on the current window size. HighSpeed TCP(HSTCP)[15]us a generalized AIMD where the linear increa factor and multiplicative decrea factor are adjusted by a convex fucntion of the current con-gestion window size.When the congestion window is less than some cutoffvalue,HSTCP us the same factors as TCP.Most of high-speed TCP variants support this form of TCP compatibility,which is bad on the window size. When the window grows beyond the cutoffpoint,the con-vex function increas the increa factor and reduces the decrea factor proportionally to the window size.
HTCP[28],like CUBIC,us the elapd time(∆)since the last congestion event for calculating the current conges-tion window size.The window growth function of HTCP is a quadratic function of∆.HTCP is unique in that it adjusts the decrea factor by a function of RTTs which is engineered to estimate the queue size in the network path of the currentflow.Thus,the decrea factor is adjusted to be proportional to the queue size.
TCP-Vegas[10]measures the difference(δ)between expected throughput and actual throughput bad on round-trip de-lays.Whenδis less than a low thresholdα,TCP-Vegas believes the path is not congested and thus increas the nding rate.Whenδis larger than a upper thresholdβ, which is a strong indication of congestion,TCP-Vegas re-duces the nding rate.Otherwi,TCP-Vegas maintai
ns the current nding rate.The expected throughput is cal-culated by dividing the current congestion window by the minimum RTT which typically contains the delay when the path is not congested.For each round trip time,TCP-Vegas computes the actual throughput by dividing the number of packets nt by the sampled RTT.
F AST[24]determines the current congestion window size bad on both round-trip delays and packet loss over a path.F AST updates the nding rate at every other RTT with rate-pacing.The algorithm estimates the queuing de-lay of the path using RTTs and if the delay is well below a threshold,it increas the window aggressively and if it gets clor to the threshold,the algorithm slowly reduces the increasing rate.The opposite happens when the delay increas beyond the threshold:slowly decreas the window first and then aggressively decreas the window.For packet loss,F AST halves the congestion window and enters loss recovery just like TCP.
TCP-Westwood[14]estimates an end-to-end available band-
width by accounting the rate of returning ACKs.For packet loss,unlike TCP which“blindly”reduces the congestion window to the half,TCP-Westwood ts the slow start thresh-old to this estimate.This mechanism is effective especially over wireless links where frequent channel loss are mis-interpreted as congestion loss and thus TCP reduces the congestion window unnecessarily.
TCP-Illinois[26]us a queueing delay to determine an in-crea factorαand multiplicative decrea factorβinstan-taneously during the window increment pha.Precily, TCP-Illinois ts a largeαand smallβwhen the average delay d is small,which is the indication that congestion is not imminent,and ts a smallαand largeβwhen d is large becau of imminent congestion.
TCP-Hybla[13]scales the window increment rule to ensure fairness among theflows with different RTTs.TCP-Hybla behaves as TCP-NewReno when the RTT of aflow is less than a certain reference ,20ms).Otherwi,TCP-Hybla increas the congestion window size more aggres-sively to compensate throughput drop due to RTT increa. TCP-Veno[17]determines the congestion window size very similar to TCP-NewReno,but it us the delay information of TCP-Vegas to differentiate non-congestion loss.When packet loss happens,if the queue size inferred by the delay increa is within a certain threshold,which is the strong indication of random loss,TCP-Veno reduces the congestion window by20%,not by50%.王者荣耀直接玩
元宵节花灯制作
3.CUBIC CONGESTION CONTROL
3.1BIC-TCP
In this ction,we give some details on BIC-TCP which is a predecessor of CUBIC.The main feature
of BIC-TCP is its unique window growth function as discusd in the introduc-tion.Figure1shows the growth function of BIC-TCP.When it gets a packet loss event,BIC-TCP reduces its window by a multiplicative factorβ.The window size just before the reduction is t to the maximum W max and the window size just after the reduction is t to the minimum W min.Then, BIC-TCP performs a binary arch using the two param-eters-by jumping to the“midpoint”between W max and W min.Since packet loss have occurred at W max,the win-dow size that the network can currently handle without loss must be somewhere between the two numbers. However,jumping to the midpoint could be too much in-crea within one RTT,so if the distance between the mid-point and the current minimum is larger than afixed con-stant,called S max,BIC-TCP increments cwnd by S max(lin-ear increa).If BIC-TCP does not get packet loss at the updated window size,that window size becomes the new minimum.This process continues until the window incre-ment is less than some small constant called S min at which point,the window is t to the current maximum.So the growth function after a window reduction will be most likely to be a linear one followed by a logarithmic one(marked as “additive increa”and“binary arch”respectively in Fig-ure1(a).)
铅球加油稿If the window grows past the maximum,the equilibrium window size must be larger than the current maximum and
a
(a)BIC-TCP window growth
function.
(b)CUBIC window growth function.
Figure1:Window growth functions of BIC-TCP and CUBIC.
new maximum must be found.BIC-TCP enters a new pha called“max probing”.Max probing us a window growth function exactly symmetric to tho ud in additive increa and binary arch(which is logarithmic;its reciprocal will be exponential)and then additive increa.Figure1(a) shows the growth function during max probing.During max probing,the window grows slowly initially tofind the new maximum nearby,and after some time of slow growth,if it does notfind the new ,packet loss),then it guess the new maximum is further away so it switches to a faster increa by switching to additive increa where the window size is incremented by a largefixed increment. The good performance of BIC-TCP comes from the slow increa around W max and linear increa during additive increa and max probing.
3.2CUBIC window growth function
BIC-TCP achieves good scalability in high speed networks, fairness among competingflows of its own and stability with low window oscillations.However,BIC-TCP’s growth func-tion can still be too aggressive for TCP,especially under short RTT or low speed networks.Furthermore,the veral different phas(binary arch increa,max probing,S max and S min)of window control add complexity in implement-ing the protocol and analyzing its performance.We have been arching for a new window growth function that while retaining strengths of BIC-TCP(especially,its stability and sc
alability),simplifies the window control and enhances its TCP friendliness.
We introduce a new high-speed TCP variant:CUBIC.As the name of the protocol reprents,the window growth function of CUBIC is a cubic function who shape is very similar to the growth function of BIC-TCP.CUBIC us a cubic function of the elapd time from the last congestion event.While most alternative algorithms to Standard TCP us a convex increa function where after a loss event,the
window increment is always increasing,CUBIC us both
the concave and convex profiles of a cubic function for win-dow increa.Figure1(b)shows the growth function of CUBIC.
The details of CUBIC are as follows.After a window re-duction following a loss event,it registers W max to be the window size where the loss event occurred and performs a multiplicative decrea of congestion window by a factor of βwhereβis a window decrea constant and the regular fast recovery and retransmit of TCP.After it enters into conges-tion avoidance from fast recovery,it starts to increa the window using the concave profile of the cubic function.The cubic function is t to have its plateau at W max so the con-cave growth continues until the window size becomes W max.
After that,the cubic function turns into a convex profile and the convex window growth begins.This style of window ad-justment(concave and then convex)improves protocol and network stability while maintaining high network utiliza-tion[12].This is becau the window size remains almost constant,forming a plateau around W max where network utilization is deemed highest and under steady state,most window size samples of CUBIC are clo to W max,thus pro-moting high network utilization and protocol stability.Note that protocols with convex growth functions tend to have the largest window increment around the saturation point, introducing a large burst of packet loss.
The window growth function of CUBIC us the following function:
W(t)=C(t−K)3+W max(1) where C is a CUBIC parameter,t is the elapd time from the last window reduction,and K is the time period that the above function takes to increa W to W max when there is no further loss event and is calculated by using the following equation:
K=3r C(2)
Upon receiving an ACK during congestion avoidance,CU-BIC computes the window growth rate during the next RTT period using Eq.(1).It ts W(t+RT T)as the candidate target value of congestion window.Suppo that the cur-rent window size is cwnd.Depending on the value of cwnd, CUBIC run
s in three different modes.First,if cwnd is less than the window size that(standard)TCP would reach at time t after the last loss event,then CUBIC is in the TCP mode(we describe below how to determine this window size of standard TCP in term of time t).Otherwi,if cwnd is less than W max,then CUBIC is in the concave region, and if cwnd is larger than W max,CUBIC is in the convex region.Algorithm1shows the pudo-code of the window adjustment algorithm of CUBIC implemented in Linux.
3.3TCP-friendly region
When receiving an ACK in congestion avoidance,wefirst check whether the protocol is in the TCP region or not.This is done as follows.We can analyze the window size of TCP in terms of the elapd time t.Using a simple analysis in [16],we canfind the average window size of additive increa and multiplicative decrea(AIMD)with an additive factor Initialization:
tcp
convergence←−1,C←−0.4
cubic
if dMin then dMin←−min(dMin,RT T)
el dMin←−RT T
if cwnd≤ssthresh then cwnd←−cwnd+1
el
update()
英语你好怎么说if cwnd
cwnd←−cwnd+1,cwnd
el cwnd cnt+1
epoch
max
and fast
W last
2
搞笑的小故事
...........................(3.7) max
←−cwnd
ssthresh←−cwnd←−cwnd∗(1−β).................(3.6) end
Timeout:
begin
ret()
end
cubic
ack cnt+1
if epoch
epoch time
max
then
W last
C
origin max
K←−0
origin
ack
t←−tcp stamp+dMin−epoch
point+C(t−K)3
if target>cwnd then cnt←−cwnd
friendliness then cubic friendliness()
end
cubic friendliness():..........................................(3.3) begin
2−β
∗ack
cwnd
ack
max
W tcp−cwnd
if cnt>max cnt
ret():
梦见摘柿子
begin
max
急救小常识
←−0,epoch point←−0 dMin←−0,W tcp←−0,K←−0,ack
αand a multiplicative factorβto be the following function:
1α
β
1
RT T q212−β.If TCP increas its window byαper RTT,we can get the window size of TCP in terms of the elapd time t as follows:
W tcp(t)=W max(1−β)+3β
RT T
(4)
If cwnd is less than W tcp(t),then the protocol is in the TCP mode and cwnd is t to W tcp(t)at each reception of ACK. The cubic friendliness()in Algorithm1describes this behavior.
3.4Concave region
When receiving an ACK in congestion avoidance,if the pro-tocol is not in the TCP mode and cwnd is less than W max, then the protocol is in the concave region.In this region, cwnd is incremented by W(t+RT T)−cwnd
cwnd ,which is shown at(3.5)in
爱情选择题Algorithm1.
3.6Multiplicative decrea
When a packet loss occurs,CUBIC reduces its window size by a factor ofβ.We tβto0.2.A side effec
t of ttingβto a smaller value than0.5is slower convergence.We believe that while a more adaptive tting ofβcould result in faster convergence,it will make the analysis of the protocol much harder and also affects the stability of the protocol.This adaptive adjustment ofβis a future rearch issue.
3.7Fast Convergence
To improve the convergence speed of CUBIC,we add a heuristic in the protocol.When a newflow joins the net-work,existingflows in the network need to give up their bandwidth shares to allow the newflow some room for growth. To increa this relea of bandwidth by existingflows,we add the following mechanism called fast convergence.With fast convergence,when a loss event occurs,before a window reduction of the congestion window,the protocol remembers the last value of W max before it updates W max for the current loss event.Let us call the last value of W max to be W last
max
,this in-dicates that the saturation point experienced by thisflow is getting reduced becau of the change in available band-width.Then we allow thisflow to relea more bandwidth by reducing W max further.This action effectively lengthens the time for thisflow to increa its window becau the
re-duced W max forces theflow to have the plateau earlier.This allows more time for the newflow to catch up its window size.The pudo code for this operation is shown at(3.7) in Algorithm1.
4.CUBIC IN LINUX KERNEL
Since thefirst relea of CUBIC to the Linux community in2006,CUBIC has gone through veral upgrades.This ction documents tho changes.
4.1Evolution of CUBIC in Linux
Table1summarizes important updates[1]on the implemen-tation of CUBIC in Linux since itsfirst introduction in Linux 2.6.13.The most updates on CUBIC are focusd on per-formance and implementation efficiency improvements.One of notable optimizations is the improvement on cubic root calculation.The implementation of CUBIC requires solving Eq.2,a cubic root calculation.The initial implementation of CUBIC[18]in Linux us the biction method.But the Linux developer community worked together to replace it with the Newton-Rhaphson method which improves the running time by more than10times on average(1032clocks vs.79clocks)and reduces the variance in running times. CUBIC also went through veral algorithmic changes to have its current form to enhance its scalability,fairness and convergence speed.
4.2Pluggable Congestion Module
More inclusions of TCP variants to the Linux kernel has substantially incread the complexity of the TCP code in the kernel.Even though a new TCP algorithm comes with a patch for the kernel,this process requires frequent kernel re-compilations and exacerbates the stability of the TCP code. To eliminate the need of kernel recompilation and help ex-perimenting with a new TCP algorithm with Linux,Stephen Hemminger introduces a new architecture[23,6],called pluggable congestion module,in Linux2.6.13.It is dynami-cally loadable and allows switching between different conges-tion control algorithm modules on thefly without recompi-lation.Figure2shows the interface to this module,named tcp ops.Each method in tcp ops is a hook in the TCP code that provides access to the TCP code.A new congestion control algorithm requires to define cong
cwnd can be ud for that
