有向雙環網絡最優路由算法

劉 輝,張 珍,彭慧子,方木云

(安徽工業大學計算機科學與技術學院,安徽馬鞍山243002)

有向雙環網絡最優路由算法

劉 輝,張 珍,彭慧子,方木云

(安徽工業大學計算機科學與技術學院,安徽馬鞍山243002)

最優路由的研究對于網絡節點的傳輸具有重要意義,但關于有向雙環網絡節點的最優路由研究,目前尚無統一的算法。現有有向雙環網絡的最優路由算法,主要集中在單位步長雙環網絡及一些特殊雙環網絡上,對于為數較多的非單位步長有向雙環網絡最優路由的研究較少。已知有向雙環網絡的MDD圖形為L形瓦,基于L形瓦參數設計提出一種通用的有向雙環網絡最優路由算法。該算法適用于單位步長和非單位步長有向雙環網絡。仿真結果表明,與基于[+h]邊優先路由及基于二叉樹的最優路由算法相比,該算法無需建造竹筏及二叉樹的空間,執行效率明顯提高。

有向雙環網絡;路由算法;最優路由;最短路徑;L形瓦;對稱

1 概述

在光纖通信領域,主干網大多以環型網絡的方式提供服務,其中,比較有代表性的有電力通信系統的SDH(Synchronous Digital Hierarchy)環網、電信系統的以太網和有線電視光纖網。近年來,關于環網的研究主要集中在雙環網絡和多環網絡上,其中雙環網絡(Double-loop Networks,DLN)因其結構相對簡單、對稱、易擴充且具有一定的容錯能力而備受關注[1]。本文通過研究有向雙環網絡L形瓦構圖,提出一種有向雙環網絡最優路由算法。

2 有向雙環網絡

有向雙環網絡分為單位步長網絡和非單位步長網絡,其圖論模型是指這樣的有向圖G(N;r,S),每個節點記為0,1,…,N-1,從節點i發出2條有向邊:i→i+r(modN),i→i+s(modN),其中,r,s為自然數,1≤r≠s＜N,gcd(N,r,s)=1,其圖為強連通圖,當r=1時,對應的有向圖通常記作G(N;1,h),相應的雙環網絡為有向單位步長雙環網絡。圖1為有向雙環網絡G(8;2,3)。

圖1 有向雙環網絡G(8;2,3)

雙環網絡路由的研究包括容錯路由[2]、最優路由[3]及其仿真[4-5],目前對于有向雙環網絡的最優路由方面的研究,主要集中在單位步長雙環網絡G(N; 1,h)[6-7]及一些特殊的雙環網絡[8]上。文獻[6]提出[+h]邊優先的路由算法,并得到一個“竹筏”型空間解;文獻[7]提出[+1]邊優先的路由算法,文獻[8]提出另一類特殊的雙環網絡G(N;1,h)(h滿足某類不等式)的最優路由方法;以上方法各異,但都是針對G(N;1,h),無法推廣到非單位步長有向雙環網絡G(N;r,S)。文獻[9]提出非單位步長網絡G(N;r,S)的路由算法,但路由方法可以進一步優化。

有向雙環網絡的 MDD(Minimum Distance Diagram)圖形為L形瓦,本文基于L形瓦參數設計有向雙環網絡的最優路由算法,對單位步長和非單位步長有向雙環網絡均適用。

根據雙環網絡的對稱性,節點u到節點v的最優路由可以轉化為節點0到v-u(如v-u＜0,則轉化為N+v-u)的最優路由,因此,研究雙環網絡的最優路由,只需要考慮0節點到其他節點的最優路由即可。

3 一種有向雙環網絡最優路由算法

首先在平面直角坐標系的第一象限構造G(N;r,s)有向雙環網絡MDD圖,原點表示0節點,構圖方法如下:

定義1第一象限訪問節點方法:把Euclid平面上的所有格點排成序列(1,0),(0,1),(2,0), (1,1),(0,2),…,同層按x遞減y遞增方向訪問節點,在每一坐標(x,y)處放置數k∈{0,1,…,N-1},其中,k=xr+ys(modN),如在此之前數k已出現過,則空出此格,考察下一格,直到數0,1,…,N-1都出現為止[10]。

按此方法得到的幾何構圖是有向雙環網絡G(N;r,s)對應的L形瓦(L-Shape tile)。如圖2所示的L形區域稱為具有參數(a,b,m,n)的一個L形瓦,記為N(a,b,m,n),則a=m+p,b=n+q,N=ab-mn,有如下重要性質:

引理1L形瓦參數a,b,m,n,可由下列等式計算[11]:

引理2p+qh≡0(modN),-m+bh≡0 (modN),a-nh≡0(modN)[12]。

圖2 有向雙環網絡對應的L型參數

引理3有向雙環網絡G(N;r,s)中,從節點0出發,無論以什么順序,經過x條[+r]邊和y條[+s]邊到節點v的充分必要條件是:v=xr+ys(modN)[9]。

定義2節點0到節點v的最短路徑指所有從節點0到節點v的路徑中長度最小的路徑。即最短路徑的長度為x?+y?=min{x+y|xr+yh(modN)=v,x≥0,y≥0},x?和y?的值可能不惟一[6]。

文獻[9]引理2“若x?+y?是節點0到節點v的最短路徑,則x?+y?的值以及x?和y?的值都是惟一存在的”。

引理2的證明過程及其結論存在誤區。x?+y?僅僅是數值,不能將其混為路徑,正確表述為“若x?+y?是節點0到節點v的最短路徑的長度,則x?+y?的值是惟一存在的。”但x?和y?的值并不惟一,例如:對于雙環網絡G(39;4,17)節點12而言,其最短路徑的長度為3,但x?=3,y?=0(此時節點12對應的最短路徑3[+r]+0[+s])或x?=0,y?=3(此時節點12對應的最短路徑0[+r]+3[+s]);類似,對于雙環網絡G(30;1,7)節點5而言,其最短路徑長度為5,但x?=5、y?=0或x?=0,y?=5,可見x?和y?的取值并不惟一。

引理2的證明過程用到雙環網絡MDD構圖作為證明的前提條件,實際上MDD圖上只是按照既定的規則生成,保證每個節點僅出現一次,但這不能說明雙環網絡節點最短路徑經過的[+r]邊x?數目及[+s]邊y?數目惟一。

定義3設從節點0到節點v的共有t條最短路徑:若,則稱為從節點0到節點v的[+r]邊最大最短路徑。

定理1有向雙環網絡G(N;r,s)所對應的L形瓦N(a,b,m,n)中,v節點對應坐標為(x?,y?),則x×[+r]+y×[+s]為節點0到節點v的[+r]邊最大最短路徑。

證明:根據定義1的構圖規則,v節點對應坐標為(x?,y?),則v=x?r+y?s(modN)且x?[+r]+y?[+s]為節點0到節點v的最短路徑。

下面證明x?[+r]+y?[+s]為節點0到節點v[+r]邊最大最短路徑。

用反證法。假設x?[+r]+y?[+s]不是節點0到節點v[+r]邊最大最短路徑,必存在(x′,y′),使得x′[+r]+y′[+s]為節點0到節點v的[+r]邊最大最短路徑,根據定義 3,x′＞x?。 因為x?[+r]+y?[+s]和x′[+r]+y′[+s]均為節點0到節點v的最短路徑,所以x?+y?=x′+y′,根據定義1的構圖規則,同層按x遞減y遞增方向訪問節點,對于x?+y?層節點訪問次序為(x?+y?,0)…(x′,y′)…(x?,y?)…(0,x?+y?),在坐標(x′,y′)處已訪問節點v,根據定義1構圖規則,節點v不可能在(x?,y?)處再次訪問,與已知v節點在L形瓦對應坐標為(x?,y?)矛盾。因此,假設不成立,x?[+r]+y?[+s]為節點0到節點v[+r]邊最大最短路徑。

定理2有向雙環網絡G(N;r,s)所對應的L形瓦N(a,b,m,n)中,設與v節點對應橫軸上的節點為α,與v節點對應縱軸上的節點為β,則節點v為:v=α+β(modN)。

證明:L形瓦N(a,b,m,n)中,β為縱軸上節點,設其坐標為(0,y?),據引理1,β=y×s(modN);α為橫軸上節點,設其坐標為(x?,0),據引理1,α=x×r(modN)。

則L形瓦N(a,b,m,n)中,v節點坐標為(x?,y?),據引理1,有:

v=x×r+y×s(modN)=α+β(modN),證畢。

推論有向雙環網絡G(N;r,s)所對應的L形瓦N(a,b,m,n)中,如果節點v可表示為:v=α+β (modN),其中,α為橫軸上某一節點,其坐標為(x?, 0);β為縱軸上某一節點,其坐標為(0,y?),則節點v對應坐標為(x?,y?)。

證明過程類似定理1,略去。

在有向雙環網絡G(N;r,s)所對應的L形瓦N(a,b,m,n)中,已知v節點對應坐標為(x?,y?),根據定理1,可知x?[+r]+y?[+s]為節點0到節點v的[+r]邊最大最短路徑;根據定理2及其推論,可快速計算x?,y?的數值。這樣無需構造雙環網絡MDD圖形,根據其四參數a,b,m,n以及橫軸、縱軸上對應節點及節點坐標,就可確定某一預先指定的節點在L形瓦上的坐標,從而得到其[+r]邊最大最短路徑。下面給出實例說明。

例計算雙環網絡G(39;7,17)中從節點8到節點2的最短路徑。

因為39+2-8=33,求解節點8到節點2的最短路徑等價于求解0節點到33的最短路徑。對于G(39;7,17)所對應的L形瓦,a=8,b=5,m=1,n=1。可知,L形瓦橫軸上節點個數為a-1=7;縱軸上節點個數為b-1=4。

L形瓦橫軸上節點存入數組NodeX()={7,14, 21,28,35,3,10},對應坐標分別為(1,0),(2,0),…, (7,0)

L形瓦縱軸上節點存入數組NodeY()={17, 34,12,29},對應坐標分別為(0,1),(0,2),(0,3), (0,4)

對于節點33,逐個與縱軸上節點17,34相減,將差值(或差值+N)和橫軸上節點進行比較,一旦相等,則退出,在本例中,33-12=21,而NodeY(3)=21,NodeX(3)=12,因此節點33橫坐標為節點14橫坐標,縱坐標為節點21對應的縱坐標,即(3,3),故從節點8到節點2的最短路徑為3[+r]+3[+s],該最短路徑為最大最短路徑。

4 路由算法

設源節點為0節點,目的節點為v,下面給出基于L形瓦參數的雙環網絡的最優路由算法,包括2個部分:

算法1非單位步長雙環網絡G(N;r,s)最優路由算法

Setp 1初始化參數N,r,s,其中N,r,s為自然數且N≥4,1＜r＜s＜N,且gcd(N,r,s)=1,初始化數組NodeX(),NodeY(),存儲橫、縱坐標軸上的節點;

Setp 2針對有向雙環網絡G(N;r,s),按引理1求其L形瓦參數a,b,m,n,計算參數的同時,將橫、縱坐標軸上的節點分別存入對應的數組NodeX(),NodeY()中,置初始值i=1,j=1;

Setp 3計算subvalue=v-NodeY(j),如果subvalue＜0,置subvalue=subvalue+N;

Setp 4比較subvalue和NodeX(i),如相等,輸出v坐標(i,j),退出;

Setp 5否則置i=i+1,然后返回Step4,直至i＞a-1;

Setp 6置j=j+1,重復Step3～Step5。

該算法需要空間存儲節點,存儲節點數為a+b-2個,空間復雜度為O(n);算法作有限次比較,比較次數小于(a-1)×(b-1)次,可得v節點在L形瓦上的坐標,繼而可得到其[+r]邊最大的最短路徑。

算法2單位步長雙環網絡G(N;1,s)最優路由算法。

Setp 1初始化參數N,s,其中,N,s為自然數且N≥4,1＜s＜N,初始化數組NodeX(),存儲橫坐標軸上的節點;

Setp 2針對有向雙環網絡G(N;1,s),按引理1求其L形瓦參數a,b,m,n,計算參數的同時,將縱坐標軸上的節點分別存入對應的數組NodeY()中,置初始值i=1,j=1;

Setp 3計算subvalue=v-NodeY(j);如subvalue＜0,跳至Step5;

Setp 4比較subvalue和p,如果subvalue＜p,輸出v坐標(subvalue,j),退出;否則比較j和q,如果j＜q,比較subvalue和a,如果subvalue＜a,輸出v坐標(subvalue,j),退出;

Setp 5置j=j+1,重復Step3～Step4。

該算法相對于算法1,利用了單位步長雙環網絡[+1]邊的特殊性,單位步長雙環網絡G(N;1,s) L形瓦圖形橫軸上節點依次為1,2,…,a-1,算法僅需存儲縱軸節點,存儲節點數為b-1個,空間復雜度為O(n);算法作有限次比較,比較次數小于b次。

將本文算法和文獻[6,9]比較,文獻[6]基于[+h]邊優先路由,但構造“竹筏”型空間解比較耗費時間;文獻[9]中節點路由區域擴充到L形瓦以外,為(a-1)×(b-1)的矩形區域,而本文算法節點路由區域僅限于L形瓦,提高了路由算法的執行效率,編程工具為Visual basic6.0,仿真實驗結果如圖3所示,本文算法效率上明顯優于其他算法。

圖3 運行時間比較

5 結束語

網絡節點路由是網絡研究中的一個重要課題,對于有向雙環網絡節點的最優路由研究,目前尚無明確的統一快捷算法。本文首先通過研究有向雙環網絡L形瓦構圖,在計算有向雙環網絡L形瓦參數的基礎上,提出一種較為通用的最優路由算法,不僅適用于非單位步長有向雙環網絡,也適用于單位步長有向雙環網絡,實現了有向雙環網絡最優路由算法的統一,并針對單位步長有向雙環網絡的特點進行了算法優化。仿真實驗結果表明,本文提出的算法效率上明顯優于其他算法,對類似拓撲結構網絡節點的最優路由研究有借鑒意義。

[1] 陳業斌,李 穎,鄭 嘯,等.關于有向環網平均直徑的研究[J].通信學報,2013,34(2):138-146.

[2] 方木云,彭慧子,劉 輝.無向雙環網絡的容錯路由研究[J].計算機工程與應用,2013,49(14):105-120.

[3] 劉 輝,方木云,鄭 嘯.基于L形瓦的無向雙環網絡直徑求解算法[J].華中科技大學學報:自然科學版, 2012,40(9):48-51.

[4] 劉 輝,何本卓,方木云.雙優雙環網絡G(N;1,s)的分布仿真[J].計算機工程,2012,38(8):47-49.

[5] 劉 輝,許發信,方木云.無向雙環網絡G(N;±r,±s)的圖形仿真算法[J].計算機工程,2011,37(6):272-276.

[6] 方木云,屈玉貴,趙保華.雙環網絡的[+h]邊優先尋徑策略[J].計算機學報,2008,31(3):536-542.

[7] 陳忠實,靳 蕃.雙環網絡[+1]邊優先最短路徑及其尋徑策略[J].計算機研究與發展,2001,38(7): 788-792.

[8] 陳協彬.步長有限制的雙環網絡的最優路由算法[J].計算機學報,2004,27(5):596-603.

[9] 李 穎,陳業斌.有向雙環網絡G(N;r,s)的尋徑策略[J].華中科技大學學報,2009,37(5):45-48.

[10] 劉 輝,方木云.直角坐標系下雙環網絡G(N;r,s)容錯路由研究[J].華中科技大學學報,2010,38(10): 43-46.

[11] 劉煥平,楊義先,楊放春.雙環網 G(N;s1,s2)的直徑[J].系統工程理論與實踐,1999,19(2):58-61.

[12] Dharmasena H P,Yan Xin.An optimal Fault-tolerant Routing Algorithm for Weighted Bidirectional Doubleloop Networks[J].IEEE Transactions on Parallel and Ditributed Systems,2005,16(9):841-852.

編輯 索書志

Optimal Routing Algorithm for Unidirectional Double Loop-network

LIU Hui,ZHANG Zhen,PENG Huizi,FANG Muyun
(School of Computer Science and Technology,Anhui University of Technology,Maanshan 243002,China)

Research on the optimal routing is significant for the transmission between network nodes,and there is no clear unified,efficient algorithms for the research on the optimal routing of Double-loop Network(DLN).Currently, research focuses on the optimal routing of the unit-step and some kind of special DLN,has little work on the non-unit step Unidirectional Double-loop Network(UDLN)which have a greater number.This paper gives general optimal routing algorithm between any two nodes for UDLN on the four parameters of L-shape tile since the Minimum Distance Diagram (MDD)of UDLN is known as L-shape tile,which is suitable for both unit-step and non-unit step UDLN,achieving the unity of optimal routing of directed double-loop network algorithm.Specially,the optimal algorithm for unit-step UDLN is improved based on the general routing algorithm.Compared with[+h]link prior routing algorithm and bintree optimal routing algorithm,the algorithm doesnot need space to build bamboo raft or bintree and efficiency of the algorithm is better than other algorithms.Simulation experiments show the validity of the algorithm.

unidirectional Double-loop Network(DLN);routing algorithm;optimal routing;shortest paths;L-shape tile;symmetry

1000-3428(2015)01-0092-04

A

TP393

10.3969/j.issn.1000-3428.2015.01.017

國家自然科學基金資助項目(61003311);安徽省教育廳基金資助重點項目(KJ2012A262,KJ2013A058)。

劉 輝(1979-),男,副教授,主研方向:數據處理;張 珍、彭慧子,碩士;方木云,教授、博士。

2014-01-09

2014-03-26 E-mail:liuhuiahut@163.com

中文引用格式:劉 輝,張 珍,彭慧子,等.有向雙環網絡最優路由算法[J].計算機工程,2015,41(1):92-95.

英文引用格式:Liu Hui,Zhang Zhen,Peng Huizi,et al.Optimal Routing Algorithm for Unidirectional Double Loopnetwork[J].Computer Engineering,2015,41(1):92-95.