一種改進(jìn)的慢開(kāi)始沖突避免算法研究

龔顯麗 王嘉梅 房曉麗 王兵

云南民族大學(xué)電氣信息工程學(xué)院 云南 650500

0 前言

慢開(kāi)始沖突避免算法是 TCP傳輸過(guò)程中慢開(kāi)始和擁塞避免這兩種方法的總稱，是因特網(wǎng)建議標(biāo)準(zhǔn)RFC 2581定義的擁塞控制的四種方法中的兩種。后來(lái)在這兩種擁塞控制方法的基礎(chǔ)之上又做出了一些改進(jìn)，分別是RFC 2582和RFC 3390中的快重傳(Fast retransmit)和快恢復(fù)(Fast recovery)算法，由于引進(jìn)了后面兩種改進(jìn)算法，最原始的慢開(kāi)始和擁塞避免算法中已經(jīng)丟棄不用。隨著信息傳送量的逐漸增大和網(wǎng)絡(luò)組成的日益復(fù)雜，網(wǎng)絡(luò)發(fā)生擁塞的可能性也越來(lái)越大。如果不對(duì)網(wǎng)絡(luò)擁塞進(jìn)行有效的控制和在網(wǎng)絡(luò)發(fā)生擁塞時(shí)使網(wǎng)絡(luò)能及時(shí)恢復(fù)到正常狀態(tài)，就會(huì)造成嚴(yán)重的網(wǎng)絡(luò)擁塞，甚至導(dǎo)致網(wǎng)絡(luò)崩潰。因此，網(wǎng)絡(luò)擁塞的避免和控制成為越來(lái)越重要和急待解決的問(wèn)題。擁塞控制是 TCP協(xié)議研究的重要內(nèi)容。目前，標(biāo)準(zhǔn)的TCP協(xié)議實(shí)現(xiàn)都包含了一些避免和控制網(wǎng)絡(luò)擁塞的算法。但是，現(xiàn)有的擁塞控制算法都有一些局限性。因此，對(duì)TCP擁塞控制算法進(jìn)行進(jìn)一步的研究具有重要的理論和應(yīng)用價(jià)值。

1 快重傳與快恢復(fù)對(duì)算法的改進(jìn)

提出這兩個(gè)算法是基于如下的考慮：如果發(fā)送方設(shè)置的超時(shí)計(jì)時(shí)器時(shí)限已到但還沒(méi)有收到確認(rèn)，那么很可能是網(wǎng)絡(luò)出現(xiàn)了擁塞，致使報(bào)文段在網(wǎng)絡(luò)中的某處被丟棄。在這種情況下，TCP馬上把擁塞窗口cwnd減小到1，并執(zhí)行慢開(kāi)始算法，同時(shí)把慢開(kāi)始門(mén)限值ssthresh減半。

快重傳算法在接收方做了一些改進(jìn)，首先要求接收方每收到一個(gè)失序的報(bào)文段后就立即發(fā)出重復(fù)確認(rèn)(為的是使發(fā)送方及早知道有報(bào)文段沒(méi)有到達(dá)對(duì)方)而不要等待自己發(fā)送數(shù)據(jù)時(shí)才進(jìn)行捎帶確認(rèn)。

與快重傳對(duì)應(yīng)，快恢復(fù)是在發(fā)送方做了一些改進(jìn)。快恢復(fù)主要過(guò)程有以下兩點(diǎn)：

（1）當(dāng)發(fā)送方連續(xù)收到三個(gè)重復(fù)確認(rèn)時(shí)，就執(zhí)行“乘法減小”算法，把慢開(kāi)始門(mén)限 ssthresh減半。這是為了預(yù)防網(wǎng)絡(luò)發(fā)生擁塞。請(qǐng)注意，接下去不執(zhí)行慢開(kāi)始算法。

（2）由于發(fā)送方現(xiàn)在認(rèn)為網(wǎng)絡(luò)很可能沒(méi)有發(fā)生擁塞(如果網(wǎng)絡(luò)發(fā)生擁塞，就不會(huì)一連有好幾個(gè)報(bào)文段到達(dá)接收方，就不會(huì)導(dǎo)致接收方連續(xù)發(fā)送重復(fù)確認(rèn))，因此與慢開(kāi)始不同之處是現(xiàn)在不執(zhí)行慢開(kāi)始算法(即擁塞窗口 cwnd現(xiàn)在不設(shè)置為1)，而是把cwnd值設(shè)置為慢開(kāi)始門(mén)限ssthresh減半后的數(shù)值，然后開(kāi)始執(zhí)行擁塞避免算法(“加法增大”)，使擁塞窗口緩慢地線性增大。

圖1 快重傳和快恢復(fù)示意圖

從圖1中可以觀察得到，使用快重傳和快恢復(fù)算法的情況，在網(wǎng)絡(luò)出現(xiàn)擁塞之后，其數(shù)據(jù)報(bào)文段的傳輸速度恢復(fù)的要比慢開(kāi)始算法快得多。改進(jìn)了的慢開(kāi)始擁塞避免算法，大大增加了網(wǎng)絡(luò)利用率。

2 從慢開(kāi)始門(mén)限的角度提出的算法不足之處

以下先給出利用Visual C++的仿真結(jié)果，如圖2所示。

圖2 傳輸輪次與門(mén)限值關(guān)系示意圖

從圖2中可以看出，當(dāng)傳輸輪次達(dá)到一定限度時(shí)，慢開(kāi)始門(mén)限ssthresh的值有可能降至最低值2*MSS(MSS定義為允許發(fā)送的最大報(bào)文段長(zhǎng)度)。從圖中可以看出，這種發(fā)送效率是比較低下的。每一次檢測(cè)到網(wǎng)絡(luò)出現(xiàn)擁塞時(shí)，都要從最低慢開(kāi)始門(mén)限慢慢增加，這種情況在網(wǎng)絡(luò)狀況不是太理想時(shí)，避免網(wǎng)絡(luò)沖突比較有效的方法。但如果在上述情況之后突然出現(xiàn)網(wǎng)絡(luò)狀況突然轉(zhuǎn)良，即每一次遇到網(wǎng)絡(luò)擁塞之間的時(shí)間間隔拉的很開(kāi)了，這個(gè)時(shí)候在每一次出現(xiàn)了網(wǎng)絡(luò)擁塞后，再?gòu)?2*MSS慢慢的加一恢復(fù)就顯得比較慢了。因此，本文試圖在此處對(duì)慢開(kāi)始和擁塞避免算法做出改進(jìn)。

在發(fā)送端發(fā)送數(shù)據(jù)時(shí)，加入統(tǒng)計(jì)機(jī)制。統(tǒng)計(jì)機(jī)制在慢開(kāi)始門(mén)限ssthresh達(dá)到最低值2*MSS時(shí)，開(kāi)始統(tǒng)計(jì)。統(tǒng)計(jì)每?jī)纱尉W(wǎng)絡(luò)出現(xiàn)擁塞之間，經(jīng)歷的傳輸輪次(記為W)。統(tǒng)計(jì)次數(shù)可以根據(jù)實(shí)際情況實(shí)際處理，下文會(huì)給出詳細(xì)算法。記錄W出現(xiàn)的情況，然后按照統(tǒng)計(jì)學(xué)的方法，得出W的分布，以及均值，方差等。表1是根據(jù)仿真結(jié)果得出的統(tǒng)計(jì)數(shù)據(jù)。

表1 仿真結(jié)果統(tǒng)計(jì)數(shù)據(jù)

根據(jù)表1的統(tǒng)計(jì)結(jié)果計(jì)算得出均值如下：

在統(tǒng)計(jì)模塊統(tǒng)計(jì)了足夠的次數(shù)之后，根據(jù)計(jì)算得出的均值和方差，確定網(wǎng)絡(luò)信道狀況是否轉(zhuǎn)良。若在統(tǒng)計(jì)完成之后，且兩次阻塞之間的輪次間隔大于某一值S，則采用適當(dāng)?shù)倪f增算法(后面會(huì)給出詳細(xì)討論)，加大慢開(kāi)始門(mén)限的值。

3 改進(jìn)的算法

3.1 統(tǒng)計(jì)開(kāi)始和停止的條件

（1）統(tǒng)計(jì)模塊檢測(cè)慢開(kāi)始門(mén)限ssthresh的值，如果ssthresh值等于2，則開(kāi)始統(tǒng)計(jì)。

（2）當(dāng)網(wǎng)絡(luò)擁塞出現(xiàn)至少兩次后，記錄當(dāng)前擁塞與前一次擁塞之間的經(jīng)歷的傳輸輪次，得到一次統(tǒng)計(jì)樣本X[i]，并且記錄當(dāng)前出現(xiàn)的擁塞的總次數(shù)i。

注：ε要根據(jù)網(wǎng)絡(luò)實(shí)際情況調(diào)整。

3.2 慢開(kāi)始門(mén)限的控制方法

（1）在慢開(kāi)始門(mén)限達(dá)到最低值前，以快重傳和快恢復(fù)的慢開(kāi)始和擁塞避免算法控制慢開(kāi)始門(mén)限。

（2）在達(dá)到最低限度后，以3.1中的算法開(kāi)始統(tǒng)計(jì)，在統(tǒng)計(jì)停止之前，仍然按照第一步中的算法控制慢開(kāi)始門(mén)限，在3.1的算法停止后。記錄每一次的擁塞出現(xiàn)時(shí)，已經(jīng)達(dá)到的數(shù)據(jù)傳輸速度Z[i]，則下一次的慢開(kāi)始門(mén)限為下式。

采用上述控制方法后，擁塞窗口接入控制過(guò)程示意圖如圖3所示。

圖3 擁塞窗口接入控制過(guò)程示意圖

從圖3中可以觀察得到，當(dāng)ssthresh的值降至最低時(shí)，也可以較快的恢復(fù)傳輸速度，不用在達(dá)到最低值之后，每一次出現(xiàn)擁塞都從2開(kāi)始慢慢增加。當(dāng)然本改進(jìn)算法在網(wǎng)絡(luò)情況出現(xiàn)極端不利時(shí)，慢開(kāi)始門(mén)限也會(huì)慢慢收斂，不至于出現(xiàn)慢開(kāi)始門(mén)限減不下來(lái)的情況。

4 結(jié)論

本文提出的 TCP流量控制算法是繼快重傳和快恢復(fù)后對(duì)慢開(kāi)始和擁塞避免算法的又一改進(jìn)。它具有一定的實(shí)際應(yīng)用價(jià)值。

[1]謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)(第5版).電子工業(yè)出版社.2008.

[2]李建東.盛敏.通信網(wǎng)絡(luò)基礎(chǔ).高等教育出版社.2004.

[3]陳鳴等.計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)教程.從原理到實(shí)踐.機(jī)械工業(yè)出版社.2007.

[4]季福坤.計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ).人民郵電出版社.2008.

[5]高傳善等.數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò).高等教育出版社.2004.