о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.737-744



֧ԴԤĶĿͨŵ·㷨ܷ
ƺơŽɡл
ժҪĿǰInternetϵ·Э֧֡ͷ.͵Ӧ顢ֲʽģҪбϵķ.ԴԤЭRSVPȿṩбϵķҪµ·Э.о֧ԴԤĶĿͨŵ·⣬·㷨.㷨2˱ʹø߸·ĻƣӶʹöĿͨŵͨķɹкܴ.лģʵĽ˷.
ؼʣĿͨţ Ŀͨţ ԴԤ 
ţTP393
MULTIPOINT TO MULTIPOINT COMMUNICATION ROUTING
SCHEME AND PERFORMANCE ANALYSIS
HUANG HaoDU Jian-ChengXIE LiSUN Zhong-Xiu
(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093)
(Department of Computer Science and Technology, Nanjing University, Nanjing 210093)
AbstractThe current routing protocols in the Internet only support best effort service. New applications, such as videoconference and distributed emulation, need guaranteed quality of service. Resource reservation protocols such as RSVP are used to guarantee the quality of service, but they need new routing protocols to cooperate with them. In the paper here, routing algorithms for multipoint to multipoint communication supporting resource reservation are studied. Two routing schemes are proposed. Using the routing algorithm 2, a feasible communication distribution tree can be constructed. Since algorithm 2 adopts the mechanism that avoids using the high load links, more communication distribution tree can be allocated in a network. Simulation results and their analysis are also given.
Key wordsunicast, multipoint-to-multipoint conmmunication, resource reservation, quality of service
1
缼ѳΪӦõĺļ֮һ.Ƿֲʽ㡢ЭͬýӦüԶͨżϢϵͳ̵¼Ļ.
ĿǰInternetṩķҪǡ(best effort)ķ.Ŭ͵ܱ֤.Ϊ㲻ӿֵӦõҪԶƵ顢ֲʽģȣӲ豸¡ͨǵṩ֧⣬Э顢֧.ṩʵʱķϣṩع·ĴԴĿƴʩ1.ԴԤЭ(RSVP)2,3ΪԴṩһƷ.ΪInternet ṩۺҵķ֧ԴԤЭ飬е·Э.
ͨŴϢߺϢߵĸһߺһߵͨţĿͨ.һߺͶԼߺͶߵͨţĿͨ.һЩĿͨЭѾMOSPF3ݣDVMP4.ǽһԷΪ̾.MOSPFDVMPЭ˵ͬһͨж߾ͻὨԷΪͨ.ԡ͡ķ˵ͨ·ϱ·ϢһͨҪһЩ֮⣬ԴЧʷ汾ʵ𲻴.ǣ͡Ѳ㲻ӿֵ͵ͨҪ.ǰһЩӦͨŵУӻ顢ֲʽģҪ֤㹻ʱӺͶʧʶо.ˣͨⲻҪݵǰ˽ṹѰͨ·ͨҪҵ·ͨ㹻Դ.ϵͳͨԴԤȻϷ.һĿͨж.磬ƵмзȨ߾м.ÿһ߶ԤһͨռôԴ.ƵͨзȨͬʱԵǺٵģԤĴԴãҪʹԴͨ޷ʹԴ.
һʱڣԴ޵.Ϊ޵ԴṩܶྡܸߵķоṩԴҲܳôԴ·㷨.ͬĶĿͨŵ·㷨.ΪÿͨԤһùͨͬһͨĳԱͨպͷ.2ڸһЩ.3ڲ㷨.4ڶ㷨ܽ˷Ƚ.
2Ŀͨŵ·
Ϊо·ȽһһȨͼ.ͼ1һϵͳ4.ͼ2ͼ1ʾļĳĸȨͼͼÿڽ֮ӦͬĻ(Ϊ˼ͼ2ÿڽֻ֮һұʾļͷϵȨҲʡ).ͼ1RT1RT12·ԲʾN1N11ǹʵľһֱ߻(N3N6N9)ʾH1MaǾеþαʾ.MaͬһͨAеĳԱ.·ɵĽǶӾеһϵͳеĳ··һ.Դ·ɵĽǶǿԲ־;ен㼯ĳԱλھе.ͼ2еĽ㼯ûлN1N2N3N6N7N11ȾͨAԱMa.ʵϣĳMaĳ·ͼMaڵľ·һ.ɴˣ˼ĳʾ.


ͼ1һϵͳ


ͼ2һϵͳӦͼ
ĳʾо·ʱ˽ṹһȨͼʾ.ڱУøȨͼG=(V,E,C,D)ʾһ磬Vǽļϣһ·һEǻļϣȨCERǻļEʵRĺeE,  C(e) ʾ·eϵĿõԴ(ܵĿõĴ)ȨDERǻļEʵRĺeE,  D(e) ʾľ·eʱĳ(ƽʱ).
ڼͨⰴշߺͽߵֿԷֳ.Ŀͨţһߺһ.Ŀͨţһ()ߺͶ.Ŀͨŵ·ҪѰһӷߵߵ·.μһĿͨŵķߺͽȫΪĿͨ.һĿͨʹһDIPַ.Ŀͨŵ·ҪѰһĿͨгԱһΪͨ.ͬĶĿͨŵ·㷨첻ͬͨ.ĿǰҪ.һĿͨ鹲ͨ.һԷΪͨжߣжͨ.ÿ··ɱһͨһ.һ·ͨ·ɱеһʾԼĳĿͨͨϵһ.·ݱĵĿַ(ĿͨǽߵĵַĿַͨ)Լ·ɱӦȷĸӿ(ĿͨһӿڣĿͨſǶӿ)ת.·ЭҪ涨·֮佻·Ϣķʽռ·Ϣ·㷨һĿַӦЩӿת·ɱ.
Ϊ㷨ȶԱнҪõļһЩ˵.
һĿͨţһһߺͶ.ڿӻĶĿͨʱҪĿͨҪϵĴ.ȨͼG=(V,E,C,D)һĳ(S,T,f)ʾһͨSVTVfΪһSΪͨķ߼TΪͨĽ߼.fΪͨͨĿͨҪϵĴf̶ǽһ.GϵͨȫΪT(G).STΪ㼯ʱ|S|=1|T|=1ʱͨͳΪĿͨ(unicast); |S|1|T|1ʱͨͳΪĿͨ(multicast).
ȨͼG=(V,E,C,D)һĳaiVi=1,2,,ks,tV,ʹ(s,a1)E(ak,t)E(ai,ai+1)Ei=1,2, ,k-1.st·s(s,a1)a1(a1,a2)a2ak (ak,t)Ϊp(s,t)stĲͬ·ȫΪ(s,t). һͼGV(G)ʾͼGĽļϣE(G)ʾͼGıߵļ.s,tVst̾Ϊd(s,t) (ڱоd(s,t)ǰȨD)TGһd(s,T)=min{d(s,t) |tT }Ϊ㵽Tľ룬p(s,T)=arg min{d(s,t) | p(s,t)P(s,t), tT}ΪsTһ··Ϊ˷żҲp(s,T)ʾ·бߵļ.
ΪһͨԤһͨʱҪڼĳͼѡһߵļϣߵļÿӦ·ԤͨĴ.ȨͼG=(V,E,C,D)һĳq=(S,T,f)ΪһͨDTEsStTp(s,t)P(s,t)ʹE(p(s,t))DTDTΪͨq=(S,T,f)һͨ.DT(q)ʾͨqͨļ.Ҳ˵ͨqһͨһðͨqзߺнߵһ.
1. ȨͼG=(V,E,C,D)һĳq=(S,T,f)ΪһͨΪСԴͨ.R*DT(q)ҶRDT(q)㣬R*ΪͨqСԴͨ.
G=(V,E,D)һȨͼSVTGSV(T)GT,V(T)STΪGйSSteiner.(V,S,E,D)ʾSteiner.
ڵĿͨ˵СԴͨ·.ڶĿͨ˵СԴͨSteiner.
֧ԴԤ·ЭУΪһͨѡͨʱҪͨҪеͨԱҪͨÿǷԴԤ.ͨÿǷԴԤϵͳڵĵǰĸ״̬й.ȨͼG=(V,E,C,
D)һĳøȨͼS=(V,E,F)ʾGһ״̬FEʵRӳ䣬eEF(e)ʾǰ·eϵĿô.S(G)ʾGе״̬ļ.S=(V,E,F)Gһ״̬q=(S,T,f)һͨDTDT(q)ͨqһͨmin{F(e)|eDT}fDT״̬SͨqĿͨһĿͨеÿһߵʣôڸͨҪĴ.ӳPS(G)T(G)2EΪGһ·㷨2EΪEӼļϣšǵѿҲ˵һ·㷨Ǹĵǰ״̬һͨѡһͨķ.
ȨͼG=(V,E,C,D)һĳPΪGһ·㷨 qi=(Si,Ti,fi)i=1,2,,nһͨУΪQs0=(V,E,F0)Ƿq1֮ǰ״̬p(si-1,qi)״̬si-1=(V,E,Fi-1)qiĿͨep(si-1, qi-1)ʱFi(e)=Fi-1(e)-fiep(si-1,qi)ʱFi(e)=Fi-1(e)Si=(E,V,Fi)qi+1ֹͣ䣬iΪ״̬s0·Qq1,q2, qn״ʧʱ̣Ϊt(s0, q1,q2,  qn)t(s0,Q).
2. ĳһ״̬£󵽴ͨһģt(s0,Q)һ.t(s0,Q)ѧӳһͨʱ״ʧʱƽֵ.ϣҵһ·㷨P*,ʹ״ʧʱѧﵽ
E(t*(s0,Q))=max{E(t(s0,Q))|PG·㷨}
E(X)ʾXѧ.
3Ŀͨŵ·㷨
ȨͼG=(V, E, C, D)һĳ󣬱о (S, S, f)͵ͨ·㷨.ͨSеÿԱǷǽ.Ǹ·㷨ķһͨģʵȽǵܣ״ʧʱѧ.
3.1㷨1
q=(S, S, f)G=(V,E,C,D)һͨ.RSteiner(V,S,E,D)һ.ȻRͨqռԴٵͨ.źһSteinerһNP6.һֻʽƽ.Steiner(V,S,E,D)ĿǰSteinerʽ㷨Ҫ.һǴT={{w},}ʼwS𲽽TеĻ(SеĽ)T·T.һǴGͼT={S,}ʼ𲽽Tͬͨͼ·T.ZoptʾSteinerȨ(еĻȨܺ)Zʾʽ㷨õĽƽȨ.Steinerʽ㷨ļ±ֵZ/Zopt2(1-|S|/|V|).ͳƽ㷨ıֵ(Z-Zopt)/ZoptС10%6.㷨1㷨2ͳƽֵ(Z-Zopt)/ZoptС3%.·㷨ʱҪͨռõԴҪ٣ҪЭƵ⣬ʹô͵·ϢҪ٣Ҫ٣㷨ʵֲӦĿͨԱĶ̬仯.ĿЭʵֵغµĻSteiner·㷨.
㷨1.
 ǸȨͼQ=(V,E,D).㼯S̾.
 ҳSоС㣬Ϊs1s2DT={s1,s2 }.
 S\DT=ֹͣ;ת.
 S\DTеDT̵ĵs*=arg min{d(s,DT) |sS\DT }, DT=DTp(s*,DT)S=S
\{s*},ת.
3.2㷨2
Ϊʹͨõ䣬һͨͨʱ,ӦЩʣٵ·.ԴŵҪ.Ϊʹ¾ܶͨͨͼ۵Żͨͨ.
ʵѡһM·eEʣF(e)MʱΪ·eEǵ͸ص·Ϊ·eEǸ߸ص·.fΪͨF(e)Mʱ(e)=0MF(e)fʱ(e)=1f>F(e)ʱ(e)=.⣺
(1)


DT (q)ͨqеĿеͨ.
1ͨͨʱڰԱS ѡ߸·ٵȻЩѡȨС.
ֱ1ǳ.ΪȽ任һ.㷨1УʱõͼG=(V,E,C,D)еȨD.ǸȨD״̬µȨD䣬Ȼ1任2Ȼ.ͨq=(S, S, f)ʱ״̬Ϊ(V, E, F)ʵѡִN1<N2.F(e)>MʱD(e)=D(e) MF(e)fʱD(e)=N1f>F(e)ʱ, D(e)=N2.
(2)
֤ʵѡN1N212ǵȼ۵.
㷨2. SteinerĶĿͨ(S,S,f)ļӵ·㷨
 캯D估ȨͼQ=(V,E,D).
 㸳ȨͼQ=(V,E,D)Ľ㼯S̾.
 ҳSоС㣬Ϊs1s2DT={s1, s2}k=2.
 S\DT=ֹͣת.
 S\DTеDT̵ĵs=arg min{d(s,DT)|s(S\DT}, DT=DTp(s,DT)S=S\{s},ת.
3.3·ϢĴ·ɱĹ޸
3.3.1·ϢĽ
˽ṹ͸·ϵĸ·ϢǶ̬仯.Ϊ˻õǰ·Ϣе·㷨붨ڵڵĽ㽻·Ϣ.㷨1㷨2Ҫ·Ϣÿ·״̬·ǰĿô.ǿOSPFHello ġDatabase DescriptionġLink State Request ġLink State Update ġLink State Acknowledgment .ǱЩĵ·ĴԴ·Ϣ.
ĿͨͨӦͨݱ.ͨĽ統е·.磬ͼ1ʾϵͳУN1N2N3N6N7N11еıΪMaΪͨAԱͨһͨͼ2е


ʾ.Ϊ˼¼Щ·Ϣÿ·άһĿͨ·ɱеÿһ¼һͨ·Ϣеÿһַתӿڵݣ (ַӿ1ӿn)ַǶĿͨĵַ.һ·յһʱȴӱͷҳַȻٴӶĿͨ·ɱҵַƥ󽫱еÿһӿתȥ.·RT1RT2RT3RT6RT10RT8RT11RT9ַΪAı.RT3Ͼб(A,1,3).RT3ӽӿ1յAıʱӿ3תӽӿ3յAıʱӿ1תӽӿ2յAıʱ.
3.3.2ͨĽ
һеͨеҪʱӵ·ΪѰһͨͨ·.
Ϊ˲ͨĽȾһ.ĿͨAĳԱΪͼ1ΪMaĿǰÿһ·ǵ͸·.N5һ̨ҪĿͨA.N5ӵ·RT5ݵǰ·ϢN5ĿͨAͨ·ΪL N5(N5,RT5)RT5(RT5,RT6)RT6.RT5RT6͡롱Ϣ·Lϵ·յϢԼĶĿ·ɱӶĿͨAı·RT6еĶĿͨAıһRT5N5Ľӿ.ĿͨAͨͳΪTL.ڴ֮N5еͿյĿͨAıĻӶĿͨAͱ.
(1) һ·ҪһͨAʱ㷨1ͨʱ
 һ㲥ϢҪͨAǳΪϢ.
 յϢ·ϢǷӵϢԴĽӿϵǣϢ.Լ·ɱǷͨAƥıޣϢĵӿнӿתУϢ·һشϢԼͨͨһϣϢĽӿнӿת.
 ͡Ϣ·յеġشϢ(üʱƣȴһʱΪܸش·ĻشϢӦյ)ѡһԼĽ(ΪB)B͡Ϣ.յϢ·ϢǷӵϢԴĽӿϵǣϢ.Լ·ɱһַΪAı·ϢĿĽ㣬򵽴BĽӿת.
(2) һ·ҪһͨAʱ㷨2ͨʱ
 һ㲥ϢҪͨAǳΪϢʱ.
 յϢ·ϢǷӵϢԴĽӿϵǣϢ.Լ·ɱǷͨAƥıޣϢĵӿе͸·Ľӿת.УϢ·һشϢԼͨͨһϣϢĵӿе͸·Ľӿת.
 ͡Ϣ·ڶʱʱ֮ǰյһشϢѡһԼķ͡شϢĽ(ΪB)B͡Ϣ.ڶʱʱ֮ǰδյһشϢ㲥һͨϢ.յͨϢλͨϵ·Դ㷢ͨ͡شϢ.յеġͨشϢ֮󣬸ýͨӶԼԼͨ··һ˼ΪB.B͡Ϣ.յϢ·ͬǰ.
4ܷ
4.1ʵĿ
ĸĶĿͨŲͬ·㷨Ӳͬķ濼Ч.㷨1ĿʹÿһڷͨռõԴܵ.㷨2ʹÿһڷͨռõԴܵ٣ҿʹ¾ܶͨ.ͨʵ۲㷨.оָ꣺
(1) ״ηʧʱѷ.һ״̬ʼһ·㷨󵽴һϵֱͨͨմ㷨ܸĳһͨʱѾ䵽ͨͨ.ڴǳƴָΪ״ʧʱFFT(first failure time).
(2) ֱͨ.ֱͨһͨԶľ.ľʾͨŵʱӣֱͨӳ˶Ŀͨŵʱ.
4.2ģʵ鷽
(1) ÿһ׶زһţΪĿͨŵͨԱ.
(2) ·㷨ֱͨͨ.
(3) ¼иߵʣĴֱ¼¸׶״̬.ͨͨ״̬.
(4) ͨĳߵʣΪ0ͨʧ.¼״ͨʧʱѾͨ״ʧʱ.¼ͨƽֱ.һ׶.
4.3ʵ
ѡ˼͵˽ṹΪʵ󣮴ӳʼ״̬ʼһϵжĿͨ񣬹۲ǵ״ʧʱͨƽֱ.ͼ3ʾǽʡ(JSDDN)˽ṹΪ˱ʾͼཻǽƸλ˸ı䣩.ͼ4ʾAPARNET˽ṹ.ͼ51010100mesh.4416meshͼ5ƣȥʾͼ.4ͬϽģʵ.еÿߵĳʼΪ4λͨÿռõĴΪ1λ.ÿݶ100εʵƽֵõ.ʵIBM RS6000վϽ.


ͼ3JSDDN


ͼ4ARPANET˽ṹ


ͼ5mesh
ͼ6JSDDNARPANET16mesh100mesh4ͬоģʵõ״ʧʱƽֵ.ͼ74ͬоģʵõƽֱ.


ͼ6ƽ״ʧʱ


ͼ7ͨͨƽֱ
ͼ6Կ㷨2״ʧʱԱ㷨1ĳ٣Լ5090.Ҳ˵ͬԴ㷨2ɵͨ㷨1Ҫ5090.㷨2ڲñʹʣٵ·ʹ·ӣͼ7ʵԿ㷨ͨƽֱС㷨2ͨŵʱӻûӰ.ͼ6Կmesh״ʧʱԱJSDDNARPANETҪ.ԭmeshĸĶȵƽֵJSDDNARPANETҪ.˽ṹԴʻӰ죬Ķȴͬȵ½ɸͨ.
5ᡡ
˹칲ͨ㷨㷨2ܹͨĿͨŵͨҪ.㷨2ʹø߸·ӶͨԤɹĸ.·㷨ԴԤЭϣ֧Դ̶ķ.ȷ··(̫)ϵķĿȻһ⣬IETFISSLL(integrated service over specific link layer)IEEE802.1跨.ͨŵİȫȨ޵ⱾĻδ漰Ҫһо.
ĿõһоʵǼƻձʡTAO(Telecommunication Advances Organization) Ŀ.
߼飺ƺƣУ19576ʿоڣҪоΪ硢֡ʽ.
ŽɣУ19715ʿоҪоΪб롢.
лУ19425УڣʿʦҪоΪֲʽơ㡢д.㣬У193612йѧԺԺʿ̡ڣʿʦҪоΪֲʽϵͳ.
ߵλƺƣϾѧ¼صʵҡϾ210093
ŽɣϾѧ¼صʵҡϾ210093
лϾѧ¼صʵҡϾ210093
㣨Ͼѧ¼صʵҡϾ210093
ƺƣϾѧѧ뼼ϵϾ210093
ŽɣϾѧѧ뼼ϵϾ210093
лϾѧѧ뼼ϵϾ210093
㣨Ͼѧѧ뼼ϵϾ210093
οף
1Braden R, Clark D, Shanker S. Integrated service in Internet architecture. RFC 1633, 1994
2Braden R, Zhang L, Berson S et al. Resource reservation protocol (RSVP) version 1Functional specification. Internet Draft, http:/ftp.ietf.org/internet-drafts/draft-ietf-rsvp-spec-16.txt/.1997
3ݻƺ,л,.֧ۺҵInternet-ATM缰,о뷢չ,1999,36(1): 814
(HUANG Hao, XIE Li, SUN Zhong-Xiu. Internet-ATM network for integrated service and internetworking. Journal of Computer Research and Development, 1999,36(1): 814)
4Moy J. Multicast extention to OSPF. RFC 1584, 1994
5Pusateri T, Distance vector multicast protocol. Internet Draft, http:/ftp.ietf.org/ internet-drafts/draft-ietf-idmr-dvmrp-v3-04/,1997
6Duin C, VoS. Efficient path and vertex exchange in Steiner tree algorithms. Networks, 1997, 29(2): 89105
ոڣ1998-06-03
޸ڣ1999-03-15
