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

劉王飛,陳寶興,岳 昊

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

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

劉王飛,陳寶興,岳 昊

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

有向雙環(huán)網(wǎng)絡(luò)G(N;1,h)(N是節(jié)點(diǎn)數(shù)，1和h是步長)是重要的互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)。給出了有向雙環(huán)網(wǎng)絡(luò)G(N;1,h)的若干性質(zhì)。作為這些性質(zhì)的兩個(gè)應(yīng)用，給出一類有向雙環(huán)網(wǎng)絡(luò)的直徑公式，以及這類有向雙環(huán)網(wǎng)絡(luò)的單播路由算法，這個(gè)算法是簡單且最優(yōu)的。

有向雙環(huán)網(wǎng)絡(luò)；最優(yōu)路由；非平常節(jié)點(diǎn)

1 引言

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

本文對在什么情況下，G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”，什么情況下存在“非平常節(jié)點(diǎn)”進(jìn)行了研究。給出了雙環(huán)網(wǎng)絡(luò)G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”的充分必要條件，并得到了它的兩個(gè)應(yīng)用：(1)給出一類有向雙環(huán)網(wǎng)絡(luò)的單播路由算法，這個(gè)算法是簡單且最優(yōu)的；(2)給出了這類有向雙環(huán)網(wǎng)絡(luò)的直徑公式。另外，指出了文獻(xiàn)[5]中兩個(gè)推論的紕漏。

2 定義及引理

網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)i與j間的距離d(i,j)定義為從i到j(luò)的最短路徑的長度。網(wǎng)絡(luò)的直徑指的是網(wǎng)絡(luò)中所有點(diǎn)對之間距離的最大者。用D(N;1,h)表示雙環(huán)網(wǎng)絡(luò)G(N;1,h)的直徑。因?yàn)殡p環(huán)網(wǎng)絡(luò)是點(diǎn)對稱性的，所以D(N;1,h)=max{d(i,j)|0≤i,j

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

下面的三個(gè)定義來自文獻(xiàn)[5]。

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

考慮0到v(0

定義3 稱以下節(jié)點(diǎn)為節(jié)點(diǎn)0所對應(yīng)的“非平常節(jié)點(diǎn)”：0到它們的[+h]邊優(yōu)先最短路徑正好就是它們的單一[+h]邊最短路徑。

比如，雙環(huán)網(wǎng)絡(luò)G(26; 1,11)中節(jié)點(diǎn)0所對應(yīng)的“非平常節(jié)點(diǎn)”為：7，11，18，22。在區(qū)間(0, 11)內(nèi)節(jié)點(diǎn)0所對應(yīng)的“非平常節(jié)點(diǎn)”為7。0到7的最短路徑是3[+11]，路徑長度為3。

下面將給出關(guān)于節(jié)點(diǎn)0所對應(yīng)的“非平常節(jié)點(diǎn)”的若干性質(zhì)。為了方便起見，把G(N;1,h)中在區(qū)間(0,h)內(nèi)節(jié)點(diǎn)0所對應(yīng)的“非平常節(jié)點(diǎn)”簡稱為在區(qū)間(0,h)內(nèi)的“非平常節(jié)點(diǎn)”。比如，網(wǎng)絡(luò)G(26; 1,11)中，在區(qū)間(0, 11)內(nèi)的“非平常節(jié)點(diǎn)”為7。

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

引理1 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，其中N=ph+q，0≤q≤h-1，則G(N;1,h)在區(qū)間(0,h)內(nèi)至少存在一個(gè)“非平常節(jié)點(diǎn)”的充分必要條件是存在兩個(gè)正整數(shù)x、xh，使得x≤xh

證明 若G(N;1,h)在區(qū)間(0,h)內(nèi)存在一個(gè)“非平常節(jié)點(diǎn)”xh，按照定義3可設(shè) 0[+1]+x[+h]是0到xh的最短路徑。因?yàn)閤h[+1]+0[+h]是0到xh的一條路徑，所以有x≤xh

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

x≤xh

且xh≡xh(modN)

(1)

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

(1)當(dāng)i=0時(shí)，則有jh≡xh(modN)且j

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

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

□

3 主要定理

這一節(jié)將對在什么情況下，G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”，什么情況下存在“非平常節(jié)點(diǎn)”進(jìn)行研究。

定理1 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，設(shè)N=ph+q，1≤q≤h-1，若p+q≥h, 則G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”。

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

xh≡xh(modN)

(2)

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

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

(3)

因?yàn)閜-t=p-(p+q-h)=h-q≥1, 所以0≤l(p-t)≤l(p+1)+r=x

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

(2)當(dāng)1≤r

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

□

定理2 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，若N=ph，則G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”。

證明 用反證法，若在區(qū)間(0,h)內(nèi)有一個(gè)“非平常節(jié)點(diǎn)”，則存在兩個(gè)正整數(shù)x、xh，使得x≤xh

xh≡xh(modN)

(4)

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

rh≡xh(modN)

(5)

因此，rh=xh。因?yàn)閤h>0，所以r≥1,xh=rh≥h，這與xh

□

證明 當(dāng)q=0時(shí)，由定理2可知,G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”。

當(dāng)q>0時(shí)，因?yàn)閜=(N-q)/h>(N-h)/h=N/h-1≥h-1，所以有1≤q≤h-1且p+q≥h。 由定理1可知,G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”。

□

證明 設(shè)N=ph+q，0≤q≤h-1。因?yàn)镹≠s2，所以可把N分為下列四種情形進(jìn)行討論：

(1)當(dāng)N=s2+r,1≤r

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

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

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

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

對于上面的第(2)種情形，因?yàn)閝=0，由定理2可知在這種情形下，G(N;1,h)在區(qū)間(0,h)內(nèi)也不存在“非平常節(jié)點(diǎn)”。

□

引理2 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，設(shè)N=ph+q，1≤q≤h-1，若p+q≤h-1，則G(N;1,h)在區(qū)間(0,h)內(nèi)至少存在一個(gè)“非平常節(jié)點(diǎn)”。

證明 因?yàn)閜+q≤h-1且1≤q≤h-1，所以有p+1≤h-q

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

(6)

從式(6)及引理1可知，區(qū)間(0,h)內(nèi)至少存在一個(gè)“非平常節(jié)點(diǎn)”。

□

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

定理3 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，設(shè)N=ph+q，0≤q≤h-1，則G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”的充分必要條件是q=0 或1≤q≤h-1且p+q≥h。

4 兩個(gè)應(yīng)用

這一節(jié)將利用上一節(jié)得到的結(jié)論，給出它們的兩個(gè)應(yīng)用：(1)當(dāng)G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”時(shí)，其直徑公式特別簡單。(2)當(dāng)G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”時(shí)，我們將給出一個(gè)簡單且最優(yōu)的單播路由算法，此算法適用的范圍大于文獻(xiàn)[6]給出的范圍(僅有一種情況除外)。

引理3 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，設(shè)N=ph+q，0≤q≤h-1，則G(N;1,h)的直徑D(N;1,h)≤p+h-2。

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

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

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

□

定理4 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，設(shè)N=ph+q，0≤q≤h-1，若G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”(即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的一條最短路徑。用反證法，若它不是最短路徑，假設(shè)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。

□

文獻(xiàn)[5]中的兩個(gè)推論有誤，現(xiàn)舉例說明之。

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

然而根據(jù)定理4，雙環(huán)網(wǎng)絡(luò)G(10099;1,100)的直徑應(yīng)為p+h-2=100+100-2=198。

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

“推論3 在G(N;1,h)中，當(dāng)d>p+h-2時(shí)，則在0→h內(nèi)至少存在一個(gè)‘非平常節(jié)點(diǎn)’ (其中d指的是網(wǎng)絡(luò)G(N;1,h)的直徑)。”

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

定理5 給定雙環(huán)網(wǎng)絡(luò)G(N;1,h)，設(shè)N=ph+q，0≤q≤h-1，當(dāng)G(N;1,h)在區(qū)間(0,h)內(nèi)不存在“非平常節(jié)點(diǎn)”時(shí)(即q=0 或1≤q≤h-1且p+q≥h)，G(N;1,h)存在簡單且最優(yōu)的單播路由算法：從0到v(其中1≤v≤N-1,v=mh+n,0≤m≤p,0≤n

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

現(xiàn)在分三種情形證之。

情形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)。因?yàn)?0≤m-y-1≤p-1,0

□

求雙環(huán)網(wǎng)絡(luò)G(42; 1，9)中從節(jié)點(diǎn)21到節(jié)點(diǎn)3的最短路徑。

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

5 結(jié)束語

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

[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.

附中文參考文獻(xiàn)：

[1] 李喬, 徐俊明, 張忠良. 最優(yōu)雙環(huán)網(wǎng)絡(luò)的無限族[J]. 中國科學(xué), A輯, 1993, 23(9):979-992.

[2] 徐俊明. 計(jì)算機(jī)互連雙環(huán)網(wǎng)絡(luò)的最優(yōu)設(shè)計(jì)[J]. 中國科學(xué), E輯, 1999, 29(3):272-278.

[3] 陳業(yè)斌, 李穎, 李中奎. 尋找緊優(yōu)有向雙環(huán)網(wǎng)絡(luò)的方法[J]. 系統(tǒng)仿真學(xué)報(bào), 2011, 23 (5):941-943.

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

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

[6] 馮斐玲, 金林鋼. 一類雙環(huán)網(wǎng)的特征分析及尋徑控制[J]. 計(jì)算機(jī)學(xué)報(bào), 1994, 17(11):859-865.

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

陳寶興(1961-),男,福建漳州人，博士后,教授,研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和算法設(shè)計(jì)。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),研究方向?yàn)镻etri網(wǎng)理論及其在系統(tǒng)死鎖控制中的應(yīng)用, 可計(jì)算性與計(jì)算復(fù)雜性理論。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

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

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

TP301;TP393

A

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

劉王飛(1981-),女,湖北通城人，碩士，講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與算法設(shè)計(jì)。E-mail:yulwf@163.com

通信地址：363000 福建省漳州市漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系

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