accountdnsfail

CoDNS:ImprovingDNSPerformanceandReliabilityviaCooperativeLookupsKyoungSooPark,VivekS.
Pai,LarryPetersonandZheWangDepartmentofComputerSciencePrincetonUniversityAbstractTheDomainNameSystem(DNS)isaubiquitouspartofeverydaycomputing,translatinghuman-friendlyma-chinenamestonumericIPaddresses.
MostDNSre-searchhasfocusedonserver-sideinfrastructure,withtheassumptionthattheaggressivecachingandredundancyontheclientsidearesufcient.
However,throughsys-tematicmonitoring,wendthatclient-sideDNSfail-uresarewidespreadandfrequent,degradingDNSper-formanceandreliability.
WeintroduceCoDNS,alightweight,cooperativeDNSlookupservicethatcanbeindependentlyandincremen-tallydeployedtoaugmentexistingnameservers.
Itusesalocalityandproximity-awaredesigntodistributeDNSrequests,andachieveslow-latency,low-overheadnameresolution,eveninthepresenceoflocalDNSnameserverdelay/failure.
Usinglivetrafc,weshowthatCoDNSreducesaveragelookuplatencyby27-82%,greatlyre-ducesslowlookups,andimprovesDNSavailabilitybyanadditional'9'.
Wealsoshowthatawidely-deployedserviceusingCoDNSgainsincreasedcapacity,higherre-liability,andfasterstarttimes.
1IntroductionTheDomainNameSystem(DNS)[15]hasbecomeaubiquitouspartofeverydaycomputingduetoitseffec-tiveness,human-friendliness,andscalability.
Itprovidesadistributedlookupserviceprimarilyusedtoconvertfromhuman-readablemachinenamestoInternetProto-col(IP)addresses.
ItsexistencehaspermeatedmuchofcomputingviatheWorldWideWeb'snear-completede-pendenceonit.
Thanksinparttoitsredundantdesign,aggressivecaching,andexibility,ithasbecomeaubiq-uitouspartofeverydaycomputingthatmostpeopletakeforgranted,includingresearchers.
MostDNSresearchfocuseson"server-side"prob-lems,whichariseonthesystemsthattranslatenamesbelongingtothegroupthatrunsthem.
Suchprob-lemsincludeunderstandingnamehierarchymiscong-uration[5,9]anddevisingmorescalabledistributioninfrastructure[4,10,18].
However,duetoincreasingmemorysizesandDNS'shighcachability,"client-side"DNShitratesareapproaching90%[9,24],sofewerre-questsaredependentonserver-sideperformance.
Theclient-sidecomponentsareresponsibleforcontactingtheappropriateservers,ifnecessary,toresolveanynamepresentedbytheuser.
Thisinfrastructure,whichhasre-ceivedlessattention,isourfocus–understandingclient-sidebehaviorinordertoimproveoverallDNSperfor-manceandreliability.
UsingPlanetLab[16],awide-areadistributedtestbed,welocallymonitortheclient-sideDNSinfrastructureof150sitesaroundtheworld,generatingalarge-scaleex-aminationofclient-sideDNSperformance.
Wendthatclient-sidefailuresarewidespreadandfrequent,andthattheireffectsdegradeDNSperformanceandreliability.
Themostcommonproblemsweobserveareintermit-tentfailurestoreceiveanyresponsefromthelocalname-servers,butthesearegenerallyhiddenbytheinternalre-dundancyinDNSdeployments.
However,thecostofsuchredundancyisadditionaldelay,andwendthatthedelaysinducedthroughsuchfailuresoftendominatethetimespentwaitingonDNSlookups.
Toaddresstheseclient-sideproblems,wehavedevel-opedCoDNS,alightweight,cooperativeDNSlookupservicethatcanbeindependentlyandincrementallyde-ployedtoaugmentexistingnameservers.
CoDNSusesaninsurance-likemodelofoperation–groupsofmutuallytrustingnodesagreetoresolveeachother'squerieswhentheirlocalinfrastructureisfailing.
Wendthatthegroupsizedoesnotneedtobelargetoprovidesubstantialbene-ts–groupsofsize2provideroughlyhalfthemaximumpossiblebenet,andgroupsofsize10achievealmostallofthepossiblebenet.
Usinglocality-enhancementtech-niquesandproximityoptimizations,CoDNSachieveslow-latency,low-overheadnameresolution,eveninthepresenceoflocalDNSdelays/failures.
CoDNShasbeenservinglivetrafconPlanetLabsinceOctober2003,providingmanybenetsoverstan-dardDNS.
CoDNSreducesaveragelookuplatencyby27-82%,greatlyreducesslowlookups,andimprovesDNSavailabilitybyanextra'9',from99%toover99.
9%.
Itsserviceismorereliableandconsistentthananyindividualnode's.
Additionally,CoDNShassal-vaged"unusable"nodes,whichhadsuchpoorlocalDNSinfrastructurethattheywereuntfornormaluse.
Appli-cationsusingCoDNSoftenhavefasterandmorepre-dictablestarttimes,improvingavailability.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation19910100100010000000612180006121800AverageResponseTime(ms)Time(a)planetlab1.
cs.
cornell.
edu101001000000612180006121800AverageResponseTime(ms)Time(b)lefthand.
eecs.
harvard.
edu10100100010000000612180006121800AverageResponseTime(ms)Time(c)planetlab-1.
cmcl.
cs.
cmu.
edu10100100010000100000000612180006121800AverageResponseTime(ms)Time(d)kupl1.
ittc.
ku.
edu10100100010000000612180006121800AverageResponseTime(ms)Time(e)planetlab-1.
stanford.
edu10100100010000100000000612180006121800AverageResponseTime(ms)Time(f)planetlab1.
cs.
ubc.
ca10100100010000000612180006121800AverageResponseTime(ms)Time(g)planetlab1.
eecs.
umich.
edu10100100010000000612180006121800AverageResponseTime(ms)Time(h)planetlab2.
cs.
northwestern.
eduFigure1:AveragecachedDNSlookupresponsetimesonvariousPlanetLabnodesovertwodays.
NotethatwhilemostYaxesspan10-1000milliseconds,someareaslargeas100,000milliseconds.
2Background&AnalysisWhiletheDomainNameSystem(DNS)wasintendedtobeascalable,distributedmeansofperformingname-to-IPmappings,itsexibledesignhasallowedittogrowfarbeyonditsoriginalgoals.
WhilemostpeoplewouldbefamiliarwithitforWebbrowsing,manysystemsdependonfastandconsistentDNSperformance.
Mailservers,Webproxyservers,andcontentdistributionnetworks(CDNs)mustallresolvehundredsoreventhousandsofDNSnamesinshortperiodsoftime,andafailureinDNSmaycauseaservicefailure,ratherjustdelays.
Theserver-sideinfrastructureofDNSconsistsofhierarchically-organizednameservers,withcentralau-thoritiesproviding"root"serversandothersdelegatedorganizationshandling"top-level"servers,suchas".
com"and".
edu".
Domainnameownersarerespon-sibleforprovidingserversthathandlequeriesfortheirnames.
WhileDNSuserscanmanuallyqueryeachlevelofthehierarchyinturnuntilthecompletenamehasbeenresolved,mostsystemsdelegatethistasktolocalname-servermachines.
Thisapproachhasperformancead-vantages(e.
g.
,cachingreplies,consolidatingrequests)aswellasmanagementbenets(e.
g.
,fewermachinestoupdatewithnewsoftwareorrootserverlists).
Withlocalnameservercachehitratesapproaching90%[9,24],theirperformanceimpactcaneclipsethatoftheserver-sideDNSinfrastructure.
However,localnameserverperformanceandreliabilityhasnotbeenwellstudied,andsinceithandlesallDNSlookupsforclients,itsfailurecandisableothersystems.
OurexperienceswithbuildingtheCoDeeNcontentdistributionnetwork,runningonover100PlanetLabnodes[23],motivatedustoinvestigatethisissue,sinceallCoDeeNnodesusethelocalnameserversattheirhostingsites.
2.
1FrequencyofNameLookupFailuresTodeterminethefailurepropertiesoflocalDNSinfras-tructure,wesystematicallymeasureDNSlookuptimesonmanyPlanetLabnodes.
Inparticular,across40NorthAmericansites,weperformaqueryoncepersecond.
Weaskthesenodestoresolveeachother'snames,allofwhicharecacheable,withlongtime-to-live(TTL)valuesofnolessthan6hours.
Lookuptimesfortheserequestsshouldbeminimal,ontheorderofafewmilliseconds,sincetheycanbeservedfromthelocalnameserver'scache.
Thisdiagnosticworkloadischosenpreciselybe-causeitistriviallycacheable,makinglocalinfrastruc-turefailuresmorevisibleandquantiable.
EvaluationofDNSperformanceonlivetrafc,withandwithoutCoDNS,iscoveredinSection5.
OurmeasurementsshowthatlocalDNSlookuptimesaregenerallygood,butoftendegradedramatically,andthatthisinstabilityiswidespreadandfrequent.
Toillus-OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation2000.
10.
20.
30.
40.
50.
60.
70.
80.
91110100100010000CDFResponseTime(ms)northwesternu-michstanfordkuhavardcmucornellubc(a)FractionofLookupsTakingXms00.
10.
20.
30.
40.
50.
60.
70.
80.
91110100100010000WeightedCDFResponseTime(ms)ubccmuu-michstanfordkuharvardnorthwesterncornell(b)FractionoftheSumofLookupsTakingXmsFigure2:CumulativeDistributionofCachedDNSLookupstratethewidespreadnatureoftheproblemanditsmag-nitude,Figure1showsthelookupbehavioroveratwo-dayperiodacrossanumberofPlanetLabnodes.
Eachpointshowstheper-minuteaverageresponsetimeofnamelookups.
AllthenodesinthegraphshowsomesortofproblemsinDNSlookupsduringtheperiod,withlookupsoftentakingthousandsofmilliseconds.
Theseproblemsarenotconsistentwithsimplecong-urationproblems,butappeartobeusage-inducedortrig-geredbyactivityonthenameservernodes.
Forexample,theCornellnodeconsistentlyshowsDNSproblems,withmorethan20%oflookupsshowinghighlookuptimesofoverveseconds,thedefaulttimeoutintheclient'sre-solverlibrary.
Thesefailedlookupsareeventuallyre-triedatthecampus'ssecondnameserver,maskingtherstnameserver'sfailures.
Sincetherstnameserverre-spondsto80%ofqueriesinatimelymanner,itisnotcompletelymiscongured.
Veryoftenthroughouttheday,itsimplystopsresponding,drivingtheper-minuteaveragelookuptimesclosetoveseconds.
TheHarvardnodealsodisplaysgenerallybadbehavior.
Whilemostlookupsarene,afewfailedrequestseveryminutesub-stantiallyincreasetheper-minuteaverage.
TheStanfordnode'sgraphshowsperiodicspikesroughlyeverythreehours.
Thisphenomenonislong-term,andwesuspectthenameserverisbeingaffectedbyheavycronjobs.
TheMichigannodeshowsa90minuteDNSproblem,drivingitsgenerallylowlookuptimestoaboveonesecond.
Althoughtheaveragelookuptimesappearquitehighattimes,theindividuallookupsaremostlyfast,withafewveryslowlookupsdominatingtheaverages.
Fig-ure2(a)displaysthecumulativedistributionfunction(CDF)ofnamelookuptimesoverthesametwodays.
WiththeexceptionoftheCornellnode,90%ofallre-queststakelessthan100msonallnodes,indicatingthatcachingiseffectiveandthatavaerage-caselatenciesarequitelow.
EventheCornellnodeworkswellmostofthetime,withover80%oflookupsareresolvedwithin6ms.
NodeAvgLowHighT-LowT-Highcornell531.
7ms82.
4%12.
9%0.
5%99.
2%harvard99.
4ms92.
3%3.
3%0.
7%97.
9%cmu24.
0ms81.
9%3.
2%8.
3%71.
0%ku53.
1ms94.
6%1.
8%2.
9%95.
0%stanford21.
5ms95.
7%1.
3%5.
3%89.
5%ubc88.
8ms76.
0%7.
6%2.
4%91.
2%umich43.
6ms96.
7%1.
3%2.
4%96.
1%northwestern43.
1ms98.
5%0.
5%4.
5%94.
8%Table1:Statisticsovertwodays,Avg=Average,Low=Per-centageoflookups10ms,High=Percentageoflookups100ms,T-Low=Percentageoftotallowtime,T-High=Per-centageoftotalhightimeHowever,slowlookupsdominatethetotaltimespentwaitingonDNS,andarelargeenoughtobenoticeablebyendusers.
InFigure2(b),weseethelookupsshownbytheircontributiontothetotallookuptime,whichin-dicatesthatasmallpercentageoffailurecasesdomi-natesthetotaltime.
ThisweightedCDFshows,forex-ample,thatnoneofthenodescrossesthe0.
5valuebefore1000ms,indicatingthatmorethan50%ofthelookuptimeisspentonlookupstakingmorethan1000ms.
Ifweassumethatawell-behavinglocalnameservercanservecachedresponsesin100ms,thentheguresareevenmoredramatic.
Thisdata,showninTable1,showsthatslowlookupscomprisemostofthelookuptime.
Thesemeasurementsshowthatclient-sideDNSin-frastructureproblemsaresignicantandneedtobeaddressed.
Ifwecanreducetheamountoftimespentontheselongercases,particularlyinthefailuresthatrequirethelocalresolvertoretrytherequest,wecandramati-callyreducethetotallookuptimes.
Furthermore,giventhesharpdifferencebetween"good"and"bad"lookups,wemayalsobeabletoensureamorepredictable(andhencelessannoying)userexperience.
Finally,itisworthnotingthattheseproblemsarenotanartifactofPlanet-Lab–inallcases,weusethesite'slocalnameservers,onwhichhundredsorthousandsofothernon-PlanetLabOSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation2010510152025000306091215182100DNSFailureRate(%)Time(a)lefthand.
eecs.
harvard.
edu0510152025000306091215182100DNSFailureRate(%)Time(b)righthand.
eecs.
harvard.
edu0100200300400500600700800000306091215182100AverageResponseTime(ms)Time(c)planetlab1.
cs.
purdue.
edu0100200300400500600700800000306091215182100AverageResponseTime(ms)Time(d)planetlab2.
cs.
purdue.
eduFigure3:AllnodesatasiteseesimilarlocalDNSbehavior,despitedifferentworkloadsatthenodes.
Shownaboveareoneday'sfailureratesatHarvard,andoneday'sresponsetimesatPurdue.
0102030405060708090000612180006121800FailureRate(%)Time(planetlab1.
cs.
northwestern.
edu)(a)northwestern-10510152025000612180006121800FailureRate(%)Time(miranda.
tkn.
tu-berlin.
de)(b)tu-berlinFigure4:Failuresseeminglycausedbynameserveroverload–inbothcases,thefailurerateisalwayslessthan100%,indicatingthattheserverisoperational,butperformingpoorly.
machinesdepend.
ThePlanetLabnodesatasiteseesim-ilarlookuptimesandfailurerates,despitethefactthattheirotherworkloadsmaybeverydifferent.
ExamplesfromtwositesareshowninFigure3,andwecanseethatthenodesatasiteseesimilarDNSperformance.
Thisobservationfurtherenhancesourclaimthattheproblemsaresite-wide,andnotPlanetLab-specic.
2.
2OriginsoftheClient-SideFailuresWhilewedonothavefullaccesstoalloftheclient-sideinfrastructure,wecantrytoinferthereasonsforthekindsoffailuresweareseeingandunderstandtheirimpactonlookupbehavior.
Absoluteconrmationofthefailureoriginswouldrequiredirectaccesstothename-servers,routers,andswitchesatthesites,whichwedonothave.
Usingvarioustechniques,wecantracesomeproblemstopacketloss,nameserveroverloading,re-sourcecompetitionandmaintenanceissues.
Wediscussthesebelow.
PacketLoss–ThesimplestcausewecanguessisthepacketlossintheLANenvironment.
MostnameserverscommunicateusingUDP,soevenasinglepacketlossei-therasarequestorasaresponsewouldeventuallytriggeraqueryretransmissionfromtheresolver.
Theresolver'sdefaulttimeoutforretransmissionisveseconds,whichmatchessomeofthespikesinFigure1.
PacketlossratesinLANenvironmentsaregenerallyassumedtobeminimal,andourmeasurementsofPrince-ton'sLANsupportthisassumption.
Wesawnopacketlossattwohops,0.
02%lossatthreehops,and0.
09%atfourhops.
Thoughwedidseeburstybehaviorinthelossrate,wherethelossrateswouldstayhighforaminuteatatime,wedonotseeenoughlossestoaccountfortheDNSfailures.
Ourmeasurementsshowthat90%ofPlanetLabnodeshaveanameserverwithin4hops,and70%arewithin2hops.
However,othercontexts,suchascablemodemsordial-upservices,havemorehops[20],andmayhavehigherlossrates.
Nameserveroverloading–Sincemostrequestpacketsarelikelytoreachthenameserver,ournextpossiblecul-pritisthenameserveritself.
Tounderstandtheirbehav-ior,weaskedallnameserversonPlanetLabtoresolvealocalnameonceeverytwosecondsandwemeasuredtheresults.
Forexample,onplanetlab-1.
cs.
princeton.
edu,weaskedforplanetlab-2.
cs.
princeton.
edu'sIPaddress.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation202Figure5:DailyRequestRateforPrinceton.
EDU0100200300400500600700800900100001002003004005006007008009001000NumberofResponses(xxK=receivebuffersize)Requests/secBIND,64KBIND,128KBIND,256KBIND,512KPING,64KFigure6:BIND9.
2.
3vs.
PINGwithburstytrafcInadditiontothepossibilityofcaching,thelocalname-serverismostlylikelytheauthoritativenameserverforthequeriedname,oratleasttheauthoritativeservercanbefoundonthesamelocalnetwork.
InFigure4,weseesomeevidencethatnameserverscanbetemporarilyoverloaded.
Thesegraphscovertwodaysoftrafc,andshowthe5-minuteaveragefailurerate,whereafailureiseitheraresponsetakingmorethanveseconds,ornoresponseatall.
InFigure4(a),thenodeexperiencesnofailuresmostoftimebuta30%to80%failurerateforaboutvehours.
Figure4(b)revealsasitewherefailuresstartduringthestartoftheworkday,graduallyincrease,anddropstartingintheevening.
Itisreasonabletoassumethathumanactivityincreasesinthesehours,andaffectsthefailurerate.
WesuspectthatapossiblefactorinthisoverloadingistheUDPreceivebufferonthenameserver.
Thesebuffersaretypicallysizedintherangeof32-64KB,andincomingpacketsaresilentlydroppedwhenthisbufferisfull.
Ifthesamebufferisalsousedtoreceivetheresponsesfromothernameservers,astheBINDname-serverdoes,thisproblemgetsworse.
Assuminga64KBreceivebuffer,a64bytequery,anda300byteresponse,morethan250simultaneousqueriescancausepacketdropping.
InFigure5,weseetherequestrate(aver-agedover5minutes)fortheauthoritativenameserverforprinceton.
edu.
Evenwithsmoothing,therequestratesareintherangeof250-400reqs/sec,andwecanexpectthatinstantaneousratesareevenhigher.
So,anyactivitythatcausesa1-2seconddelayoftheservercancauserequeststobedropped.
00.
511.
522.
533.
544.
5000612180006121800FailureRate(%)Time(pl1.
unm.
edu)Figure7:Thissiteshowsfailuresinducedbyperiodicactivity.
Inadditiontothehourlyfailurespike,alargerfailurespikeisseenonceperday.
Totestthistheoryofnameserveroverload,wesub-jectedBIND,themostpopularnameserver,toburstytrafc.
Onanotherwiseunloadedbox(Compaqau600,Linux2.
4.
9,1GBmemory),weranBIND9.
2.
3andanapplication-levelUDPpingthatsimulatesBIND.
EachrequestcontainsthesamenamequeryforalocaldomainnamewithadifferentqueryID.
OurUDPpingrespondstoitbysendingaxedresponsewiththesamesizeasBIND's.
Wesendaburstofrequestsfromaclientma-chineandwait10secondstogatherresponses.
Figure6showsthedifferenceinresponsesbetweenBIND9.
2.
3andourUDPping.
Withthedefaultreceivebuffersizeof64KB,BINDstartsdroppingrequestsatburstsof200reqs/sec,andthecapacitylinearlygrowswiththesizeofthereceivebuffer.
OurUDPpingusingthedefaultbufferlosessomerequestsduetotemporaryoverow,butthegraphdoesnotattenbecauseresponsesconsumemin-imalCPUcycles.
Theseexperimentsconrmthathigh-rateburstytrafccancauseserveroverload,aggravatingthebufferoverowproblem.
Resourcecompetition–Somesitesshowperiodicfail-ures,similartowhatisseeninFigure7.
Thesetendtohavespikeseveryhouroreveryfewhours,andsuggestssomeheavyprocessisbeinglaunchedfromcron.
BINDisparticularlysusceptibletomemorypressure,sinceitsmemorycacheisonlyperiodicallyushed.
AnyjobsthatuselargeamountsofmemorycanevictBIND'spages,causingBINDtopagefaultwhenaccessingthedata.
Thefaultscandelaytheserver,causingtheUDPbuffertoll.
Intalkingwithsystemadministrators,wendthatevensiteswithgoodDNSserviceoftenrunmultipleser-vices(somecron-initiated)onthesamemachine.
SinceDNSisregardedasalow-CPUservice,otherservicesarerunonthesamehardwaretoavoidunderutilization.
Itseemsquitecommonthatwhentheseotherserviceshaveburstyresourcebehavior,thenameserverisaffected.
Maintenanceproblems–Anothercommonsourceoffailureismaintenanceproblemswhichleadtoservicein-terruption,asshowninFigure8.
Here,theDNSlookupshowsa100%failureratefor13hours.
Bothname-OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation203020406080100000612180006121800FailureRate(%)Time(planetlab2.
millennium.
berkeley.
edu)Figure8:Thissite'snameserverswereshutdownbeforethenodeshadbeenupdatedwiththenewnameserverinformation.
Theresultwasa13-hourcompletefailureofallnamelookups,untiltheinformationwasmanuallyupdated.
serversforthissitestoppedworkingcausingDNStobecompletelyunavailable,insteadofjustslow.
DNSser-vicewasrestoredonlyaftermanualintervention.
An-othercommoncase,completefailureoftheprimarynameserver,generatesasimilarpattern,withallre-sponsesbeingretriedaftervesecondsandsenttothesecondarynameserver.
3DesignInthissection,wediscussthedesignofCoDNS,anamelookupsystemthatprovidesfasterandmorereliableDNSservicewhileminimizingextraoverhead.
Wealsodiscusstheobservationsthatshapethisapproach.
Usingtrace-drivenworkloads,wecalculatetheoverheadsandbenetsofvariousdesignchoicesinthesystem.
Oneimportantgoalshapesourdesign:oursystemshouldbeincrementallydeployable,notonlybyDNSadministrators,butalsobyindividualusers.
Themainreasonforthisdecisionisthatitbypassesthebureau-craticprocessesinvolvedwithreplacingexistingDNSin-frastructure.
GiventhedifcultywehaveinevengettinginformationaboutlocalDNSnameservers,thechancesofconvincingsystemadministratorstosendtheirlivetrafctoanexperimentalnamelookupserviceseemslow.
Providingamigrationpaththatcoexistswithexist-inginfrastructureallowspeopletheopportunitytogrowcomfortablewiththeserviceovertime.
Anotherimplicationofthisstrategyisthatweshouldaimforminimalresourcecommitments.
Inparticular,weshouldleveragetheexistinginfrastructuredevotedtomakingDNSperformancegenerallyquitegood.
Client-sidenameserversachievehighcachehitratesbydevot-ingmemorytonamecaching,andifwecantakead-vantageoftheexistinginfrastructure,itlessensthecostofdeployment.
Whilecurrentclient-sideinfrastructure,includingnameservers,isnotperfect,itprovidesgoodperformancemostofthetime,anditcanprovideause-fulstartingpoint.
Lowresourceusagealsoreducesthechancesforfailureduetoresourcecontention.
75%80%85%90%95%100%03/2504/0104/0804/15PercentageofHealthyNodesHourlystatistics,2004maxavgminFigure9:Hourly%ofnodeswithworkingnameserversOurusagemodeliscooperative,operatingsimilarlytoinsurance–nodesjoinapoolthatsharesresourcesintimesofneed.
Ifanode'slocallookupperformanceisacceptable,itproceedsasusual,butmayhavetoprovideservicetonodesthatarehavingproblems.
Whenitslo-calperformancedegrades,itcanaskothernodestohelpit.
Thebenetofjoiningistheabilitytogethelpwhenneeded,evenifthereissomeoverheadatothertimes.
3.
1Cross-siteCorrelationofDNSFailuresThe"insurance"modeldependsonfailurebeingrela-tivelyuncorrelated–thesystemmustalwayshaveasuf-cientpoolofworkingparticipantstohelpthosehavingtrouble.
Iffailureacrosssitesiscorrelated,thisassump-tionisviolated,andacooperativelookupschemeislessfeasible.
Totestourassumption,westudythecorrela-tionofDNSlookupfailuresacrossPlanetLab.
Ateveryminute,werecordhowmanynodeshave"healthy"DNSperformance.
Wedenehealthyasshowingnofailuresforoneminuteforthelocaldomainnamelookuptest.
Usingtheper-minutedataforMarch2004,weshowtheminimum,averageandmaximumnumberofnodesavail-ableperhour.
Thepercentageofhealthynodes(asafrac-tionoflivenodes)isshowninFigure9.
Fromthisgraph,wecanseesomeminorcorrelationinfailures,shownasdownwardspikesinthepercentageofavailablenodes,butmostofthevariationinavailabil-ityseemslargelyuncorrelated.
AninvestigationintothespikesrevealsthatmanynodesonPlanetLabarecong-uredtousethesamesetofnameservers,especiallythosecolocatedatInternet2backbonefacilities(nottobecon-fusedwithInternet2-connecteduniversitysites).
Whenthesenameserversexperienceproblems,thecorrelationappearslargeduetothenumberofnodesaffected.
Moreimportant,however,istheobservationthatthefractionofhealthynameserversisalwayshigh,generallyabove90%.
ThisobservationprovidesthekeyinsightforCoDNS–withenoughhealthynameservers,wecanmasklocally-observeddelaysviacooperation.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation204SoftwarePlanetLabPacketfactoryTLDBIND-4.
9.
3+/831.
1%36.
4%55.
9%BIND948.
9%25.
1%34.
0%Other20.
0%38.
5%10.
1%Table2:ComparisonofnameserversoftwareusedbyPlanet-Lab,packetfactorysurveyandtheTLDsurveyToensurethatthesefailuresarenottiedtoanyspecicnameserversoftware,wesurveythesoftwarerunningonthelocalnameserversusedbythePlanetLabnodes(135uniquenameservers)with"chaos"classqueries[14].
WendthattheyaremostlyrunningavarietyofBINDver-sions.
Weobserve11differentBIND9versionstrings,13differentBIND8versionstringsandanumberofhu-morousstrings(includedin"other")apparentlysetbythenameserveradministrators.
Thesemeasurements,showninTable2,areinlinewithtworecentnameserversur-veysconductedbyBradKnowlesin2002[11]andbypacketfactoryin2003[19].
Fromthis,weconcludethatthefailuresarenotlikelytobespecictoPlanetLab'schoicesofnameserversoftware.
3.
2CoDNSThemainideabehindCoDNSistoforwardnamelookupqueriestopeernodeswhenthelocalnameserviceisex-periencingaproblem.
Essentially,thisstrategyappliesaCDNapproachtoDNS–spreadingtheloadamongpeersimprovesthesizeandperformanceofthe"globalcache".
ManyoftheconsiderationsinCDNsystemsapplyinthisenvironment.
Weneedtoconsidertheproximityandavailabilityofanodeaswellasthelocalityofthequeries.
Adifferentconsiderationisthatweneedtodecidewhenitisdesirabletosendremotequeries.
Giventhefactthatmostnamelookupsarefastinthelocalnameserver,sim-plyspreadingtherequeststopeersmightgenerateunnec-essarytrafcwithnogaininlatency.
Worse,theextraloadmaycausemarginalDNSnameserverstobecomeoverloaded.
Weinvestigateconsiderationsfordecidingwhentosendremotequeries,howmanypeerstoinvolve,andwhatsortsofgainstoexpect.
Topreciselydeterminetheeffectsoflocality,load,andproximityisdifcult,sincewehavenocontroloverthenameserversandhavelittleinformationabouttheirworkloads,congurations,etc.
TheproximityofapeerserverisimportantinthatDNSresponsetimecanbeaf-fectedbyitspeertopeerlatency.
SincetheDNSrequestsandresponsesarenotlarge,wearemoreinterestedinpickingnearbypeerswithlowround-triplatencyinsteadofnodeswithparticularlyhighbandwidth.
Wehaveob-servedcoast-to-coastround-trippingtimesof80msinCoDeeN,withregionaltimesinthe20msrange.
BothoftheserangesaremuchlowerthantheDNStimeoutvalueofveseconds,so,intheory,anynodewouldbeanac-ceptablepeer.
Inpractice,choosingcloserpeerswillre-ducethedifferencebetweencachehittimesandremotepeertimes,makingCoDNSfailuremaskingmoretrans-parent.
Forrequestlocality,wewouldliketoincreasethechancesofremotequeriesbeingcachehitsintheremotenameservers.
Usinganyschemethatconsistentlyparti-tionsthisworkloadwillhelpreducecachepollution,andincreasethelikelihoodofcachehits.
TounderstandtherelationshipbetweenCoDNSre-sponsetimes,thenumberofpeersinvolved,andthepoli-ciesfordeterminingwhenrequestsshouldbesentre-motely,wecollected44,486uniquehostnamesfromoneday'sHTTPtrafconCoDeeNandsimulatedvariouspoliciesandtheireffects.
WereplayedDNSlookupsofthosenamesat77PlanetLabnodeswithdifferentnameservers,startingrequestsatthesametimeofdayintheoriginallogs.
Thereplayhappenedonemonthaf-terthedatacollectionstoavoidlocalnameservercacheswhichcouldskewthedata.
Duringthistime,wealsouseapplication-levelheartbeatmeasurementsbetweenallpairsofnodestodeterminetheirround-triplatencies.
SinceallofthenodesaredoingDNSlookupsataboutthesametime,byaddingtheresponsetimeatpeerYtothetimespentfortheheartbeatfrompeerXtopeerY,wewillgettheresponsetimepeerXcangetifitaskspeerYforaremoteDNSlookupforthesamehostname.
Aninterestingquestionishowmanysimultaneouslookupsareneededtoachieveagivenaverageresponsetimeandtoreducethetotaltimespentonslowlookups(denedastakingmorethan1second).
Asshownintheprevioussection,itisdesirabletoreducethenumberofslowresponsestoreducethetotallookuptime.
Fig-ures10and11showtwographsansweringthisques-tion.
Thelookupschemehereistocontactthelocalnameserverrstforanamelookup,waitforatimeoutandissuex-1simultaneouslookupsusingx-1randomly-selectedpeernodes.
Figures10showsthatevenifweuseonlyoneextralookup,wecanreducetheaveragere-sponsetimebymorethanhalf.
Also,beyondaboutvepeers,addingmoresimultaneouslookupsproducesdi-minishingreturns.
Differentinitialtimeoutvaluesdonotproducemuchdifferenceinresponsetimes,becausethebenetlargelystemsfromreducingthenumberofslowlookups.
Theslowresponseportiongraphprovesthisphenomenon,showingsimilarreductionintheslowre-sponsepercentageatanyinitialtimeoutlessthan700ms.
Wemustalsoconsidertheextraoverheadofthesi-multaneouslookups,sinceshorterinitialtimeoutsandmoresimultaneouslookupscausesmoreDNStrafcatallpeers.
Figure12showstheoverheadintermsofex-tralookupsneededforvariousscenarios.
Mostcurvesstarttoattenata500msinitialtimeout,providingonlydiminishingreturnsforlargertimeouts.
Worthnotingisthatevenwithonepeeranda200msinitialtimeout,wecanstillcuttheaverageresponsetimebymorethanhalf,withonly38%extraDNSlookups.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation20501002003004005006007001248163264AverageResponseTime(ms)#ofSimultaneousLookupsTimeout900msTimeout800msTimeout600msTimeout400msTimeout200msTimeout0msFigure10:AverageResponseTime01020304050607080901248163264%ofTotalTimeinResponses>1sec#ofSimultaneousLookupsTimeout900msTimeout800msTimeout600msTimeout400msTimeout200msTimeout0msFigure11:SlowResponseTimePortion12481602004006008001000AverageNumberofLookupsInitialDelayforRemoteQuery(ms)8extrapeers4extrapeers2extrapeers1extrapeerFigure12:ExtraDNSLookupsTheseresultsareveryencouraging,demonstratingthatCoDNScanbeeffectiveevenatverysmallscale–evenasingleextrasiteprovidessignicantbenets,anditachievesmostofitsbenetswithlessthan10sites.
Thereasonsforthisscalebeingimportantistwofold:onlysmallcommitmentsarerequiredtotryaCoDNSdeploy-ment,andDNS'slimitationswithrespecttotrustandver-ication(discussedinthenextsection)areunlikelytobeanissueatthesescales.
3.
3Trust,Verication,andImplicationsSomeaspectsofDNSanditsdesigninvariablyimpactourapproach,andthemostimportantistrustandveri-cation.
Thecentralissueiswhetheritispossibleforarequestortodeterminethatitspeerhascorrectlyresolvedtherequest,andthattheresultprovidedisactuallyavalidIPaddressforthegivenname.
Thisissuearisesifpeerscanbecompromisedorareotherwisefailing.
Unfortunately,webelievethatageneralsolutiontothisproblemisnotpossiblewiththecurrentDNS,thoughcertainfaultmodelsaremoreamenabletocheckingthanothers.
Forexample,ifthesecuritymodelassumesthatatmostonepeercanbecompromised,itmaybepossi-bletoalwayssendremoterequeststoatleastthreepeers.
Whenthesenodesrespond,iftworesultsagree,thentheanswermustbecorrect.
However,DNSdoesnotman-datethatanyoftheseresultshavetoagree,makingthegeneralcaseofvericationimpossible.
Manyserver-sideDNSdeploymentsusetechniquestoimproveperformance,reliability,orbalanceloadandlo-cality.
Forexample,round-robinDNScanreturnre-sultsfromalistofIPaddressesinordertodistributeloadacrossasetofservers.
Geography-basedredirectioncanbeusedtoreduceround-triptimesbetweenclientsandserversbyhavingDNSlookupsresolvetocloserservers.
Finally,DNS-basedcontentdistributionnet-workswilloftenincorporateloadbalancingandlocal-ityconsiderationswhenresolvingtheirDNSnames.
Inthesecases,multiplelookupsmayproducedifferentre-sults,andlookupsfromdifferentlocationsmayreceiveresultsfromdifferentpoolsofIPaddresses.
WhileitwouldbepossibletoimagineextendingDNSsuchthateachnameisassociatedwithapublickey,andeachIPaddressresultissignedwiththiskey,suchachangewouldbesignicant.
DNSSEC[6]attemptssmaller-scalechange,mainlytopreventDNSspoong,buthasbeeninsomeformofdevelopmentfornearlyadecade,andstillhasnotseenwide-scaleadoption.
Giventhecurrentimpossibilityofverifyingalllookups,werelyontrustingpeersinordertosidesteptheproblemsmentioned.
Thisapproachisalreadyusedinvariousschemes.
Nameownersoftenuseeachotherastheirsecondaryservers,sometimesatlargescale.
Forex-ample,princeton.
edu'sDNSserversactasthesecondaryserversfor60non-Princetondomains.
BINDsupportszonetransfers,whereallDNSinformationcanbedown-loadedfromanothernode,specicallyforthiskindofscenario.
Similarly,large-scaledistributedsystemsrun-ningathostingcentersalreadyhaveatrustrelationshipinplacewiththeirhostingfacility.
4ImplementationWehavebuiltaprototypeofCoDNSandhavebeenrunningitonallnodesonPlanetLabforroughlyeightmonths.
Duringthattime,wehavebeendirectingtheCoDeeNCDN[23]touseCoDNSforthenamelookup.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation206CoDNSconsistsofastand-alonedaemonrunningoneachnode,accessibleviaUDPforremotequeries,andvialoopbackTCPforlocally-originatednamelookups.
Thedaemonisevent-driven,andisimplementedasanon-blockingmasterprocessandmany(blocking)slaveprocesses.
Themasterprocessreceivesnamelookupre-questsfromlocalclientsandremotepeers,andpassesthemtooneofitsidleslaves.
Aslaveprocessresolvesthosenamesbycallinggethostbyname()andsendstheresultbacktothemaster.
Then,themasterreturnsthenalresulttoeitheralocalclientoraremotepeerdependingonwhereitoriginated.
Queriesresolvingthesamehostnamearecoalescedintoonequeryandansweredtogetherwhenresolved.
Preferenceforidleslavesisgiventolocally-originatedrequestsoverremotequeriestoensuregoodperformanceforlocalusers.
Themasterprocessrecordseachrequest'sarrivaltimefromlocalclientsandsendsaUDPnamelookupquerytoapeernodewhentheresponsefromtheslavehasnotreturnedwithinacertainperiod.
Thisdelayisusedasaboundaryfordecidingifthelocalnameserverisslow.
Intheeventthatneitherthelocalnameservernortheremotenodehasresponded,CoDNSdoublesthedelayvaluebe-foresendingthenextremotequerytoanotherpeer.
Intheprocess,whicheverresultthatcomesrstwillbede-liveredastheresponseforthenamelookuptotheclient.
Peersmaysilentlydropremotequeriesiftheyareover-loaded,andremotequeriesthatfailtoresolvearealsodiscarded.
Slavesmayadddelayiftheyreceivealocally-generatedrequestthatfailstoresolve,withthehopethatremotenodesmaybeabletoresolvesuchnames.
4.
1RemoteQueryInitiation&RetriesTheinitialdelaybeforesendingtherstremotequeryisdynamicallyadjustedbasedontherecentperformanceoflocalnameserversandpeerresponses.
Ingeneral,whenthelocalnameserverperformswell,weincreasethede-laysothatfewerremotequeriesaresent.
Whenmostremoteanswersbeatthelocalones,wereducethedelaypreferringtheremotesource.
Specically,ifthepast32namelookupsareallresolvedlocallywithoutusinganyremotequeries,thentheinitialdelayissetto200msbydefault.
Wechoose200msbecausethemedianresponsetimeonawell-functioningnodeislessthan100ms[9],so200msdelayshouldrespondfastduringinstability,whilewastingminimalamountofextraremotequeries.
However,torespondquicklytolocalnameserverfail-ure,iftheremotequerywinsmorethan50%ofthelast16requests,thenthedelayissetto0ms.
Thatis,theremotequeryissentimmediatelyastherequestarrives.
Ourtestresultsshowitisrarenottohavefailurewhenmorethan8outof16requeststakemorethan300mstoresolve,sowethinkitisreasonabletobelievethelocalnameserverishavingaprobleminthatcase.
Oncetheimmediatequeryissent,thedelayissettotheaverageresponsetimeofremotequeryresponsesplusonestan-darddeviation,toavoidswampingfastremoteservers.
4.
2Proximity,LocalityandAvailabilityEachCoDNSnodegathersandmanagesasetofneigh-bornodeswithinareasonablelatencyboundary.
WhenaCoDNSinstancestarts,itsendsaheartbeattoeachnodeinthepreconguredCoDNSnodelisteverysecond.
Theresponsecontainstheroundtriptime(RTT)andtheav-erageresponsetimeofthelocalnameserveratthepeernode,reectingtheproximityandtheavailabilityofthepeernode'snameserver.
Thetop10nodeswithdifferentnameserversarepickedasneighborsbycomparingthesumwithallnodes.
Livenessofthechosenneighborsisperiodicallycheckedtoseeiftheserviceisstillavail-able.
Oneheartbeatissenteachsecond,soweguaranteetheavailabilityin10secondgranularity.
Deadnodesarereplacedwiththenextbestnodeinthelist.
Amongtheseneighbornodes,onepeerischosenforeachremotenamelookupusingtheHighestRandomWeight(HRW)hashingscheme[22].
HRWconsistsofhashingthenodenamewiththelookupname,andthenchoosingthenodenamewiththesmallestresultinghashvalue.
BecauseHRWconsistentlypicksthesamenodeforthesamedomainname,thisprocessenhancesrequestlocalityforremotequeries.
Anotherdesirablepropertyofthisapproachisthatsomerequestlocalityispreservedaslongasneighborsetshavesomeoverlap.
Fulloverlapisnotrequired.
Thenumberofneighborsiscongurableaccordingtothedistributionofnodes.
Inthefuture,wewillmakeCoDNSdynamicallyndthepeernodesnotdependingonthepreconguredsetofnodes.
OnepossiblesolutionistomakeeachCoDNSnodeadvertiseitsneighborsetandhaveafewwellknownnodes.
Then,anewCoDNSnodewithnoinformationaboutavailableCoDNSpeernodescanaskthewellknownnodesfortheirpeernodesandrecursivelygatherthenodesbyaskingeachneighboruntilitndsareasonablepoolofCoDNSnodes.
Notethatourneighbordiscoverymechanismsarees-sentiallyadvisoryinnature–oncethenodehasenoughpeers,itonlyneedstopollothernodesinordertohaveareasonablesetofcandidatesincaseoneofitsexistingpeersbecomesunavailable.
Intheeventthatsomesiteshaveenoughpeerstomakethispollingascalabilityis-sue,eachnodecanchoosetopollanearbysubsetofallpossiblepeerstoreducethebackgroundtrafc.
4.
3Policy&TunabilityInthefuture,weexpectCoDNSnodepolicywillbecomeaninterestingresearcharea,giventhetradeoffsbetweenoverheadandlatency.
Wehavemadechoicesforinitialdelayandretrybehaviorforourenvironment,andwebe-lievethatthesechoicesaregenerallyreasonable.
How-ever,somesystemsmaychoosetotuneCoDNStohaveOSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation20701000200030004000500060007000000306091215182100AverageResponseTime(ms)Time(a)LocalDNS01000200030004000500060007000000306091215182100AverageResponseTime(ms)Time(b)CoDNSFigure13:Minute-levelAverageResponseTimeforOneDayonplanetlab1.
cs.
cornell.
edu0.
30.
40.
50.
60.
70.
80.
911.
1110100100010000100000CDFResponseTime(ms)LDNSCoDNS(a)ResponseTimeCDF00.
10.
20.
30.
40.
50.
60.
70.
80.
911.
1110100100010000100000WeightedCDFResponseTime(ms)LDNSCoDNS(b)TotalTimeCDFFigure14:CDFandWeightedCDFforOneWeekonplanet-lab1.
cs.
cornell.
edu,LDNS=localDNSmuchloweroverhead,atthecostofsomelatencybene-t.
Inparticular,systemsthatwanttouseitonlytoavoidsituationswherealllocalnameservershavefailedcoulduseaninitialdelaythresholdofseveralseconds.
Inthiscase,ifthelocalnameserverrepeatedlyfailstoresolverequestsinmultipleseconds,theinitialdelaywilldroptozeroandalllookupswillbehandledremotelyforthedurationoftheoutage.
SitesmayalsochoosetolimitCoDNSoverheadtoaspeciclevel,whichwouldturnparameterchoicesintoanoptimizationproblem.
Forexample,itmayberea-sonabletoaskquestionsoftheform"whatisthebestlatencyachievablewithamaximumremotelookuprateof10%"Ourtrace-drivensimulationsgivesomeinsightintohowtomakethesechoices,butitmaybedesirabletohaveanonlinesystemautomaticallyadjustparametervaluescontinuouslyinordertomeettheseconstraints.
Weareinvestigatingpoliciesforsuchscenarios.
4.
4BootstrappingCoDNShasabootstrappingproblem,sinceitmustre-solvepeernamesinordertooperate.
Inparticular,whenthelocalDNSserviceisslow,resolvingallpeernamesbeforestartingwillincreaseCoDNS'sstarttime.
So,CoDNSbeginsoperationimmediately,andstartsresolv-ingpeernamesinthebackground,whichgreatlyreducesitsstarttime.
ThebackgroundresolverusesCoDNSit-self,soassoonasasingleworkingpeer'snameisre-solved,itcanthenquicklyhelpresolveallotherpeernames.
Withthisbootstrappingapproach,CoDNSstartsvirtuallyinstantaneously,andcanresolveall350peernamesinlessthan10seconds,evenforslowlocalDNS.
AspecialcaseofthisproblemisstartingwhenlocalDNSiscompletelyunavailable.
Inthiscase,CoDNSwouldbeunabletoresolveevenanypeernames,andcouldnotsendremotequeries.
CoDNSperiodicallystoresallpeerinformationondisk,andusesthatinformationatstartup.
ThisleisshippedwithCoDNS,allowingoper-ationevenonnodesthathavenoDNSsupportatall.
5Evaluation/LiveTrafcTogaugetheeffectivenessofCoDNS,wecompareitsbehaviorwithlocalDNSonCoDeeN'slivetrafcus-ingavarietyofmetrics.
CoDeeNreceives5-7millionrequestsdailyfromaworld-wideclientpopulationof7-12Kusers.
TheseusershaveexplicitlyspeciedCoDeeNproxiesintheirbrowser,soalloftheirWebtrafcisdi-rectedthroughCoDeeN.
TheCoDeeNproxiesmaintaintheirownDNScaches,soonlyuncachedDNSnamescauselookups.
Toeliminatethepossiblecachingef-fectonanameserverfromotheruserssharingthesameserver,wemeasurebothtimesonlyinCoDNS,usingtheslavestoindicatelocalDNSperformance.
CoDNSeffectivelyremovesthespikesintheresponsetime,andprovidesmorereliableandpredictableser-vicefornamelookups.
Figure13comparesper-minuteaverageresponsetimesoflocalDNSandCoDNSforCoDeeN'slivetrafcforonedayononePlanetLabnode.
WhilelocalDNSshowsresponsetimespikesof7sec-onds,CoDNSneverexceeds0.
6seconds.
Thebenetstemsfromredirectingslowlookupstoworkingpeers.
ThegreaterbenetofCoDNSliesinreducingthefre-quencyofslowresponses.
Figure14showsaCDFandaweightedCDFfornamelookupresponsedistributionforthesamenodeforoneweek.
TheCDFgraphshowsthattheresponsedistributioninbothschemesisalmostsimilaruntilthe90thpercentile,butCoDNSreducesthelookupstakingmorethan1000msfrom5.
5%to0.
6%.
ThisreductiongivesmuchbenetintotallookuptimeintheweightedCDF.
ItshowsCoDNSnowspends18%oftotaltimeinlookupstakingmorethan1000ms,whilelocalDNSstillspends75%ofthetotaltimeonthem.
Thisimprovementiswidespread–Figure15(a)showsthestatisticsof95CoDeeNnodesforthesameperiod.
Theaveragenumberoftotallookupspernodeis22,208,rangingfrom12,119to131,466pernode.
TheaverageresponsetimeinCoDNSis60-221ms,whilethatoflocalDNSis113-935ms.
Inallcases,CoDNS'sresponseisOSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation208010020030040050060070080090010000102030405060708090AverageResponseTime(ms)NodesSortedbyLDNSResponseTimeLDNSCoDNS(a)AverageResponseTime01020304050607080900102030405060708090PercentageofResponseTime>1secNodesSortedbyLDNSValueLDNSCoDNS(b)SlowResponseTimeportionFigure15:LiveTrafcforOneWeekontheCoDeeNNodes,LDNS=localDNS02004006008001000120014001600180020000510152025303540AverageResponseTime(ms)Non-Internet2NodesSortedbyLDNSResponseTimeLDNSCoDNS(a)AverageResponseTime01020304050607080900510152025303540PercentageofResponseTime>1secNon-Internet2NodesSortedbyLDNSValueLDNSCoDNS(b)SlowResponseTimePortionFigure16:Non-Internet-2Nodes,LDNS=localDNSfaster,rangingfromafactorof1.
37to5.
42.
Figure15(b)showsthepercentageofslowresponsesinthetotalre-sponsetime.
CoDNSagainreducestheslowresponse'sportiondramaticallytolessthan20%ofthetotallookuptimeinmostcases,deliveringmorepredictableresponsetime.
Incontrast,localDNSspends37%to85%ofthetotaltimeintheslowqueries.
5.
1Non-Internet2BenetsSincemostCoDeeNsitesarehostedatNorthAmeri-canuniversitieswithInternet2(I2)connectivity,onemaysuspectthatlow-congestionI2peerlinksareresponsi-bleforourbenets.
Toaddressthisissue,wepicknon-I2PlanetLabnodesandreplay10,792uniquelookupsofhostnamesfromoneday'slivetrafconaCoDeeNproxy.
Figure16(a)showsthatCoDNSprovidessimilarbeneton38non-I2nodesaswell.
TheaverageresponsetimeinCoDNSrangesfrom63msto350ms,whilelocalDNSis113msto1884ms,animprovementoffactorof1.
64to9.
52.
Figure16(b)showsthatCoDNSgreatlyreducestheslowresponseportionaswell–CoDNSgen-erallyspendslessthan10%ofthetotaltimeinthisrange,whilelocalDNSstillspends32%to90%.
5.
2CDNEffectCoDNSreplacesslowlocalresponseswithfastremoteresponses,whichmayimpactDNS-basedCDNs[1]thatresolvenamesbasedonwhichDNSnameserversendsthequery.
CoDNSmayreturntheaddressofafarreplicawhenitusesapeer'snameserverresult.
Weinvestigatethisissuebytesting14popularCDNusersincludingAp-ple,CNN,andtheNewYorkTimes.
WemeasuretheDNSanddownloadtimeofURLsforthelogoimageleonthosewebsites,andcomparelocalDNSandCoDNSwhentheirresponsesdiffer.
SinceCoDNSisusedonlywhenthelocalDNSissloworfailing,itshouldcomeasnosurprisethatthetotaltimeforCDNcontentisstillfasteronCoDNSwhentheydif-ferinreturnedIPaddress.
TheDNStimegainandthedownloadingtimepenaltypresentedinthedifferencebe-tweenlocalandremoteresponsetimeisshowninFig-ure17(a).
WhenlocalDNSisslow,CoDNScombinedwithapossiblysub-optimalCDNnodeisamuchbetterchoice,withthegainfromfasternamelookupsdwarngthesmalldifferenceindownloadtimeswhenanydiffer-enceexists.
Ifweisolatethedownloadingtimediffer-encebetweentheDNS-providedCDNnodeversustheOSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation209110100100010000100000020406080100120140LatencyDifference(ms)NodesSortedbyDNSTimeDifferenceDNSGain(L-R)DownloadPenalty(R-L)(a)DNSLookupTimeGainvs.
DownloadingTimePenalty00.
10.
20.
30.
40.
50.
60.
70.
80.
91-400-2000200400600800CDFDownloadTimePenalty(R-L,ms)(b)CumulativeDistributionofDownloadingTimeDifferenceFigure17:CDNEffectforwww.
apple.
com,L=LocalResponseTime,R=RemoteResponseTime,DNSgain=LocalDNStime-CoDNStime,Downloadpenalty=downloadtimeofCoDNS-providedIP-downloadtimeofDNS-providedIP,showninlogscale.
NegativepenaltiesindicateCoDNS-providedIPisfaster,andarenotshownintheleftgraph.
CoDNS-providedCDNnode,wegetFigure17(b).
Sur-prisingly,almostathirdoftheCoDNS-providednodesarecloserthantheirDNScounterparts,and83%ofthemshowlessthana100msdifference.
ThismatchestheCDN'sstrategytoavoidnotablybadserversinsteadofchoosingtheoptimalserver[8].
ResultsforotherCDNvendorsaresimilar.
5.
3ReliabilityandAvailabilityCoDNSdramaticallyimprovesDNSreliability,mea-suredbythelocalnameserveravailability.
Toquantifythiseffect,wemeasuredtheavailabilityofnamelookupsforonemonthacrossallCoDeeNnodes,withandwith-outCoDNS.
Weassumethatanameserverisavailableunlessitfailstoanswerrequests.
Ifitfails,weconsidertheperiodsoftimewhennorequestswereansweredasitsunavailability.
Eachperiodiscappedatamaximumofveseconds,andthetotalunavailabilityismeasuredasthesumoftheunavailableperiods.
Thisdata,showninFigure18,ispresentedusingthereliabilitymetricof"9's"ofavailability.
RegularDNSachieves99%avail-abilityonabout60%ofthenodes,whichmeansroughly14minutesperdayofnoservice.
Incontrast,CoDNSisabletoachieveover99.
9%availabilityonover70%ofnodes,reducingdowntimestolessthan90secondsperday.
Onsomenodes,theavailabilityapproaches99.
99%,orroughly9secondsofunavailabilityperday.
CoDNSprovidesroughlyanadditional'9'ofavailability,withoutanymodicationstothelocalDNSinfrastructure.
5.
4OverheadAnalysisToanalyzeCoDNS'soverhead,weexaminetheremotequerytrafcgeneratedbytheCoDeeNliveactivity.
Forthisworkload,CoDNSissued11%to85%oftheto-tallookupsasremotequeries,asshowninFigure19.
Thevariationreectsthehealthofthelocalnameserver,andlessstablenameserversrequiremoreremotequeriesfromCoDNS.
Ofthesixnodesthathadmorethan50%9909999.
999.
990102030405060708090100Availability(%)NodesSortedbyAvailabilityCoDNSLDNSFigure18:AvailabilityofCoDNSandlocalDNS(LDNS)remotequeries,allexperiencedcompletenameserverfailureatsomepoint,duringwhichremotequeriesin-creasedtoover100%ofthelocalrequests.
Theseperiodsskewtheaverageoverhead.
WebelievethattheadditionalburdenonnodeswithworkingDNSistolerable,duetothecombinationofourlocality-consciousredirectionandalreadyhighlo-calnameserverhitrates.
Usingourobservedmedianoverheadof25%andalocalhitrateof80%-87%[9],thelocalDNSwillincuronly3.
25-5.
00%extraout-boundqueries.
Sinceremotequeriesareredirectedonlytolightlyloadednodes,webelievetheextralookupswillbetolerableonthepeernode'slocalnameserver.
Wealsonotethatmanyremotequeriesarenotan-swered,withFigure19showingthisnumbervariesfrom6%to31%.
ThesecanbeduetoWANpacketlosses,unresolvablenames,andremotenoderate-limiting.
CoDNSnodesdropremoterequestsiftoomanyarequeued,whichpreventsapossibledenialofserviceat-tack.
CoDNSpeersneverreplyiftherequestisunre-solvable,sincetheirownlocalDNSmaybefailing,andsomeotherpeermaybeabletoresolvethename.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation21001020304050607080900102030405060708090PercentageNodesSortedbyNumberofRemoteQueriesSentAnsweredWinFigure19:AnalysisforRemoteLookups75808590951001050102030405060708090PercentageNodesSortedbyWin-by-1Win-by-3Win-by-2Win-by-1Figure20:Win-by-NforRemoteLookupsThequeriesinwhichCoDNS"wins",bybeatingthelocalDNS,constitute2%to57%ofthetotalrequests.
Onaverage,9%oftheoriginalquerieswereansweredbytheremoteresponses,removing47%oftheslowre-sponseportioninthetotallookuptimeshownintheFig-ure15(b).
Ofthewinningremoteresponses,morethan80%wereansweredbycontactingtherstpeer,speciedas"win-by-1"inFigure20.
Ofallwinningresponses,95%areresolvedbytherstorsecondpeer,andonlyasmallnumberrequirecontactingthreeormorepeers.
ThisinformationcanbeusedtofurtherreduceCoDNS'soverheadbyreducingthenumberofpeerscontacted–ifithasnotbeenresolvedwithintherstthreepeers,thenfurtherattemptsareunlikelytoresolveit,andnomorepeersshouldbecontacted.
Wemayexplorethisopti-mizationinthefuture,butourcurrentoverheadsarelowenoughthatwehavenopressingneedtoreducethem.
Intermsofextranetworktrafcgeneratedforremotequeries,eachquerycontainsabout300bytesofarequestandaresponse.
Onaverage,eachCoDNSonaCoDeeNnodehandles414to10,287requestsperdayduringtheweekperiod,amountingto243KBto6027KB.
CoDNSalsoconsumesheartbeatmessagestomonitorthepeerseachsecond,whichcontains32bytesofdata.
Insum,eachCoDNSonaCoDeeNnodeconsumesonaverage7.
5MBofextranetworktrafcperday,consumingonly0.
2%oftotalCoDeeNtrafcinrelativeterms.
5.
5ApplicationBenetsByusingCoDNS,CoDeeNobtainsotherbenetsinca-pacityandavailability,andthesemayapplytootherap-plicationsaswell.
ThecapacityimprovementscomefromCoDeeNbeingabletousenodesthatarevirtu-allyunusableduetolocalDNSproblems.
Atanygiventime,roughly10ofthe100PlanetLabnodesthatrunCoDeeNareexperiencingsignicantDNSproblems,rangingfromhighfailureratestocompletefailureoftheprimary(andevensecondary)nameservers.
CoDeeNnodesnormallyreporttheirlocalstatustoeachother,andbeforeCoDNS,thesenodeswouldtellothernodestoavoidthemduetotheDNSproblems.
WithCoDNS,thesenodescanstillbeused,providinganadditional10%extracapacity.
Theavailabilityimprovementscomefromreducingstartuptime,whichcanbedramaticonsomenodes.
CoDeeNsoftwareupgradesarenotannounceddown-times,becauseonnodeswithworkinglocalDNS,CoDeeNnormallystartsin10-15seconds.
Thisstartupprocessisfastenoughthatfewpeoplenoticeaservicedisruption.
PartofthistimeisspentinresolvingthenamesofallCoDeeNpeers,andwhentheprimaryDNSserverisfailing,eachlookupnormallyrequiresoverveseconds.
For120peers,thisraisesthestartuptimetoover10minutes,whichisanoticeableserviceoutage.
IfCoDNSisalreadyrunningonthenode,startuptimesarevirtuallyunaffectedbylocalfailure,sinceCoDNSisalreadysendingallqueriestoremoteserversinthisen-vironment.
IfCoDNSstartsconcurrentlywithCoDeeN,thestartuptimeforCoDeeNisroughly20seconds.
6OtherApproaches6.
1PrivateNameserversSincelocalnameserversexhibitoverload,onemaybetemptedtorunaprivatenameserveroneachmachine,andhaveitcontacttheglobalDNShierarchydirectly.
Thisapproachismorefeasibleasabackupmechanismthanasaprimarynameserverforseveralreasons.
Usingsharednameserversreducesmaintenanceissues,andthesharedcachecanbelargerthanindividualcaches.
Notonlydoescacheeffectivenessincreaseduetocapacity,butthecompulsorymisseswillalsobereducedfromthesharing.
Withincreasedcachemisses,theglobalDNSfailureratebecomesmoreofanissue,sousingprivatenameserversmayreduceperformanceandreliability.
Asabackupmechanism,thisapproachispossible,buthasthedrawbackscommontoanyinfrequently-usedsys-tem.
Ifitisnotbeingexercisedregularly,failureislesslikelytobenoticed,andthesystemmaybeunavailablewhenitisneededmost.
Italsoconsumesresourceswhennotinuse,soothertasksonthesamemachinewillbeimpacted,ifonlyslightly.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation2116.
2SecondaryNameserversSincemostsiteshavetwoormorelocalnameservers,anotherapproachwouldbetomodifytheresolverli-brariestobemoreaggressiveaboutusingmultiplename-servers.
Possibleoptionsincludesendingrequeststoallnameserverssimultaneously,beingmoreaggressiveabouttimeoutsandusingthesecondarynameserver,orchoosingwhicheveronehasbetterresponsetimes.
Whilewebelievethatsomeoftheseapproacheshavesomemerit,wealsonotethattheycannotaddressallofthefailuremodesthatCoDNScanhandle.
Inparticular,wehaveoftenseenallnameserversatasitefail,inwhichcaseCoDNSisstillabletoanswerqueriesviatheremotenameservers.
Correlatedfailureoflocalnameserversrenderstheseapproachesuseless,whilecorrelatedfail-ureamonggroupsofremoteserversislesslikely.
Overlyaggressivestrategiesarelikelytobackreinthecaseoflocalnameservers,sincewehaveseenthatoverloadcauseslocalnameserverfailure.
Increasingtherequestratetoafailingserverisnotlikelytoimproveperformance.
Loadbalancingamonglocalnameserversismoreplausible,butstillrequiresmodicationstoallclientsandprograms.
Giventhecostofchanginginfras-tructure,itisperhapsappealingtoadoptatechniquelikeCoDNSthatcoversabroaderrangeoffailures.
Finally,upgradecostandeffortarerealissueswehaveheardfrommanysystemadministrators–secondarynameserverstendtobemachinesthatareagenerationbehindtheprimarynameservers,basedontheexpecta-tionoflowerload.
Increasingtherequestratetothesec-ondarynameserverwillrequireupgradingthatmachine,whereasCoDNSworkswithexistinginfrastructure.
6.
3TCPQueriesAnotherpossiblesolutionistouseTCPinsteadofUDPasawayofcommunicatingwithlocalnameservers.
IfthefailureiscausedbypacketlossesintheLANorsilentpacketdropscausedbyUDPbufferoverow,TCPcanimprovethesituationbyreliabledatadelivery.
Inaddi-tion,theowcontrolmechanisminherentinTCPcanaskthenamelookupclientstoslowdownwhenthename-serverisoverloaded.
AlthoughtheDNSRFC[14]allowstheuseofTCPinadditiontoUDP,inpractice,TCPisusedonlywhenhandlingAXFRqueriesforthezonetransferorwhentherequestedrecordsetisbiggerthan512bytes.
ThereasonwhyTCPisnotfavoredinnamelookupsismainlybe-causeoftheadditionaloverhead.
IfaTCPconnectionisneededforeveryquery,itwouldenduphandlingninepacketsinsteadoftwo:threetoestablishtheconnection,twofortherequest/response,andfourtoteardowntheconnection.
ApersistentTCPconnectionmightremovetheper-queryconnectionoverhead,butitalsoneedstoconsumeoneortwoextranetworkpacketsforACKs.
00.
10.
20.
30.
40.
50.
60.
70.
80.
911632641282565121024FractionofNodes(CDF)AverageResponseTime(ms)CoDNSPersistentTCPUDPSimpleTCPFigure21:ComparisonofUDP,TCP,andCoDNSlatenciesAlso,thereisanotherissueofreclaimingtheidlecon-nections,sincetheyconsumesystemresourcesandcandegradeperformance.
TheDNSRFC[14]speciestwominutesasacutoffbutinpracticemostserversdiscon-necttheidleconnectionwithin30seconds.
TocomparetheperformancebetweenUDPandTCP,wereplay10,792uniquehostnamesobtainedfromoneday'slivetrafcofaCoDeeNproxyat107PlanetLabnodes.
Carryingoutacompletelyfaircomparisonisdif-cult,sincewecannotissuethesamequeryforallofthematthesametime.
Instead,togivearelativelyfaircomparison,werunthetestforCoDNSrst,andsubse-quentlyrunotherparts,makingallbutCoDNSgetthebenetofcachedresponsesfromthelocalnameserverafterhavingbeenfetchedbyCoDNS.
Figure21showstheCDFoftheaverageresponsetimeforallapproaches.
PersistentTCPandUDPhavecomparableperformance,whilesimpleTCPisnoticeablyworse.
TheCoDNSla-tencies,includedforreference,arebetterthanallthree.
Thereplayscenariodescribedaboveshouldbefavor-abletoTCP,buteveninthisconservativeconguration,CoDNSstillwins.
Figure22(a)showsthatallnodesre-portthatCoDNSis10%to500%fasterthanTCP,con-rmingCoDNSisamoreattractiveoptionthanTCP.
Thelargedifferenceisintheslow-responseportion,whereCoDNSwinsthemostandwhereTCP-basedlookupscannothelp.
Figure22(b)showsthataconsiderableamountoftimeisstillspentonthelongdelayedqueriesinTCP-basedlookups.
CoDNSreducesthistimeby16%to92%whencomparedtotheTCP-basedmeasurement.
ThoughTCPensuresthattheclient'srequestreachesthenameserver,ifthenameserverisoverloaded,itmayhavetroublecontactingtheDNShierarchyforcachemisses.
7RelatedWorkTraditionalDNS-relatedresearchhasfocusedontheproblemsintheserver-sideDNSinfrastructure.
AsaseminalstudyinDNSmeasurement,Danzigetal.
foundthatalargenumberofnetworkpacketswerebeingwastedduetoDNStrafc,blamingnameserversoftwarebugsandmiscongurationsasmajorculprits[5].
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation2120100200300400500600700800900020406080100AverageResponseTime(ms)NodesSortedbyPersistentTCP'sResponseTimePersistentTCPCoDNS(a)AverageResponseTime020406080100020406080100PercentageofResponseTime>1secNodesSortedbyPersistentTCP'sValuePersistentTCPCoDNS(b)SlowResponseTimePortionFigure22:CoDNSvs.
TCPSincethen,bugsintheresolversandnameservershavebeenreduced[12],butrecentmeasurementsshowthatthereisstillmuchroomforimprovement.
In2000,Willsetal.
[24]andHuitemaetal.
[7]reported29%ofDNSlookupstakeover2seconds,andCohenetal.
[3]re-ported10%oflookupsexceedmorethan3seconds.
Jungetal.
alsopresentdataindicating23%ofallserver-sidelookupsreceivenoresults,indicatingtheproblemsofimpropercongurationsandincorrectnameserversstillpersist[9].
Theymeasuretheclient-sideperformanceintermsofresponsetimeandcachinghitratioaswell.
However,thatworkdoesnottracetheoriginsofnamelookupdelaysfromtheclient-side,concentratingonlyonthewide-areaDNStrafc.
Giventhefactthatlocalnameservercachehitratiosare80%-87%[9,24],evenasmallprobleminthelocalnameserveranditsenviron-mentcanskewthelatencyofalargenumberoflookups.
Ourstudyaddressesthisproblem.
Listonetal.
indirectlyprovidesomeevidenceoflocalnameserverproblemsbyattributingthemajorsourcesofresponsetimedelaytoendnameserversratherthantheroot/gTLDservers[13].
Theresearchcommunityhasrecentlyreneweditsfo-cusonimprovingserver-sideinfrastructure.
Coxetal.
investigatethepossibilityoftransformingDNSintoapeer-to-peersystem[4]usingadistributedhashta-ble[21].
TheideaistoreplacethehierarchicalDNSnameresolvingprocesswithaatpeer-to-peerquerystyle,inpursuitofloadbalancingandrobustness.
Withthisdesign,themiscongurationsfrommistakesbyad-ministratorscanbeeliminatedandthetrafcbottleneckontherootserversareremovedsothattheloadisdis-tributedovertheentitiesjoiningthesystem.
InCoDoNS,Ramasubramanianetal.
improvethepoorlatencyperformanceofthisapproachbyusingproactivereplicationofDNSrecords[18].
TheyexploittheZipf-likedistributionofthedomainnamesinwebbrowsing[2]toreducethereplicatingoverheadwhileprovidingO(1)proximity[17].
Ourapproachesdifferinseveralimportantaspects–weattempttoreduceover-lappinginformationincaches,inordertomaximizetheoverallaggregatecachesize,whiletheyusereplicationtoreducelatency.
Ourdesireforasmallprocessfoot-printstemsfromourobservationthatmemorypressureisoneofthecausesofcurrentfailuresinclient-sideinfras-tructure.
Whiletheirsystemappearsnottobedeployedinproduction,theyperformanevaluationusingaDNStracewithaZipffactorabove0.
9[18].
Incomparison,ourevaluationofCoDNSusesthelivetrafcgeneratedbyCoDeeNafteritsproxieshaveusedtheirlocalDNScaches,sotherequeststreamseenbyCoDNShasaZipffactorof0.
50-0.
55,whichisamoredifcultworkload.
WeintendtocomparetheliveperformanceofCoDNSversusCoDoNSwhenthelattersystementersproduc-tionandismadeavailabletothepublic.
Inanycase,sinceCoDNSdoesnotdependonthespecicsofthenamelookupsystem,weexpectthatitcaninteroperatewithCoDoNSifthelatterprovidesbetterperformancethantheexistingnameserversatPlanetLabsites.
Oneis-suethatwillhavetobeaddressedbyanyproposedDNSreplacementsystemistheuseofintelligentnameserversthatdynamicallydeterminewhichIPaddresstoreturnforagivenname.
ThesenameserversareusedinCDNsandgeographicloadbalancers,andcannotbereplacedwithpurelystaticlookups,suchasthoseperformedinCoDoNS.
SinceCoDNSdoesnotreplaceexistingDNSinfrastructure,wecaninteroperatewiththeseintelligentnameserverswithoutanyproblem.
Kangasharjuetal.
pursueasimilarapproachtoreduc-ingtheDNSlookuplatencybymoreaggressivelyrepli-catingDNSinformation[10].
InspiredbythefacttheentireDNSrecorddatabasetsintothesizeofatypi-calharddiskandwiththerecentemergenceofterrestrialmulticastandsatellitebroadcastsystems,thisschemere-ducestheneedtoquerythedistantnameserversbykeep-OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation213ingtheDNSinformationuptodatebyefcientworld-widereplication.
Thedifferenceinourapproachistotemporarilyusefunctioningnameserversofpeernodes,separatefromtheissueofimprovingtheDNSinfrastructureitself.
Weex-pectthatbenetsinimprovingtheinfrastructure"fromabove"willcomplementour"bottomup"approach.
Oneadvantageofoursystemisthatmiscongurationscanbemaskedwithoutnameserveroutage,allowingadminis-tratorsmoretimetoinvestigatetheproblem.
8ConclusionWehaveshownthatclient-sideinstabilityinDNSnamelookupsiswidespreadandrelativelycommon.
Thefail-urecasesdegradeaveragelookuptimeandincreasethe"tail"ofresponsetimes.
Weshowthatthesefailuresap-peartobecausedbytemporarynameserveroverload,andarelargelyuncorrelatedacrossmultiplesites.
Throughanalysisoflivetrafc,weshowthatasimplepeeringsystemreducesresponsetimesandimprovesreliability.
Usingtheseobservations,wedevelopalightweightnamelookupservice,CoDNS,thatusespeersatre-motesitestoprovidecooperativelookupsduringfailures.
CoDNSoperatesinconjunctionwithlocalDNSname-servers,allowingincrementallydeploymentwithoutsig-nicantresourceconsumption.
Weshowthatthissystemgenerateslowoverhead,cutsaverageresponsetimebyhalformore,andincreasesDNSserviceavailability.
AcknowledgmentsThisresearchwassupportedinpartbyNSFgrantCNS-0335214.
WewouldliketothankJeffreyMogulandHewlett-PackardfordonationoftheAlphaworkstationusedfortesting.
Wethankourshepherd,GeoffVoelker,forhisguidanceandhelpfulfeedback,andwethankouranonymousreviewersfortheirvaluablecommentsonimprovingthispaper.
References[1]Akamai.
ContentDeliveryNetwork.
http://www.
akamai.
com.
[2]L.
Breslau,P.
Cao,L.
Fan,G.
Phillips,andS.
Shenker.
WebCachingandZipf-likeDistributions:EvidenceandImplications.
InProceedingsofIEEEINFOCOM,1999.
[3]E.
CohenandH.
Kaplan.
PrefetchingtheMeansforDocumentTransfer:ANewApproachforReducingWebLatency.
InPro-ceedingsofIEEEINFOCOM,2000.
[4]R.
Cox,A.
Muthitacharoen,andR.
Morris.
ServingDNSUsingChord.
InProceedingsofthe1stInternationalWorkshoponPeer-to-PeerSystems(IPTPS),2002.
[5]P.
B.
Danzig,K.
Obraczka,andA.
Kumar.
AnAnalysisofWide-AreaNameServerTrafc:AStudyofInternetDomainNameSystem.
InProceedingsofACMSIGCOMM,1992.
[6]D.
Eastlake.
DomainNameSystemSecurityExtensions.
RFC2535,January1999.
[7]C.
HuitemaandS.
Weerahandi.
InternetMeasurements:theRis-ingTideandtheDNSSnag.
InProceedingsofthe13thITCSpe-cialistSeminaronInternetTrafcMeasuremnetandModelling,2000.
[8]K.
Johnson,J.
Carr,M.
Day,andF.
Kaashoek.
TheMeasuredPerformanceofContentDistributionNetworks.
InProceedingsofthe5thInternationalWebCachingandContentDeliveryWork-shop(WCW),2000.
[9]J.
Jung,E.
Sit,H.
Balakrishnan,andR.
Morris.
DNSPerformanceandtheEffectivenessofCaching.
InProceedingsoftheACMSIGCOMMInternetMeasurementWorkshop,2001.
[10]J.
KangasharjuandK.
W.
Ross.
AReplicatedArchitecturefortheDomainNameSystem.
InProceedingsofIEEEINFOCOM,2000.
[11]B.
Knowles.
DomainNameServerComparison:BIND8vs.
BIND9vs.
djbdnsvs.
,2002.
http://www.
usenix.
org/events/lisa02/tech/presentations/knowlesppt/.
[12]A.
Kumar,J.
Postel,C.
Neuman,P.
Danzig,andS.
Miller.
Com-monDNSImplementationErrorsandSuggestedFixes.
RFC1536,October1993.
[13]R.
Liston,S.
Srinivasan,andE.
Zegura.
DiversityinDNSPerfor-manceMeasures.
InProceedingsoftheACMSIGCOMMInternetMeasurementWorkshop,2002.
[14]P.
Mockapetris.
DomainNames-ImplementationandSpecica-tion.
RFC1035,November1987.
[15]P.
MockapetrisandK.
Dunlap.
DevelopmentoftheDomainNameSystem.
InProceedingsofACMSIGCOMM,1988.
[16]PlanetLab.
http://www.
planet-lab.
org.
[17]V.
RamasubramanianandE.
G.
Sirer.
Beehive:O(1)LookupPerformanceforPower-LawQueryDistributionsinPeer-to-PeerOverlays.
In1stSymposiumonNetworkedSystemsDesignandImplementation(NSDI),2004.
[18]V.
RamasubramanianandE.
G.
Sirer.
TheDesignandImple-mentationofaNextGenerationNameServicefortheInternet.
InProceedingsofACMSIGCOMM,2004.
[19]M.
Schiffman.
ASampingoftheSecurityPostureoftheIn-ternet'sDNSServers.
http://www.
packetfactory.
net/papers/DNS-posture/.
[20]A.
Shaikh,R.
Tewari,andM.
Agrawal.
OntheEffectivenessofDNS-basedServerSelection.
InProceedingsofIEEEINFO-COM,2001.
[21]I.
Stoica,R.
Morris,D.
Karger,M.
Kaashoek,andH.
Balakrish-nan.
Chord:AScalablePeer-to-peerLookupServiceforInternetApplications.
InProceedingsofACMSIGCOMM,SanDiego,California,2001.
[22]D.
ThalerandC.
Ravishankar.
UsingName-basedMappingstoIncreaseHitRates.
InIEEE/ACMTransactionsonNetworking,volume6,1,1998.
[23]L.
Wang,K.
Park,R.
Pang,V.
Pai,andL.
Peterson.
ReliabilityandSecurityintheCoDeeNContentDistributionNetwork.
InUSENIXAnnualTechnicalConference,2004.
[24]C.
E.
WillsandH.
Shang.
TheContributionofDNSLookupCoststoWebObjectRetrieval.
TechnicalReportWPI-CS-TR-00-12,WorcesterPolytechnicInstitute(WPI),2000.
OSDI'04:6thSymposiumonOperatingSystemsDesignandImplementationUSENIXAssociation214