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



ֲεMulticastַӿ
Ÿ
ժҪMulticastַ̬ӿǶỰеҪ.ڷֲνṹ,Multicastַơӽṹӹϵһּ򵥶ӽ㷨,ǵĹ,ͨģʵȽ3ֵַ䷽ʽ,йʽֲʽEleftheriadisֲηʽ.ֲνṹInternet֯˽ṹһ,ֲεַƽ˼зʽͷֲʽŵ,нϸߵЧ,ӽṹӹϵҲнϸ߿Ч,Ƕнϸߵ³ԡԺ.
ؼʡϵͳ,Multicastַ,ӿ,Ӧ,Multicastͨ,ͼ,Steiner,ݹ㷨,,time-out.
ͼšTP
Hierarchical Multicast Address Management and Connection Control
WANG Jian ZHANG Fu-yan
(Department of Computer Science and Technology Nanjing University 210093)
Abstract Multicast capability at the network layer is necessary in order to reduce the bandwidth requirements of multiparty, multicast applications. Integral to such a capability are multicast address management and multicast routing mechanisms. Multicast address management and connection control are two essential components needing to be solved in the Multipoint applications. Based on hierarchical autonomous structure in accordance with the self-organization topologies of INTERNET, this paper puts forward a multicast address management scheme which sets up the hierarchical partition, which is dynamic, of Multicast address space in order to reduce the blocking probability. Only MAM (multicast address management) in the bottom-layer domain may allocate directly the addresses to multipoint session so that the session acquire the address more rapidly in average. And, a connection control hierarchy (CCH) based on master/slave relationship and a simple efficient building algorithm of multi-point connection are also advanced. The paper also describes the normal operations of multicast address management and multi-point connections controller. With simulation experiment, three of multicast address allocation modes, hierarchical autonomous mode (HAM), central mode (CM) and network-divided mode (NDM) (Eleftheriadis proposed), are compared. The result shows that hierarchical autonomous mode integrates the merits of central mode and network-divided mode, owns high efficiency in the whole. Connection control hierarchy also is efficient in the connection control. They are shown to be highly robust, flexible and scalable.
Key wordsAutonomous system, multicast address management, connection control, multipoint application, multicast communication, graph, sterner tree, recursive algorithm, blocking probability, time-out periods.
Ự붨Multicastַ1.Unicastַͬ,ɶ̬.һMulticastַܷỰ,򽫻.IPĿǰûо³ԺԵĶ̬,ΪỰ,ûԤȽز,Щ谭˶ỰӦúͿ,Ҳû.ỰҪЧĶַ̬.
MulticastЭ,XTP2,ST-II2,MTPRTP2ݵ,ٶһMulticastַĶʵ.Braudes3Multicastַ,ַɷֲMGA(multicast group authority)й,ĿΪĸ,Ľ㽫еĿƸ,мʧЧ߽ͲܽMulticastַ.Eleftheriadis4ķֲMulticastַ䣨network-divided mode,NDMӹ,ûṹϵЧؽỰӳ֮ì,Multicastַռ仮ֲ걸.Pejhan 5ݻĵַ,ʺͻỰӳٴ󽵵,ʵЧӿ,·ɺʹЭ,ķѴԴҲ縺.
㲥Ӧòӿ,û֮ɢ,Ϊʽͨ.ʽָ߽ͨӦ,û֮.ַӦҪ,Ϊʵʱ,Ҫӿ,᷽֮ӽ͹.
ĵ1ڽֲܷṹ.2Multicastַ.3ӿƺtime-out.4Ǽ򵥵Ķӽ㷨.5ʧЧܷ.6ģʵ.ܽ.
1 ֲνṹ
INTERNETɵȫ,ɿɷֲ򹹳,CERNet8,ɸУ,ͨ·INTERNET,CERNetһ,,У԰Ǹһ.Ǹ,֪ӿھͿͨ.ӦһIPAM(IP address manager)һMAM(multicast address manager)CCs(connection controller)һICM(inter-domain connection manager)Լ·ɽ.IPAM¼IPַΧIPַǷڱ.MAMMulticastַ,ÿMAMһMAS(multicast address set).MASǸӼ,ͬMASཻ.ֻеײ(bottom-layer domain,BLD)MAMûMulticastַ,.BLDΡLANISP.ICM̬̬,INTERNETӿ.ֲνṹͼ1ʾ.

ͼ1ֲνṹ
ỰС(minimal magnanimous domain,MMD)н,MMDָС,һBLD,ַBLDû,轨(multipoint connection,MC),MCԽ򲢽BLD.
2 Multicastַ
Eleftheriadis4ݰַMulticastַռ,ַA1.A2.A3,ַΧ224239.A1.A2.A3,ΪA1.A2,ַΧΪ224239.A1.A2.X,X=0,255.ַʽʵּ,һЩ.
*ֲ걸.ַ1ֽڵ涨ûжʹ,ʹôMulticastַ©.
*ַܱʹ.ּ̬ȲܳЧʹõַԴ,ҲûҪ.
İ򻮷ֵַ,ֲ֮仮ֹϵ,MASǶԸMASĻ,Ժ.ֲԻдһо.BLDMAMỰMulticastַ,ϲMAMMASľ̬붯̬.Ԥ趨MAS,ַþʱ,MAMɽֱӹĻĿеַ,Ựʱõַ黹.MAM¼Multicastַʹ,ƵʴԤ,MAMMulticastַ,һѡֱӹĻַȨ.
MulticastַĴ¹̣ͼ2ʾ.

ͼ2ַ
(1) BLDMAMпеַ,֮ת(3);,BLDΪǰ;
(2) MAMõַɹ,֮ת(3);,踸Ϊǰת(2);
(3) BLDѡһCC,Multicastַַ᷽ȴ͸CC;
(4) CCӿƵķֲṹ;
(5) MAMյCCȷϢ,MulticastַȻỰϢ֪ͨû.
3 ӿ
3.1 ӿϵ
CCάỰĶ,״̬Ϣ,Ľ˳.ַӿƷֿ,ֲ,̺ʧЧ³Ի.BLDSCC(secondary connection controller)еֲӿƹʵֲַ,Чش״̬˵ı仯.
MAMڸBLDѡһCC.CCַ,MMDѡһCCΪMCC(master connection controller),MCCںBLDѡSCCMAMѡCCΪSCC,ͽӿƵӽṹ.CCsлỰϢ,ӡỰ״̬ԼMAMַ,ʼձһ.MAMMCCBLDSCCַ.
ӽṹӿƵŵ,(1) ֲνṹһ;(2) ɽϿûỰϢ;(3) ϸߵ³,CCʧЧӰỰвɽϿָ;(4) MCCSCCshop,time-out;(5) ýĶϢ.
ûʱ,BLDڸûỰSCC,SCCӲ֪ͨMCC,,MCCBLDSCC,ȻMCC֪ͨSCC.û˳ʱSCCд,SCCûΪ0,SCCӻỰ˳,ж»Ự,֪ͨMCC.MMDıʱ,ִ: MCC,ʹtime-outø,CCsMAMỰֻС; MMDѡMCC,time-out,ʹCCsMAMĻỰϴ,ʺMMDƵ䶯.԰취ǽ,ʹǰMCC䶯ʱڸ.
3.2 Time-out
Ϊʵϵͳ³,MCCSCCs֮SCCû֮䶨ڽKeep-aliveϢ.MCCϢ,SCCsյϱϢû,SCCsʼռûӦ,MCCӦͼ3ʾ.Ϊͻ,Ϣ.MCCMAM֮ҲڽϢֻƵʽϵ.

ͼ3Time-out
MCCSCCs֮hop,MCC֮hopҲ,ʹRTTcֵ,MCCÿһỰάһRTTcRTTcƽֵͦRTTcRTTcֵ.time-outֵʼΪTi=RTTc+2RTTc,ֵ,Ӧδյ,time-outֵһ.ﵽԤLֵTmaxʱ,ûӦSCCɿʧЧ.ΪCCsMAMʧЧлָ,time-outǱҪ,time-outҲʹСRTTỰֽϵͿͨ.
SCCҲһtime-outcֵ,ڴʱûٴյMCCϢΪMCCʧЧ.ֵΪTLOSTi=min{Tmax,Li=02i(RTTc2RTTc)}.ͬʱ,SCCsӦһtime-outcuֵ,жûǷʧЧ.յMCCϢ,ʱ.ֵΪTui=̡RTTc+2ҡRTTc,ֵ,ûӦδյ,ֵһ.ﵽԤLֵTmaxʱ,ûӦûɿʧЧ.
ΪжSCCǷʧ,ûҲӦһtime-outuֵ,ڴʱûٴյSCCϢΪSCCʧЧ.ֵΪTLOSTui=min{Tmax+Tmax,Li=02i(RTTc+2RTTc)+Li=02i(̡RTTc+2ҡRTTc)}.
4 (MC)㷨
ƵһֱʽỰ,᷽֮ʵʱ,ҪЧؽMC,ӱӦǸЧ͵,ӽ㷨Ӧ򵥿.ڷֲνṹ,һ򵥸ЧMC㷨,ͼ4ʾ.
1. ѰMMD
ѯBLDIPAM,
IPַǷڱ;
,ΪMMD;
,ϼָΪǰ;
while (ǰ򲻰)
{ǰϼָΪǰ;
ѯǰIPAM;}
ǰΪMMD.
MMDΪW0,Ӹ·ɽΪr0.
IF (MMDBLD), THEN RETURN.
2. MC
(1) 㼯ֳӼ,ֱΪA1,A2,...,Ak(0),Ai,AiAj=,ʹAiWi(W0).Wir0ֱ·ɽri,r0ri֮.
(2) ٷֱAiֳӼΪAi1,Ai2,...,Aik(i),Aij,Ai1Aij=,ʹAijWij(Wi).Wijriֱ·ɽrij,ririj֮.
(3) ֱBLD,ͽ˾·ɽĶ.

ͼ4ڷֲṹMC㷨
ѯӦIPAMȷǷ㲢ѯICMԽԼ֮MC.BLDͨǾ,迼MC.
5 ʧЧܷ
5.1 ʧЧ
(1) MCCʧЧ.SCCsԤʱ(time-outc)ûյMCCϢ,MulticastַMAM͡MCCӦϢ,MAM֪ͨͬBLDSCCжMCCַ,MMDѰһCCΪMCC,ỰݿMCC,MCCַȻỰݴSCCs,MCCSCCs֮.MAM⵽MCCʧЧ,ָͬӿ.ѡMCCָ״̬,Ӧ͸,κͨŵĻ.MCCʧЧ,û뿪,ʱҲԼ루¼BLDиûỰSCC.
(2) SCCʧЧ.ûMCCԤʱ䣨time-outûյSCCϢ,MCC͡SCCӦ Ϣ,MCCӦBLDѰһCCΪûỰSCC.
(3) MAMʧЧ.BLDMAMʧЧ,Ự,ΪֻCCsӿ.Multicastַ󽫲Ӧ.MAM𶯺,MAMעᲢѯCC,õش,MAMӦCCΪ,MulticastַMCCַϵ.BLDMAMʧЧӰMulticastַ,ַӦ,,MAMעᲢѯMAM.
5.2 ܷ
ڷֲνṹַ,мдĵ,ҲзֲĽСỰӳ,˼кͷֲ֮.ַMulticastַռ,൱ڼзʽ.ַBLD,ַֻþʱ,ϲ,Ựƽӳٽӽڷֲ.
ֲνṹ,Ϻõؽ˵ַ̬,ʹöӽ׽.ͨѯӦIPAM ICMԺܷؽӦBLD.ӿ,ֲͨṹ֯,ͨݱȫϢ.
ӽṹӿϵнϸ߿Чʺ³.BLDǲͬһЭľ,ûSCC֮ϢǿٸЧ,ӿƵķֲ˿Ч.ӽṹʹöỰڹ򻷾пʵָЧӿ.CCʧЧӰỰĽ,ֻӰֲû,ֻ󲿷CCsʧЧʱŻӰỰ.
6 ģʵ
ͨģʵ,Ƚ3Multicastַ䷽ʽ,йʽcentral mode,CMEleftheriadis4ݵNDMnetwork-divided modeͷֲηʽhierarchical autonomous mode,HAM.
s(0)=r0(0)s(t)=s(t-1)+r0(t).s(t)ģMulticastַ,s(t)a(a1),Multicastַs(t)=0.ͬʱgi=100*r1(t)ģỰʱ.趨һ,3.CMֻһMAM,NDM3MAMֱ3,HAM,3,ÿиMAM.Ϊ򻯶ԻỰʱģ,Χֱ趨Ựʱt1t2t1t2.t1=0.2,t2=0.1.h=3*r2(t),i-1hi(i=1,2,3),ڵi.Ϊ600,ÿ200,õַΪ42,a=1.r0,r1r2.
ÿʵһСʱ,ÿһμжǷеַͻỰֹ,ỰʱΪλ.¼ÿMAMĵַͳɹӵn0ͳɹỰn1,PB=1-n1/n0,ƽỰʱTs,CMΪt1,NDMΪt2,HAMn1нûнõַĿ,ֱΪn2n3,HAMΪ(n2*t1+n3*t2)/n1.ÿַʽֱ6ʵ,ʵ1ͱ2ʾ.PBλΪ%,TsλΪ(s).
ʾ,CMС,ƽỰʱNDMС,ָHAMӽСֵ,ѡʵַ㷨򼸺Сֵ,.
1ʵ

HAMCMNDM
N0N1N1N3N0N1N0N0
13 0113 0083012 7072 8692 8673 0022 987
22 7032 7005402 1603 3003 2982 8812 868
33 3023 2992973 0022 8572 8552 9092 983
42 7302 7271912 5363 3103 3082 9982 986
53 0053 0022402 7622 0052 0042 8882 875
62 7052 7022702 4322 8502 8483 0092 997

N0:,N1:ɹỰ,N2:õַ,N3:ûнõַ
2ʵ

123456A
PBTsPBTsPBTsPBTsPBTsPBTsPBTs
HAM0.10.110.110.120.090.1090.110.1070.10.1080.110.110.1030.117
CM0.070.20.060.20.070.20.060.20.050.20.070.20.0630.2
NDM0.50.10.450.10.550.10.40.10.450.10.40.10.4580.1

PB,TsƽỰʱ,Aƽֵ
7  
ֲνṹINTERNETϵṹΪӽ,ڷֲνṹ,һMulticastֲַͷ,Чؽ͵ַʲƽỰӳ,ֽ˼кͷֲַʽ֮,ǸЧҾ³.СԴﵽINTERNET,Ӱַ,ֻʹӽʱ,ʽȻнϸЧ.ӽṹӿƽ򻷾ỰĹӿֲַ֮ì.ҳ÷ֲνṹ,һ򵥸ЧĶӽ㷨.
ͨѶϵ:Ͼ 210093,Ͼѧѧ뼼ϵ
߼飺,1968,ʿ,,ҪоΪýͨ,CSCW,Ƶ.
Ÿ,1939,ڣʿʦ,ҪоΪý弼,ͼѧ.
ߵλϾѧѧ뼼ϵ Ͼ 210093
E-mail: wangjian@graphics.nju.edu.cn
ο
1 Deering S. Host Extensions for IP Multicasting. RFC1112, Stanford University, 1989
2 Steinmetz R, Nahrstedt K. Multimedia Computing, Communications & Applications. Beijing: Tsinghua University Press, 1997
3 Braudes R, Zabele S. Requirements for Multicast Protocol. RFC1458, TASC, Reading, MA, May 1993
4 Eleftheriadis A, Pejhan S, Anastassiou D. Address management and connection control for multicast communication application. In: Proceedings of the 14th IEEE INFOCOM'95 Conference on Computer Communications. Boston: Computer Society Press, April 1995. 386393
5 Pejhan S, Eleftheriadis A, Anastassiou D. Distributed multicast address management in the global internet. IEEE Journal on Selected Areas in Communications (Special Issue on the Global Internet), 1995,13(8):14451456
1997-12-23յԭ,1998-09-07յ޸ĸ
