有向雙環(huán)網絡最優(yōu)路由算法

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

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

有向雙環(huán)網絡最優(yōu)路由算法

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

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

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

有向雙環(huán)網絡;路由算法;最優(yōu)路由;最短路徑;L形瓦;對稱

1 概述

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

2 有向雙環(huán)網絡

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

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

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

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

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

3 一種有向雙環(huán)網絡最優(yōu)路由算法

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

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

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

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

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

圖2 有向雙環(huán)網絡對應的L型參數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 路由算法

設源節(jié)點為0節(jié)點,目的節(jié)點為v,下面給出基于L形瓦參數(shù)的雙環(huán)網絡的最優(yōu)路由算法,包括2個部分:

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

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

Setp 2針對有向雙環(huán)網絡G(N;r,s),按引理1求其L形瓦參數(shù)a,b,m,n,計算參數(shù)的同時,將橫、縱坐標軸上的節(jié)點分別存入對應的數(shù)組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。

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

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

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

Setp 2針對有向雙環(huán)網絡G(N;1,s),按引理1求其L形瓦參數(shù)a,b,m,n,計算參數(shù)的同時,將縱坐標軸上的節(jié)點分別存入對應的數(shù)組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,利用了單位步長雙環(huán)網絡[+1]邊的特殊性,單位步長雙環(huán)網絡G(N;1,s) L形瓦圖形橫軸上節(jié)點依次為1,2,…,a-1,算法僅需存儲縱軸節(jié)點,存儲節(jié)點數(shù)為b-1個,空間復雜度為O(n);算法作有限次比較,比較次數(shù)小于b次。

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

圖3 運行時間比較

5 結束語

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

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

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

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

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

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

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

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

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

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

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

[11] 劉煥平,楊義先,楊放春.雙環(huán)網 G(N;s1,s2)的直徑[J].系統(tǒng)工程理論與實踐,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-),男,副教授,主研方向:數(shù)據(jù)處理;張 珍、彭慧子,碩士;方木云,教授、博士。

2014-01-09

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

中文引用格式:劉 輝,張 珍,彭慧子,等.有向雙環(huán)網絡最優(yōu)路由算法[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.