ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



һڵ··㷨*
 ơ񷢡µл 
ժҪ۸ֻսܽǷ͵ĸߴ,Ƿ.,ǵֽ·ǵ·.е·ЭҪÿ·˫·,ܴ·.һЩѧá.ǣַҪ֪һӽߵ·վġ,Ӧ˽ṹĶ̬仯.һֶ̬·㷨,ھе·磬Ӧ˽ṹĶ̬仯.
ؼʡ·,,·㷨,,ͨ.
ͼšTP393

A Routing Algorithm for Network with Unidirectional Links
HUANG HaoWU Li-faCHEN Dao-xuXIE LiSUN Zhong-xiu
(State Key Laboratory for Novel Software Technology 
Nanjing University Nanjing 210093)
(Department of Computer Science and Technology Nanjing University Nanjing 210093)
Abstract An inexpensive satellite receiver can receive high bandwidth traffic from a satellite, while no bandwidth from the receiver to the satellite is provided. Therefore the connection between the satellite and the satellite receiver is unidirectional. The existing routing protocols stand on the fact that any links are bi-directional. They can not handle unidirectional links. Some scholars use a tunneling method to solve this problem, but the tunneling method needs a fixed back channel from satellite receiver to the satellite uplink station. It can not adapt to dynamic topology change. In this paper, the authors propose a dynamic routing algorithm that can be applied to networks with unidirectional links. The routing algorithm can also adapt to the change of network topology. 
Key wordsUnidirectional link, unidirectional network, routing algorithm, distance vector, satellite communication.
ĿǰInternetϵ·Э(routing protocol)һٶһ·֮·˫.ܴվAվB,ҲһܴվBվA.Ȼ˵(unidirectional)ǶԳ(asymmetric)·.ͨϵͳݴʡվĴСԴƶԷܴ.,İСֳֵϵͳԽպͷÿ뼸KλݣҲֱΪ׵Ľߵĵվ,Խպͷÿ뼸λ.DBSϵͳ1ڹܺƶԷһ.DBSϵͳ,վռϢ,Ȼ͸㲥,ɹ㲥ǲص.DBSϵͳ,ڶԵͬ,ܸǺܴ,ʹƼ򻯣ȥ˸ٵȷ.վֻмʮ,ĵ,ƶͰװ,ֻܽ,Ƿ.ʹ·Ϊ·.ͼ11һе·DBSϵͳ.

ͼ1DBSϵͳ
ǰе·Э(RIP2,OSPF3,MOSPF4,BGP5,IGMP6ݵ)һٶÿ·˫·.ԭеĻ˫··Эھе·н.Ϊ˽ڷٷչͨƶ߼ͨе·,һЩѧ߿ʼǹµھе·е·Э.IETF(internet engineering task force)һUDLR(unidirectional linkrouting),һЩĽķ.H.Izumiyama7ݸһáһ·ģ˫·ķ,ַҪ·Ľ߼·ߵIPַ,·ĽҪ߷ͱʱ,˱ĴIP,ߵIPַͳȥ.ַ˶̬仯.ף810ݸ˶е·Э,RIP,DVMP,OSPFȽ޸Ӧھе·ķ.ЩҪ·Ľ֪һ̶Ĵߵ·һľе·.T.Ernst11ݸһֻͼ··㷨.ַú鷺ķҵɱ·,·ϵһ㶼֪·,·ֹʱҲҪѡ鷺ķ֪ͨ.
ĸһֿھе··㷨.ڴе·,Ӧ˵ı仯,֪·Ľߵķߵһ.Ҳе·㷨,뵥·ڵĽԲıԭе·Э.
1 ·ĸ
Ϊȷ,ǸڱҪõͷ.һ·ֻع̶һݶ෴ķ,ƴ·Ϊ·,Ϊ˫·.·ȫ·ǵ·Ϊ,Ϊ˫.һ·ڵ·Ϊ,Ϊ˫.һ·,õ·ļβΪ,ͷΪӽ.
ȣǽһͼ.ʾ·,ʾ·,ϵȨʾ(ʱӻõ).ڱгֱʾͼΪͼ.ΪڼУͨŵһ㶼ҪϢ,ҲҪ໥ɴ,Բٶ۵ͼǿͨ.
ǽͼеĽֳ:һ˫,һǵ.һ,һ·Ϊβ,Ϊ.㷨ÿ϶ά.ÿ(node,distance,next-hop)Ԫ.Ԫе3ֱΪ򡢾ʹν.eĳϾеԪ,Ƿֱnode(e),dist(e)next(e)ʾԪeĽ򡢾ʹν.һΪ,һΪ.XϵĵΪIN(X),ΪOUT(X).(F,3,G)ǽAάĵ,ʾFAһ3·,·ϣF,FڵһΪG.(K,4,B)ǽAάĳеһԪ,ʾAKһ4·,·ϣA,AڵһΪB.ݱϵĳάԼ·ɱ.
ĸ·㷨ͨڽ㽻ȽϾάԼľ.ΪˣǸͬԪ֮Ĺϵĸ.G=(V,E,W)һȨͼ,ʾһҪ۵ĵ.(X,Y)E,XYĸ,(S,n,N)IN(X),(Q,m,M)IN(Y),(S,n,N)OUT(X),(Q,m,M)OUT(Y),S=Q,(Q,m,M)XϵԪ(S,n,N)ӦԪ.(X,Y)E,(S,n,N)IN(X),(S,m,M)IN(Y),n+1m,(S,n,N)ڻȼY϶ӦԪ(S,n,M).(X,Y)E,(T,n,N)OUT(X),(T,m,M)OUT(Y),m+1n,YϵԪ(T,m,M)ڻȼX϶ӦԪ(T,n,N).Ϊ,ǵ㷨УٶÿȨΪ1.ĿǰҪֵ:
(1) ˫,Щ˫ǱһЩ·,ĳΪ˫絺Ⱥͼ2ʾ.ͼвͷ߶αʾ෴Ļ.A1A7,B1B2,C1C23˫絺.

ͼ2˫Ⱥ
(2) ÿ·ǵ·,Ϊ磬ͼ3ʾ.

ͼ3
2 ·㷨
2.1 ·㷨
㷨1. Ľ.
(1) ӽ㷢Լĵ.
(2) յXĵʱ,ؽĵ޽ΪXԪ,(X,1,ؽ),ʱ;޸Ϊ(X,1,ؽ),ʱ.
(3) յĵʱ,ÿһԪ鶼ڱؽǷӦԪ.,ֵ1صĵ,ʱ.,򵱸ԪڻȼڱؽԪʱ,Ԫľֵ1ȡؽжӦԪ,ʱ.
(4) ڼ鵽еԪ,Ǽʱֵ1,ЩʱֵֵԪ鶼ɾ.
(5) ĵаԪ,ܴӸĵҵ㵽·,ͨԴ·ʽ򸸽㷢Լĳ.
(4)һʱ,ʹ˵ı仯Ѿڵ·ɾ֮µ·.13Ϊͼ3ʾнI,D,Aϵĵ.ͼ4ǸAϵĵĸ㵽A·.
1Iĵ

NodeDist.Next
D11
G11
C2D
E2D
F2G
H2G
J3H
B3C
A4B
K4B


2Dĵ

NodeDist.Next
C1D
E1D
B2C
A3B
K3B
I4A
G5I
F6C
H6G
J7H


3Aĵ

NodeDist.Next
D1A
I1A
C2D
E2D
G2I
F3G
H3G
B3C
J4H
K4B


ͼ4Aĵ·
(5)Ǹݸĵܹһ·,ǽڵ3.1ڸ֤.ͼ3ʾΪ˵,мٶÿȨ()Ϊ1.AյDĵ(2)ʱ,ֱؽADľΪ3,Ӷ֪ADĳΪ3·AX1X2D.ңӱ2пԿAD·ϵ2ΪB(ΪԪ(A,3,B),BAڸ·ϵڽ),X1=B;3ΪC(ΪԪ(B,2,C)),X2=C;4ΪD(ΪԪ(B,2,C)).Ӷ֪AD·ΪABCD.
㷨2. Ľ.
(1) ÿյĵʱ,ܴҵӱ㵽·,ͨԴ·ʽ򸸽㷢Լĳ.
(2) յӽXĳʱ,ؽĳ޽ΪXԪ,(X,1,X),ʱ;򣬽޸Ϊ(X,1,X),ʱ.
(3) յӽĳʱ,ÿһԪ鶼ڱؽǷӦԪ.ޣֵ1νΪӽصĵ,ʱ.,ӽԪڻȼڱؽԪʱ,ӽԪľֵ1νΪӽȡؽжӦԪ,ʱ.
(4) ڼеԪ,ǵļʱ1ЩʱֵֵԪ鶼ɾ.
һ·ʧЧʱ,Ӧӽ·ļͷڹ涨ʱղӦĸ··Ϣ,ӶʹԭľеĳЩԪʱɾ,ȡ֮Ǹľ½ӦµԪ.ͼ3ʾ·DIֹʱΪ,˵AIľвԪؽĹ.
DI·ֹʱ,IյDĶڵľϢ.Iԭĵ,˸ݴD͵ľԪ(D,1,I),(C,2,D),(E,2,D),ԭGľֻƳ(E,3,F),(C,4,E),(D,7,A)ȣ˱.ʱ,ΪIڹ涨ʱδյDĶڸϢ,еԪ(D,1,L),(C,2,D),(E,2,D)ʱɾ,ȡ֮ǸݴGĵйؽD,C,EȵԪ.ܿ,Iµĵ,4ʾ.
4I·DIʱĵ

NodeDist.Next
G1I
F2G
H2G
J3F
E3H
C4E
B5C
A6B
K6B
D7A


2.2 ˫Ⱥ·㷨
˫ȺĽṹ,֮ĵ·ӸĹؼ·.ֻҪ֪֮·;,ٽЩ·ϢͨԵڽͿ.Ϊ,Ƚ˫Ⱥ˽ṹһ򵥵ı任:ÿֻ;ڵ֮䶼÷෴·,Ϊԭ̾;ԭ֮·벻.,ͼ2ʾ˫Ⱥ任ͼ5ʾ.ǽ·ɹֳ:뵺˫֮·Ϣ(ԭõ·Э)Ⱥеĵ֮·Ϣ.һڵеμͬһĿͨ,ʹеĵڴִ·㷨1㷨2һ.,һЩ·˫Ⱥеĵ·,Щ·,·ϢĴݷ.һЩ·ԭ˫Ⱥв(֮һ·),Щ·,ϢõڵĶĿͨŵķʽ.˰·ӿڴϢ֮,ҪöĿͨŵķڵĵ㴫·Ϣ.㷨1㷨2޸ĺֱΪ㷨3㷨4.ڵ˫ַܽϢ͸:һǽڵһΪĬ·,Ŀַڵ͸Ĭ·;һǵڵ㽫ԼĳͨڵĽ. 

ͼ5
㷨3. Ľ.
(1) ӽ͵·Ϣ鷢Լĵ.
(2)(3)(5)(7)ֱͬ㷨1(2)(5).
(4) յǸĵڵ·Ϣĵʱ,ȷ䷢(ΪX)ؽľ(Ϊs);ÿһԪ鶼ڱؽǷӦԪ,ޣֵsصĵ,ʱ.,յľеԪΪ(Z,t,Y),֮ӦԪΪ(Z,u,W),t+su,(Z,t+s,Y)ȡصеԪ(Z,u,W),ʱ.
(6) ˫ȺаԴ·ݳʱ,Դ·ֻ.Դ·ڵĽ(ͼ2еA1A3)ͬһ,ڲֱ,ǰһ(A1)ӦԼĳ,Լһڱڵ·(A1A2A3)Դ·Լһ֮,ʹ֮˫㶼ܴ.
㷨4. Ľ.
(1)(3)(5)ֱͬ㷨2(1)(4).
(4) Ǵӵ·Ϣ,ȷ䷢(ΪX)ؽľ(Ϊs),յĳеԪΪ(Z,t,Y),֮ӦıصԪΪ(Z,u,W),t+su,(Z,t+s,X)ȡصеԪ(Z,u,W),ʱ.
3 㷨ܷ
3.1 㷨
1. X,Yͼе,ҴڴYX·,eIN(X),ʹnode(e)=Y.
֤:Ȼ,֤.
2. X,Yͼе,XYĸ,ҴYX·,YҵYX·.
֤:ѧɷ.ΪXYĸ,XᶨڵY͵IN(X),YܻøXµĵ.ΪYX·,1,شeIN(X),ʹnode(e)=Y.dist(e)=1,YȻ֪YXĸ,Կ֪Լ·.ɼ裬eIN(X),node(e)=Q,dist(e)=kʱ,Y֪ܵQX·.֤eIN(X),node(e)=Y,dist(e)=k+1ʱ,Y֪ԼX·.next(e)=Z,Ԫ֪fIN(X),node(f)=Z,dist(f)=k.ɹɼٶYԵ֪ZX·,ΪZA1A2...Ak-1X,YԽһ֪YX·ΪYZA1A2...Ak-1X.
3. ͼX,Y˫ɴ,eOUT(X)ʹnode(e)=Y;fOUT(Y)ʹnode(f)=X.
֤:XY֮һ·XA1A2...AnY,YX֮һ·YB1B2...BnX.Y丸An֮·.1,sIN(An)ʹnode(s)=Y; 2,Y֪YAn·.㷨2,YԼĳ͸An,AnԼĳмԪ(Y,1,Y),t1OUT(An),ʹnode(t1)=Y.ͬ,AnҲ֪An-1·,ԼİԪ(Y,1,Y)ĳ͸An-1,,شt2OUT(An-1),ʹnode(t2)=Y,An-1֪Y·.,X֪XA1,A2,...,An,Y·,eOUT(X)ʹnode(e)=Y.ͬ,֤fOUT(Y)ʹnode(f)=X.
3.2 㷨ģʵ
3.2.1 ģ
CPCģķʵ·㷨1㷨2.ͨͼ3ʾĵһЩʵ飬㶼ȷؽ.·ʧϢ·ָϢʹľõȷ.
3.2.2 ˫Ⱥģ
ͼ1˹(Hughes)˾ʵֵһϢֲٷֲԭϵͳ1ݵʾͼ.ϵͳ,һŵͬͨǺInternetϵһ̶վΪǵվ(uplink center);ֲڲͬɴǽߺͽսֻǷݵ΢ƶվ;ƶվͨ͹ǵ绰ϵͳѵ绰ϵͳõ绰InternetʵIAP(internet access point).ƶվװֻյվ,Խʡķ.ǰԭϵͳͼ2ʾ˫Ⱥ.A1ǵվ;B1,C1վ,ֻǵ·.A2A3IAP.B2C2ͨ˫·ֱB1C1.ͼ2ʾ,ڸRIPOSPF㷨,A1ΪĬϵ·.ÿ϶ܵõȷľ.ģʵ·㷨ڴϺ˫Ⱥȫе·㷨.
3.3 㷨ܷȽ
㷨ھе··ɹ,ǿӦ˽ṹ仯Ķ̬·㷨.㷨ÿϴ洢Ҫͳ.洢ԼInternetþƵ·ЭRIP.ΪRIPֻ·һ,㷨Ҫ·.㷨ڽʱ,·ϢԴ·,زκκ鷺,Ĵ͵ķΧС,·ϢҪ.ڡƵķ,㷨Ҫ̶ġ,Ӧ˽ṹı仯.Ѱұ·ƣ11ݵķ,㷨ش洢·,ûϢ.
4  
о˵·,һ͵·㷨.֤ģʵ鶼㷨ǿе.ⷽĹδ,ĹҪ,Ŀ͵·.ЭƶʵֻҪо.
*оõʵǼƻ.
߼顡ƺ,1957,ʿ,ҪоΪ.
,1968,ʿ,ҪоΪ.
µ,1947,,ҪоΪֲʽ벢м.
л,1942,,ʿʦ,ҪоΪֲʽͲд.
,1936,,ʿʦ,йѧԺԺʿ,ҪоΪֲʽϵͳ.
ͨѶϵ:ƺ,Ͼ 210093,Ͼѧѧ뼼ϵ
ߵλϾѧ¼صʵ Ͼ 210093Ͼѧѧ뼼ϵ Ͼ 210093
ο
1Zhang Yong-guang, Dao S. Integrating direct broadcast satellite with wireless local access. In: Proceedings of the 1st International Workshop on Satellite-based Information Services. New York: Rye, 1996. 2429
2Maldin G. RIP version 2 carrying additional information. RFC 1388, January 1993
3Moy J. OSPF version 2. RFC 1583, March 1994
4Moy J. Multicast extensions to OSPF. RFC 1584, March 1994
5Rekhter Y, Li T. A border gateway protocol 4. RFC 1771, March 1995
6Deering S. Host extensions for IP multicasting. RFC 1112, August 1989
7Izumiyama H, Tosaka A. An IP tunneling approach for unidirectional link routing. Internet-Draft, July 1997
8Duros E, Chuitema. Handling of unidirectional links with RIP. Internet-Draft, March 1996
9Duros E, Dabbous W. Handling of unidirectional links with DVMP. Internet-Draft, March 1996
10Duros E. Handling of unidirectional links with OSPF. Internet-Draft, 1996
11Ernst T. Dynamic routing in networks with unidirectional linksMS. Thesis. University of Nice-Sophia-Antipolis, France, 1997
1997-11-20յԭ,1998-06-30յ޸ĸ
