自相似模型下的交換式網(wǎng)絡(luò)仿真

盧 穎，鐘聯(lián)炯，王智廣

（1.西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710032；2.中國(guó)石油大學(xué) 計(jì)算機(jī)系，北京 102200）

網(wǎng)絡(luò)業(yè)務(wù)量特性是網(wǎng)絡(luò)性能分析和網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)的基礎(chǔ)，而傳統(tǒng)模式下的交換式網(wǎng)絡(luò)仿真，報(bào)文的到達(dá)模型均是假設(shè)整個(gè)排隊(duì)系統(tǒng)中顧客流的到達(dá)服從泊松過程，而泊松過程具有Markovian特性，即一種短相關(guān)過程[1]。隨著網(wǎng)絡(luò)研究的深入，發(fā)現(xiàn)實(shí)際上網(wǎng)絡(luò)中的業(yè)務(wù)流在幾毫秒至幾小時(shí)甚至幾天的時(shí)間段上，均表現(xiàn)出很強(qiáng)的突發(fā)特性，這說明報(bào)文的到達(dá)具有長(zhǎng)相關(guān)屬性。因此，泊松到達(dá)的仿真模型已不符合網(wǎng)絡(luò)的實(shí)際情況。筆者在考慮報(bào)文的到達(dá)服從長(zhǎng)相關(guān)過程的情況下，利用能描述長(zhǎng)相關(guān)特性的自相似模型，借助計(jì)算機(jī)仿真法對(duì)交換式網(wǎng)絡(luò)進(jìn)行了仿真，并對(duì)仿真結(jié)果作出了分析及評(píng)價(jià)。

1 自相似的數(shù)學(xué)定義

計(jì)分布。其離散時(shí)間數(shù)學(xué)定義為：離散時(shí)間隨機(jī)過程X（t）定義為{Xt，t=0，1，2，…}是一廣義平穩(wěn)隨機(jī)過程，均值 μ，方差σ2，且自相關(guān)函數(shù)為 r（k），k≥0。假設(shè) X 的自相關(guān)函數(shù)形式如下：當(dāng) k→∞ 時(shí)，r（k）～k-βL（t）。 參數(shù) β（0＜β＜1），且 L 是緩慢變化至無窮的，即對(duì)所有 x ＞0，L（tx）/L（t）=1。 定義 X 上的 m重聚集時(shí)間序列 x（m）={，k=0，1，2，…}，它可以表示為：=（Xkm-m+1+…+Xkm）/m，過程 X 稱為精確二階自相似序列[2]，且具有自相似系數(shù)H=1-β/2。參數(shù)H為自相似參數(shù)，它是自相似程度的一個(gè)重要度量，是描述自相似特性的唯一參數(shù)。H的取值范圍是（0.5，1），H=0.5表示不具備自相似性（如泊松分布），H值越接近1，過程的自相似程度就越高[3]。

2 自相似業(yè)務(wù)模型的建立

筆者所研究的網(wǎng)絡(luò)業(yè)務(wù)流在數(shù)學(xué)上等效為一離散時(shí)間序列，下面給出自相似過程的離散時(shí)間定義。自相似性從統(tǒng)計(jì)意義上可以理解為局部適當(dāng)放大后，與整體具有相同的統(tǒng)

網(wǎng)絡(luò)中自相似流量序列的產(chǎn)生可采用分?jǐn)?shù)布朗運(yùn)動(dòng)模型、ARIMA模型、ON/OFF模型和小波變換模型[4]。其中分?jǐn)?shù)布朗運(yùn)動(dòng)模型易于合成仿真數(shù)據(jù)，便于計(jì)算機(jī)仿真研究。因此，實(shí)驗(yàn)采用了能夠近似生成分?jǐn)?shù)布朗運(yùn)動(dòng)的RMD（Random Midpoint Displacement）算法。

RMD算法的設(shè)計(jì)，是一個(gè)不斷調(diào)整，不斷修正的過程，其關(guān)鍵在于偏移量的選取。偏移量是一個(gè)與原序列有關(guān)的函數(shù)。原序列的參數(shù)主要有自相似參數(shù)H和自相關(guān)函數(shù)r（k）。其中自相關(guān)函數(shù) r（k）=1/2[（k+1）2H-2k2H+（k-1）2H]，k=1，2，3，...，給定一個(gè)序列，其自相似參數(shù)H為定值，但其自相關(guān)函數(shù)是隨k值不斷變化的。由于網(wǎng)絡(luò)業(yè)務(wù)流量的自相似性主要是由H參數(shù)為描述的，因此決定使用原序列的H參數(shù)來建立偏移量值函數(shù)D。生成序列在某點(diǎn)的值等于前后兩點(diǎn)的算術(shù)均值再加上在此點(diǎn)的偏移量函數(shù)值，即X[n]=（X[n-1]+X[n+1]）/2+D（n）。因此可以通過迭代法產(chǎn)生自相似序列。

由于偏移量將會(huì)產(chǎn)生一個(gè)0均值的高斯分布序列，那么首先需要產(chǎn)生一個(gè)正態(tài)分布隨機(jī)數(shù)組G（n），其均值為0方差為1。令H為原序列的自相似參數(shù)，為生成序列的自相似參數(shù)，ΔH=（H?-H）/H為生成序列與原序列的自相似參數(shù)偏離的程度。ΔH的值越小，說明模擬的序列的特性越接近原序列的特性。

選取偏移量函數(shù)為 D（i）=G（n）θi，其中為迭代次數(shù)。由于正態(tài)分布隨機(jī)數(shù)組的方差為1，即δ=1，那么則迭代i次可生成背景序，算法流程如圖1所示。

圖1 RMD算法流程圖Fig.1 Flow chart of RMD algorithm

RMD生成法理論時(shí)間復(fù)雜度為O（n），且生成自相似隨機(jī)序列的速度較快，能夠滿足實(shí)際仿真中快速產(chǎn)生較長(zhǎng)自相似序列的需求。

3 交換策略及建模仿真

3.1 交換策略

本文所研究的交換式網(wǎng)絡(luò)，其核心設(shè)備為輸入緩存式交換機(jī)，原理是利用輸入緩存來防止阻塞，它使得所有端口的訪問總和可以超過交換體本身的交換能力。緩存位于交換機(jī)的輸入部分，報(bào)文進(jìn)入交換機(jī)后首先在這里暫存，然后交換機(jī)中的一塊特定集成電路（ASIC）對(duì)到達(dá)交換結(jié)構(gòu)的訪問進(jìn)行仲裁并將報(bào)文交換到輸出端口[5]。

對(duì)交換策略的分析描述如下：假設(shè)該交換機(jī)的交換結(jié)構(gòu)為N×N，每個(gè)輸入端口對(duì)應(yīng)有N個(gè)虛輸入隊(duì)列（分別對(duì)應(yīng)N個(gè)輸出端口）。報(bào)文按自相似序列到達(dá)后會(huì)根據(jù)自己的目標(biāo)端口號(hào)在不同虛輸入隊(duì)列中排隊(duì)，當(dāng)它排至隊(duì)首，而輸出端空閑則進(jìn)行交換并輸出。在此過程中，若出現(xiàn)多個(gè)虛輸入隊(duì)列的排頭同時(shí)競(jìng)爭(zhēng)同一輸出端口的情形，則還需要在相應(yīng)輸出端的虛隊(duì)列中排隊(duì)等候輸出，如圖2所示。

圖2 輸出虛隊(duì)列示意圖Fig.2 Schematic diagrum of the output virtual queue

3.2 仿真建模

仿真網(wǎng)絡(luò)中的交換機(jī)節(jié)點(diǎn)采用N×N交換結(jié)構(gòu)（N為輸入輸出端口數(shù)）。報(bào)文的到達(dá)時(shí)間服從自相似特性，包長(zhǎng)大小隨機(jī)并服從負(fù)指數(shù)分布。相對(duì)各端口，報(bào)文的到達(dá)是均勻的。每個(gè)輸入端口對(duì)應(yīng)N個(gè)FIFO虛輸入隊(duì)列，每個(gè)輸出端口設(shè)一個(gè)虛輸出隊(duì)列，容量為N。

3.3 仿真分析

仿真系統(tǒng)中時(shí)間以毫秒為單位，業(yè)務(wù)流分別在自相似參數(shù)選用經(jīng)驗(yàn)值H=0.85和H=0.5（H=0.5為泊松業(yè)務(wù)模型[6]）下進(jìn)行。仿真過程如下：在給定系統(tǒng)模型的基礎(chǔ)上，報(bào)文按自相似序列到達(dá)端口，然后進(jìn)行相應(yīng)的加工處理，如加入隊(duì)列、排隊(duì)、交換輸出等，直到規(guī)定數(shù)量的報(bào)文全部發(fā)送完畢則仿真結(jié)束。

仿真結(jié)果統(tǒng)計(jì)的是網(wǎng)絡(luò)利用率、平均隊(duì)長(zhǎng)及平均延遲特性。其中報(bào)文平均時(shí)延的統(tǒng)計(jì)是通過報(bào)文到達(dá)時(shí)在報(bào)文對(duì)象中記錄其到達(dá)時(shí)刻，離去時(shí)用當(dāng)前時(shí)刻減去到達(dá)時(shí)刻獲得。平均隊(duì)長(zhǎng)計(jì)算公式為f（t）為 t時(shí)刻隊(duì)長(zhǎng)，T為系統(tǒng)仿真時(shí)間）。仿真每次運(yùn)行時(shí)間為1 000 s，在經(jīng)過多次變換仿真時(shí)間尺度，增強(qiáng)網(wǎng)絡(luò)負(fù)載的情況下，得到統(tǒng)計(jì)數(shù)據(jù)如表1所示。

表1 仿真結(jié)果數(shù)據(jù)Tab.1 Result data of simulation

對(duì)表1中仿真結(jié)果進(jìn)行分析可得，在相同負(fù)載條件下，H值越大，網(wǎng)絡(luò)的平均延遲、吞吐量就越大。自相似業(yè)務(wù)對(duì)于網(wǎng)絡(luò)的性能影響非常顯著。而在H=0.5的泊松業(yè)務(wù)模型下的隊(duì)長(zhǎng)、網(wǎng)絡(luò)延時(shí)及吞吐率較自相似的要小些。泊松和自相似兩個(gè)不同業(yè)務(wù)流模型下的網(wǎng)絡(luò)平均延遲對(duì)比如圖3所示。

圖3 泊松和自相似流量模型下的網(wǎng)絡(luò)延遲比較Fig.3 Time-delay comparison under Possion and self-similar model

可以看出，不同流量模型下的網(wǎng)絡(luò)性能差別很大。原因是，流量的自相似性具有一種長(zhǎng)相關(guān)和慢衰減方差特性[7]，因此在突發(fā)性和長(zhǎng)相關(guān)性的共同作用下，網(wǎng)絡(luò)性能會(huì)急劇下降。在報(bào)文突發(fā)到達(dá)時(shí)期，信道沖突概率增大，節(jié)點(diǎn)不能及時(shí)競(jìng)爭(zhēng)到有限的信道資源，從而造成高層數(shù)據(jù)包隊(duì)列積壓過多的包使緩存迅速充滿，導(dǎo)致數(shù)據(jù)丟失。同時(shí)隊(duì)列中等待服務(wù)的時(shí)間增加，導(dǎo)致分組端到端傳輸平均延時(shí)加長(zhǎng)。而傳統(tǒng)泊松流量模型的短相關(guān)性和較弱的長(zhǎng)相關(guān)性則對(duì)緩沖區(qū)的需求不高。因此，要提高系統(tǒng)性能就需要根據(jù)網(wǎng)絡(luò)業(yè)務(wù)流的特點(diǎn)，確定所需的各種資源，例如可以增加更多的緩存，但需要考慮到，增大緩存雖然能降低丟包率，卻會(huì)導(dǎo)致端到端排隊(duì)時(shí)延的加長(zhǎng)，這在對(duì)響應(yīng)時(shí)間要求高的系統(tǒng)中并不適用。因此，在做網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)時(shí)，需要平衡排隊(duì)延遲、丟包率、吞吐率等各項(xiàng)網(wǎng)絡(luò)性能指標(biāo)之間的關(guān)系。此外，還可以考慮在性能要求較高的網(wǎng)絡(luò)中適量增加帶寬資源，來提高吞吐量，減小延遲及包丟失率。

4 結(jié)束語

對(duì)交換式網(wǎng)絡(luò)進(jìn)行仿真測(cè)量是檢驗(yàn)網(wǎng)絡(luò)性能優(yōu)劣，協(xié)議設(shè)計(jì)及網(wǎng)絡(luò)配置是否合理的重要步驟。其中，業(yè)務(wù)流量模型是網(wǎng)絡(luò)設(shè)計(jì)、管理和控制的基礎(chǔ)。因此，在對(duì)網(wǎng)絡(luò)仿真和性能檢驗(yàn)過程中，必須首先對(duì)流量進(jìn)行正確建模才能較大程度地反映實(shí)際流量的特性，才不會(huì)對(duì)網(wǎng)絡(luò)性能造成過高或過低的估計(jì)。

[1]Paxson V，F(xiàn)loyd S.Wide area traffic:the failure of Poisson modeling[J].IEEE/ACM Trans.on Networking， 1995，3（3）:226-244.

[2]Leland W E.On the self-similar nature of ethernet traffic（extended version） [J].IEEE/ACM Trans.on Networking，1994，2（1）:1-15.

[3]肖志新，楊岳湘.網(wǎng)絡(luò)流量的自相似特性[J].吉首大學(xué)學(xué)報(bào)，2004，25（2）:75-77.XIAO Zhi-xin，YANG Yue-xiang.Self-similar characteristic of network traffic[J].Journal of Jishou University，2004，25（2）:75-77.

[4]張鵬.自相似業(yè)務(wù)量的多重分形分析[J].電子學(xué)報(bào)，2000，28（1）:96-98.ZHANG Peng.Multifractal analysis of self-similar traffic[J].Acta Electronica Sinica，2000，28（1）:96-98.

[5]盧穎，鐘聯(lián)炯.以太網(wǎng)交換機(jī)運(yùn)行機(jī)制及其仿真研究[J].西安工業(yè)學(xué)院學(xué)報(bào)，2004，24（1）:53-56.LU Ying，ZHONG Lian-jiong.Operation mechanism and computer simulation of the ethernet switch[J].Journal of Xi’an Institute of Technology， 2004，24（1）:53-56.

[6]Leland W E，Taqqu M S，Willinger W，et al.On the selfsimilar nature of ethernet Traffic （extended version） [J].IEEE/ACM Trans.on Networking， 1994，2（1）:1?15.

[7]Crovella M，Bestavros A.Self-similarity in world wide Web Traffic: evidence and possible causes[J]. IEEE/ACM Transactions on Networking， 1997，5（6）:835-846.