名字釋義
Reno是目前套用最廣泛且較為成熟的算法。該算法所包含的慢啟動、擁塞避免和快速重傳、快速恢復機制,是現有的眾多算法的基礎。
優缺點
慢啟動與擁塞避免
慢啟動與擁塞避免:TCP傳送端採用慢啟動和擁塞避免算法來控制向網路輸送的數據量。為了實現這些算法,必須向TCP每個連線狀態加入3個參量:
(1)擁塞視窗(cwnd),如前所述,它是對傳送端收到確認(ACK)之前能向網路傳送的最大數據量的一個傳送端的限制。
(2)接收端通知視窗(rwnd),它是對未完成數據量的接收端的限制,cwnd和rwnd的最小值決定了數據傳送。
(3)慢啟動閾值(ssthresh),被用來確定是用慢啟動還是用擁塞避免算法來控制數據傳送,具體用法如下:當cwnd<ssthresh時使用慢啟動算法;cwnd>ssthresh時使用擁塞避免算法;當cwnd=ssthresh時,傳送端既可以使用慢啟動也可以使用擁塞避免。ssthresh的初始值可以任意大(比如,一些實現中使用接收端通知視窗的尺寸),但是一旦對擁塞回響之後,其大小可能會被減小。
在不清楚網路環境的情況下向網路傳送數據,要求TCP緩慢地探測網路以確定可用頻寬,以避免突然傳送大量數據而使網路擁塞。為達此目的,在傳送開始時,採用了慢啟動機制,這個機制在修復了由重發定時器探測到的數據丟失之後也被採用。
首先要確定的是cwnd的初始值IW(初始視窗大小),這裡規定它必須小於或等於2*SMSS(SMSS指的是傳送端能傳送的最大數據段的尺寸)位元組而且不能大於兩個數據段。
在慢啟動期間,每收到一個新的ACK,cwnd最多增長1。直到cwnd超過ssthresh或者檢測到擁塞時,停止執行慢啟動算法,轉入擁塞避免階段。在擁塞避免期間,cwnd在每個ACK以1/cwnd(或每個RTT增加SMISS個位元組)的速度遞增。擁塞避免算法一直保持直到檢測出擁塞。等式(5.1.1)給出了一個在擁塞避免期間用來修正cwnd值的公式:
cwnd+=1/cwnd (5.1.1)
每收到一個非重複的ACK都採用等式(5.1.1)來調整cwnd。等式(5.1.1)用於近似擁塞避免算法的增長。
在實現中,在擁塞避免期間常用公式:cwnd+=SMSS*SMSS/cwnd來修正cwnd的值,當SMSS*SMSS/cwnd<1時,cwnd+=1。
另一種改進的方案是每當新的ACK到來時記下被新確認的位元組數,然後cwnd就可增加相應位元組數,這個增加的數目最多可達到SMSS位元組。
一旦TCP傳送端使用重傳定時器檢測到包丟失時,ssthresh的值就如下設定:
Ssthresh=max(FlightSize/2,2*SMSS) (5.1.2)
式中,Filght Size是已傳送但未收到ACK的數據的大小。
在重發了丟失的數據段之後,cwnd必須被設定成LW(丟失視窗),它等於一個滿尺寸數據段的大小。再發丟失的數據段之後,傳送端起用慢啟動算法增長視窗直到該視窗大小增長到等於新設定的ssthresh值之後,又採用擁塞避免算法了。
快速重傳與快速恢復
當接收端收到一個失序的數據報時,會立即發回一個重複ACK,這個ACK的目的是告知傳送端收到一個失序的數據報並說明其所期望的接受序號。從傳送端的角度看,重複ACK可能是許多網路問題引起的。首先,它們有可能是因為包丟失而引起。在此情況下,在此數據段之後的所有數據段都會觸發重複ACK。其次,重複ACK可能是由於網路對數據段的重新排序引起的。最後,重複ACK有可能是ACK或數據段被網路複製所引起的。此外,當接收端部分或完整地填補了序號空缺應立即傳送一個ACK,這樣可以更及時地通知傳送端,使其迅速從重髮狀態中恢復過來。
TCP傳送端應該使用快速重傳算法來探測或者修複數據丟失,在收到3個重複ACK(即連續的4個相同的ACK,標誌著1個數據段已丟失)時,TCP不等重傳定時器逾時就立即重傳看來已丟失的數據段。此後起用快速恢復算法來進行新的數據傳輸,直到1個非重複 ACK到達。
下面是快速傳送/快速恢復算法的實現:
(1)當第二個重複ACK收到時,ssthresh根據等式(5.1.2)設值。
(2)重傳丟失的數據段並將cwnd的值設定為ssthresh+3*SMSS,稱之為給擁塞視窗“充氣”。
(3)此後對每個接收到一個重複ACK,將cwnd增大SMSS位元組,這將人為地擴充擁塞視窗用以反映已經離開網路的附加數據段。
(4)如果cwnd和接收端的通知視窗值允許的話,傳送一個數據段。
(5)當下一個確認新數據的ACK到達時,設定cwnd值為ssthresh(步驟1設定的值),這稱作給視窗“放氣”。這個ACK必須是步驟1觸發的重發引起的確認,重發之後一個RTT(在接收端有次序紊亂的數據段的情況下,它可能一會兒就到達)。另外,此ACK應該確認丟失數據段和第二個重複ACK期間的數據段,如果它們一個也沒有丟失的話。
性能分析
從Reno運行機制中很容易看出,為了維持一個動態平衡,必須周期性地產生一定量的丟失,再加上AIMD機制--減少快,增長慢,尤其是在大視窗環境下,由於一個數據報的丟失所帶來的視窗縮小要花費很長的時間來恢復,這樣,頻寬利用率不可能很高且隨著網路的鏈路頻寬不斷提升,這種弊端將越來越明顯。
公平性方面,根據統計數據,Reno的公平性還是得到了相當的肯定,它能夠在較大的網路範圍內理想地維持公平性原則。