计算机科学技术进展讲座17

计算机科学技术进展讲座

对概念篇：Advantages:WhyandWhat

等历史篇：Structuralevolution

,

I当代篇：FromAcademytoIndustry

计<______________________________

算发展篇：HowtoBuildaPracticalP2Psystem

陈贵海

2006年9月22日

1

Client/ServerModelisBeingChallenged

Nosingleserverorsearchenginecansufficiently

coverincreasingWebcontents.

•2x1018Bytes/yeargeneratedinInternet.

•Butonly3x1012Bytes/yearavailabletopublic

(0.00015%).

•Googleonlysearches1.3x108Webpages.

(Source:IEEEInternetComputing,2001)

概念篇历史篇当代篇发展篇2

Client/ServerModelHasProblems

Client/servermodelseriouslylimitsutilizationof

availablebandwidthandservice.

•Popularserversandsearchenginesbecometraffic

bottlenecks.

•Buthighspeednetworksconnectingmanyclients

becomeidle.

•Computingcyclesandinformationinclientsare

ignored.

概念篇历史篇当代篇发展篇3

ContentDeliveryNetworks(CDN):ATransitionModel

•Serversaredecentralized(duplicated)

throughouttheInternet.

•Thedistributedserversarecontrolledbya

centralizedauthority(headquarters).

•Examples:Internetcontentdistributionsby

Akamai,Overcast,andFFnet.

•BothClient/ServerandCDNmodelshavesingle

pointoffailures.

概念篇历史篇当代篇发展篇4

ANewParadigm:Peer-orientedSystems

•Bothclient(consumer)&server(producer).

•Hasthefreedomtojoinandleaveanytime.

•Hugepeerdiversity:serviceability,storagespace,networking

speed,andservicedemand.

•Awidelydecentralizedsystemopeningforbothopportunities

andnewconcerns.

概念篇历史篇当代篇发展篇

Peer-orientedSystems

Client/serverContentDeliveryNetworks

e.g.Freenet

&Gnutella

概念篇历史篇当代篇发展篇6

ObjectivesandBenefitsofP2P

•Aslongastherenophysicalbreakinthenetwork,

thetargetfilewillalwaysbefound.

•AddingmorecontentstoP2Pwillnotaffectits

performance,(informationscalability).

•AddingandremovednodesfromP2Pwillnot

affectitsperformance,(systemscalability).

概念篇历史篇当代篇发展篇7

Peer-orientedApplications

•FileSharing:documentsharingamongpeerswithnoorlimitedcentral

controls.

•InstantMessaging(IM):Immediatevoiceandfileexchangesamong

peers.

•DistributedProcessing:Onecanwidelyutilizeresourcesavailablein

otherremotepeers.

•Wherearefurtherapplications?

•Gridcomputing

•Adhocnetworking

•Webcache

•VoD

概念篇历史篇当代篇发展篇8

WhatisP2PNetwork-Myversion

■[Equality]Allpeersassumeequalrole.

■[NonCentralized]Nocentralizedserverinthe

space.

■[Robust]Highlyrobust,resilient,andself­

organizing.

■[ZeroHardwareCost]Nofurtherinvestmentsin

hardwareorbandwidth.

■[Ahottopic]Buthugeinvestmentinresearch,

e.g,IRISgot$12M.

概念篇历史篇当代篇发展篇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.

概念篇历史篇当代篇发展篇10

HowDiditStart?

■Akillerapplication:Napster

-FreemusicovertheInternet

■Keyidea:sharethestorageandbandwidthof

individual(home)users

A.A

概念篇历史篇当代篇发展篇11

Model

■Eachuserstoresasubsetoffiles

■Eachuserhasaccess(candownload)filesfrom

allusersinthesystem

概念篇历史篇当代篇发展篇12

MainChallenge

■Findwhereaparticularfileisstored

-Note:problemsimilartofindingaparticularpageinweb

caching

概念篇历史篇当代篇发展篇13

OtherChallenges

■Scalability:uptohundredofthousandsor

millionsofmachines

■Dynamicity:machinescancomeandgoat

anytime

概念篇历史篇当代篇发展篇14

Napster

■Assumeacentralizedindexsystemthatmaps

files(songs)tomachinesthatarealive

■Howtofindafile(song)

-Querytheindexsystem今returnamachinethatstores

therequiredfile

•Ideallythisistheclosest/least-loadedmachine

-ftpthefile

■Advantages:

-Simplicity,easytoimplementsophisticatedsearch

enginesontopoftheindexsystem

■Disadvantages:

-Robustness,scalability(?)

概念篇历史篇当代篇发展篇15

Napster:Example

概念篇历史篇当代篇发展篇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皿

概念篇历史篇当代篇发展篇17

Napster:architectureproblems

■centralizedserver:

-singlelogicalpointoffailure

-canloadbalanceamongserversusingDNSnotation

-potentialforcongestion

-Napster"incontrol(freedomisanillusion)

■nosecurity:

-passwordsinplaintext

-noauthentication

-noanonymity

Napsteristhe1stP2Psystem,botitisactuallynotaP2Psystem.

概念篇历史篇当代篇发展篇18

Gnutella

■Distributefilelocationanddecentralizelookup.

■Idea:multicasttherequest

■Hottofindafile:

-Sendrequesttoallneighbors

-Neighborsrecursivelymulticasttherequest

-Eventuallyamachinethathasthefilereceivestherequest,

anditsendsbacktheanswer

概念篇历史篇当代篇发展篇19

Gnutella:Example

■Assume:mi'sneighborsarem2andm3;m3's

neighborsarem4and

概念篇历史篇当代篇发展篇20

Gnutella:architectureproblems

■Notscalable:theentirenetworkcanbeswampedwith

request(toalleviatethisproblem,eachrequesthasaTTL)

■Notanonymous:Thepersonyouaregettingthefilefrom

knowswhoyouare.

■Notanymorethanitsnon-centralized.

■Whatwecareabout:

,Howmuchtrafficdoesonequerygenerate?

,howmanyhostscanitsupportatonce?

/Whatisthelatencyassociatedwithquerying?

/Isthereabottleneck?

概念篇历史篇当代篇发展篇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".

概念篇历史篇当代篇发展篇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

概念篇历史篇当代篇发展篇23

Query

■API:file=query(/d);

■Uponreceivingaqueryfordocumentid

-Checkwhetherthequeriedfileisstoredlocally

•Ifyes,returnit

•Ifnot,forwardthequerymessage

■Notes:

-EachqueryisassociatedaTTLthatisdecrementedeachtimethe

querymessageisforwarded;toobscuredistancetooriginator:

•TTLcanbeinitiatedtoarandomvaluewithinsomebounds

•WhenTTL=1,thequeryisforwardedwithafiniteprobability

-Eachnodemaintainsthestateforalloutstandingqueriesthathave

traversedithelptoavoidcycles

-Whenfileisreturneditiscachedalongthereversepath

概念篇历史篇当代篇发展篇24

QueryExample

query(10)

1

・Note:

-doesn'tshowfilecachingonthereversepath

-Usedepth-firstsearching.

概念篇历史篇当代篇发展篇25

Insert

■API:inserted,file);

■Twosteps

-Searchforthefiletobeinserted

•Iffound,reportcollision

•ifnumberofnodesexhaustedreportfailure

-Ifnotfound,insertthefile

概念篇历史篇当代篇发展篇26

Insert

■Searching:likequery,butnodesmaintainstate

afteracollisionisdetectedandthereplyissent

backtotheoriginator

■Insertion

-Followtheforwardpath;insertthefileatallnodesalong

thepath

-Anodeprobabilisticallyreplacetheoriginatorwithitself;

obscurethetrueoriginator

概念篇历史篇当代篇发展篇27

InsertExample

■Assumequeryreturnedfailurealong“gray”path;

insertf10

insert(10,f10)

14n5f144n1f4

13n2f1311n5f11

3n68n6

3n1f3

14n4f14

5n3

概念篇历史篇当代篇发展篇28

InsertExample

■Assumequeryreturnedfailurealong“gray”path;

insertf10

insert(10,f10)

10n1f10

4n1f4

14n5f144n1f4

13n2f1311n5f11

3n68n6

3n1f3

14n4f14

5n3

概念篇历史篇当代篇发展篇29

InsertExample

■n2replacestheoriginator(n1)withitself

insert(10,f10)

n1In2

10n1f1010n1f10

4n1f49n3f9

12n2

n4n5

orig=n214n5f144n1f4

13n2f1311n5f11

n33n6

10n2f10

3n1f3

14n4

概念篇历史篇当代篇发展篇30

InsertExample

■n2replacestheoriginator(n1)withitself

■n4replacestheoriginator(n2)withitselftoo

lnsert(10,f10)

n1In2

10n1f1010n1f10

4n1f49n3f9

10n4f10

4n1f4

概念篇历史篇当代篇发展篇31

FreenetProperties

■Newlyqueried/insertedfilesarestoredonnodes

withsimilarids.Birdsflockinfeather.

■Newnodescanannouncethemselvesby

insertingfiles

■Attemptstosupplantordiscoverexistingfileswill

justspreadthefiles

概念篇历史篇当代篇发展篇32

FreenetSummary

■Advantages

-Providespublisheranonymity

-Totallydecentralizearchitecture今robustandscalable

-Resistantagainstmaliciousfiledeletion

■Disadvantages

-Doesnotalwaysguaranteethatafileisfound,evenif

thefileisinthenetwork

-Space-timecomplexity=???

-Sostillnotscalable

概念篇历史篇当代篇发展篇33

|LNewSolutionstotheLocationProblem

IM

■OverlayNetworks:

-applications,runningatvarioussites

-create"logical“links(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)

-郑纬民等，“对等计算研究”中国计算机学会通讯，2005年7月

概念篇历史篇当代篇发展篇34

OverlayNetworks:agenericmodel

OverlayNetwork

peer1peer2peern

routingandroutingandroutingand

locatinglocatinglocating

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

algorithmalgorithmalgorithm

routingtableroutingtableroutingtable

DataStorageDataStorageDataStorage

DataCacheDataCacheDataCache

US~「n

Internet:SupportingNetork

AGenericTopologicalModelofP2PSystems

概念篇历史篇当代篇发展篇35

[OverlayNetworks:MappingtoIPNetwork

o端系统节点o路由器节点

TOverlay链路IP链路

概念篇历史篇当代篇发展篇36

]OverlayNetworks:ConsistentHashing

DavidKarger,EricLehman,TomLeighton,MathhewLevine,Daniel

Lewin,RinaPanigrahy,ConsistentHashingandRandomTrees:

DistributedCachingProtocolsforRelievingHotSpotsonthe

WorldWideWeb,ACMSymposiumonTheoryofComputing,1997

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

概念篇历史篇当代篇发展篇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

概念篇历史篇当代篇发展篇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

概念篇历史篇当代篇发展篇

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

概念篇历史篇当代篇发展篇

ChordalRing:DataStructure

■AssumeidentifierspaceisO..2m-1

■Eachnodemaintains

-Fingertable

•Entryiinthefingertableofnisthefirstnodethat

succeedsorequalsn+2'

-Predecessornode

■Anitemidentifiedbyidisstoredonthesuccessor

nodeofid

概念篇历史篇当代篇发展篇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

历史篇当代篇发展篇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.

概念篇历史篇当代篇发展篇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

概念篇历史篇当代篇发展篇44

ChordExample:self-organization

■Assumeanidentifier

space0..8

■Noden1:(1)joins^all

entriesinitsfinger

tableareinitializedto

itself

概念篇历史篇当代篇发展篇45

ChordExample:self-organization

■Noden2:(2)joins

概念篇历史篇当代篇发展篇46

ChordExample:self-organization

概念篇历史篇当代篇发展篇47

ChordExamples

概念篇历史篇当代篇发展篇48

Query

Uponreceivingaquery

foritemid,anode

Checkwhetherstores

theitemlocally

Ifnot,forwardsthequery

tothelargestnodeinits

successortablethat