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

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽馬鞍山243002)

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

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

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽馬鞍山243002)

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

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

1 概述

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

2 有向雙環(huán)網(wǎng)絡(luò)

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

圖1 有向雙環(huán)網(wǎng)絡(luò)G(8;2,3)

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

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

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

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

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

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

按此方法得到的幾何構(gòu)圖是有向雙環(huán)網(wǎng)絡(luò)G(N;r,s)對應(yīng)的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,有如下重要性質(zhì):

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

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

圖2 有向雙環(huán)網(wǎng)絡(luò)對應(yīng)的L型參數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 路由算法

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

算法1非單位步長雙環(huán)網(wǎng)絡(luò)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(),存儲橫、縱坐標(biāo)軸上的節(jié)點(diǎn);

Setp 2針對有向雙環(huán)網(wǎng)絡(luò)G(N;r,s),按引理1求其L形瓦參數(shù)a,b,m,n,計(jì)算參數(shù)的同時(shí),將橫、縱坐標(biāo)軸上的節(jié)點(diǎn)分別存入對應(yīng)的數(shù)組NodeX(),NodeY()中,置初始值i=1,j=1;

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

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

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

Setp 6置j=j+1,重復(fù)Step3～Step5。

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

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

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

Setp 2針對有向雙環(huán)網(wǎng)絡(luò)G(N;1,s),按引理1求其L形瓦參數(shù)a,b,m,n,計(jì)算參數(shù)的同時(shí),將縱坐標(biāo)軸上的節(jié)點(diǎn)分別存入對應(yīng)的數(shù)組NodeY()中,置初始值i=1,j=1;

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

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

Setp 5置j=j+1,重復(fù)Step3～Step4。

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

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

圖3 運(yùn)行時(shí)間比較

5 結(jié)束語

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

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

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

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

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

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

[6] 方木云,屈玉貴,趙保華.雙環(huán)網(wǎng)絡(luò)的[+h]邊優(yōu)先尋徑策略[J].計(jì)算機(jī)學(xué)報(bào),2008,31(3):536-542.

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

[8] 陳協(xié)彬.步長有限制的雙環(huán)網(wǎng)絡(luò)的最優(yōu)路由算法[J].計(jì)算機(jī)學(xué)報(bào),2004,27(5):596-603.

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

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

[11] 劉煥平,楊義先,楊放春.雙環(huán)網(wǎng) G(N;s1,s2)的直徑[J].系統(tǒng)工程理論與實(shí)踐,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

國家自然科學(xué)基金資助項(xiàng)目(61003311);安徽省教育廳基金資助重點(diǎn)項(xiàng)目(KJ2012A262,KJ2013A058)。

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

2014-01-09

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

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