同济六版高等数学课后答案完整精排版(2)

1IncentivesBuildRobustnessinBitTorrent?AnalysisonBitTorrentClientperformanceByJimmyWong2Agenda•Introduction•BitTorrentBasics•BitTyrant:Astrategicclient•BitThief:Afree-ridingclient•OtherTricksofBTClient•RealWorldExperiments•AvoidingofTricks•Conclusion3Introduction•BitTorrentcoreincentive–UploadMore,DownloadMore•ProblemDefinition–Iamaselfishuser–CanIgainwithoutpay/payless?4BitTorrentBasics•Step0–PublishingContent–CreateTorrentfile•TrackerURL•SHA-1HashChecksum–AssignaTracker–DistributeTorrenttousersthroughWebSite,NewsgrouporForum5BitTorrentBasics•Step1–Joining–PeersgettheTorrent–ConnecttoTracker•Lookforavailablepeers•DHT(DistributedHashTable)–Createconnectionwithotherpeers–StartwithOthers’OptimisticUnchoking•Lookforbetterpeers•Letotherpeersjointheswarm6BitTorrentBasics•Step2toN-1–Pipelining–Exchangebitmapaboutwhichchunksareavailable–Paymore,getmore•Tobuildincentiveforpeerstoupload•Reciprocal–Rarestfirst•TopreserveFilecompletenessamongtheswarm•Tobuilduppeer’sreputation7BitTorrentBasics•Choking–Senddatatoonlyfewgoodpeers•Contributedatatoyou•Havepiecesthatyouwants•Aresourcefulpeers–ItwillbeniceifIcanpayminimalcosttobeun-choke!!!!8BitTorrentBasics•OptimisticUn-choking–Allownewpeerstogetsomepiecesforexchange–Allowdiscoveryofbetterexchangingpartners–Mostpeersaresofriendly–Icangainwithoutcontribute!!!!9BitTorrentBasics•EndingPhase–Towardtheendofdownload–Requestformissingpieces–Searchforavailablepeers–20-30piecesleft10BitTyrant:Astrategicclient•Incentive–100KB/s15KB/s•1%drop–15KB/s10KB/s•40%drop–About1.9MbpsWorldWideBandwidth•–WhydoIstillneedtogiveusomuch?11BitTyrant:Astrategicclient•ResourceManagement–Bandwidthfixed–#ConnxSpeed=Constant•CurrentOfficialBTProtocol(=5.0)–4un-chokingpeers–1optimisticun-choking•AOptimizationProblem!!12BitTyrant:Astrategicclient•BitTyrantUn-chockingalgorithm–MarkDpbedownloadrateofconnp–MarkUpbeuploadrateofconnp–Foreachround•CalculateperformancemetricDp/Up•Un-chokingtheconnwiththehighestmetric–Attheendofeachround•Ifpeerdoesn’tun-chokingusUp(1+delta)Up•Ifpeerun-chokingusDp=downlodrate•Ifpeerhasun-chokedusforrroundUp(1-lamda)Up13BitTyrant:Astrategicclient•Verysimplealgorithm•NetEffect–Selectfriendlypeers–Filteroutunfriendlypeers–Gainfrompeersmostofthetime14BitTyrant:Astrategicclient•Dynamicsizingofactiveset–Servingthebestpeersfirst–The2ndbestnextandsoon–Untiluploadrateisexhausted•LocalOptimaltrading–Notglobal,becauseonlyconcernyourlocalpeersgroup15BitThief:Afree-ridingclient•Downloadonly–Nocopyrightissue(OnlyContributorissued)–ConserveResource–Usetospoilthecommunity•BasicIdea–Gainfromoptimisticun-choking–GainfromfreesharingofSeeder16BitThief:Afree-ridingclient•GainFromOptimisticUn-choking–Requestforasmanyclientsaspossible•MaybeblockbytheTracker•SIMDlikequerytoTracker–Connecttoallclientavailable•HigherChanceofbeingun-choking–Alwayspretendtobeanewcomer•Abitmapwithnoavailablepiece•Trytodownloadwhateveravailable•MostClientsaresonice17BitThief:Afree-ridingclient•GainFromFreeSharingofSeeder–Seederselectpeersintwoways•TheHighestBandwidth(fromtracker)•RoundRobin–BitThiefreporthighuploadrate–#ofSeeder#ofLeecherEvenbetter•Gainfrombothmethodology18OtherTricksofBTClient•ClientDiscrimination–HigherpriorityforSimilarClient–Delibratelychokeotherclient•PretendtobeLocalNeighbor–Faketrackerwithwronguploadrate–RetrievefromSeed•RapidDisconnectandReconnect–Hopetogainfromoptimisticunchoking–Removefromblack-list•MultipleConnectiontothesameclient–ForhighspeedBB–Gainthemostfromthesameclient19ExperimentwithBTClient•TestingEnvironment–Athlon642800+–1GBRam–120GB7200rpmHDD–WindowsXPSP2w/TCPConnCrack–BTSoftware•Utorrent/Mainline•BitComet•BitTryant–iCableinternetConnection20ExperimentwithBTClient•GentooAMD64MinimalISO–54.4MB–34Seeders,0Leechers•Ubuntu7.10i386DesktopISO–695MB–928Seeders/78Leechers•NBAMatch–921MB–120Seeders,714Leechers21ExperimentwithBTClientGentooUploadTimeAvgSpeedKB/sConnPeerSeed/LeechBitComet018:4050.6510/0uTorrent017:0155.6212/0BitTyrant015:0462.7516/022ExperimentwithBTClientUbuntuUploadTimeAvgSpeedKB/sConnPeerSeed/LeechBitComet32MB15:20773.5775/70uTorrent112KB69:13171.3736/1BitTyrant100KB26:28448.1640/123ExperimentwithBTClientNBAUploadTimeAvgSpeedKB/sConnPeerSeed/LeechBitComet1070MB52:3229911/53uTorrent1035MB1:42:501527/29BitTyrant540MB1:20:1019610/2224ExperimentwithBTClient•BitThief–Achieveahighdownloadrate(~150KB/s)forUbuntuandNBA–Suckat25%25AvoidingTricks•Target–StopFakeInformation–IdentifyFree-riding•Difficulties–BitTorrentissowidespread–Toomanyimplementations•Incentivedrivenworksagain!!!–Co-operativeidentifybadclient–Blockbadpeers,Sharewithgoodpeers26AvoidingTricks•SharingwithPeers–Searchforlocaloptimalbestpeers–Searchforpotentialbadpeers–Broadcastofbadpeers(Inamajoritybasics)–Itwillfailifmorethanhalfofclientsarein-honest27Conclusion•BTRobustness–Mostpeersarefriendly•WaystoCrack–Gainfromcrackingtheprotocol–BitTyrant:DownloadUpload–BitThief:FreeRiding•ProposedSolution–DecentralizedClientSolut