搜索
QoS1,2,1,1(11,100871;21,):QoS.QoS,,,.QoS;,;,.:;;QoS;:TP393103:A:037222112(2004)1222046205AnAnycastRoutingAlgorithmSupportingQoSforServiceDataZHANGLi1,JIAWei2jia2,YANWei1,LIXiao2ming1(11DepartmentofComputerScience&Technology,PekingUniversity,Beijing100871,China;21DepartmentofComputerEngineering&InformationTechnology,CityUniversityofHongKong,HongKong,China)Abstract:AnAnycastRoutingalgorithmsupportingQoSforServiceData(ARSD)isproposed.ARSDpre2computespathforanycastdestinationbythereversepathbandwidth,hopnumberandserverload.Thepathpre2computedcanfulfilltheQoSrequirementsofdatagramtransmittedonthepathreversedirectionandtheloadofserveronthepathendisnotworse.ARSDroutesanycastdata2gramalongthepathandresourceisreservedfortheservicedatarequestedbytheanycastdatagramatthesametime.WithARSD,re2sourcereservationforservicedatarequestedbyancyastdatagramcanbeaccomplishedwithoutunicastQoSroutingprotocols.Thesim2ulationresultshowsthatARSDcanimprovethebandwidthreservationrequestacceptanceratioofservicedatarequestedbyanycastdatagram,andbalancetheserverloadtosomeextentwithlittletransmitdelayofanycastdatagram.ThemessageoverheadandsetuptimeofresourcereservationcanbereducedwithARSD,too.Keywords:anycastrouting;servicedata;QoS;serverload1,IP[1,2]..,()(),.,,.,,.,.,,..().,.,.,,.,QoS,,[37].:,,(,),.:2003210227;:2004206216:(No.60273002)12200412ACTAELECTRONICASINICAVol.32No.12Dec.2004©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.,.,,,.,QoS,ARSD.QoS,,,.QoS,,,,.2211(V,E),V,.E,.u,vV,lu,vEuv,Bu,v,.AV,A.PaA,vpa,0FpaF1.paa.,ARSD,.k,BW[q]q(1,,k).ARSD,q(1,,k),A,nARSD,,SuccA,n[q].q(1,,k),ARSDP=(v1,v2,,vn),,vnA,minj=2,,n(Bvj,vj-1)EBW[q],pvn-miniD(pi)FpdD={vc|vcA&&(vP=(v1,,vc),minj=2,,c(Bvj,vj-1)EBW[q])}BW[q],BW[q],pd.pd.,,.,ARSD,.AR2SD.,ARSD.pd,,.,,ARSDP,.,ARSD.21221211ARSDn:(1)N;(2)q(1,,k),niNASA,i[q].SA,i[q]=(bwA,i[q],hA,i[q],pA,i[q])bwA,i[q]niAq;hA,i[q];pA,i[q];(3)A,SuccA,n[q],A;SbwA,n[q],;ShA,n[q],;SpA,n[q],.n:(1)q(1,,k),A,PiN,SA,i[q]SA[q].(2)q(1,,k),pA,min[q]:pA,min[q]=miniNpA,i[q](3)SA[q]SA,i[q],pA,i-pA,min[q]pdbwA,i[q]=0(4)SA[q],SuccA,n[q]=jSbwA,n[q]=bwA,j[q]SbhA,n[q]=hA,j[q]SpA,n[q]=hA,j[q]jhA,j[q]=hA,min[q]bwA,j[q]=maxhA,l[q]=hA,min[q](bwA,l[q]),hA,min[q]=minsA,l[q]SA[q](hA,l[q])j,,;(5)SA[q]=,SuccA,n[q]=nullSbwA,n[q]=0ShA,n[q]=SpA,n[q]=121212ARSDARSD,,.,(V,E),u,vV,lu,vEBu,v,.(n),lA,n,BA,n.740212:QoS©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.1,PA,n.,,1.,,.,BD,PBPD,A.nA:(1)q(1,,k),(V,E)lu,v,Bu,vBW[q],nG[q];(2)lA,iG[q],pA,min[q]pA,min[q]=minpA,i[q];(3)G[q]lA,i,pA,i-pA,min[q]pdpd;(4),DijkstraAn,nA.,.21321311ARSDnisA,i[q],inAq(1,,k).sA,i[q]=(bwA,i[q],hA,i[q],pA,i[q]),hA,i[q]=ShA,n[q]+1pA,i[q]=SpA,n[q]Bn,iBW[q],bwA,i[q]=0bwA,i[q]=min(SbwA,n,Bn,i)21312ARSDARSD..(,).,....,..,,.,,.214ARSD,,..,.,,.QoS,Path,RSVP[8].,RSVP.3311ARSD,,,,..,..ARSD...,.ARSD..:,.:.,.,pd.(1):..(2):...(3):..:,,84022004©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.;,,;,,,,.,pd,.pd,.pd.pd.312Arpanet[9].10Mbps,10ms.,..45,.,,...ARSD,,.pd016.ARSD,,.:,,QoS.,.,.,QoS.ARSDQoS,QoS.,ARSD,[10].,,.QoS,,QoS.:,.ARSD,QR:.,QoS.2.ARSDQR.ARSDQoS.ARSD.,;,.ARSD,QR,,.,,QRARSD.3.ARSDQR.ARSD,.ARSD,,,.,ARSDQR.4,.ARSDQR,ARSD.4,QoS.,QoS.,,QoSARSD.ARSD;,ARSD.:[1]PartridgeC,MendezT,MillikenW.HostAnycastingService[Z].RFC1546,1993.[2]JohnsonD,DeeringS.ReservedIpv6SubnentAnycastAddresses[Z].RFC2526,1999.[3]KatabiD,WroclawskiJ.AframeworkforscalableglobalIP2anycast(GIA)[A].ACMSIGCOMMComputerCommunicationReview[C].NewYork,NY,USA:ACMPress,2000.3-15.[4]XuanD,JiaW,ZhaoW,ZhuH.Aroutingprotocolforanycastmes2940212:QoS©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.sages[J].IEEETransactionsonParallesandDistributiedSystems,2000,11(6):571-588.[5]XuanD,JiaW.DistributedadmissioncontrolforanycastflowswithQoSrequirements[A].IEEEInternationalConferenceonDistributedComputingSystems[C].Mesa,AZ:IEEE,2001.292-300.[6]WANGJX,CHENSQ.AnycastservicemodelanditsQoSroutingal2gorithm[J].JCENTSOUTHUNIVTECHNOL.2001,8(2):135-139.[7]FangH,ZeguraEW,AmmarMH.QoSroutingforanycastcommuni2cations:motivationandanarchitectureforDiffServnetworks[J].IEEECommunicationsMagazine,2002,40(6):48-56.[8]BradenR(Ed.),ZhangL,BersonS,HerzogS,JaminS.ResourceReSerVationProtocol(RSVP),Version1,FunctionalSpecification[Z].RFC2205,September1997.[9]ParsaM,Garcia2Luna2AcevesJJ.Aprotocolforscalableloop2freemul2ticastrouting[J].SelectedAreasinCommunications.IEEEJSelectedAreasinComm.,1997,15(3):316-331.[10],,.AnycastIP[J].,2003,40(6):784-790.:,1973,anycast.,19571110,,,.05022004©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.