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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 交換策略及建模仿真

3.1 交換策略

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

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

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

3.2 仿真建模

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

3.3 仿真分析

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

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

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

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

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

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

4 結(jié)束語

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

[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é)報，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é)報，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è)學(xué)院學(xué)報，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.