分布式隊(duì)列服務(wù)算法在無(wú)線網(wǎng)狀網(wǎng)包調(diào)度中的應(yīng)用

李精華,嵇建波

(桂林航天工業(yè)高等?？茖W(xué)校 電子工程系, 廣西 桂林541004)

1 引 言

無(wú)線網(wǎng)狀網(wǎng)作為下一代的無(wú)線網(wǎng)絡(luò)技術(shù),必然要求它能夠傳輸高速的多種數(shù)據(jù)業(yè)務(wù),支持這些業(yè)務(wù)關(guān)鍵就是要保證業(yè)務(wù)的QoS 要求[1],與QoS 密切相關(guān)的技術(shù)就是如何為網(wǎng)絡(luò)設(shè)計(jì)合適的包調(diào)度算法。包調(diào)度算法就是通過(guò)對(duì)數(shù)據(jù)包進(jìn)行緩存,控制數(shù)據(jù)包的發(fā)送時(shí)間和發(fā)送次序。

目前的無(wú)線包調(diào)度算法主要集中在保障網(wǎng)絡(luò)各連接的QoS 前提下,追求系統(tǒng)吞吐量極大化,是基于數(shù)據(jù)包所屬的“類”或“流”來(lái)進(jìn)行調(diào)度的,在進(jìn)行調(diào)度時(shí),調(diào)度器首先會(huì)把應(yīng)用業(yè)務(wù)分成不同的“類”或“流”,并給這些業(yè)務(wù)流賦予不同的優(yōu)先級(jí),然后調(diào)度器根據(jù)這個(gè)優(yōu)先級(jí)來(lái)對(duì)數(shù)據(jù)包進(jìn)行調(diào)度,比如EDF調(diào)度算法就屬于這種。這樣的調(diào)度策略有一個(gè)典型的缺點(diǎn),就是當(dāng)網(wǎng)絡(luò)增加一類新的服務(wù)時(shí)就需要對(duì)調(diào)度器進(jìn)行相應(yīng)的配置,使它能支持相應(yīng)的服務(wù),因此傳統(tǒng)調(diào)度算法的可擴(kuò)展性是一個(gè)不容忽視的問(wèn)題。另外,傳統(tǒng)調(diào)度器對(duì)應(yīng)用業(yè)務(wù)的分類不細(xì),從而會(huì)導(dǎo)致一些低優(yōu)先級(jí)的包長(zhǎng)時(shí)間得不到服務(wù)。

基于以上算法的弱點(diǎn),本文提出一種分布式隊(duì)列服務(wù)算法(DQS),能根據(jù)數(shù)據(jù)包所經(jīng)過(guò)端到端的變化情況進(jìn)行動(dòng)態(tài)的調(diào)度。DQS 算法為網(wǎng)絡(luò)提供更為細(xì)化的應(yīng)用業(yè)務(wù),在保證實(shí)時(shí)用戶的QoS 需求的前提下,充分考慮用戶的公平性,實(shí)現(xiàn)最大化系統(tǒng)的吞吐量。

2 分布式隊(duì)列服務(wù)算法(DQS)描述

差分隊(duì)列服務(wù)算法[2]目的是為了在有線網(wǎng)絡(luò)中為各類數(shù)據(jù)業(yè)務(wù)提供更加細(xì)化的QoS,主要優(yōu)點(diǎn)是能夠根據(jù)資源的利用情況給業(yè)務(wù)應(yīng)用提供更加細(xì)化的端到端QoS 服務(wù)。其算法的基本原理是:設(shè)一個(gè)網(wǎng)路由n 個(gè)節(jié)點(diǎn)組成,數(shù)據(jù)包的傳輸路徑是固定不變的,在不考慮傳播延時(shí),當(dāng)一個(gè)數(shù)據(jù)包到達(dá)節(jié)點(diǎn)i時(shí),該數(shù)據(jù)包端到端的剩余延時(shí)為

其中,T 為數(shù)據(jù)包的最大的端到端延時(shí), τi為數(shù)據(jù)包經(jīng)過(guò)i 所花費(fèi)的實(shí)際延時(shí)。這樣,數(shù)據(jù)包在某個(gè)節(jié)點(diǎn)所允許最大有效延時(shí)δi為

如果上游的節(jié)點(diǎn)都按固定的算法限制了每個(gè)數(shù)據(jù)包的延時(shí),那么就可以得:

其中,yi為數(shù)據(jù)包到達(dá)某個(gè)節(jié)點(diǎn)的時(shí)間;xi為數(shù)據(jù)包離開(kāi)某個(gè)節(jié)點(diǎn)最近的時(shí)間,這個(gè)時(shí)間被用來(lái)作為包在緩存中排隊(duì)順序的依據(jù)。

由式(1)～(3)可以看出,差分隊(duì)列服務(wù)算法對(duì)數(shù)據(jù)包進(jìn)行調(diào)度的依據(jù)是端到端的延時(shí)而不是根據(jù)數(shù)據(jù)包所屬的數(shù)據(jù)流或類。通過(guò)這種方式,差分隊(duì)列服務(wù)算法可以為應(yīng)用業(yè)務(wù)提供更加細(xì)化的QoS 支持。在無(wú)線網(wǎng)格網(wǎng)中利用差分隊(duì)列服務(wù)算法為應(yīng)用業(yè)務(wù)提供端到端QoS 的支持是很有益處的,但公式(2)中節(jié)點(diǎn)i 是利用δj(j >i)來(lái)推導(dǎo)公式(3)中的xi,這在無(wú)線網(wǎng)絡(luò)中是很困難的,因?yàn)棣膉只能在將來(lái)的某個(gè)時(shí)刻得到,而不可能在數(shù)據(jù)包到達(dá)本節(jié)點(diǎn)時(shí)計(jì)算出來(lái)。因此實(shí)現(xiàn)DQS 算法一個(gè)很重要的問(wèn)題就是如何在節(jié)點(diǎn)i 去估計(jì)δj的值,也就是說(shuō)如何去估計(jì)數(shù)據(jù)包在剩余路徑的延時(shí)情況。

分布式貝爾曼-福特算法[3]是在貝爾曼-福特算法基礎(chǔ)上演進(jìn)出來(lái)的可預(yù)測(cè)表驅(qū)動(dòng)路由算法,也就是說(shuō)每一個(gè)節(jié)點(diǎn)都會(huì)維護(hù)一個(gè)路由表,每一個(gè)節(jié)點(diǎn)都會(huì)初始化一個(gè)到它相鄰節(jié)點(diǎn)的距離矢量表。比如有一條鏈路,它由6 個(gè)節(jié)點(diǎn)組成,節(jié)點(diǎn)1 在某個(gè)時(shí)刻t 1發(fā)送出去一個(gè)探測(cè)包,在時(shí)刻t 2節(jié)點(diǎn)2 收到這個(gè)探測(cè)包,則節(jié)點(diǎn)1 到節(jié)點(diǎn)2 的單步延時(shí)為t1-t2,此時(shí)為節(jié)點(diǎn)2 創(chuàng)建一個(gè)時(shí)延表,這個(gè)表用來(lái)記錄經(jīng)過(guò)節(jié)點(diǎn)2 的所有數(shù)據(jù)包的延時(shí)情況。同時(shí),為了讓節(jié)點(diǎn)2 能夠知道其他節(jié)點(diǎn)間的延時(shí)情況,必須要求每個(gè)節(jié)點(diǎn)在發(fā)送探測(cè)包的同時(shí)把自己的時(shí)延表也發(fā)送出去。這樣經(jīng)過(guò)一段時(shí)間后節(jié)點(diǎn)2 就能夠知道這條鏈路中任意兩個(gè)節(jié)點(diǎn)之間的延時(shí)了,這個(gè)時(shí)延表如表1 所示。

表1 節(jié)點(diǎn)2 中的時(shí)延表Table 1 Delay table at node 2

根據(jù)表1 所示的時(shí)延表,當(dāng)一個(gè)數(shù)據(jù)包到達(dá)節(jié)點(diǎn)時(shí)DQS 調(diào)度器可以通過(guò)查詢表1 所示的延時(shí)表來(lái)知道數(shù)據(jù)包在剩余路徑的延時(shí)情況,然后通過(guò)公式(2)計(jì)算出數(shù)據(jù)包在本節(jié)點(diǎn)的最遲離開(kāi)時(shí)間,DQS調(diào)度器會(huì)根據(jù)離開(kāi)時(shí)間的大小對(duì)數(shù)據(jù)包進(jìn)行排隊(duì)。離開(kāi)時(shí)間越小表示數(shù)據(jù)包需要越早得到服務(wù),反之說(shuō)明數(shù)據(jù)包可以在節(jié)點(diǎn)里停留相對(duì)較長(zhǎng)的時(shí)間,因此可以把它放在隊(duì)列的后面。

3 分布式隊(duì)列服務(wù)算法性能分析

這里使用Ad Hoc 網(wǎng)絡(luò)仿真模型[4],在NS2 仿真平臺(tái)上進(jìn)行仿真分析[5]。

3.1 探測(cè)包性能

數(shù)據(jù)包在剩余路徑所經(jīng)歷的時(shí)延估計(jì)主要是通過(guò)路由層發(fā)送探測(cè)包得到的,探測(cè)包發(fā)送的目的是為了估計(jì)當(dāng)前網(wǎng)絡(luò)的延時(shí)情況,即探測(cè)包的延時(shí)反映了網(wǎng)絡(luò)當(dāng)前的延時(shí)情況,探測(cè)包的延時(shí)小網(wǎng)絡(luò)則當(dāng)前的擁塞小,探測(cè)包的延時(shí)大則網(wǎng)絡(luò)擁塞也大。一般探測(cè)包的數(shù)量隨著探測(cè)周期的變大而減少,探測(cè)包的數(shù)量可以通過(guò)理論公式(4)計(jì)算:

式中,N 表示節(jié)點(diǎn)數(shù),L 表示仿真的時(shí)間長(zhǎng)度, T 表示探測(cè)包的發(fā)送周期, n 表示仿真過(guò)程中總共發(fā)送多少探測(cè)包。

在NS 仿真平臺(tái)上對(duì)7 個(gè)節(jié)點(diǎn)的探測(cè)包數(shù)量在不同的發(fā)送周期下進(jìn)行仿真分析,仿真場(chǎng)景采用CBR 流和VBR 流共存的方式,使用線性拓?fù)浣Y(jié)構(gòu),路徑長(zhǎng)度為6,仿真時(shí)間為500 s。圖1 是7 個(gè)節(jié)點(diǎn)的探測(cè)包的數(shù)量在不同發(fā)送周期下的曲線變化圖。從圖1 可以看出,當(dāng)時(shí)延探測(cè)包發(fā)送周期為1 s時(shí),節(jié)點(diǎn)在仿真過(guò)程中總共發(fā)送出約3 500個(gè)探測(cè)包;當(dāng)時(shí)延探測(cè)包發(fā)送周期為12 s時(shí),節(jié)點(diǎn)在仿真過(guò)程中總共發(fā)送出290 個(gè)探測(cè)包。仿真結(jié)果與公式(4)計(jì)算出來(lái)的結(jié)果是相吻合的,從而驗(yàn)證了DQS 調(diào)度算法的探測(cè)包的延時(shí)符合設(shè)計(jì)需求。

圖1 不同探測(cè)周期下的探測(cè)包數(shù)量Fig.1 The number of hello packet in different period

3.2 緩沖區(qū)的使用率

在DQS 調(diào)度算法中使用了控制包隊(duì)列和數(shù)據(jù)包隊(duì)列兩個(gè)隊(duì)列,NS 仿真使用CBR 流和VBR 流,線性拓?fù)浣Y(jié)構(gòu),7 個(gè)節(jié)點(diǎn)數(shù),仿真總時(shí)間是500 s,每個(gè)隊(duì)列的最大長(zhǎng)度為50 個(gè)包,探測(cè)包的發(fā)送周期每3 s發(fā)送一次。對(duì)控制包隊(duì)列和數(shù)據(jù)包隊(duì)列在每個(gè)節(jié)點(diǎn)的使用情況進(jìn)行統(tǒng)計(jì),計(jì)算每個(gè)節(jié)點(diǎn)隊(duì)列的平均使用率和最大使用長(zhǎng)度。圖2 為控制包隊(duì)列中每個(gè)節(jié)點(diǎn)在整個(gè)仿真周期內(nèi)的使用情況。從圖2(a)可以看出,中間節(jié)點(diǎn)隊(duì)列的使用率最高,這也表明中間節(jié)點(diǎn)最可能成為網(wǎng)絡(luò)的瓶頸節(jié)點(diǎn)。圖2(b)是每個(gè)節(jié)點(diǎn)中控制隊(duì)列的最大使用長(zhǎng)度,最大使用長(zhǎng)度是指節(jié)點(diǎn)在最繁忙時(shí)最多需要處理多少個(gè)包,圖2(b)的中間部分最高,表明需要處理的包數(shù)量最多。因此從圖2 中可以看出,控制包在中間節(jié)點(diǎn)會(huì)等待較長(zhǎng)的時(shí)間,這與實(shí)際情況也是吻合的。

圖2 控制包隊(duì)列的統(tǒng)計(jì)Fig.2 Statistic of control packet queue

圖3 為數(shù)據(jù)包隊(duì)列在每個(gè)節(jié)點(diǎn)的使用情況,其曲線的趨勢(shì)與控制包隊(duì)列基本相似。在DQS 調(diào)度算法中,由于控制包和數(shù)據(jù)包的發(fā)送速率以及處理優(yōu)先級(jí)是不同的,其中數(shù)據(jù)包的優(yōu)先級(jí)比控制包的優(yōu)先級(jí)低,因此從圖2 和圖3 可以看出,數(shù)據(jù)包隊(duì)列的平均利用率比較高,但數(shù)據(jù)包隊(duì)列要比控制包隊(duì)列要長(zhǎng)。

圖3 數(shù)據(jù)包隊(duì)列的統(tǒng)計(jì)Fig.3 Statistic of data packet queue

從圖2 和圖3 中可以看出,DQS 算法對(duì)緩存的要求不高,這樣可以節(jié)省更多的緩存空間。

3.3 實(shí)際平均吞吐量分析

實(shí)際平均吞吐量[6]是指數(shù)據(jù)發(fā)送者成功地傳輸給接收者的度量標(biāo)準(zhǔn),即接收端成功接收到的包個(gè)數(shù)與發(fā)送端發(fā)送的包個(gè)數(shù)的一個(gè)比值。為了便于仿真分析,在這里接收端只計(jì)算那些滿足端到端延時(shí)的數(shù)據(jù)包個(gè)數(shù)。在NS 仿真中采用隨機(jī)拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu),運(yùn)用恒速比特率(CBR)和變速比特率(VBR)兩種數(shù)據(jù)源,每一個(gè)隊(duì)列的長(zhǎng)度是50 個(gè)數(shù)據(jù)包,通過(guò)改變數(shù)據(jù)源的個(gè)數(shù)和節(jié)點(diǎn)的個(gè)數(shù)來(lái)模擬真實(shí)網(wǎng)絡(luò)中的情景。這里以EDF 調(diào)度算法作為參照算法與DQS 算法進(jìn)行對(duì)比分析。圖4 為DQS 調(diào)度算法和EDF 調(diào)度算法的平均實(shí)際吞吐量曲線圖,其中圖4(a)使用CBR 流,圖4(b)使用VBR 流,這兩種數(shù)據(jù)源的前6 跳EDF 調(diào)度性能與DQS 調(diào)度性能相差不大,一旦數(shù)據(jù)包的路徑長(zhǎng)度大于6 以后,DQS 調(diào)度算法平均實(shí)際吞吐量下降的程度明顯要低于EDF 調(diào)度算法。最好的情況是DQS 調(diào)度算法的實(shí)際平均吞吐量比EDF 調(diào)度算法的實(shí)際平均吞吐量性能提高了16%。其原因是DQS 調(diào)度算法充分考慮了應(yīng)用業(yè)務(wù)的端到端情況,它可以根據(jù)數(shù)據(jù)包端到端的變化來(lái)對(duì)其進(jìn)行調(diào)度;而EDF 只是在每一跳給數(shù)據(jù)包一個(gè)固定的延時(shí),并且是基于這個(gè)延時(shí)來(lái)對(duì)數(shù)據(jù)包進(jìn)行調(diào)度,它并沒(méi)有把數(shù)據(jù)包端到端的變化情況考慮進(jìn)去。所以當(dāng)數(shù)據(jù)包路徑長(zhǎng)度發(fā)生變化時(shí),EDF 調(diào)度算法的實(shí)際平均吞吐量性能比DQS 調(diào)度算法的性能下降得快。

圖4 平均實(shí)際吞吐量Fig.4 Average throughput

3.4 平均端到端延時(shí)分析

平均端到端延時(shí)是指數(shù)據(jù)包從原節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)歷的平均端到端延時(shí)[7]。使用的仿真條件和2.3 節(jié)的仿真條件一樣, 圖5 為DQS 調(diào)度算法和EDF 調(diào)度算法[8]的端到端延時(shí)曲線圖。

圖5 端到端延時(shí)Fig.5 The delay of end-to-end

從圖5 可以看出,DQS 調(diào)度算法的端到端延時(shí)性能比EDF 調(diào)度算法的性能好,這主要是由于DQS調(diào)度算法會(huì)把數(shù)據(jù)包的端到端延時(shí)作為一個(gè)調(diào)度因素來(lái)考慮,所以它具有更好的端到端延時(shí)性能。

4 總 結(jié)

無(wú)線網(wǎng)狀網(wǎng)作為下一代無(wú)線網(wǎng)絡(luò)的關(guān)鍵技術(shù),為其設(shè)計(jì)合適的包調(diào)度算法是一項(xiàng)很有挑戰(zhàn)性的工作。DQS 包調(diào)度算法解決了無(wú)線網(wǎng)狀網(wǎng)為多個(gè)等待接收服務(wù)的分組業(yè)務(wù)流安排合理的服務(wù)規(guī)則,特別是DQS 包調(diào)度算法在緩沖區(qū)的使用率、實(shí)際平均吞吐量性能和平均端到端延時(shí)性能上具有較高的性能。但還存在一些不夠完善及有待改進(jìn)的地方,比如在DQS 調(diào)度算法中控制包和業(yè)務(wù)數(shù)據(jù)包在網(wǎng)絡(luò)傳輸過(guò)程中的相互影響,如何在環(huán)境變化的無(wú)線鏈路中使探測(cè)包的周期控制在一個(gè)合適的范圍之內(nèi),在高速運(yùn)動(dòng)情況下的性能情況有何區(qū)別等,這些問(wèn)題還需要深入研究。

[1] 劉俊芳,趙爾敦,劉巍.小無(wú)線網(wǎng)絡(luò)中基于BLUF 的包調(diào)度算法[J] .計(jì)算機(jī)工程與應(yīng)用,2008,44(16):108-110.

LIU Jun-fang, ZHAO Er-dun, LIU Wei.Wireless packet scheduling algorithm based on BLUF in wireless networks[J] .Computer Engineering and Applications, 2008,44(16):108-110.(in Chinese)

[2] Jiang S M.Granular Differentiated Queueing Services for QoS:Structure and Cost Model[ J] .ACM SIGCOMM Computer Communication Review, 2005, 35(2):13-22.

[3] Bertsekas D, Gallager R.Data Networks[ M] .Englewood Cliffs, NJ:Prentice-Hall,1987.

[4] 錢(qián)權(quán).無(wú)線Ad Hoc 網(wǎng)絡(luò)安全[M] .北京:清華大學(xué)出版社,2009.

QIAN Quan.Wireless Ad Hoc Network Security[M] .Beijing:Tsinghua University Press,2009.(in Chinese)

[5] 時(shí)慧晶, 趙燁.基于NS2 的Ad Hoc 網(wǎng)絡(luò)路由協(xié)議性能研究[C]//全國(guó)第21 屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議(CACIS·2010)暨全國(guó)第2 屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集.上海:[ s.n.] ,2010:17-131.

SHI Hui-jing, ZHAO Ye.Research on Performance of Ad Hoc Routing Protocol Using NS2[ C]//Proceedings of the 21th National Computer Technology and Application Conference and the National 2nd safety -critical Technology and App lication Conference.Shanghai:[ s.n.] , 2010:17 -131.(in Chinese)

[6] 顧金媛, 章國(guó)安, 包志華.認(rèn)知無(wú)線mesh 網(wǎng)中聯(lián)合路由的分布式信道分配算法[J] .計(jì)算機(jī)應(yīng)用研究,2010(9):3476-3479.

GU Jin-yuan,ZHANG Guo-an, BAO Zhi-hua.Distributed joint routing and channel assignment algorithm in cognitive wireless mesh networks[ J] .App lication Research of Computers, 2010(9):3476-3479.(in Chinese)

[ 7] 陳潛,劉云.動(dòng)態(tài)高速環(huán)境下Ad Hoc 路由協(xié)議研究[J] .中北大學(xué)學(xué)報(bào)(自然科學(xué)版),2011(10):579-582.

CHEN Qian,LIU Yun.Research on Ad Hoc Routing Protocol in High Speed Dynamic Environment[ J] .Journal of North University of China(Natural Science Edition), 2011(10):579-582.(in Chinese)

[ 8] Guerin R,Peris V.Quality-of-service in packet networks:Basic mechanisms and directions [ J] .Computer Networks,1999, 31(3):169-189.