關于WDM雙環(huán)網絡網絡負荷的研究

李穎，陳業(yè)斌

1.安徽省馬鞍山師范高等?？茖W校，安徽馬鞍山 243041

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

關于WDM雙環(huán)網絡網絡負荷的研究

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

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

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

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

光網絡模型可用有向圖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]。光網絡中信息是通過每條鏈路中所容納的波長來承載的。節(jié)點u需將信息傳送到v，稱作u、v之間的業(yè)務需求（Request），記作R(u、v)。要完成u、v之間的業(yè)務需求就需要在u、v間建立光路徑。用R表示網絡節(jié)點間業(yè)務需求的集合，一般而言，網絡中的業(yè)務需求可統(tǒng)一表示為一個節(jié)點到其他相異節(jié)點對之間的業(yè)務需求的集合。在光網絡中有關鏈路負荷的概念定義如下：

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

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

目前，大多有向雙環(huán)網絡采用光波來傳送信息，因此，本文以有向雙環(huán)網絡的拓撲結構為基礎來研究光網絡負荷的相關問題。

1 有向雙環(huán)網的網絡負荷

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

有向雙環(huán)網絡的圖論模型是指這樣一個有向圖G(N;r，s)[5]，如圖1所示。N、r、s是自然數，其中N是網絡節(jié)點的個數，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所得非負余數。從定義可知，對于給定的N、r和s，唯一決定了一個有向雙環(huán)網絡G(N;r，s)的結構，因而也決定了它的相關特性。

圖1 有向雙環(huán)網絡G(15;1，7)的拓撲結構

根據有向雙環(huán)網絡G(N;r，s)的對稱性，節(jié)點v到任意節(jié)點u之間的路由問題可轉化為節(jié)點0到節(jié)點u-v之間的路由問題，因此，在有向雙環(huán)網絡中，任意兩節(jié)點之間的距離問題都可轉化為節(jié)點0和其他節(jié)點之間的距離問題。為了更直觀地了解雙環(huán)網絡的結構，根據有向雙環(huán)網絡的路由特性，把雙環(huán)網絡拓撲結構中的所有節(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)網絡G(N;r，s)的節(jié)點v∈{0，1，…，N-1}，其中v=xr+ys(modN)。如果在此之前節(jié)點v已出現過，則空出此格點，考察下一個格點，直到雙環(huán)網絡G(N;r，s)中所有的節(jié)點0，1，…，N-1都已出現或不再產生新的節(jié)點為止。生成圖形的形狀通常為“L”型，故稱為L-型瓦[6]。其中四個參數a、b、p和q分別表示L-型瓦四條邊上的格點個數。并記L-型瓦為L(N;a，b，p，q)。如G(15;1，7)所對應的L-型瓦如圖2所示。

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

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

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

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

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

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

定義5設x0，y0是正整數且滿足同余方程：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)網絡G(N;r，s)，同余方程定義如下：定理1對于給定的有向雙環(huán)網絡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）根據雙環(huán)網絡G(N;r，s)的L-型瓦定義可知，a是X軸上的最大格點數。定義6中的方程（1）ks=jr(modN)，0≤k＜j，j=1，2，…，N-1所得最小正解(k1，j1)的含義是：從節(jié)點0出發(fā)，最少走j1個[+r]邊就會出現和Y軸上相同的節(jié)點。根據L-型瓦的定義，L-型瓦內不允許出現重復節(jié)點。因此，從節(jié)點0出發(fā)，向X軸的正方向只能走j1-1步，每走一步到達一個節(jié)點。包括0節(jié)點在內，共有j1個節(jié)點。所以a=j1；同理在Y軸上可得：b=k2。

證明根據定義3，有向雙環(huán)網絡的網絡負荷是指雙環(huán)網絡中一個節(jié)點到其他所有節(jié)點所要經過的邊集。由于L-型瓦為有向雙環(huán)網絡的最小路徑圖，因此，網絡負荷可利用L-型瓦來得到。根據有向雙環(huán)網絡的對稱性，只要考慮從節(jié)點0到其他所有節(jié)點的距離，就能知道有向雙環(huán)網絡的網絡負荷，因此，網絡負荷可以通過計算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)網絡G(N;r，s)的L-型瓦分為長為a、寬為b-q和長為q、寬為a-p的兩個長方形，分別計算兩個長方形中[+r]邊的個數，可得下式：

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

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

2 實驗結果及分析

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

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

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

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

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

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

圖4 G(40;1，s)的網絡負荷分布圖

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

3 結論

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

[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)網絡G(N;r，s)的尋徑策略[J].華中科技大學學報：自然科學版，2009，37（5）：45-48.

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

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

[13]方木云，趙保華，屈玉貴.雙環(huán)網絡G(N;1，s)的L形瓦仿真算法[J].系統(tǒng)仿真學報，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網絡的結構特征，選擇具有代表性的有向雙環(huán)網絡G（N；r，s）進行研究。給出一組同余方程，用于快速計算其L-型瓦圖的四個參數。根據L-型瓦的結構，給出了計算有向雙環(huán)網絡的網絡負荷公式。實驗結果分析表明：有向雙環(huán)網絡的一個無限族中可能存在多個負荷平衡的網絡。對于有向雙環(huán)網絡G（N；r，s）的任意一個無限族中，其網絡負荷的分布呈軸對稱圖形。網絡負荷存在上界和下界，負荷達到下界值的網絡稱為最優(yōu)負荷網絡。該研究成果對于設計最優(yōu)雙環(huán)網絡和提高網絡通信效率起到決定性的作用。

波分復用（WDM）網絡；有向雙環(huán)網絡；網絡負荷；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）；安徽省高校級自然科學基金資助重點項目（No.KJ2012A262，No.KJ2013A058）。作者簡介：李穎（1971—），女，教授，研究方向為計算機網絡及數據庫。

2012-10-19

2013-02-05

1002-8331（2014）18-0122-04

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