云计算第1讲：分布式系统的进化

1Lecture1:EvolutionofDistributedSystemsDrLuLiuTeachingTeamDrLuLiu -Room508 -chinaliulu@2DrLuLiuPhDatSurrySpaceCentre,theUniversityofSurreyandMScinBrunelUniversityPost-doctoralResearchFellowatWRGe-ScienceCentre,theUniversityofLeedsLectureratMiddlesexUniversitySeniorLecturerattheUniversityofDerbyUniversityReaderinDistributedComputingattheUniversityofDerbyProfessor,JiangsuUniversity3AssessmentYouwillbegivenopportunities,throughbothformativeandsummativeassessments,toreflectonyourlearningtosupportprofessionalandpersonaldevelopmentFormativeAssessment-thebidirectionalprocessbetweenteacherandstudenttoenhance,recognizeandrespondtothelearningSummativeAssessment-summarizesthedevelopmentoflearnersataparticulartimeSummativeAssessmentCWThestudentwillcarryoutaliteraturesurveyandproduceacriticalreportdetailingthecurrentapproachesandthelatestadvancesinthefieldofVirtualizationandCloudComputing.ContentFromClientServertoP2PExampleofP2PApplicationsClassificationofP2PnetworksAdvantagesP2PblindsearchSummary&nextlecture

LearningObjectivesAtthecompletionofthislessonyoushouldbeabletoUnderstandcutting-edgeInternetcommunicationtechnologies:P2PUnderstandP2Pdatasharinganddistribution78ExamplesofClient-ServerInternetApplications:

Client-ServerAdvantage-EfficientDisadvantage–single-point-of-failure,scalability,limitedresourcesattheserversideClient-ServerandP2PWWW,E-mail,FTP,etcGoogleDataCentresGooglespent$2.4Bin2007onnewdatacentresEachdatacentreuses50-100megawattsofpower910Eachpeeractsas,requestingresourcesfromaswellasroutingqueriesandservingresourcesforotherpeersPeer-to-Peer(P2P)bothclientandserverQuestionDoesanyonehereuseanyP2Psoftware?Why?11“InternetCommunications”“DataNetworks”FileDistributionBitTorrent

InternetTelephony:SkypeBitTorrentPopular,tensofmillionsofusersTodistributelargeamountsofdata.usersneedtocreateasmall.torrentfilethatcontainstheaddressofthetrackermachinethatlaunchesthefiledistribution.TorrentfilesarelocatedatBitTorrentdownloadwebsitesTorrentfilesleaddownloaderstotrackersTrackersdirectdownloaderstoswarms12BitTorrentFileisbrokenintosmallerfragments(typically256KBeach)Peerjoiningtorrent:hasnofragments,butwillaccumulatethemovertimeregisterswithtrackertogetlistofpeers,connectstosubsetofpeers(“neighbors”)simultaneouslyconnectstothesepeernodesthatareparticipatinginfiletransfer,anddownloadsdifferentpiecesofthefilefromdifferentpeernodes.Whiledownloading,peeruploadschunkstootherpeers.Terminology:Leecher:DownloadsfilesbutdoesnothavecompletefilesSeeder:Hascompletefilesandletsothersdownloadfilesfromhim/her13HowBitTorrentWorksPeerAPeerBPeerCSeederLeecherListofpeersPiecesPiecesWebsitewithlinkto.torrentTrackerPiecesLeecherSeederShrek.torrentPieces14Betteravailability,betterredundancy,higherspeed15InternetTelephony-SkypeAhybridP2PSystemClient-server:findingaddressofremotepartyP2P:direct(notthroughserver)HierarchicaloverlaywithSupernodes(SNs)IndexmapsusernamestoIPaddresses;distributedoverSNsSkypeclients(SC)Supernode(SN)Skypeloginserver16PeersasrelaysProblemwhenbothAliceandBobarebehind“NAT”–NATpreventsanoutsidepeerfrominitiatingacalltoinsiderpeerSolution:UsingAlice’sandBob’sSNs,RelayischosenEachpeerinitiatessessionwithrelay.PeerscannowcommunicatethroughNATsviarelayNetworkAddressTranslation

17PrivateaddressesMoresecure:notadvertisedorforwardedintheInternetNATisusedtomapprivateIPaddressesbetweenprivateandpublicaddressspaces.18NAT:NetworkAddressTranslationlocalnetwork(e.g.,homenetwork)restofInternetDatagramswithsourceordestinationinthisnetworkhaveprivateaddressforsource,destination(asusual)AlldatagramsleavinglocalnetworkhavesamesinglesourceNATIPaddress:,differentsourceportnumbers19NAT:NetworkAddressTranslationMotivation:localnetworkusesjustoneIPaddressasfarasoutsideworldisconcerned:rangeofaddressesnotneededfromISP:justoneIPaddressforalldevicescanchangeaddressesofdevicesinlocalnetworkwithoutnotifyingoutsideworldcanchangeISPwithoutchangingaddressesofdevicesinlocalnetworkdevicesinsidelocalnetnotexplicitlyaddressable,visiblebyoutsideworld(asecurityplus).20NAT:NetworkAddressTranslationImplementation:

NATroutermust:outgoingdatagrams:

replace(sourceIPaddress,port#)ofeveryoutgoingdatagramto(NATIPaddress,newport#) ...remoteclients/serverswillrespondusing(NATIPaddress,newport#)asdestinationaddr.remember(inNATtranslationtable)every(sourceIPaddress,port#)to(NATIPaddress,newport#)translationpairincomingdatagrams:

replace(NATIPaddress,newport#)indestfieldsofeveryincomingdatagramwithcorresponding(sourceIPaddress,port#)storedinNATtable21NAT:NetworkAddressTranslationS:,3345D:86,8011:hostsendsdatagramto86,80NATtranslationtableWANsideaddrLANsideaddr,5001,3345…………S:86,80D:,33454S:,5001D:86,8022:NATrouterchangesdatagramsourceaddrfrom,3345to,5001,updatestableS:86,80D:,500133:Replyarrivesdest.address:,50014:NATrouterchangesdatagramdestaddrfrom,5001to,3345

22NAT:NetworkAddressTranslation16-bitport-numberfield:60,000simultaneousconnectionswithasingleLAN-sideaddress!NATiscontroversial:violatesend-to-endargumentNATpossibilitymustbetakenintoaccountbyappdesigners,eg,P2PapplicationsaddressshortageshouldinsteadbesolvedbyIPv6NetworkLayer23NATtraversalNATedclientestablishesconnectiontorelayExternalclientconnectstorelayrelaybridgespacketsbetweentwoconnectionsClientNATrouter1.connectiontorelayinitiatedbyNATtedhost2.connectiontorelayinitiatedbyclient3.relayingestablishedContentFromClientServertoP2PExampleofP2PApplicationsClassificationofP2PnetworksAdvantagesP2PblindsearchSummary&nextlecture

CentralisedP2PApplicationsNapsterthefirstwidely-usedP2Pmusicsharingservice.Napsterutilisesasimplebuthighlyefficientmechanismtoshareandsearchfilesinthenetwork.ToparticipateintheNapsternetwork,newusersneedtoregistertotheNapsterserverandpublishalistoffilestheyarewillingtoshare.Tosearchasharedfileinthenetwork,userscanrequesttheNapsterserverandretrievealistofprovidershostingthefilesmatchingthequery.FiletransfertakesplacewithouttheNapsterserverparticipating.Therequestedfileistransferreddirectlybetweentherequesterandtheprovider25DecentralisedP2PNetworksGnutellaTheGnutellanetworkisadecentralisedfile-sharingP2Pnetwork,whichisbuiltonanopenprotocoldevelopedtoenablepeernodediscovery,distributedsearch,andfiletransfer.EachGnutellauserneedsaGnutellaclientsoftwaretojointheGnutellanetwork.TheGnutellaclientsoftwareontheinitialusecanbootstrapandfindanumberofpossiblyworkingpeernodesinthenetworkandtrytoconnecttothem.Ifsomeattemptssucceed,theseworkingpeernodeswillthenbecomethenewnode’sneighboursandgivethenewnodetheirownlistsofworkingnodes.Thenewnodecontinuestoconnecttotheseworkingpeernodes,untilitreachesacertainquota(usuallyuser-specified).26DecentralisedP2PNetworksGnutella(cont.)Breadth-FirstSearch(BFS)mechanismtosearchthenetworkbybroadcastingthequerywithaTime-to-Live(TTL)TTLrepresentsthenumberoftimesamessagecanbeforwardedbeforeitisdiscarded.Eachpeernodereceivingthequerywillprocessit,checkthelocalfilestorage,andrespondtothequeryifonematchedfileisfound.EachpeernodedecreasesTTLbyoneandforwardsthequerytoallofitsneighbours.ThisprocesscontinuesuntilTTLisequaltozero.27HybridP2PNetworksKazaaKazaareorganisespeernodesintoatwo-levelhierarchywithsupernodesandleaves.Asupernodeisatemporaryindexserverforotherpeernodes.AnewlyjoinednodewillattempttocontactanactivesupernodefromalistofsupernodesofferedbyKazaaclientsoftware.Thenewlyjoinednodewillsendalistoffilesitsharestotheconnectedsupernodesandfurtherretrievemoreactivesupernodesfromtheconnectedsupernodesforfutureconnectionattempts28HybridP2PNetworksKazzaInKazaa,eachleavenodebeginsalookupbysendingalookuprequesttoitsconnectedsupernode.Thesupernodenotonlychecksthelocalindexforthefilerequested,butalsocommunicateswithothersupernodesforalistofaddressesofpeernodessharingthefiles.Whenasupernodediscoverstherequestedfilefromitslocalindex,itwillrespondtotheoriginalsupernode.Thefileistransferreddirectlybetweenthequeryoriginatorandthetargetpeernodethatsharesthefile.29RequestResponseFiletransferAdvantagesP2Pfreesusersfromthetraditionaldependenceoncentralservers,whichenablesenduserstoeasilyshareresources(e.g.music,movies,gamesandothersoftware).P2Papplicationsaremoreresilientthanthosebuiltontheclient-serverarchitecturebyremovingthesingle-point-of-failure.P2Pdistributestheresponsibilityofprovidingservicesfromcentralisedserverstoeachindividualpeernodeinthenetwork.P2Pexploitsavailablebandwidth,processor,storageandotherresourcesacrosstheentirenetwork.P2Pinteractionsareonlybetweenindividualpeerswhicheliminatethebottleneckofcentralisedservers.MostP2Papplicationsusevirtualchannelsforcommunicationwhichbreaktheobstaclesofcorporateprivatenetworks,suchasfirewallsandNetworkAddressTranslation(NAT).30Question

ForaP2Pfile-sharingapplication,doyouagreewiththestatement,“Thereisnonotionofclientandserversidesofacommunicationsession”?Whyorwhynot?

No.Allcommunicationsessionshaveaclientsideandaserverside.InaP2Pfile-sharingapplication,thepeerthatisreceivingafileistypicallytheclientandthepeerthatissendingthefileistypicallytheserver.CCM481031ContentFromClientServertoP2PExampleofP2PApplicationsClassificationofP2PnetworksAdvantagesP2PblindsearchSummary&nextlecture

Peer-to-PeerSearchStructuredP2PSearchEstablishalinkbetweenthestoredcontentandtheaddressofanodeAlgorithms:Chord,ROME,Pastry,CANandKademliaNeedstomaintainaconsistentdistributedindexUnstructuredP2PSearchDonotmaintainnetworkstructureBlindSearch:e.g.Flooding,IterativeDeepeningInformedSearch:e.g.Neurogrid33BlindSearchPeernodesdonotmaintainadditionalinformationaboutresourcelocation.AdvantagesDonotneedanycommunicationoverheadtomaintaintheadditionalindicesaboutresourcelocationsextremelyresilientinthehighlydynamicnetworks.Floodingisthefundamentalapproachofblindsearchwherequeriesareforwardedtoallconnectedpeernodetoseewhethertheyhavearequestedfile.34Breadth-FirstSearchBreadth-FirstSearch(BFS)mechanismtosearchtheGnutellanetworkbybroadcastingthequerywithaTime-to-Live(TTL)TTLrepresentsthenumberoftimesamessagecanbeforwardedbeforeitisdiscarded.Eachpeernodereceivingthequerywillprocessit,checkthelocalfilestorage,andrespondtothequeryifonematchedfileisfound.EachpeernodedecreasesTTLbyoneandforwardsthequerytoallofitsneighbours.ThisprocesscontinuesuntilTTLisequaltozero.35IterativeDeepeningIterativedeepeningenablesqueryoriginators