SatoshiDoi∗,ShingoAta†,HiroshiKitamura‡,andMasayukiMurata§
∗OsakaUniversity
Email:s-doi@ist.osaka-u.ac.jp†OsakaCityUniversity
Email:ata@info.eng.osaka-cu.ac.jpAbstract—Althoughanycastcommunicationsupportsservice–orientedaddresses,manyofitscurrentdefinitionsinIPv6areunclear.Furthermore,sincetherearenoprotocolstandardsorevenaconsensusoncontrollingrouting,inter–segmentanycastcommunicationsarenotyetavailable.Inthispaper,wefirstreviewIPv6–basedanycastcommunication.Atpresent,thereareseveralpossibleapplicationsthataresuitedtothis.Wethenraiseseveralproblemsandprovidepossiblesolutionstothese.Basedonthisbackground,wepresenttheAnycastAddressResolvingProtocol(AARP)toestablishTCPconnectionswithaspecificanycastaddress,andwethenproposearoutingprotocolforinter–segmentanycasts.Ourproposedarchitecturemakesanycastaddressesmoreusefulwithout(oratmostminimum)theneedformodifications/extensionstoexistingapplicationsand/orupper–layerprotocols.
IndexTerms—IPv6,AnycastCommunication,Network-layerAnycast,AnycastRouting,AddressResolving
I.INTRODUCTION
Anycastingisanewnetworkingparadigmsupportingservice–orientedAddresseswhereanidenticaladdresscanbeassignedtomultiplenodesprovidingaspecificservice.Ananycastpacket(i.e.,onewithananycastdestinationaddress)isdeliveredtooneofthesenodeswiththesameanycastaddress.AnycastwasfirstdefinedinRFC1546[1],whichstatedthatthemotivationforanycastingwastodrasticallysimplifythetaskoffindinganappropriateserverontheInternet.Thebasicideabehindanycastcommunicationistoseparatethelogicalserviceidentifierfromthephysicalhostequipment,i.e.,theanycastaddressisassignedonatype-of-servicebasis,whichenablesthenetworkservicetoactasalogicalhost.
TheInternetProtocolversion6(IPv6)hasthreetypesofIPaddresses,i.e.,unicastandmulticastaddressesasinIPv4,andananycastaddressthatisthesubjectofthecurrentpaper.TableIsummarizestheformsofcommunicationfortheseaddresses.Aunicastaddressisauniqueidentifierforeachnetworkinterface,andmultipleinterfacesmustnotbeassignedthesameunicastaddress.Packetswiththesamedestinationaddressaresenttothesamenode.Amulticastaddress,ontheotherhand,isassignedtoagroupofnodes,i.e.,allgroupmembershavethesamemulticastaddressandpacketsforthisaddressaresenttoallmemberssimultaneously.Likeamulticastaddress,asingleanycastaddressisassigned
‡NECCorporation
Email:kitamura@da.jp.nec.com
§OsakaUniversity
Email:murata@cmc.osaka-u.ac.jp
TABLEIIPV6
ADDRESSTYPES.
unicastmulticastanycastcommunicationpointpointpointformtototopointmultipointpointtargetofnode
group
servicetype
addressnumberof
singlemultiplemultiplemembershiprolesinC/Smodelbothclient(listener)servertomultiplenodes(calledanycastmembership),butunlikemulticasting,onlyonememberoftheassignedanycastaddresscommunicateswiththeoriginatoratatime.Figure1hasanexampleofanycastcommunication.TherearethreenodesassociatedwiththeanycastaddressAany.Whenthesourcenodesendsapacket,wherethedestinationaddressisAany,thepacketissenttooneofthreenodes(Xuniinthisfigure),nottoallhosts.Theadvantageofanycastingisthatthesourcenodecanreceiveaspecificservicewithoutknowledgeoncurrentconditionsinservicenodesand/ornetworks.WhenhostXunigoesdown,thepacketforAanycanbesenttoanotherhost(YuniorZuni)(Fig.1).Howappropriatelythedestinationnodeischosenfromanycastmembershipdependsontheanycastroutingprotocol,whichwillbediscussedmoreinSectionIII.
However,IPv6anycastingstillhasseveralproblemsthatneedtobeclarifiedwithinthecontextofthecurrentspecifi-cations.First,weshouldhaveclearanswersto“whatkindsofapplicationsaresuitedtousinganycasting?”and“whataretheadvantages/disadvantagesofusinganycastingforapplica-tions?”AnotherproblemwithIPv6–basedanycastingisthataroutingprotocolhasnotbeenincludedinitsspecifications,whichisindispensableinmakinganycastingmorewidespread.Theroutershouldplayanactiveroleindecidingthedesti-nationnetworksothatanycastpacketscanbeappropriatelyforwarded.Weneedtodesignandimplementananycast
Fig.1.Anycastcommunication.
routingprotocolthatissuitedtoanycastapplications.WealsoneedamigrationscenariowheretheInternetwillgraduallybeabletosupportanycasting.Forexample,anycastroutingshouldworkadequately(thoughnotnecessarilyoptimally)evenwhenonlyafewnodesand/orrouterssupportanycastroutingwithintheInternet.WewilldiscussproblemswithanycastroutinginSectionIII,andpresentourproposalinSectionV.
Wealsoneedtoidentifyhowstatefulapplicationsutilizeanycastingindesigningtheirroutingprotocols.Internetap-plicationsusingallTCP-basedorsomeUDP-basedprotocolsarestateful,i.e.,endhostsestablishtheconditionsofcom-municationwitheachotherandassumethattheirpartnersareidenticalduringtheexchange.Thisisveryimportantbecausethecurrentdefinitionofanycastingisessentiallystateless,i.e.,thedestinationhostshouldbedeterminedonapacket-by-packetbasisbytherouters.WewilldiscussoursolutiontothisprobleminSectionIV.
Ofcourse,securityconsiderationsarealsoveryimportantinanycastcommunications.Amaliciousnodemayhijackcom-municationbyannouncingaspoofedadvertisementthroughwhichitreceivespacketsfortheanycastaddress.Thus,someauthenticationmechanismisnecessarytoactuallyvalidateanycasting.Public-key-basedauthenticationisonepromisingapproachtocounteractthisproblem,butfurtherconsiderationsonsecurityarebeyondthescopeofthecurrentpaper.
Finally,weneedtonotethatthenotionofanycastingisnotonlylimitedtothenetwork(i.e.,IP)layer,butcanalsobeachievedinother(e.g.,application)layers.AswillbediscussedinSectionII,network–andapplication–layeranycastinghavebothstrengthsandweakness,andwewillfocusonnetwork–layeranycastinginthispaper.
Therestofthispaperisorganizedasfollows.Thenextsectiondiscussesapplicationssuitable(andnotsuitable)tonetwork–layeranycastcommunications.SectionIIIisdevotedtoanintroductiononthecurrentimplementationsofanycast-ingandassociatedproblems.SectionIVpresentsourapproachcalledtheAARP(AnycastAddressResolvingProtocol)thatenablesTCPcommunicationsutilizinganycastaddresses.SectionVdiscussesourroutingschemeforinter–segmentanycasting,wherescalabilityanddeploymentaretakeninto
2
account.SectionVIconcludesthepaper.
II.ANYCASTAPPLICATIONS
Thissectionreviewswhatkindsofapplicationsaresuitedtoanycastcommunication.AnexcellentsurveyonIPv6anycastaddressescanbefoundin[2],wheretheyintroducedseveralapplicationsthatcanbeachievedthroughanycasting.Oneimportantexampleisserverlocation,throughwhichthesenderhostcanchooseoneofmanyfunctionallyidenticalhosts.Asaresult,loaddistributionamonganycasthostscanbeachievedifweutilizesomeappropriateanycastroutingmethod,whereanycastrequestsareevenlydistributedtohosts.However,asimplemethodsuchasrandomizationamonganycasthostsmaynotbesufficientsinceitisdifficulttotakethestatusoftheresourcesofeachserver,suchastheCPUload,intoaccountinnetwork–layeranycasting.Instead,application–layeranycastingshouldbeemployedinthiscase.
Anotherexampleisservicelocation[2],wherethesenderhostcancommunicatewithanoptimal(e.g.,minimumdelayorlargestthroughput)hostchosenfrommultipleanycasthostsbyspecifyingtheanycastaddress.Thisisespeciallyusefulindynamicallychangingenvironmentssuchasmobileadhocnetworks.Whilethiskindofservicecanbeobtainedthroughapplication–layeranycasting,thenodecancommunicateau-tomaticallywithanappropriate(e.g.,nearest)serverthroughnetwork–layeranycasting.
Insummary,theadvantageofnetwork–layeranycastingliesessentiallyinthatitprovidesasimplemechanismwherethesourcenodecanreceiveaspecificservicewithouttheknowledgeofservicenodesand/ornetworks.However,thisimmediatelyimpliesthatitisdifficulttoobtainrichfunc-tionalitiesandtheadditionalanycastexamplesthatarelistedbelowclearlydemonstratethis.
A.HostAuto-Configuration(Plug&Play)
Bydefiningandassigningawellknownanycastaddresstowidelyusedapplications(e.g.,DomainNameServices(DNS),andproxyservices),theusercanreachthesewithoutknowingthelocation(i.e.,theirunicastaddress)oftheserver[1].Moreover,theusercanutilizetheseapplicationseverywherebyspecifyingawellknownanycastaddress.DNSresolverswouldnolongerhavetobeconfiguredwiththeIPaddressesoftheirDNSservers,anditwouldbesufficienttosendaquerytoawellknownDNSanycastaddress.Thisfunctionalitycanalsobeusedforplug&play.Autoconfigurationthroughanycastingisquiteeffectiveduringtheprimitivesetupphase(e.g.,DNSservercannotbeused).Whenahostispluggedin,itsIPv6addressisconfigured,automatically.However,toachievetrueplug&play,varioussettingsarenecessary(e.g.,configuringunicastaddressesofDNSandproxyservers).Ifawell-knownanycastaddressisinstalledinthehardwarebeforehand,enduserscanutilizetheseserviceswithoutconfiguration.
Sinceautoconfigurationofhostsisoftendonetodiscoverlocally-providedservers(e.g.,DNS,SMTP,orproxyservers),anycastroutingprotocolcrossingsegmentsarenotmandatory,whichmeansthatthescalabilityproblempreviouslymentionedisnotanissuehere.
B.GatetoOverlayNetwork
Thegatetooverlaynetworkisanotherexampleofananycastapplication.AdistributedapplicationlikeaP2P(Peer-to-Peer)serviceconstructsalogicalnetworktopologyamongnodesparticipatingintheservice.However,thepeerneedstoknowtheaddresstoconnectthelogicalnetworkpriortoparticipatingintheservice.Eachpeeronlyspecifiestheanycastaddressinordertoparticipateinthelogicalnetworkandoneoftheparticipatingpeersbecomesthegateofthelogicalnetworkforthenewnode,whichshouldbedeterminedbytheanycastroutingprotocol.Theadvantageofthismodelisthatallprocessesarecompletedwithinitsownprotocol.Furthermore,evenwhentheconnectedpeerleavesthelogicalnetwork,itispossibletocontinueparticipatingviaanotherpeer,whichisautomaticallychangedbytheanycastroutingprotocol.Thiscannotbeattainedwithanyoftheexistingtechnologies.
C.ImprovingSystemReliability
Anycastingpermitsmultiplehostswiththesameaddressandbyincreasingthenumberofhosts,systemreliabilitycanbeimprovedbecauseitstillworksevenifsomeofthesefail.Throughamechanismthatwassimilartothis,wewouldhaveservicesthathadbetterpropertiestotoleratefaults.However,ifanycastpacketsaredestinedforothersegments,weagainneedanycastrouting.
III.PROBLEMSANDPOSSIBLESOLUTIONSTOIPV6
ANYCASTINGThissectiondiscussesproblemsthatremainwiththecurrentspecificationsforIPv6anycastingbecausetheycontaintoofewdefinitions.Italsoreviewsseveralsolutions.
A.Howahostannouncesitsparticipationinanycastmem-bership
Therearenostandardsfornodestoannouncethattheycanreceiveanycastpacketsexceptforpublishingroutinginformationforanycastaddresses,i.e.,thenodemustbearouterintheIPv6specifications.Thisimpliesthatahost(i.e.,notarouter)thatintendstoparticipatein(orleave)anycastmembershipmusthaveadifferentcapabilityofnotifyingthenearestanycastrouterofthestatus(joining/leaving).B.Howanupper–layerstatefulprotocolissupportedAnycastinghasastatelessnature,whereitcannotassurethatallpacketsbelongingtothesameanycastaddresswillgotothesamedestinationnode.
However,thisleadstoseriousproblemsinthatstatefulprotocolslikeTCPcannotbesupported.WhenahostinitiatesaTCPconnectiontoananycastaddress,thereceivinghostcannotsetitsownanycastaddressasthesourceaddressfortheacknowledgementpacket.TheIPv6specificationsprohibittheanycastaddressfrombeingsetintothesourceaddressfieldofthepacketheader.ThisisbasicallybecauseanIPv6anycastaddressdoesnotidentifyasinglesourcenode.Iftheprotocolallowedtheanycastaddresstobesetintothe
3
sourceaddressofthepacket,thereceivinghostcouldnotbesurethatallpacketssentduringthecommunicationhadcomefromthesamehost.Thismeansthatthehostcannotreceiveacknowledgementforapacketsenttoananycastaddress.WeberandCheng[2]recentlydiscussedtheanycastaddressmapper,whichhadbeenproposedbyOeandYamaguchi[3].Ittranslatesanycastaddressestocorrespondingunicastaddressesatthehostreceivinganycastpacketsandthisisdonepriortoanycastcommunication.However,eachapplicationmustbemodifiedinusingtheanycastaddressmappertomapananycastaddressbeforecommunicationbegins.Oursolutionissimilartoanycastaddressmapper,butthereisnoneedtomodifyupper–layerprotocolsorapplications.ThisisdiscussedinSectionIV.
C.Howanycastroutingisachieved
Thecurrentanycaststandarddoesnotdefinetheroutingprotocol,andthereareseveralchallengingissuesthatneedtoberesolvedindesigninganycastroutingprotocols.1)Scalabilityissue
Theroutingentriesforanycastaddressescannotbeaggregatedbecauseanycastmembershiplocationsarewidespreadregardlessoftheiractualprefix.Hence,routingentriesforanycastaddressesshouldbestoredindividuallyontherouter.Itiseasytoimagineexplo-sionsinroutingtablesasanycastaddressesgettobemorewidelyused.
2)Criteriaforselectinganycastmembership
Themeaningofappropriateneedstodifferamongapplications.Forexample,ifanapplicationrequiresafasterresponse,thepropagationdelaybetweenthesourcenodeandanycastnodeisextremelyimportant,i.e.,thenearestnodeforanycastmembershipshouldbechosen.Thecriteriaforanycastroutingstronglyaffectsanycastcommunicationcapabilities.3)Securityissues
Maintaininganycastmembershipisparticularlyimpor-tant.Theeasiestwayforahostthatintendstogainmembershipisforittosimplyadvertisetheroutingentryfortheassociatedanycastaddresstotherouter.However,suchanapproachcansometimesleadtoserioussecurityproblemsinthattheanycasthostcanfreelyaddordeleteanycastentriesintheroutingtable.
Oneimportantfeatureofanycastaddressesisthattheyshouldbeassignedfromthesameaddressspaceasaunicastaddressandarethussyntacticallyindistinguishablefromuni-castaddresses.RFC1546originallyrecommendedassigninganycastingitsownaddressspacebecauseitgreatlyexpectedthistoreducetheriskofapplicationsmistakenlyfailingtorecognizeanycastaddresses.However,whenweconsiderthedeploymentofanycastrouters,itisverylikelythatsomeroutersontheInternetwillnotbeabletoprocessanycastaddresses.Iftheseaddressesareallocatedinaunicastaddressspace,itisnotnecessaryforlegacyrouterstodeployspecialoperationsforcommunication:i.e.,thesesimplypassonanycastpacketsthroughunicastforwarding,expectingpacketscanbereached.Asitisdifficultforananycastroutertodecide
Fig.2.ProtocolstackofAARP.
whetherthereceivingpacket’sdestinationaddressisanycastorunicast,designingananycastroutingprotocolisproblematic.Therehavebeenseveralproposalsforananycastroutingprotocol[2],buttothebestofourknowledge,noneofthesehaveconformedtoIPv6anycastspecificationsandanycastaddressesareallocatedintheirownaddressspace,whichisdifferentfromtheunicastaddressspace.However,theroutingprotocolweproposedinSectionVallowsthesamespacetobeusedforbothunicastandanycastaddresses.
IV.ANYCASTADDRESSRESOLVINGPROTOCOLOurproposalfillsagapbetweenanycastandupper–layerprotocolslikeTCPandUDPwithouttheneedtomodifyapplicationsorprotocols[4].Morespecifically,thetaskoftheAARP(AnycastAddressResolvingProtocol)istoresolvetheanycastaddressspecifiedbytheapplicationintothecorrespondingunicastaddress.Figure2outlinestheprotocolstackforanycastcommunicationwiththeAARP.TheAARPisimplementedasakindofDLL(DynamicLinkableLibrary)thatoverwritestheoriginal(i.e.,theprovidedoperatingsys-tem)APIs(ApplicationProgrammingInterfaces).WecalledthislibrarytheAARPLibrary(AARPLibinFigure2),whichprovidesthesamesetofAPIsastheoriginalIPv6socketAPIs,andhooksthemtoresolveanycastaddresses.ItconvertsananycastaddressintoitscorrespondingunicastaddresspriortocallingtheoriginalAPIs.TheanycastaddressisonlyusedintheapplicationlayerandtheAARPLibrarylayer.LayersbelowtheAARPLibraryarenotawareoftheanycastaddress,andonlyhandlethetranslatedunicastaddress.A.AddressResolvingProcessinAARP
WhenhostCwantstoestablishanycastcommunicationwithahostwhoseanycastaddressisAA,theprocessforanycastaddressresolutionisasfollows;
1)HostCcallsthesocketAPI(e.g.,connect()inTCP)withtheanycastaddressAAwithinitsparameters.TheAARPLibrary’sAPIiscalledinsteadofthesocketlayer’sAPI.
2)TheAARPLibraryconvertstheanycastaddressintotheunicastaddressUAinthecalleefunction.
3)Afterconversion,theAARPLibrarycallstheoriginalsocketAPIthroughtheunicastaddressUA.
4
4)Aftercommunicationhasbeenestablished,allpacketsfromhostCaregiventheunicastaddressUAintheirdestinationaddressesandtransferredtohostS.B.AddressConversionMethod
BecauseofIPv6anycast’sprotocolspecifications,itcannotidentifytheaddressasanycastbyitselfandforconversionthehostconnectingtotheanycastaddressshouldreceiveatleastonepacketfromthedestinationhost.Therearetwoapproachestoconvertthisaddress.
1)ProbePacketMethod(ClientInitiated)
Thehostsendsaprobepackettotheanycastaddresspriortothestartofcommunicationanditcanobtainthedestination’sunicastaddressfromthesourceaddressofthereplypacket.
2)PiggybackMethod(ServerInitiated)
Theanycasthostappendsitsanycastaddresstothepacketwhensendingitbacktotheconnectingpeer.Itcanrecognizethatthepackethasbeensentfromthehostassociatedwiththeanycastaddressbycheckingtheinformationthathasbeenaddedtothepacket.
Theprobepacketmethodrequiresadditionalnetworkband-widthtoprobepackets,whichwastesnetworkresources.However,thepiggybackmethodrequiresapplicationstobemodifiedsothattheanycastaddresscanbepiggybackedonthepacket.Sinceweneededtoavoidanymodificationstoapplications,weusedthepacketprobingapproachtoincludetheunicastaddressintheAARP.C.ImplementationofAARP
WeimplementedandtestedtheAARP[4].Toresolvetheanycastaddressintoitscorrespondingunicastaddress,weusedICMPv6ECHOREQUEST/REPLYpackets.Sincetheanycastaddressshouldnotbesetinthesourceaddressofthepacketheader,theanycastmembershiphostsetsthecorrespondingunicastaddressinthesourceaddressfieldoftheICMPpacketinsteadoftheanycastaddress.Therefore,thehostthatreceivestheICMPECHOREQUESTpacketsenttoananycastaddresswillsendthispacketwithitsunicastaddress.IftheAARPcannotusetheICMPv6mechanism,specialsoftwareisrequiredtorespondtotheprobepacketfromthecallerhost.
OurAARPlibraryalsoprovidesacachetableforresolvedanycastaddresses.Whentheanycastaddressisnotcachedinthetable,theAARPsendsaprobepackettoresolvetheanycastaddress.Theresolvedunicastaddressisstoredintothecachetablewithatimer,andwillbedeletedwhenthetimerexpires.Thatis,fortheclient,packetstotheanycastaddressaredeliveredtothesameanycastserveruntilthecacheexpires.Otherwise,theAARPreturnstheresolvedunicastaddressfromthecachetable,andaprobepacketisnotsentuntiltheentryfortheanycastaddresshasexpiredinthecachetable.NoteherethatthissimpleapproachusingICMPpacketscannotsolvesecurityproblems.EvenifamalicioususerhookstheICMPECHOREQUESTpacketandsendsit,theclientusesthesourceaddressofthispacket.
Intests,weusedTCP(telnet,ftp)andUDPappli-cations(DNS).Wemonitoredpacketexchangesbytheseapplicationswithtcpdump.TheresultsrevealedthatAARPmakesanycastcommunicationspossiblebyonlyspecifyingtheanycastaddressinallexistingapplications(e.g.,ftpanycastaddr).
V.DESIGNOFINTER-SEGMENTANYCASTROUTING
PROTOCOLA.DesignChoices
Thedesignchoiceswemadeinouranycastroutingprotocolareasfollows.
1)Weallowedunicastandanycastaddresseswithinthesamespaceandtodothiswechoseaseednodefromanycastmembershipbeforeassigningananycastaddress.Wethenestablishedtheanycastaddressofmembershiptobetheunicastaddressoftheseednode.Theanycastrouterforwardsananycastpackettoanappropriatenodewithintheanycastmembership.How-ever,theunicastrouteronlytriestoforwardtheanycastpackettotheseednode.Ananycastpacketleavinganarbitrarynodeisattheveryleastsenttotheseednode.Anypacketdestinedfortheanycastaddressisguaranteedtobesenttoatleastonedestinationnode.2)Weenvisionthegradualdeploymentofanycastingandtheprotocolworkscorrectlyinourarchitectureandoffersadvantagesevenifthereisonlyoneanycastrouterbetweenthesenderandseednode.Itsimpactwillincreaseasmoreanycastroutersaredeployed.
3)Weadoptedanapproachthatmodifiesmulticastroutingtotheanycastroutingprotocoltoreducethecomplexityofimplementation,sincetheyhavemanysimilarities.B.ProposedArchitecture
Figure3isanoverviewoftheroutingarchitectureweproposeandtherearetwotypesofroutingtopologies.Theunicastnetworkistheexistingnetworktopologywherebothunicastandanycastpacketsareforwardedonthebasisofaunicastaddress.Intheanycastnetwork,anycast-awarerouters(calledanycastrouters)areconnectedtooneanotherandonlyanycastpacketsareforwardedbytreatingtheiraddressesasanycastaddresses.Theanycastnetworkcanthusbeconsideredasalogicaloverlaynetworkovertheunicastnetwork.
Inananycastnetwork,nodesarenotphysically(i.e.,directly)connected,butareconnectedviavariouskindsoflogicalpeer-to-peerconnections(e.g.,virtualpath,tunneling,orencapsulation).Ananycastrouterisupper-compatible,doesanycastroutingfunctions,andhasthecapabilitiesofunicastrouters.Ananycastrouterhasanextraroutingtable(calledananycastroutingtable)tohandleanycastaddresses.Ananycastroutingtableconsistsofatleast(anycastaddressandnextanycastrouter’saddress)pairs.Whenapacketarrivesattheanycastrouter,itfirstcheckstheanycastroutingtabletofindanentryregardingthedestinationaddressofthepacket.Ifitfindsthis,thepacketistreatedasananycastpacketandforwardedtothenextanycastrouteraccordingtotheanycast
5
Fig.3.Proposedarchitecture.
routingtable.Otherwise,itisforwardedthroughtheunicastroutingmechanism.
Figure3hasanexampleofanycastroutingwherewehaveassumedthatthenodeselectioncriterionisthenumberofhops.Asmallercountismoreappropriatehere.InFig.3,shortcylindersrepresentroutersandtheonelabeled“AR”isananycastrouter.Theothershortcylinders(i.e.,non-labeledcylinders)areunicastrouters.Therearetwoanycastmembersfortheanycastaddress3ffe:5::5.Noteherethat3ffe:5::5isalsotheunicastaddressofanycastserverA1.Here,nodeA1istheseednodeofanycastmembershipfor3ffe:5::5.TheothernodeA2isinadifferentnetwork(3ffe:4::/32).Letusnowconsiderwheretwonodes(C1andC2)sendpacketsdestinedforanycastaddresses3ffe:5::5.ThedifferenceiswhetherthereisananycastrouterontheroutetoseednodeA1.C1firstforwardsthepackettorouterARthroughunicastrouting(solidarrow).IntermediaterouterARisananycastrouterandcandetectthatthepacketisalsoananycastpacket.
Accordingtoanycastrouting(dashedarrow),anycastrouterARthenforwardsittonodeA2,whichisthenodenearestC1.However,sincethereisnoanycastrouterbetweenC2andA1,thepacketissimplyforwardedtoA1throughunicastroutingonly.Notethatthereisamoreappropriatenode(A2)inthisnetwork.Forexample,ifwereplacetherouternexttoC2(short-checkedcylinder)withananycastrouter,thepacketcouldbetransmittedtothemoreappropriateA2nodethroughanycastrouting.
Theabovedescriptionrevealsthatouranycastroutingprotocolworksappropriatelyevenwhentherearealimitednumberofanycastrouters.Iftheseareincreased,betterroutingisachieved.Whenallroutersinthenetworkareanycast,flexibleroutingadoptingacontrolpolicyusingvariousmetricswillbepossible.
Wedividedtheanycastroutingprotocolintothefollowingtwoprocessestodefineit.
1)Initiateanycastmembership(SubsectionV-C)
Theanycastroutercollectsinformationonnodesthatintendtojoinanycastmemberships.
Fig.4.Overviewofanycastroutingprotocol.
2)Constructandupdateroutingtable(SubsectionV-D)Accordingtoinformationcollected,anycastrouterscon-structtheirownroutingtablesandthenexchangeroutinginformationwithoneanothertoreconfigurethese.Figure4hasanoverviewofouranycastroutingprotocol.Noteagainthatourbasicmotivationinsupportingany-castingwastominimizeoverheadsorimplementationfordeploymentasmuchaspossible.Wethereforefocusedonthedifferencebetweenanycastingandmulticastingtodevelopananycastroutingprotocolthroughmulticastroutingprotocols.Anycastingandmulticastinghavemanysimilarcharacteristicswhiletheyalsohavesomedifferences.Ourfirststepindesign-ingtheanycastroutingprotocolistoclarifythesesimilaritiesbetweenanycastingandmulticastingandthenshowhowtomodifytheexistingmulticastroutingprotocolstosupportanycastrouting.Inthispaper,wechosethreemulticastroutingprotocolsthatarecurrentlyavailableandwidelyusedinIPv4networkstoday;(1)theDVMRP(DistanceVectorMulticastRoutingProtocol)[5],(2)theMOSPF(multicastextensionofOSPF)[6],andthePIM-SM(ProtocolIndependentMulticast–SparseMode)[7].
Sinceeachmulticastprotocolhasbothadvantagesanddisadvantages,wedefinedtheanycastroutingprotocolbasedonallofthese,i.e.,(1)theDistanceVectorAnycastRout-ingProtocol(DVARP),(2)theanycastextensionofOSPF(AOSPF),and(3)theProtocolIndependentAnycastSparseMode(PIA-SM).Thesewillbepresentedinturninthesubsectionsthatfollow.Whenmodifyingtheseprotocols,weconsideredthefollowingdifferencesbetweenanycastingandmulticasting(SeeTableI):
•
Communicationform
Inanycasting,onlyonemembercommunicateswiththeoriginator.Inmulticasting,however,allmembersareequallytreatedintheroutingtable.Apacketdestinedforananycastaddresswillbedeliveredtoonlyoneofthehostswiththataddress.•
Rolesinclient/servermodel
Ananycastaddressisassignedtotheserverinanycasting.Inmulticasting,however,amulticastaddressisassigned
6
totheclient(i.e.,multicastlistener).Therefore,multicastmembershipmaychangefrequently.Iftherearedesignpointsbasedonthisfeatureinmulticastroutingprotocols,weshouldmodifythesepoints.
NotethatcomparisonsoftheseanycastroutingprotocolswillbepresentedinSubsectionV-Ealongwithsomeguide-linesusedinchoosingtheprotocol.C.InitiateAnycastMembership
Likemulticasting,thehostparticipatingin(orleavingfrom)anycastmembershipmusthavethecapabilityofnotifyingthenearestanycastrouterofthestatus(joining/leaving).Themethodoffindingahostparticipatinginanycastmembership(calledanycasthostbelow)isdifferentandisbasedonthelocationoftheanycasthost.Iftheanycasthostandtheanycastrouterareonthesamesegment,anextendedversionofMLD(MulticastListenerDiscovery)isused[8].WecallthisARD(AnycastReceiverDiscovery).AnanycasthostgeneratesanMLDreportmessagetotheanycastrouterbeforejoininganycastmembership.However,theanycasthostsendsanMLDleavemessagepriortoleavingmembership.BecausethedestinationaddressfieldofMLDpacketsissettothelink-localaddressofrouters(FF02::2),thismethodcanonlybeappliedwhereallhostsandroutersresidewithinthesamesegment.
AlledgeroutersmustbecomeanycastrouterswiththecapabilityofARDtoenableinter-segmentanycastrouting.However,thisisunrealisticintheearlystagesofanycasting.Onepossiblesolutionistolocatetheauthorizationnodeonthesamesegmentastheanycastrouter.Anodewiththecapabilityofforwardingananycastpacketestablishesatunnelingpathtotheauthorizationnode.Afterestablishingthetunnelingpath,theauthorizationnodeadvertisesanycastaddressinformationtotheanycastrouterthroughARD.Thetunnelingpathisonlyusedtoannounceanycastroutinginformation.
Againnotethatthemethodbywhichanycasthostsarecollectedsometimesleadstoserioussecurityproblems.Theanycastroutershouldhavesomemechanismthatpreventsillegaland/orspoofedanycasthostnotifications.D.ConstructingandUpdatingRoutingTable
1)DVARP:SincemulticastmembershipisexpectedtochangedynamicallyintheDVMRP,itishardtospecifytheroutethatmulticastpacketswilltraversebeforebeginningtransmission.Therefore,aflooding(orbroadcasting)approachiseffective.However,anycastmembershipdoesnotchangeasfrequentlyasthatformulticasting,anditsroutinginformationismorestable.Therefore,DVARPdoesnotusefloodingbutexchangesroutinginformationperiodically.
Figure5(a)hasanexampleofupdatingaDVARProutingtable.DVARPoperationisdoneasfollows.
1)Iftheanycastrouterdetectschangesinanycastmember-ship,theanycastrouterupdates/createstheroutingentryinitsownroutingtable.
2)EachDVARProuterperiodicallysendsitsownroutinginformationtoitsadjacentrouters.
7
(a)DVARP.(b)PIA-SM.
Fig.5.Examplesofproposedanycastroutingprotocols.
3)Ifarouterreceivesroutinginformationfromadjacentrouters,itupdatesentriesintheroutingtable.2)AOSPF:UnlikeDVMRP,routinginformationisnotfloodedwhenmulticastpacketsinMOSPFfirstarrive.Instead,therouterexchangesroutinginformationwithotherrouterswhenmulticastmembershipchanges.Thisapproachsuitsanycastroutingbecauseitsmembershipismorestablethanmulticast’s.Therefore,AOSPFalsoadoptsthismembershipchange-drivenapproach,andtheAOSPFroutingtableisexactlythesameasDVARP’s.AOSPFoperationisdoneasfollows.
1)Iftheanycastrouterdetectsachangeinanycastmem-bership,itupdates/createstheentryinitsownlink-statedatabase.
2)Whendetectingmembershipchanges,eachAOSPFrouterimmediatelysendsthelinkstateupdatetoad-jacentAOSPFrouters.
3)Afterupdating/creatingitsownlink-statedatabase,therouterusesDijkstra’sSPF(ShortestPathFirst)algorithmandcalculatestheshortestpathtreefromtherouter.Then,theanycastroutercreates/updatesitsroutingtablefromtheshortestpathtree.TheAOSPFoperationissimilartothatofDVARP’sexceptthatitusesDijkstra’sSPFalgorithmandthereisadifferenceinthefrequencyofroutinginformationexchanges.DVARPperiodicallyexchangesinformationwhileAOSPFdoesthisattopologychangeevents,whichgreatlyaffectstheconvergencetimefortheroutingtable.WhenthereisachangeinrouteinAOSPF,itistransmittedfasterthanitiswithDVARP.
3)PIA-SM:PIA-SMusesacore-based-treealgorithmlikePIM-SM[7]andmembershipmanagementisdonebythecorerouter.WecalledthiscorenodetheRendezvousPoint(RP)followingPIM-SM.TheRPisselectedfromallPIA-SMroutersandhastheresponsibilityofmanaginganycastmem-berships.Apackettowardananycastaddressistransmitted
oncetotheRP.AftertransfertotheRP,thepacketcanbeforwardedtotheappropriateanycastreceiverbytheRP.TheregistrationinformationontheRPisequivalenttoDVARPandAOSPFroutingtables.
Becausethiscore-basedapproachcanbeappliedtoPIA-SM,thePIM-SMmechanismcandirectlybeusedforit.Figure5(b)hasanexampleofanewregistrationtothePIA-SM’sRP.WewillnowdescribetheoperationsofRPandPIA-SMrouters.
1)Ifananycastrouterdetectschangesinanycastmem-bership,thePIA-SMrouterreportsthesetotheRP,whichdetectstwotypesofmessagepackets,PIA-JoinandPIA-Prune.ThePIA-Joinmessageindicatesthatanewanycastreceiverhasjoinedmembership,andthePIA-Prunemessageindicatesthenodenolongerbelongstoit.
2)IfthePIA-SMrouter(notRP)receivesaPIA-Join(PIA-Prune)message,itcreates(cuts)thecorrespondinganycastmembershipandsendsthePIA-Join(PIA-Prune)totheupperPIA-SMrouterstowardtheRP.IfthePIA-SMalreadyhasacorrespondingentryandthedownstreamPIA-SMindicatesadifferentrouter,thenexthopisaddedtoanexistingentryformultipathrouting.
3)Similarly,iftheRPreceivesaPIA-Join(PIA-Prune),itcreates(cuts)thecorrespondinganycastmembership.IftheRPalreadyhasacorrespondingentry,whichindi-catesthatthedownstreamPIA-SMrouterisdifferent,thenexthopisaddedtotheexistingentryformultipathrouting.E.ComparisonsofAnycastRoutingProtocols
Letusnowcompareourproposedprotocols,i.e.,DVARP,AOSPF,andPIA-SM.Wehadthefollowingthreeobjectivesinmindforourcomparisons.
TABLEII
COMPARISONSOFTHREEANYCASTROUTINGPROTOCOLS.
DVARPAOSPFPIA-SMoverheadnetworkO(gm)O(gm)RP:O(ng)O(gs)router
O(gs)+
RP:O(gs)O(l*log(gm))convergencehopbyhopnoneimplementabilitynotavailableavailablen:thetotalnumberofnodesinthenetwork,g:thenumberofanycastgroups,m:themeannumberofnodeswhichsharethesameanycastaddress,s:themeannumberofanycastroutingentries,l:thetotalnumberoflinks.
•
Protocoloverheads(e.g.,CPUloadandmemorycon-sumption)
•Convergencetimeduetomembershipchanges•Easeofimplementingprotocols
TableIIsummarizesthecomparisons.Notethatthesearesimilartowhatweobtainedformulticastroutingprotocols.Withrespecttoprotocoloverheads,bothDVARPandAOSPFconsumeavastamountofnetworkresourcesandtheirtrafficconsumptionisalmostlinearforthenumberofanycastgroupsandthenumberofnodessharingthesameanycastaddress.Therefore,theseprotocolscanonlybeappliedtosmallnet-workswithhighlevelsofavailablebandwidth.
PIA-SMhashardlyanytrafficconsumption,however,be-causeonlytheRPhasroutinginformation,whichtheotherPIA-SMroutersdonot.Therefore,PIA-SMismorescalablethantheothertwoprotocols.However,PIA-SMhasoneprobleminthatanycastpacketsarenottransferredthroughtheoptimalpathbecausetheyarealwaystransferredthroughtheRP.AnotherproblemisthattrafficconcentratesaroundtheRP.Theseproblemscauseextradelaysinpackettransmissions.Becauseofthis,PIA-SMcanbeappliedtolargenetworksliketheInternet.
DVARPtakesalongtimeforroutestoconvergealthoughAOSPFtakesless.SinceallroutinginformationisonlykeptbytheRPinPIA-SM,itisnotnecessarytoexchangeroutinginformation.
TheimplementationofPIM-SMforIPv6hasalreadybeenavailablewhileDVMRPandMOSPFhavenotasfarasweknow.Thatis,PIA-SMiseasiertoimplementthantheothertwo.
VI.CONCLUSIONANDFUTUREWORK
IPv6anycastinghasseveralproblemsinfacilitatingcom-municationswithexistingapplications.Tosolvethese,weproposedanewprotocolcalledtheAARP,whichchangestheanycastaddressintoacorrespondingunicastaddress,whichisusedinactualcommunicationafterconversion.Wedemonstratedthatcommunicationswiththeanycastaddresscouldoccurwithoutchangingtheexistingapplicationprogramwiththisprotocol.
Wealsoproposedanddesignedthreeanycastroutingproto-colsbyfocusingonandcomparingsimilaritiesbetweenany-castingandmulticastingandmodifyingtheexistingmulticast
8
routingprotocol.Inthispaper,however,weonlydiscussedthedesignofoneanycastroutingprotocolalthoughwearecurrentlyimplementingothersandevaluatingtheirfeasibility.
REFERENCES
[1]C.Patridge,T.Mendez,andW.Milliken,“Hostanycastingservice,”
RFC1546,Nov.1993.
[2]S.WeberandL.Cheng,“AsurveyofanycastinIPv6networks,”IEEE
CommunicationsMagazine,vol.42,Jan.2004.
[3]M.OeandS.Yamaguchi,“ImplementationandevaluationofIPv6
anycast,”inProceedingsofthe10thAnnualInternetSocietyConference,2000.[4]S.Ata,H.Kitamura,andM.Murata,“Aproto-colforanycastaddressresolving,”Internetdraft
draft-ata-ipv6-anycast-resolving-01.txt,Feb.2004.[5]D.Waitzman,C.Partridge,andS.Deering,“Distancevectormulticast
routingprotocol,”RFC1075,Nov.1988.
[6]J.Moy,“MOSPF:Analysisandexperience,”RFC1584,Mar.1994.
[7]S.Deering,D.Estrin,D.Farinacci,V.Jacobson,C.gungLiu,andL.Wei,
“ThePIMarchitectureforwide-areamulticastrouting,”inProceedingsofIEEE/ACMTransactionsonNetworking,vol.4,pp.153–162,Apr.1996.[8]B.HabermanandD.Thaler,“Host-basedanycastusingMLD,”Internet
draftdraft-haberman-ipngwg-host-anycast-01.txt,May2002.(ExpiredNovember2002).
因篇幅问题不能全部显示，请点此查看更多更全内容