有向双环网络的单播路由算法研究

　　1、引言

　　设N和h是正整数,其中N ≥5,2≤h ≤N-1。N个节点的双环网络G(N;1,h)是如下定义的有向图:其节点集为ZN={0,1,…,N -1},边集为E={i→i+1(mod N),i→i+h(mod N)|i∈ZN}。双环网络由于其点对称性、连通性、易扩展性且具有一定的容错能力,已广泛地应用于局域网和计算机分布式系统的设计中。最优双环网络设计、双环网络的寻径策略研究及其网络的直径估计及计算一直是受到关注的研究课题。

　　信息路由是通信网络的基本功能。若每个信息总是沿着从信源到信宿的最短路经传送,则称为最优信息路由。对于双环网络G(N;1,h),文献[6]给出了2≤h≤ 槡N +1时任意两点间最短路径的一个非常简便的算法。文献[4]提出了“非正常节点”概念,提出的寻径策略是预先存储0~h所有“非正常节点”编号及节点0到这些节点的最短路径,以便提高寻径效率。文献[5]也对0~h的“非正常节点”进行了研究,并给出了在满足某些条件的情况下,G(N;1,h)在区间 (0,h)内不存在“非平常节点”,并给出了类似于文献[4]的寻径策略。

　　本文对在什么情况下,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<N}= max{d(0,j)|0≤j<N}。

　　给定G(N;1,h),从点i到i+1的边称为[+1]边,从点i到i+h的边称为[+h]边。考虑一条从i到j的路径,它包含[+1]边、[+h]边的个数分别为x、y(x、y均为非负整数),则有j≡(i+x+yh)(mod N),等式成立与边出现的顺序无关,我们可把此路径记为x[+1]+y[+h]。

　　下面的三个定义来自文献。

　　定义1若存在整数x,使得x[+1]是0到v(0<v<N)的路径,则称x[+1]是0到v的单一[+1]边路径。设x′[+1]是0到v的单一[+1]边路径,若不存在比x′更小的x,使x[+1]也是0到v的单一[+1]边路径,则称x′[+1]是0到v的单一[+1]边最短路径。若存在整数y,使得y[+h]是0到v(0<v<N)的路径,则称y[+h]是0到v的单一[+h]边路径。设y′[+h]是0到v的单一[+h]边路径,若不存在比y′更小的y,使y[+h]也是0到v的单一[+h]边路径,则称y′[+h]是0到v的单一[+h]边最短路径。

　　考虑0到v(0<v<N)的最短路径,为了尽快到达v点,可优先走[+h]边,当走[+h]边不再有利时,走[+1]边,这种策略称为[+h]边优先的最短路径寻径策略。定义2设从节点0到节点v共有t条最短路径:x(i)v[+1]+y(i)v[+h](i = 1,2,…,t),若y(j)v=max{y(i)v,i=1,2,…,t},且所有[+h]边依次在前,所有[+1]边依次在后,则称x(j)v[+1]+y(j)v[+h]为从节点0到节点v的[+h]边优先最短路径。

　　定义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<h,且xh ≡xh(mod N)。证明若G(N;1,h)在区间 (0,h)内存在一个“非平常节点”xh,按照定义3可设0[+1]+x[+h]是0到xh的最短路径。因为xh[+1]+0[+h]是0到xh的一条路径,所以有x≤xh<h,且xh ≡xh(mod N)。

　　另一方面,若存在两个正整数x、xh使得式(1)成立:x≤xh<h,且xh ≡xh(mod N) (1)不妨设xh是使得式(1)成立的最小正整数,对于使得式(1)成立的最小正整数xh,x是使得式(1)成立的最小正整数。现证0[+1]+x[+h]是0到xh的一条最短路径。用反证法,若i[+1]+j[+h]是0到xh的一条最短路径且i+j<x≤xh。

　　(1)当i=0时,则有jh≡xh(mod N)且j<x≤xh<h。这与假设对于给定的xh,x也是使得x≤xh<h,且xh≡xh(mod N)成立的最小正整数矛盾!

　　(2)当i>0时,则有xh≡i+jh(mod N),即jh ≡xh-i(mod N)且j<xh-i<h。这与假设xh是使得x ≤xh<h,且xh≡xh(mod N)成立的最小正整数矛盾!

　　从上可知,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<h,且:xh ≡xh(mod N) (2)设x=l(p+1)+r,其中0≤r≤p,由式(2)可得 [l(p+1)+r]h≡xh(mod N),即:l(p-t)+rh ≡xh(mod N) (3)因为p-t=p-(p+q-h)=h-q≥1,所以0≤l(p-t)≤l(p+1)+r=x<h。

　　(1)当r=0,由式(3)可得xh=l(p-t),因此x=l(p+1)+r>xh,这与x≤xh的假设矛盾!

　　(2)当1≤r<p,由式(3)可得xh=l(p-t)+rh≥h,这与xh<h的假设矛盾!

　　(3)当r=p,由式(3)可得l(p-t)+ph+q≡xh+q(mod N),即l(p-t)≡xh+q(mod N)。

　　因此l(p-t)=xh+q,从而xh<l(p-t)<x,这与x≤xh<h的假设矛盾!

　　定理2给定双环网络G(N;1,h),若N =ph,则G(N;1,h)在区间 (0,h)内不存在“非平常节点”。证明用反证法,若在区间 (0,h)内有一个“非平常节点”,则存在两个正整数x、xh,使得x≤xh<h,且:xh ≡xh(mod N) (4)设x=lp+r,其中0≤r≤p-1,由式(4)可得 (lp+r)h≡xh(mod N),即:rh ≡xh(mod N) (5)因此,rh =xh。因为xh>0,所以r≥1,xh=rh ≥h,这与xh<h的假设矛盾!

　　推论1给定双环网络G(N;1,h),设N =ph+q,0≤q≤h-1,当h≤ 槡N时,G(N;1,h)在区间 (0,h)内不存在“非平常节点”。证明当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)内不存在“非平常节点”。

　　推论2对于给定的正整数N ≥5,令s=槡N,h=s+1。若N ≠s2,则G(N;1,h)在区间 (0,h)内不存在“非平常节点”。证明设N =ph+q,0≤q≤h-1。因为N ≠s2,所以可把N分为下列四种情形进行讨论:

　　(1)当N =s2+r,1≤r<s时,可得N =(s-1)(s+1)+r+1=(s-1)h+r+1,即p=s-1,q=r+1。此时p+q=s+r≥s+1=h。

　　(2)当N =s2+s时,可得N =s(s+1),即p=s,q=0。

　　(3)当N =s2+s+r,1≤r<s时,可得N =s(s+1)+r,即p=s,q=r。此时p+q=s+r≥s+1=h。

　　(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<h。因此,存在两个正整数p+1、h-q,使得p+1≤h-q<h且:(p+1)h≡h-q(mod N) (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< N}≤p+h-2。□定理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,y>p-1)是0到ph-1的一条最短路径且x+y<p+h-2。可知0[+1]+(y-p+1)[+h]是0到h-1-x的一条路径。因为y-p+1<h-1-x且 (y-p+1)h≡h-1-x(mod N),由引理1可知,G(N;1,h)在区间 (0,h)内至少存在一个“非平常节点”,这与G(N;1,h)在区间 (0,h)内不存在“非平常节点”矛盾!

　　从上可知,(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< N}≥d(0,ph-1)=p+h-2。

　　由引理3,D(N;1,h)≤p+h-2,即可得D(N;1,h)=p+h-2。□从推论1和推论2可知,此定理拓广了文献[6]中定理5的范围(仅有一种情况G(s2;1,s+1)除外)。比如,双环网络G(42;1,9)的步长9大于槡42 +1=7,它不在文献[6]中定理5所确定的范围。然而,因为42=4×9+6,4+6>9,据定理4可知,双环网络G(42;1,9)的直径等于4+9-2=11。

　　文献中的两个推论有误,现举例说明之。文献中的推论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<h)的最短路径为n[+1]+m[+h]。

　　证明用反证法,若n[+1]+m[+h]不是最短路径,假设x[+1]+y[+h](其中0≤x<h,y≥0)是0到v的一条最短路径,x+y<m+n。现在分三种情形证之。

　　情形1 y>m。由mh+n≡yh+x(mod N)及x+y<m+n,可得n-x≡(y-m)h(mod N)且0<y-m <n-x<h,由引理1可知,G(N;1,h)在区间 (0,h)内至少存在一个 “非平常节点”,这与G(N;1,h)在区间 (0,h)内不存在“非平常节点”矛盾!

　　情形2 y=m。由mh+n≡yh+x(mod N)及x+y<m+n,可得n-x≡0(mod N)且0<n-x<h,可得n-x=kN,k≥1,即n-x>h,这与0<n-x<h矛盾!

　　情形3 y < m。若x ≤n,则由mh+n ≡yh+x(mod N),可得 (m-y)h+n-x≡0(modN)。即0<(m-y)h+n-x=kN,k≥1,这与0<(m-y)h+n-x≤mh+n=v<N矛盾!若x>n,则由mh+n≡yh+x(mod N),可得 (m-y-1)h+h-x+n≡0(mod N)。因为0≤m-y-1≤p-1,0<h-x+n,所以有0<(m-y-1)h+h-x+n=kN,k≥1,这与0<(m-y-1)h+h+n-x<ph ≤ N矛盾!

　　□从第2节的推论1和推论2可以看出,定理5给出的单播路由算法适用的范围大于文献[6]给出的范围(仅有一种情况G(s2;1,s+1)除外),也就是说,文献算法适用的范围比定理5的范围更狭隘一些。比如,双环网络G(42;1,9)的步长9大于槡42 +1=7,它不在文献[6]中所确定的步长范围内。然而,因为42=4×9+6,4+6>9,据定理1可知,G(42;1,9)在区间(0,9)内不存在“非平常节点”。从定理5可知其存在简单且最优的单播路由算法。

　　求双环网络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)内的“非平常节点”。