一类有向双环网络的最优单播路由算法
2014-09-15刘王飞陈宝兴
刘王飞,陈宝兴,岳 昊
(漳州师范学院计算机科学与工程系，福建 漳州 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)成立的最小正整数。现证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)内的一个“非平常节点”。 □ 这一节将对在什么情况下，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。 这一节将利用上一节得到的结论，给出它们的两个应用：(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≤x 从上可知，(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)的直径)。” 从引理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+y 情形3y □ 求双环网络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。 本文给出了有向双环网络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 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.China3 主要定理
4 两个应用
5 结束语
(Department of Computer Science and Engineering,Zhangzhou Normal University,Zhangzhou 363000,China)
