基于NS2的優(yōu)先級隊列管理算法設(shè)計*

潘豐旻， 江 明， 周加文， 葛 愿

(安徽工程大學，安徽 蕪湖 241000)

0 引 言

網(wǎng)絡(luò)控制系統(tǒng)(Networked Contorl Systems，NCS)于1999年出現(xiàn)在馬里蘭大學Walsh的論著中，該系統(tǒng)利用通信媒介使控制回路形成閉環(huán)[1]。與傳統(tǒng)的控制系統(tǒng)不同，它采用多樣的網(wǎng)絡(luò)連接方式提高了系統(tǒng)組件的靈活性，在智能電網(wǎng)、智能交通等領(lǐng)域有著巨大的應(yīng)用前景[2-3]。融合了計算機技術(shù)和通信技術(shù)的NCS，除了控制算法影響其性能好壞以外，合理地調(diào)度計算機的網(wǎng)絡(luò)資源也十分必要.NCS的網(wǎng)絡(luò)服務(wù)質(zhì)量指標包括時延、丟包和吞吐量等。由于網(wǎng)絡(luò)的不穩(wěn)定性必然引入時延、丟包等問題[4-6]。因此，要在NCS的網(wǎng)絡(luò)傳輸部分采用合適有效的隊列管理算法。

進行實驗?zāi)M是研究分析NCS性能的高效方法。NCS模擬工具主要包括MATLAB、OPNET以及NS2.MATLAB的TrueTime工具箱在控制策略方面的模擬功能強大，但其網(wǎng)絡(luò)模塊的功能相對薄弱，模擬NCS網(wǎng)絡(luò)環(huán)境中的隊列管理機制較為困難；OPNET具有很強的網(wǎng)絡(luò)功能，但這款商用軟件使用費較為高昂；而NS2作為一款開源免費的軟件，它采用分裂對象模型的方式，利用Otcl語言搭建網(wǎng)絡(luò)拓撲結(jié)構(gòu)，C++語言實現(xiàn)具體協(xié)議，達到了模擬配置靈活性和仿真運行高效性的統(tǒng)一[7-9]，受到越來越多的重視。如高文宇等人提出的網(wǎng)絡(luò)仿真軟件NS2中隊列調(diào)度算法的擴展[10]。楊故等提出的基于NS2的改進隊列管理算法及其實現(xiàn)[11]。高鵬等人基于NS2的主動隊列管理算法的仿真與分析[12]等。為此，本文首先設(shè)計NCS中的優(yōu)先級隊列管理算法；其次利用NS2搭建一個網(wǎng)絡(luò)傳輸模型，并調(diào)用隊列管理算法進行仿真實驗；最后進行實驗數(shù)據(jù)的分析和實驗結(jié)果的總結(jié)。

1 基于NS2的優(yōu)先級隊列管理算法實現(xiàn)

1.1 隊列管理算法

網(wǎng)絡(luò)業(yè)務(wù)流以數(shù)據(jù)分組的形式在網(wǎng)絡(luò)中傳輸。它們流經(jīng)不同網(wǎng)絡(luò)節(jié)點時會采取隊列緩存、延遲轉(zhuǎn)發(fā)等服務(wù)方式，而隊列管理的作用就在于此。能通過丟棄或者標記這些數(shù)據(jù)分組來管理網(wǎng)絡(luò)傳輸節(jié)點中的隊列緩沖資源。隊列管理主要分為主動式隊列管理及被動式隊列管理。主動式隊列管理算法通過預(yù)測分組的狀態(tài)特性，在網(wǎng)絡(luò)擁塞還未發(fā)生之前就按照預(yù)先的設(shè)定進行相應(yīng)的棄包，從而有效控制隊列緩沖區(qū)的長度，其中的典型算法為RED；而被動式隊列管理算法在隊列緩沖區(qū)設(shè)置了固定的數(shù)據(jù)分組存儲上限，當隊列中接收到的分組達到上限值，則啟動棄包機制，其中典型算法有DropTail算法。驗證隊列管理算法性能的好壞，要從業(yè)務(wù)需求和算法復雜程度出發(fā)，結(jié)合時延、丟包、吞吐量等因素進行綜合討論,而兩種典型算法的算法性能如表1所示。

主動隊列管理算法結(jié)構(gòu)較為復雜，增加設(shè)備開銷，平均時延相對較高，網(wǎng)絡(luò)吞吐量也相對較低。其參數(shù)設(shè)置敏感并且網(wǎng)絡(luò)響應(yīng)相對滯后，并沒有在網(wǎng)絡(luò)當中得到大量使用；相比之下，雖然被動式隊列管理算法丟包率相對較高，但其相對較低的延時特性以及簡單的算法結(jié)構(gòu)，在實際網(wǎng)絡(luò)中仍獲得廣泛使用。

1.2 PDropTail算法設(shè)計

NCS因為系統(tǒng)業(yè)務(wù)類型復雜，不同業(yè)務(wù)之間對于網(wǎng)絡(luò)服務(wù)質(zhì)量往往有著不同需求，需要在保持較低時延和較高吞吐量的基礎(chǔ)上進行優(yōu)先級區(qū)分服務(wù)。所以新的算法具有優(yōu)先級識別機制，它在選擇棄包方面不再是直接“棄尾”，而是綜合考慮了隊列中數(shù)據(jù)分組的優(yōu)先級情況：當數(shù)據(jù)分組進入節(jié)點的隊列緩沖區(qū)時，若緩沖區(qū)為未滿狀態(tài)，則仍然按照先進先出的原則實行隊列管理；若緩沖區(qū)為已滿狀態(tài)，則啟動優(yōu)先級識別機制，選取隊列緩沖區(qū)隊頭前兩個數(shù)據(jù)分組進行優(yōu)先級比較。若第一個數(shù)據(jù)分組的優(yōu)先級較高，則選擇丟棄隊列尾的數(shù)據(jù)分組，否則丟棄隊列頭。PDropTail隊列管理算法原理如圖1所示。

表1 隊列管理算法性能對比

圖1 PDropTail隊列管理算法原理圖

1.3 PDropTail算法在NS2中的實現(xiàn)

利用NS2仿真軟件進行PDropTail算法的設(shè)計，首先需要在NS2中進行算法腳本的編譯與添加。而PDropTail算法的優(yōu)先級識別機制和棄包選擇機制的部分核心程序代碼如下：

void PDropTail::enque(Packet* p)

{

……

int qlimBytes = qlim_ * mean_pktsize_;

if ((!qib_ && (q_->length() + 1) >= qlim_) ||

(qib_&&(q_->byteLength()+hdr_cmn::access(p)

->size()) >= qlimBytes))

{

int prio1,prio2;

prio1=HDR_IP(q_->lookup(0))->prio();

prio2=HDR_IP(q_->lookup(1))->prio();

if(prio2>prio1) {

q_->enque(p);

Packet* pp=q_->deque();

drop(pp);

}

else {

drop(p);

}

} else {

q_->enque(p);

}

}

qib_&&(q_->byteLength()+hdr_cmn::access(p)函數(shù)部分是對緩沖區(qū)的狀態(tài)進行判斷，若隊列為滿狀態(tài)，則啟動優(yōu)先級比較機制對隊列頭前兩個數(shù)據(jù)分組的優(yōu)先級prio1和prio2進行比較。該比較機制中若第二個數(shù)據(jù)分組的優(yōu)先級更大則強制丟棄隊頭數(shù)據(jù)分組drop(pp)；若第一個數(shù)據(jù)分組優(yōu)先級大則強制丟棄隊尾分組drop(p)。而當隊列狀態(tài)為未滿時，數(shù)據(jù)分組將直接進入隊列緩沖區(qū)enque(p)。

2 基于NS2的網(wǎng)絡(luò)模擬與算法性能分析

2.1 搭建網(wǎng)絡(luò)拓撲結(jié)構(gòu)

利用NS2仿真軟件搭建如圖2所示的NCS網(wǎng)絡(luò)傳輸模型。搭建該模型的步驟包括節(jié)點設(shè)置以及鏈路配置兩方面。從節(jié)點設(shè)置方面考慮，標號為8、9的兩節(jié)點設(shè)為路由節(jié)點，0、1、2、3節(jié)點設(shè)為發(fā)送節(jié)點，4、5、6、7設(shè)置為接收節(jié)點；從鏈路配置方面考慮，兩路由節(jié)點間的瓶頸鏈路帶寬設(shè)為1.7 M，時延設(shè)為20 ms，其余鏈路帶寬均設(shè)為2 M，時延為設(shè)10 ms。這樣的拓撲結(jié)構(gòu)設(shè)計和帶寬配置主要為了讓數(shù)據(jù)分組在傳輸過程中產(chǎn)生一定的網(wǎng)絡(luò)擁塞情況。

在0到4,1到5,2到6以及3到7鏈路之間各建立一條UDP聯(lián)機，并在UDP聯(lián)機之上建立CBR流量發(fā)生器.為了模擬4個不同優(yōu)先級業(yè)務(wù)，需要對數(shù)據(jù)分組的IP包頭設(shè)置優(yōu)先級。將4種業(yè)務(wù)的優(yōu)先級分別設(shè)置為1、2、3、4，其中數(shù)字越大為優(yōu)先級越高，在網(wǎng)絡(luò)中將獲得優(yōu)先服務(wù)。網(wǎng)絡(luò)模型搭建完成后，分別調(diào)用兩種算法進行模擬實驗，模型正常工作后會出現(xiàn)如下的動畫效果如圖2所示。網(wǎng)絡(luò)模型搭建的主要代碼如下：

set n8 [MYMns node]

set n9 [MYMns node] //路由節(jié)點設(shè)置

MYMns duplex-link MYMn8 MYMn9 1.7M 20ms 算法

MYMns queue-limit MYMn8 MYMn9 10

for {set i 0} {MYMi<3} {incr i} {

set s(MYMi) [MYMns node]

set d(MYMi) [MYMns node]

MYMns duplex-link MYMs (MYMi) MYMn8 2M 10ms 算法

MYMns duolex-link MYMn9 MYMd (MYMi) 2M 10ms 算法

//發(fā)送節(jié)點、接收節(jié)點設(shè)置以及鏈路參數(shù)配置

set udp (MYMi) [new Agent/UDP]

set null (MYMi) [new Agent/Null]

MYMns attach-agent MYMs (MYMi) MYMudp (MYMi)

MYMns attach-agent MYMd (MYMi) MYMnull (MYMi)

MYMns connect MYMudp (MYMi) MYMnull (MYMi)

MYMudp (MYMi) set fid_ MYMi

MYMudp (MYMi) set prio_ MYMi //建立udp聯(lián)機

set cbr (MYMi) [new Application/Traffic/CBR]

MYMcbr (MYMi) attach-agent MYMudp (MYMi)

} //cbr流量發(fā)生器設(shè)置

圖2 網(wǎng)絡(luò)模擬動畫效果

2.2 隊列管理算法性能分析與比較

調(diào)用兩種算法下的業(yè)務(wù)時延情況如圖3所示，其中業(yè)務(wù)cbr1為獲得最高優(yōu)先級的業(yè)務(wù)，cbr4為優(yōu)先級最低的業(yè)務(wù)。調(diào)用兩種算法下，當模擬時間在0.3 s之前，網(wǎng)絡(luò)業(yè)務(wù)量都不斷上升，節(jié)點緩沖區(qū)中的數(shù)據(jù)分組不斷增多導致網(wǎng)絡(luò)時延不斷增大。但此時由于緩沖區(qū)為未滿狀態(tài)，隊列管理機制仍采取“先進先出”的原則，此時，兩種算法下的網(wǎng)絡(luò)時延情況大體一致。當數(shù)據(jù)分組在隊列緩沖區(qū)開始擁塞的情況下，DropTail算法采取“棄尾”機制不停丟棄隊尾分組。而PDropTail算法采取優(yōu)先級識別和棄包選擇機制后，高優(yōu)先級業(yè)務(wù)獲得優(yōu)先服務(wù)，相比DropTail算法就得到了更低的時延。因此兩種算法下的時延情況有較大不同。而表2為不同業(yè)務(wù)流的平均網(wǎng)絡(luò)時延情況。

圖3 兩種算法下的時延情況

表2兩種算法下的業(yè)務(wù)流平均時延

算法業(yè)務(wù)分組時延/scbr1cbr2cbr3cbr4DropTail0.052 0860.064 0970.082 4840.080 544PDropTail0.053 0870.060 7260.066 660.065 628

明顯可以看出在調(diào)用PDropTail算法時，不同業(yè)務(wù)的時延基本低于DropTail算法下的時延，事實證明新算法能保證較低的網(wǎng)絡(luò)時延。而兩種算法下的實時網(wǎng)絡(luò)丟包率情況如圖4所示。兩種算法的實際網(wǎng)絡(luò)丟包情況如表3。

圖4 兩種算法下的丟包率情況

表3兩種算法下的業(yè)務(wù)流丟包情況

算法業(yè)務(wù)分組丟包(/125個)cbr1cbr2cbr3cbr4DropTail951022313PDropTail92101328

由圖形和表格數(shù)據(jù)可知：兩種算法下的實時丟包率均隨著模擬時間逐步上升。雖然兩種算法情況下的總丟包數(shù)保持一樣的水平，但是調(diào)用PDropTail算法下確保了優(yōu)先級較高的業(yè)務(wù)cbr4獲得優(yōu)先服務(wù)，保證了其較低的網(wǎng)絡(luò)丟包情況。 調(diào)用兩種算法的網(wǎng)絡(luò)吞吐量情況如圖5所示。圖5反映了新算法能保持與DropTail算法幾乎一致的高吞吐量。因此，通過時延、丟包和吞吐量等方面因素的實驗對比分析，驗證了新算法對于優(yōu)先級業(yè)務(wù)具有一定區(qū)分服務(wù)的能力，能保證較高優(yōu)先級業(yè)務(wù)較低的網(wǎng)絡(luò)時延和丟包率，也能確保業(yè)務(wù)在網(wǎng)絡(luò)傳輸過程中較高的吞吐量。

圖5 兩種算法下的吞吐量情況

3 結(jié)束語

本文利用NS2對NCS的網(wǎng)絡(luò)傳輸模型進行模擬仿真，設(shè)計添加了優(yōu)先級隊列管理算法，并在實驗中對DropTail算法、PDropTail算法的性能進行了分析比較。從實驗數(shù)據(jù)中可以得出，PDropTail算法能為NCS中具有不同優(yōu)先級的業(yè)務(wù)提供更好的區(qū)分服務(wù)，保證較高優(yōu)先級業(yè)務(wù)具有較低的網(wǎng)絡(luò)傳輸延時、較低的網(wǎng)絡(luò)低丟包率，同時也繼承了DropTail算法較高吞吐量的優(yōu)點。因此，實驗?zāi)M的結(jié)果達到了預(yù)期效果。

參考文獻：

[1] WALSH G, HONG Y, BUSHNELL L. Stability analysis of networked control systems[J]. American Control Conference, 1999. Proceedings of the 1999 ,14(4):2876-2880

[2] IPACCHI A, ALBUYEH F. Grid of the future[J]. Power and Energy Magazine, IEEE ,2009,7(2):52-62

[3] WANG Feiyue. Parallel Control and Management for Intelligent Transportation Systems: Concepts, Architectures, and Applications[J]. Intelligent Transportation Systems, IEEE Transactions on,2010,11(3):630-638

[4] YUE Dong, HAN Qinglong, CHEN Peng. State feedback controller design of networked control systems[J]. Circuits and Systems II: Express Briefs, IEEE Transactions on,2004,51(11):640-644

[5] WU Jing, CHEN Tongwen. Design of Networked Control Systems With Packet Dropouts[J]. Automatic Control, IEEE Transactions on,2007,52(7):1314-1319

[6]WANG Xiaofeng. LEMMON M. Event-Triggering in Distributed Networked Control Systems[J]. Automatic Control, IEEE Transactions on,2011，56(3):586-601

[7] 徐雷鳴，龐博，趙耀.NS 與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版社，2003

[8] 于斌，孫斌.NS2 與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版社，2007

[9] 柯志亨，程榮祥，鄧德雋.NS2 仿真實驗——多媒體和無線網(wǎng)絡(luò)通信[M].北京：電子工業(yè)出版社，2009

[10] 高文宇,王建新,陳松喬. 網(wǎng)絡(luò)仿真軟件NS2中隊列調(diào)度算法的擴展[J].系統(tǒng)仿真學報,2006(2):521-525

[11] 楊吉文,張衛(wèi)東.基于NS2的主動隊列管理仿真研究[J].計算機工程，2006(17):189-191

[12] 高鵬,戴旭初. 基于NS的主動隊列管理算法的仿真與分析[J]. 計算機仿真,2006(5):98-100,155