ONOFF過程模擬突發(fā)業(yè)務(wù)在調(diào)度仿真中的應(yīng)用研究

《ONOFF過程模擬突發(fā)業(yè)務(wù)在調(diào)度仿真中的應(yīng)用研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、ON-OFF過程模擬突發(fā)業(yè)務(wù)在調(diào)度仿真中的應(yīng)用研究作者：王鵬金德鵬　伊鵬　曾烈光　　論文關(guān)鍵詞：ON-OFF模型　突發(fā)業(yè)務(wù)　輸入排隊(duì)　調(diào)度　　論文摘要：介紹了一種使用ON-OFF模型完成網(wǎng)絡(luò)突發(fā)業(yè)務(wù)建模的方法，并且利用該模型完成了突發(fā)業(yè)務(wù)在輸入排隊(duì)調(diào)度中的仿真，為下一步研究開發(fā)在突發(fā)業(yè)務(wù)條件下具有魯棒性的輸入排隊(duì)調(diào)度算法打下了基礎(chǔ)。　　1概述　　伴隨著各種寬帶技術(shù)的出現(xiàn),近幾十年發(fā)展起來的新業(yè)務(wù)如數(shù)字廣播、數(shù)字電視、IP電話和數(shù)字視頻點(diǎn)播等迅速增長(zhǎng)。這使得現(xiàn)代網(wǎng)絡(luò)融合了數(shù)據(jù)、語音和圖像等多種業(yè)務(wù),從而需要針對(duì)不同業(yè)務(wù)、不同需求提供服務(wù)質(zhì)量保證。這對(duì)傳統(tǒng)的網(wǎng)絡(luò)業(yè)務(wù)建模理論提出了新的挑戰(zhàn),同時(shí)

2、也對(duì)于通信網(wǎng)絡(luò)的性能分析、資源分配與流量控制等提出了新的要求。11　　網(wǎng)絡(luò)業(yè)務(wù)源的分析建模問題在網(wǎng)絡(luò)性能分析、控制中尤為重要。合理的假設(shè)近似不親能夠反映特定業(yè)務(wù)的特點(diǎn)，而且可以極大的簡(jiǎn)化分析計(jì)算，從而快速準(zhǔn)確的得到完了性能。傳統(tǒng)的排隊(duì)論理論[1]，一般是假設(shè)時(shí)間的到達(dá)具有獨(dú)立同分布和無記憶的特性，那么這個(gè)過程就構(gòu)成了Poisson過程。但是在某些場(chǎng)合下，以上兩個(gè)假設(shè)無法同時(shí)成立，尤其是在日益復(fù)雜的通信網(wǎng)中，即使可以假設(shè)各個(gè)事件的到達(dá)或吃力滿足相互獨(dú)立性，但其間隔分布一般不具備無記憶性[2]。一個(gè)典型的例子就是在當(dāng)前的計(jì)算機(jī)網(wǎng)絡(luò)中，骨干網(wǎng)高速路由器為了提高硬件處理速度對(duì)到達(dá)的變長(zhǎng)數(shù)據(jù)（64b

3、yte~64kbyte）包采用了切片（fragment）技術(shù)。數(shù)據(jù)包經(jīng)過切片后成為多個(gè)固定長(zhǎng)度的信元（cell），這樣對(duì)于切片后的業(yè)務(wù)流就不能再簡(jiǎn)單的假設(shè)為Poisson到達(dá)過程，并且對(duì)于每個(gè)cell的處理時(shí)間變?yōu)槎ㄩL(zhǎng)，所以也不能用負(fù)指數(shù)分布來近似。大量測(cè)試表明，這樣的信元到達(dá)具有極大的突發(fā)性[3]?！　”疚恼轻槍?duì)核心路由器輸入端口的這種突發(fā)型業(yè)務(wù)使用馬爾代夫過程調(diào)制的ON-OFF模型對(duì)其近似，并且針對(duì)輸入排隊(duì)調(diào)度系統(tǒng)應(yīng)用該業(yè)務(wù)源進(jìn)行仿真，從而得出典型調(diào)度算法在突發(fā)業(yè)務(wù)下的性能。通過研究表明，典型算法在突發(fā)業(yè)務(wù)條件下性能迅速惡化，需要研究新型抗突發(fā)調(diào)度算法來彌補(bǔ)這項(xiàng)空白?！　?輸入排隊(duì)調(diào)

4、度背景11　　當(dāng)前網(wǎng)絡(luò)高速發(fā)展，寬帶技術(shù)不斷出現(xiàn)，作為網(wǎng)絡(luò)核心設(shè)備的路由器和交換機(jī)通常采用輸入排隊(duì)的縱橫開關(guān)（Crossbar）這種交換體系結(jié)構(gòu)[4]。如圖1所示，但是在這種交換結(jié)構(gòu)中，對(duì)頭（HOL）信元阻塞使系統(tǒng)性能大幅下降[5]，為了克服（HOL）信元阻塞，一般在輸入端采取虛擬輸出排隊(duì)（VOQ）的形式，這樣就要求有一個(gè)調(diào)度器來控制數(shù)據(jù)包的交換轉(zhuǎn)換?！　】紤]一個(gè)N*N輸入排隊(duì)交換結(jié)構(gòu)：每個(gè)輸入端口的緩存分為N個(gè)VOQ隊(duì)列，每個(gè)VOQ隊(duì)列存儲(chǔ)從輸入端口i到達(dá)，目的端口為j的數(shù)據(jù)包。在以下討論中，假定所有的數(shù)據(jù)包定長(zhǎng)，t時(shí)刻VOQ隊(duì)列長(zhǎng)度用qn(t)表示。Q(t)=[qn(t)]為N*N維矩

5、陣指示在t時(shí)刻VOQ的隊(duì)列長(zhǎng)度。　　在輸入端i(1<=i<=N),設(shè)到達(dá)過程Ai(t)是離散時(shí)間過程，每個(gè)時(shí)刻在美國(guó)輸入端有0或1個(gè)信元到達(dá)（對(duì)于單播業(yè)務(wù)），而每個(gè)數(shù)據(jù)包都有一個(gè)指向其目的輸出端j(t<=j<=N)的標(biāo)識(shí)符。定義At,j(t)為輸入i到輸出j的到達(dá)過程，其到達(dá)率為λt=i，到達(dá)過程集合A(t)={Ai(t);t<=i<=N},若輸入和輸出都在負(fù)載范圍內(nèi)（），則A（t）被認(rèn)為是容許的，否則就是非容許的。顯然輸出端j得離開過程Di(t)也是一個(gè)離開率為μi的離散時(shí)間過程，在每個(gè)時(shí)刻有0個(gè)或個(gè)數(shù)1據(jù)包離開，定義輸入到i輸出的j離開過程Di,j(

6、t)，其i,jμ離開率為。x(t)ij使用表示t時(shí)刻輸入端口i與輸出端口j的連接關(guān)系。x(t)=1ij當(dāng)且僅當(dāng)時(shí)，輸入端口i和11輸出端口j相連通。不失一q(t)=0ij般性，考慮完全連接關(guān)系，即當(dāng)時(shí)允許輸入端口i與輸出端口j連通。因此可以將Crossbar的結(jié)構(gòu)約束描述如下：x(t)∈{0,1}ij，其中i,j=1,2,L,N;　　1=i一個(gè)可行的連接關(guān)系可以看作是圖論中的二分圖的匹配，調(diào)度算法的核心就是在各個(gè)時(shí)刻根據(jù)VOQ的狀態(tài)決定匹x(t)配，從而置相應(yīng)的ij。在到達(dá)過程Ai(t)的建模中，作者設(shè)計(jì)并實(shí)現(xiàn)了簡(jiǎn)單的貝努力分布的業(yè)務(wù)和基于馬爾可夫過程調(diào)制的ON-OFF過程的突發(fā)業(yè)務(wù)。需要

7、指出的是，對(duì)于突發(fā)業(yè)務(wù)建模的方法很多，作者使用ON-OFF過程建模實(shí)現(xiàn)簡(jiǎn)單并且能夠真實(shí)地反映核心路由器線路卡輸入數(shù)據(jù)包切片后的到達(dá)情況[5]?！　‘?dāng)前在輸入排隊(duì)調(diào)度算法中最為流行的是NickMckeown于1994年提出的iSLIP算法[5]，該算法以其高性能易于硬件實(shí)現(xiàn)成為了輸入排隊(duì)調(diào)度算法的里程碑，并且已經(jīng)在Cisco的GSR12000路由器和Stanford大學(xué)的TinyTera項(xiàng)目中得到了成功應(yīng)用。算法已經(jīng)被證明