計算機科學(xué)技術(shù)進展講座17

計算機科學(xué)技術(shù)進展講座

對概念篇：Advantages:WhyandWhat

等歷史篇：Structuralevolution

,

I當代篇：FromAcademytoIndustry

計<______________________________

算發(fā)展篇：HowtoBuildaPracticalP2Psystem

陳貴海

2006年9月22日

1

Client/ServerModelisBeingChallenged

Nosingleserverorsearchenginecansufficiently

coverincreasingWebcontents.

?2x1018Bytes/yeargeneratedinInternet.

?Butonly3x1012Bytes/yearavailabletopublic

(0.00015%).

?Googleonlysearches1.3x108Webpages.

(Source:IEEEInternetComputing,2001)

概念篇歷史篇當代篇發(fā)展篇2

Client/ServerModelHasProblems

Client/servermodelseriouslylimitsutilizationof

availablebandwidthandservice.

?Popularserversandsearchenginesbecometraffic

bottlenecks.

?Buthighspeednetworksconnectingmanyclients

becomeidle.

?Computingcyclesandinformationinclientsare

ignored.

概念篇歷史篇當代篇發(fā)展篇3

ContentDeliveryNetworks(CDN):ATransitionModel

?Serversaredecentralized(duplicated)

throughouttheInternet.

?Thedistributedserversarecontrolledbya

centralizedauthority(headquarters).

?Examples:Internetcontentdistributionsby

Akamai,Overcast,andFFnet.

?BothClient/ServerandCDNmodelshavesingle

pointoffailures.

概念篇歷史篇當代篇發(fā)展篇4

ANewParadigm:Peer-orientedSystems

?Bothclient(consumer)&server(producer).

?Hasthefreedomtojoinandleaveanytime.

?Hugepeerdiversity:serviceability,storagespace,networking

speed,andservicedemand.

?Awidelydecentralizedsystemopeningforbothopportunities

andnewconcerns.

概念篇歷史篇當代篇發(fā)展篇

Peer-orientedSystems

Client/serverContentDeliveryNetworks

e.g.Freenet

&Gnutella

概念篇歷史篇當代篇發(fā)展篇6

ObjectivesandBenefitsofP2P

?Aslongastherenophysicalbreakinthenetwork,

thetargetfilewillalwaysbefound.

?AddingmorecontentstoP2Pwillnotaffectits

performance,(informationscalability).

?AddingandremovednodesfromP2Pwillnot

affectitsperformance,(systemscalability).

概念篇歷史篇當代篇發(fā)展篇7

Peer-orientedApplications

?FileSharing:documentsharingamongpeerswithnoorlimitedcentral

controls.

?InstantMessaging(IM):Immediatevoiceandfileexchangesamong

peers.

?DistributedProcessing:Onecanwidelyutilizeresourcesavailablein

otherremotepeers.

?Wherearefurtherapplications?

?Gridcomputing

?Adhocnetworking

?Webcache

?VoD

概念篇歷史篇當代篇發(fā)展篇8

WhatisP2PNetwork-Myversion

■[Equality]Allpeersassumeequalrole.

■[NonCentralized]Nocentralizedserverinthe

space.

■[Robust]Highlyrobust,resilient,andself-

organizing.

■[ZeroHardwareCost]Nofurtherinvestmentsin

hardwareorbandwidth.

■[Ahottopic]Buthugeinvestmentinresearch,

e.g,IRISgot$12M.

概念篇歷史篇當代篇發(fā)展篇9

WhatisP2PNetwork—Anotherversion

—M.Ripeaunu,A.Lamnitchi,andI.Foster,"MappingtheGnutellaNetwork",IEEEIC,No.1,2002.

■[Dynamicoperability]P2Papplicationsmustkeep

operatingtransparentlyalthoughhostsjoinandleavethe

networkfrequently.

■[Performanceandscalability]P2Papplicationsexhibit

whateconomistscalltheunetworkeffect”inwhicha

network'svaluetoanindividualuserscaleswiththetotal

numberofparticipants.

?[Reliability]Externalattacksshouldnotcausesignificant

dataorperformanceloss.

■[Anonymity]Theapplicationshouldprotecttheprivacyof

peopleseekingorprovidingsensitiveinformation.

概念篇歷史篇當代篇發(fā)展篇10

HowDiditStart?

■Akillerapplication:Napster

-FreemusicovertheInternet

■Keyidea:sharethestorageandbandwidthof

individual(home)users

A.A

概念篇歷史篇當代篇發(fā)展篇11

Model

■Eachuserstoresasubsetoffiles

■Eachuserhasaccess(candownload)filesfrom

allusersinthesystem

概念篇歷史篇當代篇發(fā)展篇12

MainChallenge

■Findwhereaparticularfileisstored

-Note:problemsimilartofindingaparticularpageinweb

caching

概念篇歷史篇當代篇發(fā)展篇13

OtherChallenges

■Scalability:uptohundredofthousandsor

millionsofmachines

■Dynamicity:machinescancomeandgoat

anytime

概念篇歷史篇當代篇發(fā)展篇14

Napster

■Assumeacentralizedindexsystemthatmaps

files(songs)tomachinesthatarealive

■Howtofindafile(song)

-Querytheindexsystem今returnamachinethatstores

therequiredfile

?Ideallythisistheclosest/least-loadedmachine

-ftpthefile

■Advantages:

-Simplicity,easytoimplementsophisticatedsearch

enginesontopoftheindexsystem

■Disadvantages:

-Robustness,scalability(?)

概念篇歷史篇當代篇發(fā)展篇15

Napster:Example

概念篇歷史篇當代篇發(fā)展篇16

Napster:History

■history:

-5/99:ShawnFanning(freshman,Northeaster!U.)founds

NapsterOnlinemusicservice

-12/99:firstlawsuitWellKnownServicesMb/s

120

-3/00:25%UWisctrafficNapster100

-2000:est.60Musers80

60

-2/01:USCircuitCourtof40

Appeals:Napsterknewusers20

0

18：0020：0022：00

■Napsteri/o■HTTPsrci/o■HTTPdsti/o

violatingcopyrightlaws□FTP-DATASrcI/O■FTP-DATAd5tI/O口MCASTI/O

■NNTPsrcI/O■NNTPdstI/O口RealServerI/O□SMTPsrcI/O

-7/01:#simultaneousonlineusers:■SMTPdStI/O□ICMP■TOTALI/O

Napster*23.136666%HTTP20,960013%FTP-DATA18.356126%

MCAST0.006092%NNTP1.936819%Real0.764512%SMTP0.400603%

Napster160K,Gnutella:40K,ICMP0.181571%Other34.257597%

-Now:trytocomeback

—?E皿

概念篇歷史篇當代篇發(fā)展篇17

Napster:architectureproblems

■centralizedserver:

-singlelogicalpointoffailure

-canloadbalanceamongserversusingDNSnotation

-potentialforcongestion

-Napster"incontrol(freedomisanillusion)

■nosecurity:

-passwordsinplaintext

-noauthentication

-noanonymity

Napsteristhe1stP2Psystem,botitisactuallynotaP2Psystem.

概念篇歷史篇當代篇發(fā)展篇18

Gnutella

■Distributefilelocationanddecentralizelookup.

■Idea:multicasttherequest

■Hottofindafile:

-Sendrequesttoallneighbors

-Neighborsrecursivelymulticasttherequest

-Eventuallyamachinethathasthefilereceivestherequest,

anditsendsbacktheanswer

概念篇歷史篇當代篇發(fā)展篇19

Gnutella:Example

■Assume:mi'sneighborsarem2andm3;m3's

neighborsarem4and

概念篇歷史篇當代篇發(fā)展篇20

Gnutella:architectureproblems

■Notscalable:theentirenetworkcanbeswampedwith

request(toalleviatethisproblem,eachrequesthasaTTL)

■Notanonymous:Thepersonyouaregettingthefilefrom

knowswhoyouare.

■Notanymorethanitsnon-centralized.

■Whatwecareabout:

,Howmuchtrafficdoesonequerygenerate?

,howmanyhostscanitsupportatonce?

/Whatisthelatencyassociatedwithquerying?

/Isthereabottleneck?

概念篇歷史篇當代篇發(fā)展篇21

Freenet

■Additionalgoalstofilelocation:

-Providepublisheranonymity,security

-Resistanttoattacks-athirdpartyshouldn'tbeabletodenythe

accesstoaparticularfile(dataitem,object),evenifit

compromisesalargefractionofmachines

■Architecture:

-Eachfileisidentifiedbyauniqueidentifier

-Eachmachinestoresasetoffiles,andmaintainsa“routing

table"toroutetheindividualrequests

SeehowFreenetuse"Routingtable,depth-firstsearching,anonymity,caching".

概念篇歷史篇當代篇發(fā)展篇22

DataStructure

Routingtable

■Eachnodemaintainsacommonstack

-id—fileidentifier

-next_hop—anothernodethatstoresthe

fileid

-file—fileidentifiedbyidbeingstoredon

thelocalnode

■Forwarding:

-Eachmessagecontainsthefileiditis

referringto

-Iffileidstoredlocally,thenstop;

-Ifnot,searchforthe“closest"idinthe

stack,andforwardthemessagetothe

correspondingnext_hop

-Birdsflockinfeather

概念篇歷史篇當代篇發(fā)展篇23

Query

■API:file=query(/d);

■Uponreceivingaqueryfordocumentid

-Checkwhetherthequeriedfileisstoredlocally

?Ifyes,returnit

?Ifnot,forwardthequerymessage

■Notes:

-EachqueryisassociatedaTTLthatisdecrementedeachtimethe

querymessageisforwarded;toobscuredistancetooriginator:

?TTLcanbeinitiatedtoarandomvaluewithinsomebounds

?WhenTTL=1,thequeryisforwardedwithafiniteprobability

-Eachnodemaintainsthestateforalloutstandingqueriesthathave

traversedithelptoavoidcycles

-Whenfileisreturneditiscachedalongthereversepath

概念篇歷史篇當代篇發(fā)展篇24

QueryExample

query(10)

1

?Note:

-doesn'tshowfilecachingonthereversepath

-Usedepth-firstsearching.

概念篇歷史篇當代篇發(fā)展篇25

Insert

■API:inserted,file);

■Twosteps

-Searchforthefiletobeinserted

?Iffound,reportcollision

?ifnumberofnodesexhaustedreportfailure

-Ifnotfound,insertthefile

概念篇歷史篇當代篇發(fā)展篇26

Insert

■Searching:likequery,butnodesmaintainstate

afteracollisionisdetectedandthereplyissent

backtotheoriginator

■Insertion

-Followtheforwardpath;insertthefileatallnodesalong

thepath

-Anodeprobabilisticallyreplacetheoriginatorwithitself;

obscurethetrueoriginator

概念篇歷史篇當代篇發(fā)展篇27

InsertExample

■Assumequeryreturnedfailurealong“gray”path;

insertf10

insert(10,f10)

14n5f144n1f4

13n2f1311n5f11

3n68n6

3n1f3

14n4f14

5n3

概念篇歷史篇當代篇發(fā)展篇28

InsertExample

■Assumequeryreturnedfailurealong“gray”path;

insertf10

insert(10,f10)

10n1f10

4n1f4

14n5f144n1f4

13n2f1311n5f11

3n68n6

3n1f3

14n4f14

5n3

概念篇歷史篇當代篇發(fā)展篇29

InsertExample

■n2replacestheoriginator(n1)withitself

insert(10,f10)

n1In2

10n1f1010n1f10

4n1f49n3f9

12n2

n4n5

orig=n214n5f144n1f4

13n2f1311n5f11

n33n6

10n2f10

3n1f3

14n4

概念篇歷史篇當代篇發(fā)展篇30

InsertExample

■n2replacestheoriginator(n1)withitself

■n4replacestheoriginator(n2)withitselftoo

lnsert(10,f10)

n1In2

10n1f1010n1f10

4n1f49n3f9

10n4f10

4n1f4

概念篇歷史篇當代篇發(fā)展篇31

FreenetProperties

■Newlyqueried/insertedfilesarestoredonnodes

withsimilarids.Birdsflockinfeather.

■Newnodescanannouncethemselvesby

insertingfiles

■Attemptstosupplantordiscoverexistingfileswill

justspreadthefiles

概念篇歷史篇當代篇發(fā)展篇32

FreenetSummary

■Advantages

-Providespublisheranonymity

-Totallydecentralizearchitecture今robustandscalable

-Resistantagainstmaliciousfiledeletion

■Disadvantages

-Doesnotalwaysguaranteethatafileisfound,evenif

thefileisinthenetwork

-Space-timecomplexity=???

-Sostillnotscalable

概念篇歷史篇當代篇發(fā)展篇33

|LNewSolutionstotheLocationProblem

IM

■OverlayNetworks:

-applications,runningatvarioussites

-create"logical“l(fā)inks(e.g.,TCPorUDPconnections)pairwisebetweeneachother

-eachlogicallink:multiplephysicallinks,routingdefinedbynativeInternet

routing

■Goal:Scalability,Resilient,Security.

■Abstraction:Hashfunction+Routingtable

-DatalD=hash(data);

-NodelD=hash(IP)

-data=lookup(ID);

-Note:datacanbeanything:adataobject,document,file,pointertoafile...

■Proposals

-CAN(ACIRI/Berkeley)最新一代：

-Chord(MIT)Koordle(USA)

-Pastry(Rice)Viceroy(lsrael)

-Tapestry(Berkeley)Cycloid(China)

-鄭緯民等，“對等計算研究”中國計算機學(xué)會通訊，2005年7月

概念篇歷史篇當代篇發(fā)展篇34

OverlayNetworks:agenericmodel

OverlayNetwork

peer1peer2peern

routingandroutingandroutingand

locatinglocatinglocating

................

algorithmalgorithmalgorithm

routingtableroutingtableroutingtable

DataStorageDataStorageDataStorage

DataCacheDataCacheDataCache

US~「n

Internet:SupportingNetork

AGenericTopologicalModelofP2PSystems

概念篇歷史篇當代篇發(fā)展篇35

[OverlayNetworks:MappingtoIPNetwork

o端系統(tǒng)節(jié)點o路由器節(jié)點

TOverlay鏈路IP鏈路

概念篇歷史篇當代篇發(fā)展篇36

]OverlayNetworks:ConsistentHashing

DavidKarger,EricLehman,TomLeighton,MathhewLevine,Daniel

Lewin,RinaPanigrahy,ConsistentHashingandRandomTrees:

DistributedCachingProtocolsforRelievingHotSpotsonthe

WorldWideWeb,ACMSymposiumonTheoryofComputing,1997

SHA-1:/PICS/DSig/SHA1_1_0.html

概念篇歷史篇當代篇發(fā)展篇37

]IL■OverlayNetworks:Problems

■OverlayMaintenance:

-(1)periodicallypingtoverifylivenessofpeers;

-(2)deletetheedgewithandeadpeer;

-(3)newpeerneedstobootstrap.

-Geographicaldismatch:

-(1)topology-unaware;

-(2)duplicatedmessages;

-(3)inefficientnetworkusage.

-LoosingSecurityandPrivacy:

-(1)Providingaconduitforevilcodeandviruses.

-(2)Providingloopholesforinformationleakage.

-(3)Relaxingtheprivacyprotectionbyexposingpeeridentities.

■WeakResourceCoordinations

-(1)Withlimitedornocentralcontrol,butmainlyrelyonself-organization.

-(2)Lackingcommunicationmonitoringandscheduling:causeunnecessarytrafficjams.

-(3)Lackingaccessandservicecoordinations:unbalancedloadsamongpeers.

-Manyothers

概念篇歷史篇當代篇發(fā)展篇38

OverlayNetworks:TypicalSystems

RingMeshHypercube

SystemsChord[MIT]CAN[Berkeley]Pastry[Rice],

Tapestry[Berkeley]

PersonsDabekRatnasamy,Druschel,

KaashoekShenkerRowstron

StoicaStoica(fbrmerlyinMIT)

ApplicationsCFSPAST,SCRIBE,OceanStore

Keyspace1-dimensionalcycle2ord-dimensionaltorus1-dimensionalcycle

Space-timeO(logN)<?(logN)O(d)O(dx)(9(logN)(9(logN)

complexity

DataEachnodeholdsasegmentEachnodeholdsazoneEachnodeholdsasegmentof

distributionofdatakeysbetweenofdatakeyswhereitselfdatakeysthataretheclosest

predecessoranditselfresidesnumerically.

Datalookup(k)->successor(k)lookup(k)->region(k)lookup(k)-^nearest(k)

Incatinn

RoutingSuccessorset+O(d)neighborsc>(Iz,I)leafset+

tableo(iogN)fingerso(\Mi)proximityset+

odnpN、neishobrs

概念篇歷史篇當代篇發(fā)展篇

ChordalRing:definition

■Hashfunction:nodeN^nodelD,dataD^datalD

■nodelD,datalDin{0,n-1}wheren=2m

■PutdataDonnodeN,sothatnodelD(N)issmallestnodelDlarger

thanorequaltodatalD(D)

■Givenkey=dataID(D),howtofindsuccessor(key)?

Lookup(key)=successor(key),findthefirstlivenodelDwhichis>key.

■Fingertable:nodekstorespointersto

攵1711

k+lrk+2,+4…,k+2-(mod〃)

01234...789...141516n-2n-1

■FindnodeforeverydatainO(log(#nodes))steps;O(log(#nodes))

storagepernode

概念篇歷史篇當代篇發(fā)展篇

ChordalRing:DataStructure

■AssumeidentifierspaceisO..2m-1

■Eachnodemaintains

-Fingertable

?Entryiinthefingertableofnisthefirstnodethat

succeedsorequalsn+2'

-Predecessornode

■Anitemidentifiedbyidisstoredonthesuccessor

nodeofid

概念篇歷史篇當代篇發(fā)展篇41

]IL■ChordalRing:fingertable

Aringof25nodeIds.m=5,i=.

Start-k+2l(modulo2'")IPaddrofsuccessor{start)

24

34

57

Node'sfingertable

912

Actualnode1720

JNodeidentifier

[25)V57

67

812

1212Node4'sfingertable

2020

1315

1415

1620

2020Node12'sfingertable

281

歷史篇當代篇發(fā)展篇42

ChordalRing:routingalgorithm

Whennodekreceivesthelookup(key),

1)Ifk<key<next(k),returnnext(k)

2)elseifkey<katintermediatenodek,returnk

3)elseforwardtofsuchthatf=MAX{fingers|fingers<key}

■Lookupmessagecontainstherequester'sIPaddresssothatlookup

resultcanbereturned.

■Whennodekisalive,successor(k)=k,next(k)isthenextalive

nodewhichisIPaddressofthefirstentry.

■Makeasbiggerstepaspossible,orsendtherequestasclosetothe

destinationaspossible,confirmingtothesmallworldphenomena.

■Correctness(convergence):distanceiscloserandcloser.

概念篇歷史篇當代篇發(fā)展篇43

ChordalRing:routingexample

Kokupkey=16,17atnode1.

Start-k+2'(modulo2'")IPaddrofsuccessor(start)

因儂'\2/，__、24

(、-3,)34

碗一57

Node'sfingertable

912

3)

1720

126；

（25）757

67

812

124)Node4'sfingertable

1212

2020

w，；‘、9}

（

：22；1、一10/)

1315

1415

121620

2020Node12'sfingertable

?：13

(19)、、/281

114)

、-J

概念篇歷史篇當代篇發(fā)展篇44

ChordExample:self-organization

■Assumeanidentifier

space0..8

■Noden1:(1)joins^all

entriesinitsfinger

tableareinitializedto

itself

概念篇歷史篇當代篇發(fā)展篇45

ChordExample:self-organization

■Noden2:(2)joins

概念篇歷史篇當代篇發(fā)展篇46

ChordExample:self-organization

概念篇歷史篇當代篇發(fā)展篇47

ChordExamples

概念篇歷史篇當代篇發(fā)展篇48

Query

Uponreceivingaquery

foritemid,anode

Checkwhetherstores

theitemlocally

Ifnot,forwardsthequery

tothelargestnodeinits

successortablethat