關(guān)于WDM雙環(huán)網(wǎng)絡(luò)網(wǎng)絡(luò)負荷的研究

李穎，陳業(yè)斌

1.安徽省馬鞍山師范高等專科學(xué)校，安徽馬鞍山 243041

2.安徽工業(yè)大學(xué)計算機學(xué)院，安徽馬鞍山 243002

關(guān)于WDM雙環(huán)網(wǎng)絡(luò)網(wǎng)絡(luò)負荷的研究

李穎1，陳業(yè)斌2

1.安徽省馬鞍山師范高等專科學(xué)校，安徽馬鞍山 243041

2.安徽工業(yè)大學(xué)計算機學(xué)院，安徽馬鞍山 243002

波長資源是WDM（Wavelength Division Multiplexing）[1]光網(wǎng)絡(luò)中的稀有資源，雖然在實驗環(huán)境中可用波長將近有300個左右，但在實用環(huán)境中可用波長不到64個，因此WDM網(wǎng)絡(luò)要解決的基本問題就是如何合理、有效地使用波長，即路由和波長分配問題。網(wǎng)絡(luò)負荷是網(wǎng)絡(luò)在完成業(yè)務(wù)需求集合的前提下，網(wǎng)絡(luò)通信所需波長數(shù)目的下界，這個參數(shù)用于衡量可用波長資源的消耗情況，也是路由選擇需要考慮的重要因素之一。因此網(wǎng)絡(luò)負荷一直是光網(wǎng)絡(luò)的研究重點。

光網(wǎng)絡(luò)模型可用有向圖G(V，E)表示，節(jié)點集和邊集分別表示為V(G)、E(G)[2]。節(jié)點u、v之間有一條鏈路，當且僅當u、v之間有一條邊。從節(jié)點x到y(tǒng)的光路徑或路由記作P(x，y)，是指從節(jié)點x至y的有向傳輸路徑[2-3]。光網(wǎng)絡(luò)中信息是通過每條鏈路中所容納的波長來承載的。節(jié)點u需將信息傳送到v，稱作u、v之間的業(yè)務(wù)需求（Request），記作R(u、v)。要完成u、v之間的業(yè)務(wù)需求就需要在u、v間建立光路徑。用R表示網(wǎng)絡(luò)節(jié)點間業(yè)務(wù)需求的集合，一般而言，網(wǎng)絡(luò)中的業(yè)務(wù)需求可統(tǒng)一表示為一個節(jié)點到其他相異節(jié)點對之間的業(yè)務(wù)需求的集合。在光網(wǎng)絡(luò)中有關(guān)鏈路負荷的概念定義如下：

定義1[4]鏈路e在路由集R中的負荷，指R中通過鏈路e的路徑數(shù)目，記為η(G，R，e)。最大的鏈路負荷稱為網(wǎng)絡(luò)負荷，記為η(G，R)，容易得到：

最小的滿足需求集的弧負荷稱作圖G在需求R下的最優(yōu)弧負荷，記為η(G)。容易得到：η(G)=minη(G，R)。

目前，大多有向雙環(huán)網(wǎng)絡(luò)采用光波來傳送信息，因此，本文以有向雙環(huán)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)為基礎(chǔ)來研究光網(wǎng)絡(luò)負荷的相關(guān)問題。

1 有向雙環(huán)網(wǎng)的網(wǎng)絡(luò)負荷

近年來，關(guān)于有向雙環(huán)網(wǎng)絡(luò)的研究主要集中在網(wǎng)絡(luò)直徑、路由算法、最小路徑圖和最優(yōu)步長等問題上。Wong和Coppersmith[5]證明了有向雙環(huán)網(wǎng)絡(luò)的直徑存在下界。該結(jié)論給人們尋找最優(yōu)雙環(huán)網(wǎng)絡(luò)提供了理論依據(jù)。Chen[6-8]證明了有向雙環(huán)網(wǎng)絡(luò)最小路徑圖——L-型瓦的存在，并給出了求L-型瓦相關(guān)參數(shù)的定義。有了L-型瓦，使得與距離相關(guān)的問題的研究變得更加方便。接下來，人們又對有向雙環(huán)網(wǎng)絡(luò)的最優(yōu)步長問題進行了研究[9-11]，發(fā)現(xiàn)了步長與緊優(yōu)雙環(huán)網(wǎng)絡(luò)之間的關(guān)系[12-15]。關(guān)于雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷方面的研究，目前還沒有見到相關(guān)文獻。

有向雙環(huán)網(wǎng)絡(luò)的圖論模型是指這樣一個有向圖G(N;r，s)[5]，如圖1所示。N、r、s是自然數(shù)，其中N是網(wǎng)絡(luò)節(jié)點的個數(shù)，r、s是步長，且1≤r≠s＜N。節(jié)點集V={0，1，…，N-1}，邊集為E={v→v+r(modN)，v→v+s(modN)|v∈V}。從每個節(jié)點v發(fā)出兩條有向邊v→v+r(modN)和v→v+s(modN)，稱v→v+r(modN)形式的邊為[+r]邊，v+s(modN)形式的邊為[+s]邊，其中x(modN)是x除以N所得非負余數(shù)。從定義可知，對于給定的N、r和s，唯一決定了一個有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的結(jié)構(gòu)，因而也決定了它的相關(guān)特性。

圖1 有向雙環(huán)網(wǎng)絡(luò)G(15;1，7)的拓撲結(jié)構(gòu)

根據(jù)有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的對稱性，節(jié)點v到任意節(jié)點u之間的路由問題可轉(zhuǎn)化為節(jié)點0到節(jié)點u-v之間的路由問題，因此，在有向雙環(huán)網(wǎng)絡(luò)中，任意兩節(jié)點之間的距離問題都可轉(zhuǎn)化為節(jié)點0和其他節(jié)點之間的距離問題。為了更直觀地了解雙環(huán)網(wǎng)絡(luò)的結(jié)構(gòu)，根據(jù)有向雙環(huán)網(wǎng)絡(luò)的路由特性，把雙環(huán)網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的所有節(jié)點映射到直角坐標系中，其生成算法如下：

在直角坐標系中，令X軸的單位長度定義為r，Y軸的單位長度為s。由X軸、Y軸以及間隔為r的垂直線和間隔為s的水平線將第一象限分隔為多個格點，把第一象限中的所有格點(x，y)按下列順序排成序列：(0，0)，(r，0)，(0，s)，(2r，0)，(r，s)，(0，2s)，…，(jr，0)，((j-1)r，s)，…，((j-i)r，is)，…，(r，(j-1)s)，(0，js)，…。并且依次在每一格點上安置雙環(huán)網(wǎng)絡(luò)G(N;r，s)的節(jié)點v∈{0，1，…，N-1}，其中v=xr+ys(modN)。如果在此之前節(jié)點v已出現(xiàn)過，則空出此格點，考察下一個格點，直到雙環(huán)網(wǎng)絡(luò)G(N;r，s)中所有的節(jié)點0，1，…，N-1都已出現(xiàn)或不再產(chǎn)生新的節(jié)點為止。生成圖形的形狀通常為“L”型，故稱為L-型瓦[6]。其中四個參數(shù)a、b、p和q分別表示L-型瓦四條邊上的格點個數(shù)。并記L-型瓦為L(N;a，b，p，q)。如G(15;1，7)所對應(yīng)的L-型瓦如圖2所示。

圖2 L(15;6，5，5，3)

定義2對于給定N(N≥4)的有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)，當r取整數(shù)1，s依次取(r，N)中的所有整數(shù)值，將得到的一組有向雙環(huán)網(wǎng)絡(luò)稱為有向雙環(huán)網(wǎng)絡(luò)的一個無限族（infinite family），記為IF_G(N)。

有向雙環(huán)網(wǎng)絡(luò)只存在兩種有向邊：[+r]邊和[+s]邊，根據(jù)定義1，對于有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷可以進行如下定義：

定義3用P表示有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)最小路徑圖中一個節(jié)點到其他節(jié)點間的路徑，用η(G，P，e)表示P中所包含的[+r]邊和[+s]邊的數(shù)目，有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷是指所有P中所包含的[+r]邊和[+s]邊的總數(shù)目，記為η(G，e)。因此可得：

定義4在有向雙環(huán)網(wǎng)絡(luò)的一個L-型瓦中，所有[+r]邊負荷記為η(G，e+r)，所有[+s]邊負荷記為η(G，e+s)，若η(G，e+r)=η(G，e+s)，則稱有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的邊負荷是平衡的。

在有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的一個IF_G(N)中，由于不同步長的網(wǎng)絡(luò)所對應(yīng)的L-型瓦是不同的，因此，其網(wǎng)絡(luò)負荷也不同。完成相同的業(yè)務(wù)需求所經(jīng)過的邊越少，其網(wǎng)絡(luò)的通信效率越高，因此，邊負荷越小的網(wǎng)絡(luò)性能越好。如何才能計算出有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷，根據(jù)定義3和定義4可知，有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷也是一個與距離相關(guān)的指標，因此，它也可從有向雙環(huán)網(wǎng)絡(luò)的最小路徑圖——L-型瓦中得到解決。方法如下：

定義5設(shè)x0，y0是正整數(shù)且滿足同余方程：xr+ys=v(modN)(v∈{0，1，…，N-1})。則稱(x0，y0)是同余方程的正解。若對于同余方程的任意異于(x0，y0)的正解(x1，y1)都有：

（1）x0+y0＜x1+y1

（2）當x1+y1=x0+y0時，有x1＜x0

則稱(x0，y0)是同余方程的最小正解。

定義6對于給定的有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)，同余方程定義如下：定理1對于給定的有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)，其最小路徑圖記為L(N;a，b，p，q)。若同余方程如定義6所定義，且方程（1）的最小正解為(k1，j1)，方程（2）的最小正解為(k2，j2)，則a=j1，b=k2，p=j2，q=k1。

證明（1）根據(jù)雙環(huán)網(wǎng)絡(luò)G(N;r，s)的L-型瓦定義可知，a是X軸上的最大格點數(shù)。定義6中的方程（1）ks=jr(modN)，0≤k＜j，j=1，2，…，N-1所得最小正解(k1，j1)的含義是：從節(jié)點0出發(fā)，最少走j1個[+r]邊就會出現(xiàn)和Y軸上相同的節(jié)點。根據(jù)L-型瓦的定義，L-型瓦內(nèi)不允許出現(xiàn)重復(fù)節(jié)點。因此，從節(jié)點0出發(fā)，向X軸的正方向只能走j1-1步，每走一步到達一個節(jié)點。包括0節(jié)點在內(nèi)，共有j1個節(jié)點。所以a=j1；同理在Y軸上可得：b=k2。

證明根據(jù)定義3，有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷是指雙環(huán)網(wǎng)絡(luò)中一個節(jié)點到其他所有節(jié)點所要經(jīng)過的邊集。由于L-型瓦為有向雙環(huán)網(wǎng)絡(luò)的最小路徑圖，因此，網(wǎng)絡(luò)負荷可利用L-型瓦來得到。根據(jù)有向雙環(huán)網(wǎng)絡(luò)的對稱性，只要考慮從節(jié)點0到其他所有節(jié)點的距離，就能知道有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷，因此，網(wǎng)絡(luò)負荷可以通過計算L-型瓦中節(jié)點0到其他節(jié)點的邊負荷之和來得到。由于節(jié)點0到其他節(jié)點的邊負荷可以表示為x條[+r]邊和y條[+s]邊之和(x≥0，y≥0)。因此，可分兩個步驟來計算[+r]邊和[+s]邊的負荷。

（1）計算節(jié)點0到其他節(jié)點[+r]邊的負荷。如圖2所示，可將向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的L-型瓦分為長為a、寬為b-q和長為q、寬為a-p的兩個長方形，分別計算兩個長方形中[+r]邊的個數(shù)，可得下式：

（2）計算節(jié)點0到其他節(jié)點[+s]邊的負荷。如圖2所示，可將向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的L-型瓦分為長為b寬為a-p和長為p寬為b-q的兩個長方形，分別計算兩個長方形中[+s]邊的個數(shù)，可得下式：

由定理1可知，有向雙環(huán)網(wǎng)絡(luò)的最小路徑圖L(N;a，b，p，q)的四個參數(shù)可以使用定義6的同余方程直接得出，無需繪制出L(N;a，b，p，q)。用此方法得出四個參數(shù)值的算法復(fù)雜度比通過繪制出L-型瓦算法的復(fù)雜度大大降低。有了L(N;a，b，p，q)的四個參數(shù)，根據(jù)定理2就能快速地計算出任意N值有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的網(wǎng)絡(luò)負荷了。

2 實驗結(jié)果及分析

對于一個業(yè)務(wù)需求，如何設(shè)計一個好的網(wǎng)絡(luò)結(jié)構(gòu)，使得完成該業(yè)務(wù)需求的網(wǎng)絡(luò)負荷最小，即尋找最優(yōu)負荷網(wǎng)絡(luò)和平衡負荷網(wǎng)絡(luò)的分布規(guī)律，這是研究網(wǎng)絡(luò)負荷的最終目標。為了實現(xiàn)這個目標，對多個有向雙環(huán)網(wǎng)絡(luò)的無限族進行了仿真實驗。實驗參數(shù)選取如下：

對于有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)，N取[4，1 000]內(nèi)的所有整數(shù)值和[1 000，10 000]內(nèi)的1 000個隨機整數(shù)值；對于任意N值，r取1，s取(1，N)內(nèi)的所有整數(shù)值，這種取值方式每次都能得到一個完整的無限族。圖3所示的是N=40的一個完整無限族的[+r]邊的負荷和[+s]邊的負荷的分布情況。圖4所示的是N=40的一個完整無限族中的網(wǎng)絡(luò)總負荷的分布情況。根據(jù)實驗結(jié)果分析，不難發(fā)現(xiàn)如下一些關(guān)系：

（1）對于有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的任意無限族，可能存在多個負荷平衡的網(wǎng)絡(luò)，如G(40;1，19)、G(40;1，29)和G(40;1，35)都是負荷平衡網(wǎng)絡(luò)。負荷平衡網(wǎng)絡(luò)的總負荷通常都比較小，如η(G(40;1，19)，e)=238，η(G(40; 1，29)，e)=204，η(G(40;1，35)，e)=210。其中204是該無限族中最小的網(wǎng)絡(luò)負荷。但并沒有發(fā)現(xiàn)負荷平衡網(wǎng)絡(luò)分布的任何規(guī)律。

（2）對于有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的任意一個無限族中，其網(wǎng)絡(luò)負荷的分布呈軸對稱圖形。

（3）對于有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的任意一個無限族中，其網(wǎng)絡(luò)負荷存在一個上界值和下界值，達到下界值的網(wǎng)絡(luò)稱為最優(yōu)負荷網(wǎng)絡(luò)。在G(40;1，s)無限族中，G(40;1，12)和G(40;1，29)都是最優(yōu)負荷網(wǎng)絡(luò)。如圖4所示。

圖3 G(40;1，s)的[+r]邊的負荷和[+s]邊的負荷

圖4 G(40;1，s)的網(wǎng)絡(luò)負荷分布圖

容易求得有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)網(wǎng)絡(luò)負荷η(G，e)的上界值與N的關(guān)系：當N為大于4的奇數(shù)時，η(G，e)= (N2-1)/4；當N為大于4的偶數(shù)時，η(G，e)=N2/4。但網(wǎng)絡(luò)負荷的下界值與N之間的關(guān)系并沒有發(fā)現(xiàn)，這將是下一個努力的方向。

3 結(jié)論

對于給定的有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)，通過參數(shù)k1、k2、j1和j2的定義，求出G(N;r，s)最小路徑圖L(N;a，b，p，q)的四個參數(shù)值。根據(jù)有向雙環(huán)網(wǎng)絡(luò)的最小路徑圖——L-型瓦，給出了計算有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷公式，該公式只與L(N;a，b，p，q)的四個參數(shù)相關(guān)。通過實驗結(jié)果的對比分析不難發(fā)現(xiàn)：有向雙環(huán)網(wǎng)絡(luò)的負荷可分為[+r]邊的負荷和[+s]邊的負荷，在有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的一個無限族中，可能存在多個負荷平衡的網(wǎng)絡(luò)。在有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的任意一個無限族中，其網(wǎng)絡(luò)負荷的分布呈軸對稱圖形，且網(wǎng)絡(luò)負荷存在上、下界值，達到該下界值的網(wǎng)絡(luò)稱為最優(yōu)負荷網(wǎng)絡(luò)，但該下界值與N之間的關(guān)系目前并未發(fā)現(xiàn)。該實驗結(jié)果對于研究網(wǎng)絡(luò)負荷的意義是顯而易見的。網(wǎng)絡(luò)負荷是否達到或接近最優(yōu)將成為雙環(huán)網(wǎng)絡(luò)設(shè)計時考慮的重要因素之一。

[1]Wilfong G，Winkler P.Ring routing and wavelength translation[C]//Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms，1998：333-341.

[2]Heydemann M，Meyer J C，Sotteau D.On forwarding indices of networks[J].Discrete Applied Mathematics，1989，23（2）：103-123.

[3]Hou X M，Xu M，Xu J M.Forwarding indices of consistent routings and their complexity[J].Networks，1994，24：75-82.

[4]Gargano L，Vaccaro U.Routing in all-optical networks：algorithmic and graph-theoretic problems[C]//Numbers，Information and Complexity，2000：555-578.

[5]Wong C K，Coppersmith D.A combinatorial problem related tomultimoduleorganizations[J].Journalof Association Computer，1974，21（3）：392-402.

[6]Chen C Y，Hwang F K.The minimum distance diagram of double-loop networks[J].IEEE Transactions on Computers，2000，49（9）：977-979.

[7]Chen C Y，James K L，Tang W S.An efficient algorithm tofindadouble-loopnetworkthat realizesagiven L-shape[J].Theoretical Computer Science，2006，359（1/3）：69-76.

[8]Chen C Y，Hwang F K.Equivalent L-shapes of doubleloop networks for the degenerate case[J].Journal of Interconnection Networks，2000，1：47-60.

[9]Chan C F，Chen C Y，Hong Z X.A simple algorithm to find the steps of double-loop networks[J].Discrete Applied Mathematics，2002，121（1/3）：61-72.

[10]李穎，陳業(yè)斌.有向雙環(huán)網(wǎng)絡(luò)G(N;r，s)的尋徑策略[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2009，37（5）：45-48.

[11]林宣治，陳寶興.關(guān)于有向雙環(huán)網(wǎng)絡(luò)L-形瓦的四個參數(shù)[J].漳州師范學(xué)院學(xué)報：自然科學(xué)版，2006，33（2）：12-16.

[12]陳業(yè)斌.基于二叉樹的有向雙環(huán)網(wǎng)絡(luò)最優(yōu)路由算法[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2008，36（6）：43-46.

[13]方木云，趙保華，屈玉貴.雙環(huán)網(wǎng)絡(luò)G(N;1，s)的L形瓦仿真算法[J].系統(tǒng)仿真學(xué)報，2005，17（4）：914-916.

[14]Gomez D，Gutierrez J，Ibeas A.Optimal routing in double loop networks[J].Theoretical Computer Science，2007，381（1/3）：68-85.

[15]Chen Y B，Li Y，Wang J K.On the wide diameter of directed double-loop network[J].Journal of Network and Computer Applications，2011，34（1）：692-696.

LI Ying1,CHEN Yebin2

1.Ma’anshan Teacher’s College,Ma’anshan,Anhui 243041,China
2.School of Computer Science,Anhui University of Technology,Ma’anshan,Anhui 243002,China

Based on analyzing the structure feature of WDM networks,this paper chooses some representative directed double-loop networks to study.It also provides the solutions of some congruence equations to compute the parameter values of L-shaped tile.According to the structure of L-shaped tile,it provides a formula to compute its network load.The experiment results demonstrate that there may be many load-balanced networks.For anyone of infinite families forG(N;r，s),the distribution of loads is axis symmetric figure,and there is a upper bound and a lower bound for loads.The network is called optimal load network when its load equals the lower bound.These results are important to design optimal double networks and improve transmission efficiency about networks.

Wavelength Division Multiplexing（WDM）networks;directed double-loop networks;network load;L-shaped tile;shortest path;infinite family

針對WDM網(wǎng)絡(luò)的結(jié)構(gòu)特征，選擇具有代表性的有向雙環(huán)網(wǎng)絡(luò)G（N；r，s）進行研究。給出一組同余方程，用于快速計算其L-型瓦圖的四個參數(shù)。根據(jù)L-型瓦的結(jié)構(gòu)，給出了計算有向雙環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)負荷公式。實驗結(jié)果分析表明：有向雙環(huán)網(wǎng)絡(luò)的一個無限族中可能存在多個負荷平衡的網(wǎng)絡(luò)。對于有向雙環(huán)網(wǎng)絡(luò)G（N；r，s）的任意一個無限族中，其網(wǎng)絡(luò)負荷的分布呈軸對稱圖形。網(wǎng)絡(luò)負荷存在上界和下界，負荷達到下界值的網(wǎng)絡(luò)稱為最優(yōu)負荷網(wǎng)絡(luò)。該研究成果對于設(shè)計最優(yōu)雙環(huán)網(wǎng)絡(luò)和提高網(wǎng)絡(luò)通信效率起到?jīng)Q定性的作用。

波分復(fù)用（WDM）網(wǎng)絡(luò)；有向雙環(huán)網(wǎng)絡(luò)；網(wǎng)絡(luò)負荷；L-型瓦；最短路徑；無限族

A

TP393.14

10.3778/j.issn.1002-8331.1210-0208

LI Ying,CHEN Yebin.Research on network loads of WDM double-loop networks.Computer Engineering and Applications,2014,50（18）：122-125.

國際科技合作項目（No.2011DFB61530）；安徽省高校級自然科學(xué)基金資助重點項目（No.KJ2012A262，No.KJ2013A058）。作者簡介：李穎（1971—），女，教授，研究方向為計算機網(wǎng)絡(luò)及數(shù)據(jù)庫。

2012-10-19

2013-02-05

1002-8331（2014）18-0122-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-02-28，http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.008.html