一類有向雙環網絡的最優單播路由算法

劉王飛,陳寶興,岳 昊

(漳州師范學院計算機科學與工程系，福建 漳州 363000)

一類有向雙環網絡的最優單播路由算法

劉王飛,陳寶興,岳 昊

(漳州師范學院計算機科學與工程系，福建 漳州 363000)

有向雙環網絡G(N;1,h)(N是節點數，1和h是步長)是重要的互聯網絡結構。給出了有向雙環網絡G(N;1,h)的若干性質。作為這些性質的兩個應用，給出一類有向雙環網絡的直徑公式，以及這類有向雙環網絡的單播路由算法，這個算法是簡單且最優的。

有向雙環網絡；最優路由；非平常節點

1 引言

設N和h是正整數，其中N≥5,2≤h≤N-1。N個節點的雙環網絡G(N;1,h)是如下定義的有向圖：其節點集為ZN={0,1,…,N-1}，邊集為E={i→i+1(modN),i→i+h(modN)|i∈ZN}。雙環網絡由于其點對稱性、連通性、易擴展性且具有一定的容錯能力，已廣泛地應用于局域網和計算機分布式系統的設計中。最優雙環網絡設計[1～3]、雙環網絡的尋徑策略研究[4～6]及其網絡的直徑估計及計算[7]一直是受到關注的研究課題。

本文對在什么情況下，G(N;1,h)在區間(0,h)內不存在“非平常節點”，什么情況下存在“非平常節點”進行了研究。給出了雙環網絡G(N;1,h)在區間(0,h)內不存在“非平常節點”的充分必要條件，并得到了它的兩個應用：(1)給出一類有向雙環網絡的單播路由算法，這個算法是簡單且最優的；(2)給出了這類有向雙環網絡的直徑公式。另外，指出了文獻[5]中兩個推論的紕漏。

2 定義及引理

網絡中兩個節點i與j間的距離d(i,j)定義為從i到j的最短路徑的長度。網絡的直徑指的是網絡中所有點對之間距離的最大者。用D(N;1,h)表示雙環網絡G(N;1,h)的直徑。因為雙環網絡是點對稱性的，所以D(N;1,h)=max{d(i,j)|0≤i,j

給定G(N;1,h)，從點i到i+1的邊稱為[+1]邊，從點i到i+h的邊稱為[+h]邊?？紤]一條從i到j的路徑，它包含[+1]邊、[+h]邊的個數分別為x、y(x、y均為非負整數)，則有j≡(i+x+yh)(modN)，等式成立與邊出現的順序無關，我們可把此路徑記為x[+1]+y[+h]。

下面的三個定義來自文獻[5]。

定義1 若存在整數x， 使得x[+1]是0到v(0

考慮0到v(0

定義3 稱以下節點為節點0所對應的“非平常節點”：0到它們的[+h]邊優先最短路徑正好就是它們的單一[+h]邊最短路徑。

比如，雙環網絡G(26; 1,11)中節點0所對應的“非平常節點”為：7，11，18，22。在區間(0, 11)內節點0所對應的“非平常節點”為7。0到7的最短路徑是3[+11]，路徑長度為3。

下面將給出關于節點0所對應的“非平常節點”的若干性質。為了方便起見，把G(N;1,h)中在區間(0,h)內節點0所對應的“非平常節點”簡稱為在區間(0,h)內的“非平常節點”。比如，網絡G(26; 1,11)中，在區間(0, 11)內的“非平常節點”為7。

以下總設N、p、h為正整數，且N≥5,p≥1,h≥2，q為非負整數，0≤q≤h-1。

引理1 給定雙環網絡G(N;1,h)，其中N=ph+q，0≤q≤h-1，則G(N;1,h)在區間(0,h)內至少存在一個“非平常節點”的充分必要條件是存在兩個正整數x、xh，使得x≤xh

證明 若G(N;1,h)在區間(0,h)內存在一個“非平常節點”xh，按照定義3可設 0[+1]+x[+h]是0到xh的最短路徑。因為xh[+1]+0[+h]是0到xh的一條路徑，所以有x≤xh

另一方面，若存在兩個正整數x、xh使得式(1)成立：

x≤xh

且xh≡xh(modN)

(1)

不妨設xh是使得式(1)成立的最小正整數，對于使得式(1)成立的最小正整數xh，x是使得式(1)成立的最小正整數?，F證0[+1]+x[+h]是0到xh的一條最短路徑。用反證法，若i[+1]+j[+h]是0到xh的一條最短路徑且i+j

(1)當i=0時，則有jh≡xh(modN)且j

(2)當i>0時，則有xh≡i+jh(modN)，即jh≡xh-i(modN)且j

從上可知，0[+1]+x[+h]是0到xh的一條最短路徑，它也是單一[+h]邊最短路徑，即xh是G(N;1,h)在區間(0,h)內的一個“非平常節點”。

□

3 主要定理

這一節將對在什么情況下，G(N;1,h)在區間(0,h)內不存在“非平常節點”，什么情況下存在“非平常節點”進行研究。

定理1 給定雙環網絡G(N;1,h)，設N=ph+q，1≤q≤h-1，若p+q≥h, 則G(N;1,h)在區間(0,h)內不存在“非平常節點”。

證明 令t=p+q-h≥0, 則有N+p-t=(p+1)h。用反證法，若在區間(0,h)內有一個“非平常節點”，則存在兩個正整數x、xh，使得x≤xh

xh≡xh(modN)

(2)

設x=l(p+1)+r，其中0≤r≤p，由式(2)可得 [l(p+1)+r]h≡xh(modN)，即:

l(p-t)+rh≡xh(modN)

(3)

因為p-t=p-(p+q-h)=h-q≥1, 所以0≤l(p-t)≤l(p+1)+r=x

(1)當r=0， 由式(3)可得xh=l(p-t)， 因此x=l(p+1)+r>xh，這與x≤xh的假設矛盾！

(2)當1≤r

(3)當r=p，由式(3)可得l(p-t)+ph+q≡xh+q(modN)，即l(p-t)≡xh+q(modN)。因此l(p-t)=xh+q，從而xh

□

定理2 給定雙環網絡G(N;1,h)，若N=ph，則G(N;1,h)在區間(0,h)內不存在“非平常節點”。

證明 用反證法，若在區間(0,h)內有一個“非平常節點”，則存在兩個正整數x、xh，使得x≤xh

xh≡xh(modN)

(4)

設x=lp+r，其中0≤r≤p-1，由式(4)可得 (lp+r)h≡xh(modN)，即:

rh≡xh(modN)

(5)

因此，rh=xh。因為xh>0，所以r≥1,xh=rh≥h，這與xh

□

證明 當q=0時，由定理2可知,G(N;1,h)在區間(0,h)內不存在“非平常節點”。

當q>0時，因為p=(N-q)/h>(N-h)/h=N/h-1≥h-1，所以有1≤q≤h-1且p+q≥h。 由定理1可知,G(N;1,h)在區間(0,h)內不存在“非平常節點”。

□

證明 設N=ph+q，0≤q≤h-1。因為N≠s2，所以可把N分為下列四種情形進行討論：

(1)當N=s2+r,1≤r

(2)當N=s2+s時，可得N=s(s+1)，即p=s,q=0。

(3)當N=s2+s+r,1≤r

(4)當N=s2+2s時，可得N=s(s+1)+s，即p=s,q=s。此時p+q=2s=h+s-1≥h。

對于上面的第(1)、(3)、(4)三種情形，均有p+q≥h，由定理1可知在這三種情形下，G(N;1,h)在區間(0,h)內不存在“非平常節點”。

對于上面的第(2)種情形，因為q=0，由定理2可知在這種情形下，G(N;1,h)在區間(0,h)內也不存在“非平常節點”。

□

引理2 給定雙環網絡G(N;1,h)，設N=ph+q，1≤q≤h-1，若p+q≤h-1，則G(N;1,h)在區間(0,h)內至少存在一個“非平常節點”。

證明 因為p+q≤h-1且1≤q≤h-1，所以有p+1≤h-q

(p+1)h≡h-q(modN)

(6)

從式(6)及引理1可知，區間(0,h)內至少存在一個“非平常節點”。

□

由定理1、定理2及引理2，可得如下的定理3。

定理3 給定雙環網絡G(N;1,h)，設N=ph+q，0≤q≤h-1，則G(N;1,h)在區間(0,h)內不存在“非平常節點”的充分必要條件是q=0 或1≤q≤h-1且p+q≥h。

4 兩個應用

這一節將利用上一節得到的結論，給出它們的兩個應用：(1)當G(N;1,h)在區間(0,h)內不存在“非平常節點”時，其直徑公式特別簡單。(2)當G(N;1,h)在區間(0,h)內不存在“非平常節點”時，我們將給出一個簡單且最優的單播路由算法，此算法適用的范圍大于文獻[6]給出的范圍(僅有一種情況除外)。

引理3 給定雙環網絡G(N;1,h)，設N=ph+q，0≤q≤h-1，則G(N;1,h)的直徑D(N;1,h)≤p+h-2。

證明 當0≤j≤(p-1)h+h-1時，設j=xh+y，其中0≤y≤h-1，則有x≤p-1,y≤h-1。注意到y[+1]+x[+h]是0到j的一條路徑，因此有d(0,j)≤x+y≤p+h-2。

當ph≤j≤N-1=ph+q-1時，設j=ph+y，其中0≤y≤q-1，注意到y[+1]+p[+h]是0到j的一條路徑，因此有d(0,j)≤p+y≤p+q-1≤p+h-2。

由上可知，D(N;1,h)=max{d(0,j)|0≤j

□

定理4 給定雙環網絡G(N;1,h)，設N=ph+q，0≤q≤h-1，若G(N;1,h)在區間(0,h)內不存在“非平常節點”(即q=0 或1≤q≤h-1且p+q≥h)，則G(N;1,h)的直徑為D(N;1,h)=p+h-2。

證明 先證(h-1)[+1]+(p-1)[+h]是0到(p-1)h+h-1=ph-1的一條最短路徑。用反證法，若它不是最短路徑，假設x[+1]+y[+h](其中 0≤xp-1)是0到ph-1的一條最短路徑且x+y

從上可知，(h-1)[+1]+(p-1)[+h]是0到ph-1的一條最短路徑，從而有d(0,ph-1)=p+h-2。這樣可得，D(N;1,h)=max{d(0,j)|0≤j

由引理3，D(N;1,h)≤p+h-2，即可得D(N;1,h)=p+h-2。

□

文獻[5]中的兩個推論有誤，現舉例說明之。

文獻[5]中的推論2有誤。取h=100,p=100,q=99,N=10099。所給的雙環網絡符合推論2的條件，按照推論2的公式，雙環網絡G(10099;1,100)的直徑為max{p-1+h-1,p+q}=max{198,199}=199。

然而根據定理4，雙環網絡G(10099;1,100)的直徑應為p+h-2=100+100-2=198。

文獻[5]中的推論3有誤。為了討論方便起見，現把其摘錄如下：

“推論3 在G(N;1,h)中，當d>p+h-2時，則在0→h內至少存在一個‘非平常節點’ (其中d指的是網絡G(N;1,h)的直徑)?！?/p>

從引理2可知，不管在什么情況下，雙環網絡G(N;1,h)的直徑是小于或等于p+h-2，不可能出現G(N;1,h)直徑大于p+h-2的情況，因此推論3所給的條件是沒有意義的。

定理5 給定雙環網絡G(N;1,h)，設N=ph+q，0≤q≤h-1，當G(N;1,h)在區間(0,h)內不存在“非平常節點”時(即q=0 或1≤q≤h-1且p+q≥h)，G(N;1,h)存在簡單且最優的單播路由算法：從0到v(其中1≤v≤N-1,v=mh+n,0≤m≤p,0≤n

證明 用反證法，若n[+1]+m[+h]不是最短路徑，假設x[+1]+y[+h](其中 0≤x

現在分三種情形證之。

情形1y>m。由mh+n≡yh+x(modN)及x+y

情形2y=m。由mh+n≡yh+x(modN)及x+yh，這與0

情形3yn，則由mh+n≡yh+x(modN)，可得(m-y-1)h+h-x+n≡0(modN)。因為 0≤m-y-1≤p-1,0

□

求雙環網絡G(42; 1，9)中從節點21到節點3的最短路徑。

因為3-21≡24(mod 42)，24=2×9+6，所以從節點21到節點3的最短路徑是6[+1]+2[+9]，即21→30→39→40→41→0→1→2→3。

5 結束語

本文給出了有向雙環網絡G(N;1,h)在區間(0,h)內不存在“非平常節點”的一個充分必要條件，并得到了它的兩個應用：(1)給出一類有向雙環網絡的單播路由算法，這個算法是簡單且最優的，此單播路由算法適用的范圍大于文獻[6]給出的范圍(僅有一種情況G(s2;1,s+1)除外)；(2)給出了這類有向雙環網絡的直徑公式。對存在“非平常節點”的情形，下一步的工作將確定有向雙環網絡G(N;1,h)在區間(0,h)內的“非平常節點”。

[1] Li Qiao, Xu Jun-ming, Zhang Zhong-liang. Infinite families of optimal double loop networks[J]. Science in China, Series A, 1993, 23(9):979-992. (in Chinese)

[2] Xu Jun-ming. Designing of optimal double loop networks [J]. Science in China, Series E, 1999, 29(3):272-278. (in Chinese)

[3] Chen Ye-bin, Li Ying, Li Zhong-kui. Methods to find optimal double-loop networks[J]. Journal of System Simulation, 2011, 23(5):941-943. (in Chinese)

[4] Chen Zhong-xue, Jin Fan. On the [+1]-link-prior shortest path and optimal routing for double-loop networks[J]. Journal of Computer Research and Development, 2001, 38(7):788-792. (in Chinese)

[5] Fang Mu-yun, Qu Yu-gui, Zhao Bao-hua. [+h]-link prior routing strategy for double-loop network[J]. Chinese Journal of Computers, 2008, 31(3):536-542. (in Chinese)

[6] Feng Fei-ling, Jin Lin-gang. Characteristics analysis and rou-ting control for a class of double-loop networks[J]. Chinese Journal of Computers, 1994, 17(11):859-865. (in Chinese)

[7] Chen B X, Xiao W J. A diameter formula for an undirected double-loop network[J]. Ars Combinatoria, 2009, 90:395-404.

附中文參考文獻：

[1] 李喬, 徐俊明, 張忠良. 最優雙環網絡的無限族[J]. 中國科學, A輯, 1993, 23(9):979-992.

[2] 徐俊明. 計算機互連雙環網絡的最優設計[J]. 中國科學, E輯, 1999, 29(3):272-278.

[3] 陳業斌, 李穎, 李中奎. 尋找緊優有向雙環網絡的方法[J]. 系統仿真學報, 2011, 23 (5):941-943.

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

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

[6] 馮斐玲, 金林鋼. 一類雙環網的特征分析及尋徑控制[J]. 計算機學報, 1994, 17(11):859-865.

LIU Wang-fei,born in 1981,MS,lecturer,her research interests include computer networks, and computer algorithm design.

陳寶興(1961-),男,福建漳州人，博士后,教授,研究方向為計算機網絡和算法設計。E-mail:cbaoxing@126.com

CHEN Bao-xing,born in 1961,post doctor,professor,his research interests include computer networks, and computer algorithm design.

岳昊(1980-),男,山東菏澤人，博士后,副教授,CCF會員(E200016135M),研究方向為Petri網理論及其在系統死鎖控制中的應用, 可計算性與計算復雜性理論。E-mail:yuehao_1980@126.com

YUE Hao,born in 1980,post doctor,associate professor,CCF member(E200016135M),his research interests include Petri nets and their application in the deadlock control, computability and computational complexity theory.

An optimal routing algorithm for a class of directed double loop network

LIU Wang-fei，CHEN Bao-xing，YUE Hao
(Department of Computer Science and Engineering,Zhangzhou Normal University,Zhangzhou 363000,China)

Directed double loop networkG(N;1,h), whereNis the number of its nodes, 1 andhare its steps, is an important interconnection network. Some properties ofG(N;1,h) are given. As two applications of these properties, a diameter formula for this network is given. An optimal and simple routing algorithm for a class of directed double loop network is also obtained.

directed double loop network;optimal routing; abnormal node

2012-09-24;

2012-12-19

國家自然科學基金資助項目(60973150)；福建省自然科學基金資助項目(2010J01354)

1007-130X(2014)03-0458-05

TP301;TP393

A

10.3969/j.issn.1007-130X.2014.03.014

劉王飛(1981-),女,湖北通城人，碩士，講師，研究方向為計算機網絡與算法設計。E-mail:yulwf@163.com

通信地址：363000 福建省漳州市漳州師范學院計算機科學與工程系

Address:Department of Computer Science and Engineering,Zhangzhou Normal University,Zhangzhou 363000,Fujian,P.R.China