一種適用于無線通信網(wǎng)絡(luò)的隨機(jī)提前檢測算法

摘 要：在無線通信網(wǎng)絡(luò)環(huán)境下，提出了一種改進(jìn)的基于平均隊(duì)列長度和等待時間的隨機(jī)提前檢測算法。這種算法根據(jù)平均隊(duì)列長度和等待時間計算數(shù)據(jù)包的丟棄概率。仿真結(jié)果表明，與單純基于平均隊(duì)列長度的RED算法相比較，在大的數(shù)據(jù)業(yè)務(wù)負(fù)荷條件下可以獲得相對更大的吞吐量、更低的丟包率以及較低的時延抖動，從而能更有效地實(shí)現(xiàn)無線網(wǎng)絡(luò)中的擁塞控制。

關(guān)鍵詞：服務(wù)質(zhì)量；擁塞控制；隨機(jī)提前檢測；無線網(wǎng)絡(luò)

中圖法分類號：TP393.06文獻(xiàn)標(biāo)識碼：A

文章編號：1001—3695(2007)02—0302—03

隨著人們對高速無線多媒體業(yè)務(wù)需求的快速增長，對無線通信系統(tǒng)提出了更高的要求，不僅需要系統(tǒng)有高數(shù)據(jù)傳輸能力、高頻譜利用效率，而且還需要系統(tǒng)能保證多業(yè)務(wù)傳輸?shù)姆?wù)質(zhì)量（QoS）。在通信網(wǎng)絡(luò)中，當(dāng)用戶提交給網(wǎng)絡(luò)的負(fù)載超過路由器等網(wǎng)絡(luò)設(shè)備的處理能力時，網(wǎng)絡(luò)就會發(fā)生擁塞，造成網(wǎng)絡(luò)吞吐量急劇下降，數(shù)據(jù)包大量丟失，嚴(yán)重時網(wǎng)絡(luò)處于癱瘓狀態(tài)。為了限制發(fā)送方不顧當(dāng)前網(wǎng)絡(luò)狀態(tài)盲目發(fā)送數(shù)據(jù)，TCP協(xié)議[1]采用擁塞控制算法來調(diào)整數(shù)據(jù)發(fā)送速率，主要包括慢啟動、擁塞避免、快速重傳、快速恢復(fù)和選擇性應(yīng)答等幾種核心算法[2]。接到擁塞通知后，TCP 協(xié)議根據(jù)上述算法調(diào)整數(shù)據(jù)發(fā)送速率，減少注入網(wǎng)絡(luò)的流量，達(dá)到緩解擁塞的目的。

隨機(jī)提前檢測（Random Early Detection，RED）算法[3]是S.Flord于1993年提出的一種主動式隊(duì)列管理算法，它用于預(yù)測擁塞，通過一定概率的丟包行為迫使端點(diǎn)調(diào)整速率，避免網(wǎng)絡(luò)擁塞。其核心思想是維護(hù)隊(duì)列的平均長度，當(dāng)有包到達(dá)時根據(jù)配置的參數(shù)和當(dāng)前平均隊(duì)列長度決定是否丟棄。之后人們還提出了這種算法的一些改進(jìn)形式[4，5]?？偟貋碚f，大多數(shù)RED算法都是針對有線網(wǎng)絡(luò)提出的。現(xiàn)有有線環(huán)境中應(yīng)用的RED算法卻不能簡單地移植到無線環(huán)境中，這是因?yàn)闊o線信道由于終端移動性和多徑傳播的影響，呈現(xiàn)時變快衰落特性，其惡劣的信道環(huán)境就可能導(dǎo)致無線鏈路的擁塞，而單純的基于平均隊(duì)列長度的RED算法無法及時感知無線鏈路的擁塞，因此不能有效地實(shí)現(xiàn)無線網(wǎng)絡(luò)中的擁塞控制，從而無法滿足寬帶無線網(wǎng)絡(luò)多業(yè)務(wù)傳輸?shù)腝oS需求。

1 隨機(jī)提前檢測算法基本原理

隨機(jī)提前檢測算法的基本思想是基于平均隊(duì)列長度的，這樣做的好處是允許一些短暫的突發(fā)業(yè)務(wù)量。它在路由器處檢測數(shù)據(jù)包的平均隊(duì)列長度，在擁塞即將發(fā)生時，按一定的概率丟棄進(jìn)入路由器的數(shù)據(jù)包，這樣就可以在擁塞發(fā)生之前及時地通知源端調(diào)整發(fā)送窗口，降低進(jìn)入網(wǎng)絡(luò)的數(shù)據(jù)流量，避免擁塞之后丟棄更多的數(shù)據(jù)包。

RED 路由器設(shè)置兩個閾值，即maxth和minth，對于每個到達(dá)的數(shù)據(jù)包，更新計算平均排隊(duì)隊(duì)列長度：

當(dāng)Qavgmaxth時，所有到來的數(shù)據(jù)包均被丟棄。因此，RED 算法可以簡單描述為如下數(shù)學(xué)過程[7]：

該算法在無線網(wǎng)絡(luò)中有兩種基本變形，一種是計算丟包率時，考慮數(shù)據(jù)包的大??；另一種則不考慮數(shù)據(jù)包的大小[6]。前者一個吸引人的特點(diǎn)是可以避免連續(xù)丟包，從而防止TCP的全局同步。后續(xù)的仿真中，將采用這種考慮丟包率大小的RED算法作為與本文提出算法的對比。

2 綜合考慮平均隊(duì)列長度和等待時間的RED算法

2.1 算法原理

本文提出的RED算法的改進(jìn)在于綜合考慮了平均隊(duì)列長度和等待時間的影響，其核心思想是對所有滿足插入隊(duì)列的數(shù)據(jù)包需要記錄其到達(dá)的絕對時間。當(dāng)有新的數(shù)據(jù)包到達(dá)時，根據(jù)配置的參數(shù)、當(dāng)前平均隊(duì)列長度、隊(duì)列是否為空以及當(dāng)前數(shù)據(jù)包與該隊(duì)列隊(duì)首數(shù)據(jù)包的時間差決定是否丟棄。

算法的基本原理描述如下：

（1）當(dāng)有新的業(yè)務(wù)數(shù)據(jù)包到達(dá)時，若該業(yè)務(wù)優(yōu)先級隊(duì)列為空，則直接將該數(shù)據(jù)包放入相應(yīng)隊(duì)列中，并記錄該數(shù)據(jù)包的絕對到達(dá)時間；

（2）當(dāng)有新數(shù)據(jù)包到達(dá)時，若該業(yè)務(wù)優(yōu)先級隊(duì)列非空，則計算新數(shù)據(jù)包與該隊(duì)列中最“老”的數(shù)據(jù)包的到達(dá)時間差，以及隊(duì)列平均長度，并根據(jù)這個時間差和平均隊(duì)列長度采用如下的丟棄處理原則：

①若到達(dá)時間差大于最大時間閾值或平均隊(duì)列長度大于最大隊(duì)列長度閾值時，予以丟棄；

②若到達(dá)時間差小于最小時間閾值，且平均隊(duì)列長度小于最小隊(duì)列長度閾值時，放入該業(yè)務(wù)優(yōu)先級隊(duì)列中，并記錄該數(shù)據(jù)包的到達(dá)時間；

③當(dāng)?shù)竭_(dá)時間差位于最小時間閾值和最大時間閾值之間，且平均隊(duì)列長度小于最小隊(duì)列長度閾值時，以較小的概率P₁丟棄該數(shù)據(jù)包；

④若到達(dá)時間差小于最小時間閾值，且平均隊(duì)列長度位于最小隊(duì)列長度閾值和最大隊(duì)列長度閾值時，以較大的概率P₂丟棄該數(shù)據(jù)包；

⑤當(dāng)?shù)竭_(dá)時間差位于最小時間閾值和最大時間閾值之間，且平均隊(duì)列長度也位于最小隊(duì)列長度閾值和最大閾值之間時，以較大的概率P₃丟棄該數(shù)據(jù)包。

其中，P₁23。

2.2 等待時間的計算

由于在數(shù)據(jù)包插入隊(duì)列時需要記錄該數(shù)據(jù)包到達(dá)的絕對時間，但在實(shí)際系統(tǒng)中絕對時間的表示范圍是有限的，因此，隨著時間的推移，其絕對時間存在溢出的現(xiàn)象。若采用32位機(jī)器碼表示時間，則等待時間的計算方法如下：

（1）根據(jù)到達(dá)包業(yè)務(wù)的優(yōu)先級，從該業(yè)務(wù)優(yōu)先級隊(duì)列中獲得最“老”的數(shù)據(jù)包即隊(duì)首的到達(dá)時刻（以firstTimeStamp標(biāo)記）；當(dāng)該業(yè)務(wù)優(yōu)先級隊(duì)列為空時，將firstTimeStamp置為0。

2.3 平均隊(duì)列長度的計算

用Qavg表示平均隊(duì)列長度，Qlen表示當(dāng)前隊(duì)列長度，則平均隊(duì)列長度的更新式為

其中，w是權(quán)重因子。權(quán)重因子w越大，平均隊(duì)列長度的舊值對整個平均隊(duì)列長度的影響就越大，平均隊(duì)列長度值的變化將越緩和；權(quán)重因子w越小，當(dāng)前隊(duì)列長度對平均隊(duì)列長度的影響越大，隊(duì)列長度的變化將很快反映給平均隊(duì)列長度。

2.4 隊(duì)列進(jìn)入空閑狀態(tài)時平均隊(duì)列長度的處理

由于RED算法是數(shù)據(jù)包驅(qū)動的，當(dāng)一段時間內(nèi)無數(shù)據(jù)包到達(dá)時，平均隊(duì)列長度無法更新。最惡劣的情況下，若數(shù)據(jù)包間歇性地突發(fā)到達(dá)，平均隊(duì)列長度將一直保持較大值，導(dǎo)致錯誤的丟包行為。

因此當(dāng)隊(duì)列進(jìn)入空閑狀態(tài)之后，有包到達(dá)時直接將該數(shù)據(jù)包插入相應(yīng)優(yōu)先級隊(duì)列，并記錄該數(shù)據(jù)包的絕對到達(dá)時間，同時還必須根據(jù)特定算法虛擬產(chǎn)生m個數(shù)據(jù)包進(jìn)入隊(duì)列，來更新平均隊(duì)列長度，以免造成后續(xù)數(shù)據(jù)包不必要的丟失。一般來說

其中，t是隊(duì)列為空的時間，Lavpkt是數(shù)據(jù)包平均長度，Bwidth是帶寬。再根據(jù)m更新平均隊(duì)列長度：

參數(shù)符號的定義說明如表1所示。其中，Lmin的值一般等于用戶所能接受的最大時延和設(shè)備帶寬的乘積，而Lmax一般為Lmin的兩倍以上。

3 試驗(yàn)仿真

采用Opnet進(jìn)行了試驗(yàn)仿真，對本文提出的算法性能進(jìn)行了仿真分析。仿真的拓?fù)浣Y(jié)構(gòu)采用典型的啞鈴模型，如圖1所示。瓶頸帶寬為30MB，延時分兩組15ms和60ms，MTU大傳輸單元（Maximum Transport Unit）分別為350B，700B，1500B。TCP的有效吞吐率公式為BW≤MTU×CRTT×P，其中，C是常量，它依賴于所采用的TCP類型，RTT是往返時間（Round Trip Time），P是丟包率。以文獻(xiàn)[6]中考慮數(shù)據(jù)包大小的RED算法作為試驗(yàn)參照，記作T-RED，本文算法記作M-RED。

首先仿真了系統(tǒng)吞吐量和丟包率的性能。丟包率是某個MTU下丟棄的數(shù)據(jù)包數(shù)和發(fā)送的總數(shù)據(jù)包數(shù)之比。結(jié)果如表2和表3所示。由仿真結(jié)果可以看出，一般來說，丟包率越高，相應(yīng)的吞吐量越小。本文的M-RED算法在MTU較大時可以獲得較高的吞吐量和相對較低的丟包率。這就意味著，在負(fù)荷較重的網(wǎng)絡(luò)情況下，本文提出的M-RED能更好地應(yīng)對網(wǎng)絡(luò)擁塞的狀況，低負(fù)載條件下，則是T-RED算法略優(yōu)。因此，可以預(yù)見，對于普通的話音業(yè)務(wù)一類低負(fù)荷業(yè)務(wù)，本文的M-RED算法不一定能顯出優(yōu)勢，但在多用戶視頻對話，實(shí)時點(diǎn)播一類多媒體業(yè)務(wù)背景下，本文的M-RED算法能有更好的表現(xiàn)。

然后作點(diǎn)對點(diǎn)的加載FTP業(yè)務(wù)試驗(yàn)。FTP文件的大小為100MB，為模擬無線信道的時變快衰落特性造成的效應(yīng)，控制誤幀率和數(shù)據(jù)誤幀率分別設(shè)置為（0，10％）和（5％，20％）兩種情況，仿真中TCP協(xié)議采用Jacobson所提出的方法[8]來實(shí)時地更新超時重傳時間。從圖2的實(shí)驗(yàn)結(jié)果可以看出，M-RED算法比T-RED算法具有更低的鏈路層時延抖動，即便在數(shù)據(jù)誤幀達(dá)到20％和控制誤幀達(dá)到5％時的相對惡劣信道條件下，鏈路層的時延抖動仍小于6×10^-3。這表明M-RED算法在衰落嚴(yán)重的無線信道條件能提供更穩(wěn)定的網(wǎng)絡(luò)服務(wù)質(zhì)量。

4 結(jié)束語

本文提出的將平均隊(duì)列長度和等待時間綜合考慮進(jìn)行擁塞控制的RED算法的優(yōu)點(diǎn)，包括通過最大隊(duì)列長度的動態(tài)調(diào)整，能有效地實(shí)現(xiàn)無線鏈路中的擁塞控制；在負(fù)荷較大時能獲得較高的吞吐量和相對較低的丟包率，更適合于承載無線寬帶業(yè)務(wù)；減少了數(shù)據(jù)包的時延抖動，能夠獲得更穩(wěn)定的系統(tǒng)性能；不同條件下采用不同的丟棄概率；在網(wǎng)絡(luò)負(fù)荷較大時，盡量使TCP進(jìn)行快速重傳和快速恢復(fù)，達(dá)到有效進(jìn)行擁塞控制的同時，提高了網(wǎng)絡(luò)的利用效率。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。