羅麗獻(xiàn) 賓志燕 王春霞 周耿銘

（廣西科技大學(xué) 廣西壯族自治區(qū)柳州市 545006）

在對WDM 光網(wǎng)絡(luò)研究中一般有靜態(tài)與動態(tài)兩種流量模型。在靜態(tài)流量模型中，網(wǎng)絡(luò)的光路連接請求不是隨機到達(dá)而是預(yù)先知道且不會隨著時間的推移而產(chǎn)生變化，當(dāng)全部的連接一旦被建立好之后，將維持這種連接關(guān)系。此時的網(wǎng)絡(luò)狀態(tài)將保持不變，既不會建立新的連接又不會拆除掉那些已經(jīng)建立好了的連接，故對各個連接的路由和波長分配可以是非實時的（off-line）。此時主要是利用高效的路由與波長分配算法為光通路連接請求選擇路由并分配波長，從而達(dá)到最佳的優(yōu)化效果。

在靜態(tài)流量模型下研究光網(wǎng)絡(luò)的配置對網(wǎng)絡(luò)規(guī)劃是有一定意義的，但實際網(wǎng)絡(luò)的業(yè)務(wù)請求通常不是靜態(tài)的而是動態(tài)變化的。在動態(tài)流量模型中，網(wǎng)絡(luò)中的光路連接請求是隨機到達(dá)、無法預(yù)知的，光工作通路建立后將維持一段有限時間，在通信結(jié)束后光通道被拆除，這就是意味著工作通路及備份通路的建立與拆除是隨著不斷動態(tài)改變的業(yè)務(wù)流量需求而動態(tài)變化，而且這些連接請求能否被接納還得取決于網(wǎng)絡(luò)的當(dāng)前狀態(tài)。由于因此網(wǎng)絡(luò)狀態(tài)是不斷變化的?？梢灶A(yù)見未來的WDM 光網(wǎng)絡(luò)將會是更加動態(tài)變化和對故障是較為敏感的。因此，與光網(wǎng)絡(luò)生存性的動態(tài)服務(wù)配置將成為網(wǎng)絡(luò)規(guī)劃和管理的關(guān)鍵要求[1,2]。

基于動態(tài)流量的光網(wǎng)絡(luò)性能分析，大都采用傳統(tǒng)的短相關(guān)的泊松分布模型(Poisson Model)，即假設(shè)網(wǎng)絡(luò)中業(yè)務(wù)的連接請求的到達(dá)速率服從泊松分布。早期相關(guān)研究人員對網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行分析，首次提出了網(wǎng)絡(luò)流量中存在著自相似現(xiàn)象[3,4]。在其后的一些研究中，研究人員發(fā)現(xiàn)網(wǎng)絡(luò)通信量的自相似性始終是存在的。經(jīng)典理論分析泊松過程體現(xiàn)的是短相關(guān)，自相似體現(xiàn)的是業(yè)務(wù)量的長相關(guān)性，因此泊松過程不再適合網(wǎng)絡(luò)流量的分析和建模。由于傳統(tǒng)的泊松模型不能準(zhǔn)確地模擬網(wǎng)絡(luò)中的真實業(yè)務(wù)量，而自相似性過程能更好的描述真實網(wǎng)絡(luò)中的業(yè)務(wù)流量，所以在自相似性業(yè)務(wù)得到的網(wǎng)絡(luò)阻塞率分析更接近事實。

本文采用分形高斯噪聲（FGN）方法生成自相似業(yè)務(wù)流，結(jié)合P 圈啟發(fā)式配置算法，將其應(yīng)用到光網(wǎng)絡(luò)的動態(tài)仿真中，并與泊松業(yè)務(wù)流的阻塞率相比較。

1 自相似動態(tài)流量

1.1 基于分形布朗運動和分形高斯噪聲模型

圖1：均值M=20，V=50，H=0.89 的自相似業(yè)務(wù)序列

當(dāng)前網(wǎng)絡(luò)流量建模研究中，相關(guān)研究者提出了不少模型理論，比較常用的是：統(tǒng)一建模的FARIMA（p，d，q)過程模型、M/G/co 排隊模型、直接疊加具有重尾特性的ON/OFF 源模型及擁有平穩(wěn)增量的隨機過程的建模方法（典型方法為基于分形布朗運動和分形高斯噪聲。本文將介紹一種典型的自相似生成模型——Mandelbrot和VanNess 于1968年提出的一種描述統(tǒng)計自相似過程的數(shù)學(xué)模型“分形布朗運動(fractional Brownian motion, FBM)及 FGN[6]，F(xiàn)BM的增量過程即為 FGN 序列分形高斯噪聲（fractional Gaussian Noise, FGN）過程。

滿足以下條件的隨機函數(shù)x(t)為分形布朗運動過程：

（1）x(0)=0；

（2）對所有的t ≥0，有

其中，Н 滿足0<Н<1。這個過程因具有分形維的故被稱為分形布朗運動。當(dāng)Н=1/2 的時候，分形布朗運動過程x(t)就退化成了一般的布朗運動過程（布朗運動B(t)是一種是初始位置為原點、在不相交叉的時間區(qū)間上有獨立增量及服從高斯分布隨機過程）。

基于分形布朗運動過程的整個網(wǎng)絡(luò)的自相似業(yè)務(wù)流模型可形式化表示如下[7]：

單位時間內(nèi)網(wǎng)絡(luò)自相似流量模型為：

圖2：均值M=20 的泊松業(yè)務(wù)分布序列

圖3：動態(tài)P 圈配置的流程圖

圖4：NST 網(wǎng)絡(luò)拓?fù)?/p>

其中At為到時刻t 為止的網(wǎng)絡(luò)業(yè)務(wù)流，BН(t)表示為一個標(biāo)準(zhǔn)FBM 過程m 為業(yè)務(wù)的平均到達(dá)速率，a 為方差系數(shù)且取值范圍為a > 0, BН(t)為Нurst 參數(shù)(即Н)，其取值范圍為0.5<Н<1，主要用來描述自相似程度的高低，Н 值的數(shù)值越大，其自相似程度就越高。

1.2 生成泊松和自相似的時間序列

FGN 序列是一個精確自相似過程，該模型有3 個特征參數(shù)，即為自相似系數(shù)Н，單位時間內(nèi)到達(dá)的平均連接數(shù)M，方差系數(shù)a。為便于取數(shù)，假設(shè)單位時間內(nèi)達(dá)到的連接數(shù)的方差為V，a=V/M。確定此3 個特征參數(shù)即可生成自相似業(yè)務(wù)序列，圖1 為隨機生成的自相似業(yè)務(wù)序列。

基于泊松業(yè)務(wù)流量下，在仿真的過程中我們假設(shè)光路連接請求符合到達(dá)率均值為λ 泊松過程，光路的平均維持時間滿足1/μ 指數(shù)分布。生成業(yè)務(wù)到達(dá)率服從均值為λ 泊松分布，相當(dāng)于生成任意連續(xù)到達(dá)的兩次業(yè)務(wù)的間隔時間服從參數(shù)為1/λ 的指數(shù)分布，因此，我們先生成通過函數(shù)(log(rand())/RAMD_MAX)產(chǎn)生0 到1 之間的隨機數(shù)，并可通過1/λ*(log(rand())/RAMD_MAX)計算出下一個業(yè)務(wù)到達(dá)的時間間隔。為計算所有光路請求的維持時間，我們?nèi)耘f通過函數(shù)(log(rand())/RAMD_MAX)產(chǎn)生0 到1 之間的隨機數(shù)，接著通過1/μ*(log(rand())/RAMD_MAX)計算出光路的持續(xù)時間。

比較圖1 和圖2 可看出，泊松業(yè)務(wù)序列較平穩(wěn)，而自相似業(yè)務(wù)序列波動范圍較大，較能體現(xiàn)出業(yè)務(wù)量的突發(fā)性。

2 動態(tài)的P圈配置

2.1 P圈啟發(fā)式配置算法

光網(wǎng)絡(luò)可表示為為一系列點V 和一系列邊E 組成的圖G = (V, E)。設(shè)i 為網(wǎng)絡(luò)所有備選圈的集合。保護(hù)效率（ER）定義為此P 圈所能保護(hù)的工作容量與配置這個P 圈所需的空閑容量的比值[5]。

此式中，Wj表示鏈路的工作資源；xij表示當(dāng)前情況下鏈路j 是否可以被備選 的所保護(hù)，是則xij為1，否則xij為0；pij表示表示鏈路j 是否為備選圈i 的圈上鏈路；是則pij為1，否則pij為0。ERj為性能指標(biāo)，量化這個備選圈的高低，ERj值越大，代表此P 圈越高效。

基于P 圈啟發(fā)式配置算法的配置如下：

（1）根據(jù)P 圈的最大物理長度或者所經(jīng)過的節(jié)點數(shù)，計算出網(wǎng)絡(luò)中的P 圈的物理長度都不超，構(gòu)成所有簡單圈的集合：

1.找出任一鏈路（邊）e∈E，并從集合G 中刪去邊L；

2.在網(wǎng)絡(luò)資源圖G = (V, E)找出途經(jīng)鏈路e 的兩節(jié)點之間的所有路徑的集合Lpath。

3.路徑的集合Lpath 各自與原鏈路e 首尾連接，就可得到與鏈路e 相關(guān)的備選圈集。

4.轉(zhuǎn)到步驟（1）直到找完所有的簡單圈。

（2）根據(jù)網(wǎng)絡(luò)中的流量需求,采用最短路徑算法（鏈路的代價為鏈路空閑資源數(shù)的倒數(shù)）來給光路需求分配路由并計算網(wǎng)絡(luò)每條鏈路上的工作容量。

（3）計算步驟（1）找出的每個備選圈所能保護(hù)的工作容量和構(gòu)造此備選圈所消耗的空閑容量，求出所有備選圈的ER。

（4）選擇具有最大ER的P圈，記為imax，并把imax配置到網(wǎng)絡(luò)中，通過減去imax所能保護(hù)的工作容量，更新網(wǎng)絡(luò)中未被保護(hù)的工作容量，同時通過釋放構(gòu)造imax所消耗的空閑容量，更新網(wǎng)絡(luò)中剩余的工作容量。

（5）重新計算步驟（4）所選的P 圈及與此P 圈有一條或多條公共鏈路的備選圈的ER，并保留與此P 圈不存在公共鏈路的其他備選圈的ER，轉(zhuǎn)步驟（4）。

（6）如果網(wǎng)絡(luò)中每條鏈路的未被保護(hù)的工作容量都為0，則算法結(jié)束；否則，則轉(zhuǎn)步驟（5）。

2.2 動態(tài)P圈設(shè)計

對于動態(tài)P 圈配置的過程中，網(wǎng)絡(luò)間的業(yè)務(wù)是動態(tài)的，各個節(jié)點之間的業(yè)務(wù)是不是固定的，而是隨機到達(dá)的，建立好的業(yè)務(wù)的連接請求在持續(xù)一段時間后將北釋放掉，整個網(wǎng)絡(luò)的業(yè)務(wù)分布情況都是動態(tài)變化的。因此，需要動態(tài)的P 圈配置來保護(hù)動態(tài)變化的網(wǎng)絡(luò)業(yè)務(wù)。動態(tài)P 圈配置是根據(jù)當(dāng)期網(wǎng)絡(luò)的實時資源情況、故障發(fā)生情況及當(dāng)前所計算的P 圈集合是否可以保護(hù)當(dāng)前的網(wǎng)絡(luò)業(yè)務(wù)的情況，動態(tài)地計算最優(yōu)的P 圈，并且修改P 圈的配置情況，為下一次新業(yè)務(wù)的到達(dá)及發(fā)生的故障提供保護(hù)。動態(tài)P 圈配置具有能夠為網(wǎng)絡(luò)提供可靠的保護(hù)和資源利用率高的優(yōu)點。

此算法為光通路連接請求動態(tài)的選擇路由并分配波長，最終優(yōu)化目標(biāo)是使網(wǎng)絡(luò)的阻塞率達(dá)到最小化。本文的阻塞率=被網(wǎng)絡(luò)阻塞的業(yè)務(wù)數(shù)/到達(dá)網(wǎng)絡(luò)的業(yè)務(wù)總數(shù)。此算法的流程圖如圖3 所示。

新業(yè)務(wù)請求隨機到達(dá)時，本文基于動態(tài)P 圈配置的算法思路主要為：

（1）拆除所有先前配置的P 圈，釋放占用的波長資源數(shù)，運用最短路由（Dijkstra）算法計算源節(jié)點到目的點的路由，如果能到為光通路連接請求選擇路由并分配波長，則為該請求分配連接；否則就阻塞掉該請求。

（2）當(dāng)步驟1 中的光通路成功連接后，更新網(wǎng)絡(luò)中鏈路的工作容量，用基于P 圈啟發(fā)式算法來配置P 圈，如能夠?qū)υ袠I(yè)務(wù)的光通路以及新業(yè)務(wù)的光通路進(jìn)行100%的保護(hù)，則接受此連接請求，否則阻塞掉此連接請求。

2.3 實驗結(jié)果分析

本文的實驗數(shù)據(jù)結(jié)果選取點度數(shù)和網(wǎng)絡(luò)密度較小的北美NSFNET 網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真，見圖5 在仿真實驗中，有兩點前提假設(shè)。一是假設(shè)節(jié)點具有全波變化功能，每條鏈路都滿足雙向傳輸?shù)墓ぷ饕?，每個業(yè)務(wù)請求的帶寬為1 個波長單位。二是假設(shè)網(wǎng)絡(luò)中所有的節(jié)點間的業(yè)務(wù)強度都相同，即支持均勻分布的業(yè)務(wù)量。到達(dá)業(yè)務(wù)請求的源、宿節(jié)點在所有節(jié)點對之間隨機選擇，如果能夠找到合適的工作路徑和保護(hù)通道，則為該請求分配連接；否則阻塞該請求，即無等待隊列。

本文所分析的阻塞率為全網(wǎng)平均阻塞率，圖4 為NSF 網(wǎng)絡(luò)拓?fù)湎虏此蓸I(yè)務(wù)流和自相似業(yè)務(wù)流的阻塞率，其中自相似業(yè)務(wù)流量的Н=0.83，V 為一個固定常數(shù)，兩種流量的維持時間滿足從均值為1/μ 的指數(shù)分布M 與泊松業(yè)務(wù)的均值λ 相對應(yīng)。

從圖5 中看觀察到， 當(dāng)整個網(wǎng)絡(luò)處于較輕的網(wǎng)絡(luò)負(fù)載且在相同的均值M 下，由于基于自相似業(yè)務(wù)具有突發(fā)性，所以其阻塞率要遠(yuǎn)遠(yuǎn)高于基于泊松業(yè)務(wù)流的阻塞率。隨著均值M 的不斷增大，整個網(wǎng)絡(luò)處于較重的網(wǎng)絡(luò)負(fù)載，而處于較重負(fù)載網(wǎng)絡(luò)的阻塞是由于通道鏈路上沒有足夠剩余空閑波長可用，造成連接請求被阻塞掉，所以基于自相似業(yè)務(wù)的阻塞率與基于泊松業(yè)務(wù)的阻塞率的差距會大大縮小。

由以上數(shù)據(jù)可知，由于FGN 模型可以提供更詳細(xì)的參數(shù)生成自相似性業(yè)務(wù)流，傳統(tǒng)的泊松模型已不能準(zhǔn)確地模擬網(wǎng)絡(luò)中的真實業(yè)務(wù)量，故在自相似性業(yè)務(wù)得到的網(wǎng)絡(luò)阻塞率分析更接近事實。

3 結(jié)語

本文主要介紹了FGN 法生成自相似業(yè)務(wù)分布序列的過程，并與泊松業(yè)務(wù)分布序列相比較，體現(xiàn)了自相似流量具有突發(fā)性。當(dāng)整個網(wǎng)絡(luò)處于較輕的網(wǎng)絡(luò)負(fù)載且在相同的均值M 下基于自相似業(yè)務(wù)的阻塞率比基于泊松業(yè)務(wù)的阻塞率要高。由于FGN 模型可以提供更詳細(xì)的參數(shù)生成自相似性業(yè)務(wù)流，而傳統(tǒng)的泊松模型不能準(zhǔn)確地模擬網(wǎng)絡(luò)中的真實業(yè)務(wù)量，故在自相似性業(yè)務(wù)得到的網(wǎng)絡(luò)阻塞率分析更接近事實。

圖5：泊松與自相似的阻塞率比較