一種改進的網(wǎng)絡(luò)擁塞控制算法及仿真實現(xiàn)

張宗福

（廣東江門職業(yè)技術(shù)學(xué)院 廣東江門 529090）

1 引言

網(wǎng)絡(luò)擁塞指的是當(dāng)網(wǎng)絡(luò)中存在過多的數(shù)據(jù)包時，網(wǎng)絡(luò)的性能就會下降。在網(wǎng)絡(luò)通信的過程中，網(wǎng)絡(luò)擁塞是造成延遲和吞吐量等性能指標(biāo)下降的主要原因，是影響帶寬和緩存等網(wǎng)絡(luò)資源利用率的關(guān)鍵因素。網(wǎng)絡(luò)擁塞的根本原因是用戶提供給網(wǎng)絡(luò)的負載大于網(wǎng)絡(luò)資源容量和處理能力；直接原因是INTERNET中的存儲空間不足、帶寬容量不足及處理機處理能力較弱等[1]。網(wǎng)絡(luò)擁塞如果不加以控制，往往會導(dǎo)致惡性循環(huán)，因此，網(wǎng)絡(luò)擁塞已成為制約網(wǎng)絡(luò)發(fā)展和應(yīng)用的一個瓶頸，研究如何有效解決擁塞問題對于提高網(wǎng)絡(luò)性能有著特別重要的意義。

Jacobson在TCP中增加的擁塞控制算法，提出了著名的“慢啟動”、“擁塞避免”、“快速重傳”和“快速恢復(fù)”4個算法。這4個算法是TCP擁塞控制的核心算法，是Internet上主要使用的端系統(tǒng)擁塞控制機制。雖然這些算法在Internet中執(zhí)行能有效的控制擁塞，避免擁塞崩潰現(xiàn)象的發(fā)生，但是實質(zhì)上這是一種較保守的策略，它并非在所有的網(wǎng)絡(luò)條件下都能保證其良好的性能。慢啟動算法中存在的問題尤為突出，比如丟包嚴重、網(wǎng)絡(luò)資源利用率低、延遲增加以及傳輸延遲較大等。

文章將對Internet中的TCP/IP擁塞控制進行探討，針對TCP擁塞控制策略中的慢啟動階段存在的問題，提出一種改進的基于歷史連接參數(shù)的擁塞控制算法，并對慢啟動算法作了相應(yīng)的改進，并使用NS2對研究內(nèi)容進行仿真實現(xiàn)，為有效控制擁塞提供一種新的解決方案。

2 慢啟動及其存在的問題

TCP擁塞控制由慢啟動、擁塞控制、快速重傳和快速恢復(fù)4個核心算法組成。這4個基本算法互相聯(lián)系，是目前在Internet上主要使用的擁塞控制機制。慢啟動是其中的一個關(guān)鍵算法，主要思想是：為了解決擁塞的問題，新建立的TCP連接不是一開始就發(fā)送大量數(shù)據(jù)，而是逐步增加每次發(fā)送的數(shù)據(jù)量，也就是說，當(dāng)建立一個新的TCP連接時，可以把擁塞窗口（cwnd）初始設(shè)置為一個數(shù)據(jù)包的大小，源端按擁塞窗口（cwnd）的大小發(fā)送數(shù)據(jù)，每當(dāng)接收端收到一個確認信號（ACK），擁塞窗口（cwnd）就會自動增加一個數(shù)據(jù)包的發(fā)送量，這樣擁塞窗口（cwnd）就將隨著回路響應(yīng)時間（RTT）的增長而呈指數(shù)型增長，源端向網(wǎng)絡(luò)發(fā)送的數(shù)據(jù)量也將隨之而急劇增加。在慢啟動策略中，要達到每個RTT發(fā)送W 個數(shù)據(jù)包所需要的時間僅為RTT×logW。由于在發(fā)生擁塞時，擁塞窗口會減半或降到1，因此慢啟動確保了源端的發(fā)送速率最多是鏈路帶寬的2倍。

雖然慢啟動策略在TCP擁塞控制機制中運用能有效地避免擁塞現(xiàn)象，但越來越多的研究表明，這是一種比較保守的策略，并不是在所有的網(wǎng)絡(luò)條件下都能保證良好的性能，存在以下3個問題：

①建立新的TCP連接時，在慢啟動階段，由于發(fā)送方無法了解到瓶頸鏈路的帶寬，所以在每個回路響應(yīng)時間（RTT）內(nèi)都會將擁塞窗口（cwnd）的數(shù)量增加一倍，假如慢啟動閾值（ssthresh）比較大，發(fā)送方窗口也增加到足夠大時，連接將會丟失大約一半的數(shù)據(jù)包；

②TCP慢啟動在傳輸數(shù)據(jù)前，是要先設(shè)定好參數(shù)，然后按照參數(shù)開始傳輸?shù)?，取擁塞窗口（cwnd）數(shù)為1個數(shù)據(jù)包大小，取慢啟動閾值（ssthresh）為64個數(shù)據(jù)包大小，TCP連接在閑置一段時間后，再使用慢啟動算法重新開始通信，當(dāng)網(wǎng)絡(luò)可用帶寬較大時，會造成網(wǎng)絡(luò)資源利用率降低及延遲增加；

③雖然TCP給予窗口的擁塞控制機制對于傳輸大批量文件具有良好的適應(yīng)性，但是當(dāng)這一機制為萬維網(wǎng)應(yīng)用等短小數(shù)據(jù)流服務(wù)時性能較差，往往需要幾個RTT時間探測合適的網(wǎng)絡(luò)帶寬，傳輸延遲較大[2]。

3 改進的擁塞控制算法

3.1 基本思想

針對慢啟動算法中存在的問題，人們已經(jīng)提出了很多解決方案，在相關(guān)研究的基礎(chǔ)上提出一個基于歷史連接參數(shù)和令牌技術(shù)的改進算法，通過調(diào)整慢啟動階段初始參數(shù)的設(shè)置來提高TCP的性能[3]。在擁塞控制的慢啟動階段，讓相類似的連接實例共享擁塞控制信息庫，利用一個緩存表把類似的連接實例的相關(guān)參數(shù)保存下來，如果下次需要建立相類似的連接時，可以使用該表中的歷史連接參數(shù)對新的連接進行初始化，避免了重新探測網(wǎng)絡(luò)帶寬的過程，減少了傳輸延遲。

但是，往往根據(jù)緩存表信息設(shè)置的初始窗口（cwnd）會大于一個數(shù)據(jù)包的大小，在建立連接時，如果在開始進行數(shù)據(jù)傳輸時不采取相應(yīng)的措施，容易造成大量的突發(fā)數(shù)據(jù)在很短的時間內(nèi)注入網(wǎng)絡(luò)，加重擁擠程度，為了避免這一情況，可在發(fā)送方引入令牌控制的思想，使用RTT/cwnd作為令牌的生成速度，用來調(diào)節(jié)初始窗口中的數(shù)據(jù)包在一個RTT時間內(nèi)均勻發(fā)送[4]，一直到確認信號（ACK）自計時開始。

3.2 算法實現(xiàn)

基于前面的算法思想，該算法只需要對發(fā)送方進行修改，具體算法如下：

①建立一個緩存表，用于存放連接參數(shù)（如目標(biāo)主機地址、cwnd、ssthresh、RTT等），當(dāng)每一次建立新的連接時，根據(jù)歷史記錄，如存在與之匹配的歷史記錄，則從緩存表中取出相應(yīng)的信息，然后對新的連接的參數(shù)進行初始化（RTT，ssthresh值保持不變），cwnd值取決于上一個連接結(jié)束前是處于慢啟動階段還是擁塞避免階段，如果是在慢啟動階段，cwnd的值設(shè)為原值的1/2，如在擁塞避免階段，cwnd的值設(shè)為原值減1；

②發(fā)送方在傳輸數(shù)據(jù)的過程中，如果遇到cwnd值減少，則將當(dāng)前的擁塞參數(shù)保存在緩存中，然后使用如下方法計算并存儲擁塞參數(shù)的初始值：t=now-times，cwnds=(1-f(α，t))×cwndc+f(α，t)×cwnds)，其中(0≤f(α，q)≤1，0≤α≤1)，t是該記錄在緩存中的存儲時間，now是系統(tǒng)當(dāng)前時間，times是該記錄被存儲在緩存中的時間，cwnds是當(dāng)前緩存表中保存的擁塞窗口大小，cwndc是當(dāng)前連接獲得的擁塞窗口大小。值得注意的是擁塞參數(shù)保存的時間越長，反映網(wǎng)絡(luò)當(dāng)前狀態(tài)的可能性越小，所以，在保存擁塞參數(shù)時，必須考慮時間的影響；

③當(dāng)根據(jù)緩存信息設(shè)置好初始參數(shù)并建立一個新的連接時，初始窗口的大小往往大于一個數(shù)據(jù)包，為了避免初始窗口中的大量數(shù)據(jù)包注入網(wǎng)絡(luò)，可使用令牌技術(shù)控制數(shù)據(jù)包須在第一個RTT內(nèi)均勻發(fā)送，將突發(fā)的數(shù)據(jù)流轉(zhuǎn)化為相對平緩傳輸?shù)臄?shù)據(jù)流。令牌機制僅在發(fā)送窗口中使用，采用令牌機制時，發(fā)送方在發(fā)送前先調(diào)用申請令牌的函數(shù)，獲得發(fā)送令牌，每獲得一個令牌就發(fā)送一個數(shù)據(jù)包，令牌的產(chǎn)生速度由RTT/cwnd來確定，這樣就確保了在第一個RTT時間內(nèi)數(shù)據(jù)包是按照一定的時間間隔發(fā)送的，降低了數(shù)據(jù)的突發(fā)性。

4 使用NS2進行算法的仿真分析

4.1 NS2及其仿真步驟

NS2是一種針對網(wǎng)絡(luò)技術(shù)的,面向?qū)ο蟮?、離散事件驅(qū)動的網(wǎng)絡(luò)仿真模擬平臺，能夠仿真多種局域網(wǎng)和廣域網(wǎng)性能。NS2仿真分2個層次：①是基于OTcl編程的層次。利用NS已有的網(wǎng)絡(luò)元素實現(xiàn)仿真，無需修改NS本身，只需編寫OTcl腳本；②是基于C++和OTcl編程的層次。如果NS中沒有所需的網(wǎng)絡(luò)元素，則需要對NS進行擴展，添加所需網(wǎng)絡(luò)元素，即添加新的C++和OTcl類，編寫新的OTcl腳本[5]。

進行網(wǎng)絡(luò)仿真前，首先分析仿真涉及哪個層次，假設(shè)用戶已經(jīng)完成了對NS的擴展，或者NS所包含的構(gòu)件已經(jīng)滿足了要求，那么進行一次仿真的步驟大致如下[6]：

①開始編寫OTcl腳本。首先配置模擬網(wǎng)絡(luò)拓撲結(jié)構(gòu)，此時可以確定鏈路的基本特性，如延遲、帶寬和丟失策略等；

②建立協(xié)議代理，包括端設(shè)備的協(xié)議綁定和通信業(yè)務(wù)量模型的建立；

③配置業(yè)務(wù)量模型的參數(shù)，從而確定網(wǎng)絡(luò)上的業(yè)務(wù)量分布；

④設(shè)置Trace對象。NS通過Trace文件來保存整個模擬過程。仿真完后，用戶可以對Trace文件進行分析研究；

⑤編寫其他的輔助過程，設(shè)定模擬結(jié)束時間，至此OTcl腳本編寫完成；

⑥用NS解釋執(zhí)行剛才編寫的OTcl腳本；

⑦對Trace文件進行分析，得出有用的數(shù)據(jù)；

⑧調(diào)整配置拓撲結(jié)構(gòu)和業(yè)務(wù)量模型，重新進行上述模擬過程。

4.2 運用NS2仿真分析

根據(jù)上述仿真步驟，運用NS2進行仿真分析如下：

⑴編寫OTcl腳本

配置模擬網(wǎng)絡(luò)拓撲結(jié)構(gòu)，對應(yīng)的拓撲結(jié)構(gòu)圖如圖1所示。

圖1 拓撲結(jié)構(gòu)圖

⑵各時刻進程信息：

時刻與進程信息如下：

⑶演示過程與分析

源端開始向接收端發(fā)送報文段，擁塞窗口（cwnd）大小為1時，發(fā)送0號分組，當(dāng)接收到0號ACK后，擁塞窗口（cwnd）增加到2，發(fā)送1，2號分組，接收到1，2號ACK后，同理,按指數(shù)規(guī)律增加擁塞窗口，擁塞窗口（cwnd）大小增加到8后，一直保持在最大值8上。發(fā)送完所有38個分組，收到31號ACK后，F(xiàn)TP傳送結(jié)束。從以上過程數(shù)據(jù)可以看出，經(jīng)過改進后算法，在慢啟動后期，擁塞窗口cwnd越接近慢啟動閾值，ssthresh增長越趨于平緩，最后能平滑地過渡到擁塞避免階段[7]，能很好地解決慢啟動階段存在的問題，有效地對網(wǎng)絡(luò)擁塞進行控制。

5 結(jié)束語

慢啟動算法是網(wǎng)絡(luò)擁塞控制中的一種重要的算法，在網(wǎng)絡(luò)建立連接或重傳超時的情況下，都會轉(zhuǎn)入慢啟動階段，慢啟動算法的好壞對于網(wǎng)絡(luò)擁塞控制的性能有著直接的影響。一個好的慢啟動算法能夠降低慢啟動階段數(shù)據(jù)包的丟棄率，提高鏈路的利用率，還能降低數(shù)據(jù)傳輸?shù)难舆t[8]。文章提出的基于歷史連接參數(shù)和令牌技術(shù)的改進算法，通過調(diào)整慢啟動階段初始參數(shù)的設(shè)置來提高TCP的性能。通過NS2仿真分析也證明了改進的慢啟動算法的有效性。

[1]劉文遠，馮 波，龍承念等.一種新的TCP 擁塞控制慢啟動策略[J].小型微型計算機系統(tǒng),2005，26(1):23-25.

[2]林 荔.基于擁塞控制和資源調(diào)節(jié)的DDOS 攻擊防范策略[J].計算機與網(wǎng)絡(luò),2011,37（18）:71-73.

[3]王 強，普杰信，劉 偉.TCP 擁塞控制慢啟動策略的研究[J].微電子學(xué)與計算機,2007，24（12）:210-212.

[4]陳 晶,鄭明春,孟 強.一種基于歷史連接的網(wǎng)絡(luò)擁塞控制算法及其性能分析[J].計算機研究與發(fā)展,2003,40（10）:1470-1475.

[5]劉星宇.TCP 擁塞控制算法的NS 模擬實驗[J].實驗技術(shù)與管理,2011,28（9）:79-81.

[6]杜玉林,張術(shù)平,王 煒.隨機早期檢測算法公平性的改進[J].計算機與網(wǎng)絡(luò),2009,35（3）:112-115.

[7]張宗福.無線局域網(wǎng)安全問題及解決方案[J].計算機安全,2011(6):48-51.

[8]黃 敏,張鵬麗,段 焰.基于Petri 網(wǎng)的Internet 擁塞控制慢啟