TCP Protocol congestion control algorithm (Reno,HSTCP,BIC,Vegas,Westwood)

One ,TCP Research framework of congestion control

Two , existing TCP Congestion control algorithm (Reno,HSTCP,Vegas,Westwood)

Three , reference

One ,TCP Research framework of congestion control


notes :

l   Based on packet loss feedback : adopt ACK The packet loss information brought back to adjust the congestion window at the source end .Reno Wait is for ACK Improved tradition with returned packet loss information TCP
agreement . This year , With the increase of network bandwidth , Increase of transmission delay , For improvement TCP Bandwidth utilization , appear HSTCP,BIC-TCP,STCP agreement .

l   Based on path delay feedback :RTT More responsive than packet loss information , It can reflect the congestion of general network in time . Intermediate nodes for small cache , Better efficiency . But for routers, caching data often drives
RTT Extend congestion window , No congestion actually happened .

l   Congestion feedback based on display : typical ECN Using intermediate nodes to detect their own congestion state , Such as the feedback status of router , Direct feedback to TCP Source end , So as to adjust the window value and transmission rate of the source .

Two ,   a key TCP Extended algorithm

1.       Based on packet loss feedback TCP agreement (Tahoe,Reno,New Reno,SACK)

1988 year  V.Jacobson Proposed , Algorithm of slow start and congestion avoidance . Later on TCP Continuous optimization and improvement of transmission protocol algorithm . The most widely used TCP Reno Congestion control is mainly divided into 4
Stages :


1) Slow start phase :  cwnd Showing exponential growth trend

2) congestion avoidance :cwmd>ssthresh   Linear growth trend

3) Fast retransmission stage : As soon as the sender receives three repeated acknowledgments, it should immediately retransmit the message segments that the other party has not yet received , Instead of waiting for the retransmission timer to time out . from 3
Repeated response to determine packet loss , Resend packet loss information .

4) Fast recovery phase : It mainly depends on the initial threshold value of the received repeated response data ( Generally 3)

Different from slow start ,Reno The sender uses the extra arrival response to time the subsequent packets .

Upper limit of sender window =min【 Receiver window , Congestion window 】

whole reno See the following figure for the process :





2.       Delay feedback based TCP agreement (Vegas,Westwood)

classical Vegas Basic idea of algorithm :RTT increase , Congestion window reduction ;RTT reduce , Congestion window becomes larger .

1) Retransmission mechanism :Vegas More accurate RTT The estimate determines whether to resend in the following two cases :

-  When a duplicate is accepted ACK Time ,Vegas Check whether the difference between the current time and the recorded time tag is greater than the timeout value , If it is , Then resend the packet immediately , Don't wait for the third repeat ACK. After receiving retransmission packet response ,
Vegas with 3/4 instead of 1/2 Factor reduction congestion window .

-  When non repetitive ACK Time , If it's the first or second confirmation after the resend ,Vegas Check whether the data sending time interval has exceeded the time value again . If it is , Then resend .

2) congestion avoidance :Vegas Adjust the size of congestion window by comparing the actual throughput with the expected throughput .

Expected throughput :Expected=cwmd/BaseRTT

Actual throughput :Actual=cwnd/RTT

Calculate the difference :diff=(Expected-Actual)*BaseRTT

BaseRTT Is the minimum response time of all observations , It is usually the first packet sent after the connection is established RTT.cwnd Is the current congestion window size .

Define thresholds a,b, When diff Congestion window increases ,+1; When diff>b, Congestion window reduction ,-1; When a<=diff<=b, Congestion window unchanged . usually a=1,b=3
, Means that the connection keeps at least one package in the queue . <>

3) Slow start mechanism

At the beginning, there are no parameters such as transmission data and bandwidth speed related to slow start , Slow start threshold needs to be set .Vegas Every two RTT send cwnd Congestion window increase 1 times . Then calculate diff, When
diff>a, End slow start , Turn in congestion avoidance .

stay  Vegas Slow start in progress , Every two  RTT send  W increase  1 times . The former one  RTT Internal and  TCP Reno Same exponential growth , I.e. every time one is received  ACK The bag will be added  1
, Send two packets at the same time , It can be called growth period ; The latter  RTT Keep unchanged in order to observe  RTT Changes in , It can be called observation period .Vegas
The slow start-up process is a cycle of growth period and observation period , At the end of each observation period , Calculate new  RTT and diff Value of , To decide whether to continue the next cycle or to end the slow start .

This fact of slow start severely reduces the transmission rate . Some scholars have proposed adaptive slow start algorithm , Or slow start phase Reno method .

Vegas-A: The main idea is a,b It can be adjusted automatically according to the network conditions , The initial values are 1 and 3.



In wireless transmission Westwood algorithm

Basic ideas : Sender uses detected ACK To estimate the available bandwidth .

1) Fast recovery mechanism :westwood The algorithm focuses on how to use bandwidth estimation to set congestion window in case of packet loss cwnd and ssthresh. After receiving three duplicate ACK
Or timeout , Specific algorithm :

among ,PacketSize  Group size ,BWE  Is the bandwidth estimate ( Number of groups per unit time * Group size ),RTTmin  Is the smallest measurement  RTT 
value , Ideally equal to the value measured when the length of the intermediate queue is zero .TCPW  stay Reno Based on , Estimate the available bandwidth of the network by measurement , To congestion window cwnd
Make appropriate adjustments , Faster recovery . This mechanism is particularly effective in wireless networks , And Reno Double the throughput .

2) Slow start phase

Slow start and incremental phase are still adopted Reno Increase mechanism of . Slow start in bandwidth detection phase , Slow start in bandwidth detection phase ,cwnd Exponential growth ,ssthresh
If it's too high , It is easy to cause more packet retransmissions , And if ssthresh  Too low , It will lead to early linear increase , Reduce bandwidth utilization .

because westwood Unable to distinguish between network congestion packet loss and wireless random error packet loss , Especially, delay jitter and random error packet loss in wireless networks will be westwood Mistaken for network congestion , Greatly reduce network bandwidth utilization .

Westwood-v algorithm : In the slow start phase ,  The improved algorithm is based on the packet length in the queue for the network state in the slow start phase N  Make a distinction ,  And the window adjustment is closely combined with the estimated bandwidth ,  According to network conditions
,  Adopt different window adding strategies ,  Avoid the original  TCPW  Packet congestion loss caused by blind increase of congestion window in . in addition ,  For segments ,  Not fixed ssthresh/2, 
Instead, segments are based on the relationship between the current congestion window and the predicted available bandwidth at the next time ,  Dynamic adaptability . In short , Slow start , use vegas Method calculation of diff And b compare , If
Indicates that the bandwidth has not been fully utilized , keep reno Exponential and linear increase of . When >b Means bandwidth is fully utilized , But close to congestion , If it is still in the slow start stage , explain ssthresh Larger , Change required , send TCP
Enter congestion avoidance phase . If in congestion avoidance phase , Decrease the window increase rate .

3, High speed Bandwidth Algorithm Based on packet loss feedback (HSTCP,STCP,BIC-TCP,CUBIC)

HSTCP And STCP The basic idea of : When congestion window > At threshold , Window increase factor a(w) And reduction factors b(w) Become window resize w Function of .

1.      HSTCP-high speed TCP High speed transmission protocol  

For high speed , Large delay network    Rapid growth of windows , Multiplicative reduction

The basic idea of the algorithm is to modify the standard TCP Reaction function of protocol , Affected by window growth and packet loss decline function . Highlights HSTCP The adjustment algorithm of congestion avoidance phase window based on . In congestion avoidance phase , Accept one
ACK after , The growth mode is :

Linear increase   cwmd=cwmd+a(w)/cwmd

A congestion occurs , Congestion window reduction method is :

Multiplicative reduction   cwnd=(1-b(w))*cwnd

a(w) and b(w) The formula of is :

When w>WL

When w<=WL Time ,a(w)=1  b(w)=0.5


2.      STCP- scable TCP

Congestion avoidance phase is affected by ACK:cwmd=cwmd+a(w)

When congestion occurs :cwnd=(1-b(w))*cwnd

a=0.01  b=0.125 Fixed parameters .


3.    BIC-TCP

BIC Consider congestion control as a search problem , Good expansibility , Friendliness and fairness . But the loss rate <1e-8 Its transmission rate is not growing as fast HSTCP,STCP fast .

BIC It consists of two parts : Binary search increase (Binary Search increase)+ Additive increase (additive increase)

       Binary search : TCP Active rather than passive search for a packet transmission rate at the threshold of packet loss triggering .

Wmin  Fast recovery of congestion window size after lodging

Wmax  Congestion window size before the end of fast recovery

First, set the size of the target window to Wmin and Wmax Middle value of . If there is no packet loss , The value of the current window is set to Wmin, Congestion window increase now vs Wmin Half the difference ; If the packet is lost , The current window value is

Additive growth : If the difference between the current value and the target value is too large , Setting the congestion window directly to the target value brings a lot of pressure . Set a Smax, according to Smax Step growth .

4.   CUBIC

Yes BIC Simplification of algorithm , The algorithm of window expansion dominated by cubic terms , Size of new window w by :



Three , reference

And many masters , Doctoral Dissertation , Not one by one , Thank you .