о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3610ڡVol.36No.101999



·ڽӷֺ·ɵо
˽ƽ˹Ⱥ
ժҪ·ͲԳӦĳʹôͳ·㷨Э鲻.װ·޸ǽ˫ͨӵ·ĳ÷޷ʺȫ·ԶĿ.ȸ·ɵĶͱʾнɢڽӷ㷨֤ĳһ·Խض·Ͻ磻ȻڽӾ·㷨ʵ֤㷨ȷ.
ؼʡ磬Э飬·㷨
ͼšTP393
RESEARCH ON NEIGHBOR DISCOVERY AND 
PATH GENERATION FOR UNIDIRECTIONAL LINKS 
PAN Jian-Ping and GU Guan-Qun
(Department of Computer Science, Southeast University, Nanjing 210096)
AbstractWith the emergence of unidirectional links and asymmetric applications requirements, traditional routing algorithms and protocols for bi-directional and symmetric links are facing some severe challenges. Tunnel encapsulation and route modification are two common solutions to the short-term scenario where some unidirectional links are added into the connected bi-directional networks, but they also fail to meet the long-term scenario where only unidirectional links are available. Following the definition of graph topology and network routing, a bounded neighbor discovery algorithm is proposed, and the upper bound on trips of any loop crossing one specified links is proved. A path generation algorithm based on the neighbor/path matrix is also presented and validated by some examples.
Key wordscomputer network, network protocol, routing algorithm
1о
ͳ·㷨ЭʽʽҪ²·˫ͨΪ˫·(bi-directional link, BDL)·.ھRIP[1]·Э飬abڣbcľΪxaΪacľΪx+1.·״̬OSPF[2]Э飬ҪڽӽԳƵؽӦԱ֤·Ϣɿ.
µӦʹʹĺĳЩϲ.WebļӦãݴӷصͻˣӦû·Ӧ󲢷ǶԳƵ.ŵдǹص㣬淢豸ĴҪԶڽ豸ƶûЯ豸.xDSLCable ModemͨṩǶԳƴŵЧ.ͳ·㷨Эڵ·(uni-directional link, UDL)޷RIPľOSPFĿɿӦ.ⵥ·ԶͶ[3]ԴЭӰ.о·ɵ.
ڳֵͨBDLһЩUDL·[4,5]װ[6]·޸[7].ǰ߽UDLķ·BDLԱ;·ɵ޸ģȱԺͿչԣҪRIPЭ飬Ҫ޸Ĵͳ·㷨Э.ԶҪ[8]ȫUDLͨ(һBDLͬUDL)ȻлĽ·㷨Э鶼ʺֳ[8,9].ȶ·ɽϸойؼӷֺ·⣬õһЩĽ.
2ʾ
ͼ1UDLɵͨ磬ɱʾͼG=(V,E)н㼯V={a,b,c,d,e,f}ߵļE={a,b,c,b,d,a,b,e,f,c,e,d, e,f}u,vʾӽuv.C:ERmǴEmάʵRӳ䣬ʾÿ·ӦĶ(m).u1un·(u1,u2,u2,u3,,un-1,un)(Ϊ(u1,u2,,un))ļϼR1n.R1n·.


ͼ1һUDL
·ɱʾΪͼG=(V,E)ӳCȡv1,v2VRv1v2Rv2v1CĶԼѡĳ(ĳЩ)ضrv1v2rv2v1ɻ·.̺ÿ㶼ͼˣ޴ԼܵõRv1v2Rv2v1Ӽ.·v1v2v1v2v1v2ûбҪԳƣ·v1v2v1ļϼLv1v2v1=Rv1v2Rv2v1.
ԶͶԴf޼S=(s1,s2,)RfS Ϊ{Rfs1, Rfs2,}RSf Ϊ{Rs1f, Rs2f,}.CĶԼ·ѡһض{{rfs1, rs1f},{rfs2,rs2f},}fһsiĻ·.ͶݽfsifĻ·ΪдԴ޵.ڴRfS һfΪsiΪҶмɢ.
3ڽӷ
ڽӷֶBDLԶ׼(a,bb,a)UDLȴǺܴ(̺ٳ).رڽϢ·ɻظԽĳһض·(ͼ1afٷصaafa=(a,b,e,f,c,b,e,d,a)贩Խ·b,e)BDLظͬһԽĳһ·.ҵ֤ظԽϽ.
3.1ԽϽ
UDLͼG=(V,E)·uvu=(u,u2,,,v,v,,un-1,un)Ҫ֤ȡx,y{u,u2,,,v,v,,un-1,un}x,y(u,u2,,,v,v,,un-1,un)ִΪmͼGͻ·L޹صMʹmM(ȺųMΪȷ).
1. (·)uv=(u,u2,u2,u3,,un-1,v)Ruv{u,u2,u2,u3,,un-1,v}-{x,y}Ruvuv·֮Ϊ·.ƶ·.
1. u,y{u,y,u2,u3,,un-1,v}u,yɽuv1.
֤. ʧһԣu,yuv=(u,y,,u,yi,,un-1,v)һγΪu,yi .(u,yi,,un-1,v)Ruv·Ķȼԭеuv.
2. x,v{u,u2,u2,u3,,x,v}x,vɽuv1.
֤. ʧһԣx,vuv=(u,u2,,x,vj,,x,v)ǰһγΪx,vj .(u,u2,,x,vj)Ruv·Ķȼԭеuv.
3. x,y{u,u2,,x,y,,un-1,v}x,yɽuv1.
֤. ʧһԣx,yuv=(u,u2,,x,yi,, x,yj,x,y䡵j+1,,un-1,v)ǰһγֱַΪx,yi͡x,yj.(u,u2,,x,yi, x,y䡵j+1,, un-1,v)RuvҸ·Ķȼԭеuv.
һuvuuvvuɣu,yx,vv,yx,uuvu1.
1. (һ·ĳһ·ִ) x,y{x,y}-{u,v}={x,y}({x,y}uv)x,y{u,u2,,,v,v,,,un-1,u}x,yuvu2.
֤. (÷֤)衴x,yuvu3.
13s,vv,tuvu1Σvuvuָ2ֱ֣Ϊ{u,u2,,s,v}{v,t,,un-1,u}.衴x,yuvu3Σݡԭ򡱣{u,u2,,s,v}{v,t,,un-1,u}һ2ϵġx,y.ʧһԣ{u,u2,,x,yi,,x,yj,w,zj+1,s,v}2x,y.·Ķ壬((u,u2,,x,yj,w,zj+1,s,v),(v,t,,un-1,u))Luvuȼuvu.
޴ʹ򣬿Ա֤һx,yuvu2.ͼ1˵ĳһ·2ȫҪ(ڡb,eڻ·afa2).
һUDL·ĳһ·ӳֵĴȷΪ2. 
֤.
1. x,y{x,y}-{u,v}={x,y}({x,y}uv)x,yuvu2ΣֵܳӦ{u,u2,,x,yi,,,v,v,,,x,yj,,un-1,u}.
3.2ɢ
ͼ1aִ2ӿڣһһ.ʼʱaԼĽӿϢϢͨӿڸ֪һ(עa֪bһ).baĽӿϢ󼴵a,ba,bb·û.ba,bӿϢһٴݸһ.Ƶأeӿڷa,bb,eӿϢ.d/f/cƵĹ.adáa,bb,ee,dd,aɵab,ae,ad·.ϢaʼϢ(̺a,a)ͬa··Ϣһ.bcáa,bb,ee,ff,cc,bɵbe,bf,bcaͬԭb··Ϣ.bٴδa·Ϣ·baaabbϤab֮γɻ·(˺ҲaϤ).ӷֹȶÿ㽫·ɷΧϢÿ㽫ؽ·ɼѡ.
·Ϣ󣬽Ҫά·ɣӦ·Ķ̬(µ·ԭ·ʧܵ).ÿԸνDirect-Hello֪ͨνý㼰ڽ·Ļ.νһʱûлνDirect-HelloΪýڽ·ʧ.ν㽫ɢ·ʧܵϢν㣬ֱнôϢ.νҲͨԵRouted-Hello龭·֪ͨӦν·ĻԣνںܳһʱûлνRouted-HelloΪ֮·ʧܣҪ¼ѡ·ɣӿ֪ͨ.ͼ1ġa,b·ʧܣbûյDirect-HelloΪaa,bʧܣ֪ͨ̽ef/d/c/aҲϢ.Routed-HelloaսϤa,b·ʧ.b/c/e/fγɻ·Ϊĳ·޷γɻ·.¼㽫ֲڽӷ֣ĳõµ·ɣݸֱϢȶ.
4·
4.1·
ڽӷԺÿܹڽϢԼص·ɶҪڽϢ·.A=(ai,j)n,nͼG=(V,E)ڽӾ󣬵ҽai,j=1i,jEai,j=0nڡV.(A)n,n[A]i,jֱʾnnľ(i,j)Ԫ.ڽӷֺÿ㶼ܶԡi,jEؽж.
ai,k=1ak,j=1Ȼڴij·(ikڽkjڽ)ijľΪ2.kȡ1n֮һʶ=bi,jҽbi,jkʹai,k=1ak,j=1.B=A.A=(bi,j)n,n=()n,nBԪbi,jʾӽijbi,jΪ2·.(B)=(di,j)n,ndi,j=bi,ji=jdi,j=0(B)ΪBĶԽǾ.ai,i=0di,i>0ʾdi,ikʹai,k=1ak,i=1. 2A=B-(B)=A.A-D(A.A)2Ai,j=1ijľΪ2.
߽׵kAҪAk-1Aĳ˻ɾȥԽԪرʾԻ⣬Ӧ[A]i,m[k-1A]m,jɵĲԻ[k-1A]m,j Ӧ·ѴԽi.k-1A泤Ϊk-1·ԽĽ㼯k-1Vi,j.kAɶΪ



֤[kA]i,jʾӽij[kA]i,jΪk·ҲԻ(abeda)ͲԻ(efcbed).
2. (·)kAͼG=(V,E)ڽӾAɵľΪk·.
֤. (ʹökѧɷ)
(1) k=1Ȼ.
(k0) k=k0ʱk0AͼG=(V,E)ڽӾAɵľΪk0·.
(k0+1) k=k0+1ʱk0+1A壬(i,m,j)=1k0+1A=A.k0A-(A.k0A),[A.k0A]i,j=[k0A]k,jǴӽkj[k0A]k,jΪk0ļ·.[A]i,k=1ӽikj[k0A]k,jΪk0+1·.kȡ1nһʶǴӽiпܽkjľΪk0+1·.k0+1A=A.k0A-(A.k0A)ȥܵԻ(i,m,j)=0ɾȥܴڵĲԻ.ԭ۳.
֤.
2. kAͼG=(V,E) ·Ҵi,jʹ[kA]i,j0kn.
֤. ʹ÷֤k=nҴi,jʹ[kA]i,j0ĳ·Խn+1.
ͼGĽV=nȻ·Խ1㳬1Σì.
4.2·
ͨ·󣬾ܻüRv1v2Rv2v1ٸLv1v2v1=Rv1v2Rv2v1Ϳɻôv1v2صv1Ļ·ϣСRv1v=[A]v1,v2+[2A]v1,v2++[nA]v1,v2Rv2v1=[A]v2,v1+[2A]v2,v1++[nA]v2,v1Lv1v2v1=[A]v1,v2+[2A]v1,v2++[nA]v1,v2)([A]v2,v1++[nA]v2,v1).ҲѡRv1v2Rv2v1һ·Ϳɹһv1v2صv1Ļ·Ҫָǣÿ·δԽͬһ㣬ɵĻ·ͿܴԽĳض·2ΣҲǿܴԽ·˽.
5ʵ
ͼ1UDL磬ڽӾ·ֱΪ
