TCP Congestion control algorithm(Reno,HSTCP,BIC,Vegas,Westwood)

One,TCP Research framework of congestion control

Two, ExistingTCP Congestion control algorithm(Reno,HSTCP,Vegas,Westwood)

Three, Reference




One,TCP Research framework of congestion control

<http://photo.blog.sina.com.cn/showpic.html#blogid=73b05f070101ipaw&url=http://album.sina.com.cn/pic/0027lYLJty6J2T7r2TU4a>


notes:

l   Based on packet loss feedback: adoptACK The packet loss information brought back to adjust the congestion window at the source end.Reno And so on.ACK Improved tradition with returned packet loss informationTCP
Agreement. This year, With the increase of network bandwidth, Increase of transmission delay, Aim at improvingTCP Bandwidth utilization, AppearHSTCP,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: TypicalECN Using intermediate nodes to detect their own congestion state, Such as the feedback status of router, Direct feedback toTCP Source end, So as to adjust the window value and transmission rate of the source.





Two,   A keyTCP Extension algorithm

1.       Based on packet loss feedbackTCP Agreement(Tahoe,Reno,New Reno,SACK)

1988 year V.Jacobson Put forward, Algorithm of slow start and congestion avoidance. Later stageTCP Continuous optimization and improvement of transmission protocol algorithm. The most widely usedTCP Reno Congestion control is mainly divided into4
Phases:

 

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. from3
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 speaking3)

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】

Wholereno See the following figure for the process:

 

 
<http://photo.blog.sina.com.cn/showpic.html#blogid=73b05f070101ipaw&url=http://album.sina.com.cn/pic/0027lYLJty6J2Tp9l4Le3>

 

 

2.       Delay feedback basedTCP Agreement(Vegas,Westwood)

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

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

-  When a duplicate is acceptedACK 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 repeatACK. After receiving retransmission packet response,
Vegas with3/4 Instead of1/2 Factor reducing congestion window.

-  When non repetitiveACK 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, Reissued.

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 establishedRTT.cwnd Is the current congestion window size.

Defining thresholda,b, Whendiff Congestion window increases,+1; Whendiff>b, Congestion window reduction,-1; Whena<=diff<=b, Congestion window unchanged. usuallya=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 twoRTT sendcwnd Congestion window increase1 times. Then calculatediff, When
diff>a, End slow start, Turn in congestion avoidance.

stay Vegas Slow start, 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 one RTT Keep unchanged in order to observe RTT Changes, 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, New calculation RTT anddiff Value, 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 phaseReno Method.

Vegas-A: The main idea isa,b It can be adjusted automatically according to the network conditions, The initial values are1 and3.

 

 

In wireless transmissionWestwood algorithm

Basic thinking: Sender uses detectedACK 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 losscwnd andssthresh. After receiving three duplicateACK
Or overtime, Concrete algorithm:


<http://photo.blog.sina.com.cn/showpic.html#blogid=73b05f070101ipaw&url=http://album.sina.com.cn/pic/0027lYLJty6J2TNIZkJc9>
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  stayReno On the basis of, Estimate the available bandwidth of the network by measurement, To congestion windowcwnd
Make appropriate adjustments, Faster recovery. This mechanism is particularly effective in wireless networks, AndReno Double the throughput.

2) Slow start phase

Slow start and incremental phase are still adoptedReno 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 ifssthresh  Fixed low, It will lead to early linear increase, Reduce bandwidth utilization.

Becausewestwood 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 bewestwood 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 phaseN  Distinguish,  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 segmentation,  Not fixedssthresh/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 time, Usevegas Method calculation ofdiff Andb compare, If
Indicates that the bandwidth has not been fully utilized, keepreno 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, Explainssthresh Too large, Need to change, sendTCP
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 AndSTCP The basic idea of: When congestion window> Threshold time, Window increase factora(w) And reduction factorsb(w) Become window resizew Function.

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 standardTCP Reaction function of protocol, Affected by window growth and packet loss decline function. HighlightsHSTCP 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) andb(w) The formula of is:

Whenw>WL


<http://photo.blog.sina.com.cn/showpic.html#blogid=73b05f070101ipaw&url=http://album.sina.com.cn/pic/0027lYLJty6J2TVzRjE2e>
Whenw<=WL Time,a(w)=1  b(w)=0.5

 

2.      STCP- scable TCP

Congestion avoidance phase is affected byACK: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 fastHSTCP,STCP fast.

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

       Two point 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 toWmin andWmax Intermediate value. If there is no packet loss, The value of the current window is set toWmin, Congestion window increase now vsWmin Half the difference; If packet loss occurs, The current window value is
Wmax.

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 aSmax, according toSmax Step growth.

4.   CUBIC

YesBIC Simplification of algorithm, The algorithm of window expansion dominated by cubic terms, Size of new windoww by:

 


<http://photo.blog.sina.com.cn/showpic.html#blogid=73b05f070101ipaw&url=http://album.sina.com.cn/pic/0027lYLJty6J2TXv0iS6a>







Three, Reference

http://blog.csdn.net/zhangskd/article/details/6715751
<http://blog.csdn.net/zhangskd/article/details/6715751>

http://baike.baidu.com/view/1954873.htm
<http://baike.baidu.com/view/1954873.htm>

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