CDN网络技术综述PPT

ContentDeliveryNetworks:OverlayNetworksforScalingandEnhancingtheWebRajkumarBuyyaandMukaddimPathanGridComputingandDistributedSystems(GRIDS)LaboratoryDept.ofComputerScienceandSoftwareEngineeringTheUniversityofMelbourne,Australia@ADCOM2008,Chennai,India2CDN:OverlayNetworksforScalingandEnhancingtheWebOutline„PartI:CDNFundamentals„CDNinsights„CDNtaxonomy„Contentdistributionandmanagement„Contentreplication„Cachingtechniques„Request-redirection„PartII:CDNModelingandPerformance„Economics-informeddesign„CDNpricing„Mathematicalmodeling„CDNperformance„PartIII:AdvancedCDNPlatformsandApplications„DynamicCDNsforadaptivecontentdelivery„Collaborativemediastreaming„Liveandon-demandvideoservicesoverIP„MobiledynamicCDNs„Contentdeliveryforcommunitynetworks„CDNinternetworkingContentDeliveryNetworks:Designs,ModelsandPerformancePartII4CDN:OverlayNetworksforScalingandEnhancingtheWebOutline„PartI:CDNFundamentals„CDNinsights„CDNtaxonomy„Contentdistributionandmanagement„Contentreplication„Cachingtechniques„Request-redirection„PartII:CDNModelingandPerformance„Economics-informeddesign„CDNpricing„Mathematicalmodeling„CDNperformance„PartIII:AdvancedCDNPlatformsandApplications„DynamicCDNsforadaptivecontentdelivery„Collaborativemediastreaming„Liveandon-demandvideoservicesoverIP„MobiledynamicCDNs„Contentdeliveryforcommunitynetworks„CDNinternetworking5CDN:OverlayNetworksforScalingandEnhancingtheWebIndividualIncentivesandCDNs„“Tragedyofthecommons”isobservedintheP2Pnetwork„Misalignmentbetweeneachindividual’sownincentivesandasituationdesirablefromasocietalpointofview„Studyingperceiveduserrationality,incentives,orselfishnesshasseverallevelsofinteresttoaCDNdesigner„Usingend-usersashelpersforcontentdistribution(e.g.YouTube),inordertoincreaseuserQoS,whilereducinginfrastructurecost„CDNinternetworkingcanbenefitfromparticipants’incentivestodeviseameaningful,enforceableServiceLevelAgreement(SLA)„EveninasingleCDNdomain,characterizingtheamountofresourcesfromeachparticipantisnecessaryforproperoperations„Understandingcostandbenefitsassociatedwithparticipationhelpstogainvaluableinsightsintoviablecustomerpricingschemes„Researchonincentive-basedstrategicinteraction„Commoninappliedmathematics,economicstomodelcompetitivemarkets„Relativelynewinnetworkresearch,focusingongametheory6CDN:OverlayNetworksforScalingandEnhancingtheWebGame-TheoreticBackground„Involvesstrategicinteractions(games)amongindividualdecision-makers(players)„Eachuserobtainsautilitydependentonadoptedstrategy,i.e.getsarewardorapenalty,basedonheractionsandthatofotherplayers„Competitiveequilibrium(ConceptofNashequilibrium)„Predictuserbehaviorandinfertheoutcomeofacompetitivegame„PlayersareinaNashequilibriumifachangeinstrategiesbyanywouldleadthatplayertoobtainalowerutilitythanhercurrentone„Definitions„Purestrategies:deterministic„Mixedstrategies:non-deterministic(probability-based)„Usefulforexogenousconditionsthatimpactuserbehavior,e.g.networkcongestions„Socialoptimum:ensurehighestaverageutility„Situationthatisthebestforallplayers,takenasanaggregate,i.e.tothesociety7CDN:OverlayNetworksforScalingandEnhancingtheWebCDNCostModel„AimsatassessingtheamountofresourcesagivennodemustcontributetoparticipateinaCDNanditsperceivedbenefits„TotalcostCuimposedonnodeuis:Cu=Lu+Su+Ru+Mu„Luisthelatencycostexperiencedbynodeu„Sumofindividualcostmultipliedbytheprobabilityforaitemktoberequested„Suistheservicecostincurredbynodeu„Expectednominalcostvalueoverallpossiblerequests„Ruistheroutingcostsufferedbynodeuforforwardingarequest„Denotesthecostforresourcesusedbyaserverwhichreceivesaqueryfork,cannotresolveitandhastoredirectthequerytoaDNSserverhigherupinthetree,averagedoverallpossiblequeries„Muisthemaintenancecostincurredbynodeu„Costformaintainingalinkwithitsneighbor8CDN:OverlayNetworksforScalingandEnhancingtheWebSocialOptimaandNashEquilibria„Staticnetworktopologywithshortestpathrouting„Allnodeshaveequalprobabilityforservingarequest„l,s,r,mareconstants„Fullmeshcost,C(fullmesh)=s+l(N-1)+mN(N-1)„Thefullmeshisthesocialoptimumifthemaintenancecostis“smallenough”,m≤l/N+r/N2„Starnetworkcost,C(star)=2m(N-1)+s+2l(N-1)2/N+r(N-1)(N-2)/N2„Thestarisasocialoptimumif(i)conditionforfullmeshdoesnothold;and(ii)linksarebi-directional„Noguaranteeforstartobeauniquesocialoptimum„PossibleNashequilibria„Ifml/N,thefullmeshisaunique(pure)Nashequilibrium„Ifm≥l/N,thestarnetworkisapureNashequilibriumƒIndividualincentivesandoverallresourceusageareconflictingƒSocialoptimumdeviatesbasedontheamountofforwardtrafficƒCDNdesignersshouldminimizeredirectionasmuchaspossible9CDN:OverlayNetworksforScalingandEnhancingtheWebAlternativeNetworkGeometries„DeBruijngraph„AdirectedgraphofdiameterD,withshortaverageroutingdistanceandhighresiliencytonodefailures„Maintenancecostforanodeu,Mu=m∆,∆isafixedout-degree„Usedforoverlaynetworkmaintenancealgorithms„D-dimensionaltori„EachnodeisrepresentedbyDCartesiancoordinates,andhas2Dneighbors„Maintenancecostforanodeu,Mu=2mD„UsedinCAN„PRRtrees„NodesarerepresentedbyastringofDdigitsinbase∆,andhasD(∆-1)distinctconnected