新一代对等网络系统拓扑性的研究

Why

P

2

P

1

s

t

Generatio2

n

d

Generatio

n

GenericModel

Problems

Conclusion新一代对等网络系统的拓扑性研究▅

为什么要P2P▅

第一代无结构的P2P系统有什么问题▅

新一代有结构的P2P系统有什么好处▅

新一代P2P系统的拓扑结构模型▅

新一代P2P系统的研究问题南京大学软件新技术国家重点实验室陈贵海2003年12月27日“

计算机科学面临的挑战”

高层研讨会1So

all

together,

we

can

summarize

such

5

propertiesof

P2P

systems:1)Equality2)Dynamicity3)Scalability4)Reliability5)AnonymityWhat

is

P2P

Network—one

version

[Dynamic

operability]

P2P

applications

must

keepoperating

transparently

although

hosts

join

and

leavenetwork

frequently.

[Performance

and

scalability]

P2P

applications

exhibiwhat

economists

call

the

“network

effect”

in

which

anetwork’s

value

to

an

individual

user

scales

with

thetotal

number

of

participants.

[Reliability]

External

attacks

should

not

cause

signidata

or

performance

loss.

[Anonymity]

The

application

should

protect

the

privacpeople

seeking

or

providing

sensitive

information.---M.Ripeaunu,A.Lamnitchi,andI.Foster,“MappingtheGnutellaNetwork”,IEEEIC,No.1,22Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionAccordingtomyversion,someP2PsystemsshouldbeexcludedsuchasNapster,FastTrack().Somyversioncanberegardedasthedefinitionofpure(100%pure)P2Psystems.What

is

P2P

Network—

My

version[Equality]

All

peers

assume

equal

role.[Non

Centralized]

No

centralized

server

in

thespace.[Robust]

Highly

robust,

resilient,

and

self-organizing.[Zero

Hardware

Cost]

No

further

investments

inhardware

or

bandwidth.[A

hot

topic]

But

huge

investment

in

research,e.g,

IRIS

got

$

12M.3Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionHow

Did

it

Start?A

killer

application:

Napster-

Free

music

over

the

Internet

Key

idea:

share

the

storage

and

bandwidth

ofindividual

(home)

usersInternet4Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionNapster:

ExampleABCDEFm1m2m3m4m5m6

m1

A

m2

B

m3

Cm4

Dm5

Em6

FE?m5E?E5Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionNapster:

Historyhistory: 5/99:ShawnFanning(freshman,NortheastenU.)foundsNapsterOnlinemusicservice12/99:firstlawsuit3/00:25%UWisctrafficNapster2000:est.60Musers2/01:USCircuitCourtofAppeals:Napsterknewusersviolatingcopyrightlaws7/01:#simultaneousonlineusers:Napster160K,Gnutella:40K,Now:trytocomeback:6Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionButNapsterisstillcalledasP2Psystem?Itmightbebecausethatinteractionorcommunicationbetweenuseranduserispeer-to-peeralthoughthemanagementofcommunicationismonitoredbyacentralserver.Thisisverymuchsimilartothemobilephone.Conversationbetweenuseranduserispeer-to-peerbutthephonecompanycanmonitoreverything.Napster:

problemscentralized

server:single

logical

point

of

failurecan

load

balance

among

servers

using

DNS

notationpotential

for

congestionNapster

“in

control”

(freedom

is

an

illusion)no

security:passwords

in

plain

textno

authenticationno

anonymityNapster

is

the

1st

P2P

system,

but

it

is

actually

not

a

P2P

system.7Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionGnutellaDistribute

file

location

and

decentralize

lookup.Idea:

multicast

the

requestHot

to

find

a

file:Send

request

to

all

neighborsNeighbors

recursively

multicast

the

request

Eventually

a

machine

that

has

the

file

receives

the

request,and

it

sends

back

the

answerAdvantages:Totally

decentralized,

highly

robustDisadvantages:

Not

scalable;

the

entire

network

can

be

swamped

withrequest

(to

alleviate

this

problem,

each

request

has

a

TTL)8Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionQuestion:

how

to

maintain

the

neighbors’

information?

Is

there

a

neighbor

table

on

each

node?Gnutella:

Example·

Assume:

m1’s

neighbors

are

m2

and

m3;

m3’sneighbors

are

m4

and

m5;…ABCDEFm1m2m3m4m5m6E?E?E?E?E9Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionGnutella:

problems

Not

scalable:

the

entire

network

can

be

swamped

withrequest

(to

alleviate

this

problem,

each

request

has

a

TTL

Not

anonymous:

The

person

you

are

getting

the

file

fromknows

who

you

are.Not

anymore

than

it’s

non-centralized.What

we

care

about:√How

much

traffic

does

one

query

generate?√how

many

hosts

can

it

support

at

once?√What

is

the

latency

associated

with

querying?√Is

there

a

bottleneck?10Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionNew

Solutions

to

the

Location

Problem11Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionOverlay

Networks:applications,

running

at

various

sites

create

“logical”

links

(e.g.,

TCP

or

UDP

connections)

pairwise

betweeneach

other

each

logical

link:

multiple

physical

links,

routing

defined

by

native

InroutingGoal:

Scalability,

Resilient,

Security.Abstraction:

a

distributed

hash-table

data

structure

+

routing

tKey

=

hash(data);Key

=

hash(IP)data=

lookup(key);Note:

data

can

be

anything:

a

data

object,

document,

file,

pointer

to

a

fProposals-

Koorde[MIT]-

Viceroy[Weizman]-Cycloid[南京大学]CAN

(ACIRI/Berkeley)Chord

(MIT)Pastry

(Rice)Tapestry

(Berkeley)Overlay

Networks:

Consistent

Hashing12Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionSHA-1:/PICS/DSig/SHA1_1_0.htmlDavid

Karger,

Eric

Lehman,

Tom

Leighton,

Mathhew

Levine,

DanLewin,

Rina

Panigrahy,

Consistent

Hashing

and

Random

TreeDistributed

Caching

Protocols

for

Relieving

Hot

Spots

onWorld

Wide

Web,

ACM

Symposium

on

Theory

of

Computing,

1997Overlay

Networks:

Typical

Systems

1Ring

Mesh

HypercubeSystemsChord[MIT]

CAN[Berkeley]PersonsRatnasamy,ShenkerStoica(formerly

in

MIT)Pastry[Rice],Tapestry[Berkeley]Druschel,RowstronApplicationsDabekKaashoekStoicaCFSPAST,

SCRIBE,

OceanStoreKey

space1-dimensional

cycle2

or

d-dimensional

torus1-dimensional

cycleSpace-timecomplexityDatadistributionEach

node

holds

a

zone

Each

node

holds

a

segment

ofof

data

keys

where

itself

data

keys

that

are

the

closestresides numerically.lookup(k) region(k)lookup(k)

nearest(k)DatalocationRoutingtableEach

node

holds

a

segmentof

data

keys

betweenpredecessor

and

itself.lookup(k)

successor(k)Successor

set

+fingersneighborsleaf

set

+proximity

set

+neighobrs13Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionOverlay

Networks:

Typical

Systems

2DeBruijn

Butterfly

CCCSystemsViceroy[Weizman]

Cycloid[NJU,Wayne]PersonsKoorde[MIT]ODRI[Texas

A&M]Kaashoek,

Karger,Malkhi,

Naor,

RatajczakGuihai

ChenChengzhong

XuApplicationsLoguinov,Kumar,

Rai?

?

??

?

?Key

space1-dimensional

cycle1-dimensional

cycle2-dimensional

cycleSpace-timecomplexityDatadistributionEach

node

holds

asegment

of

keys

that

areEach

node

holds

a

segment

ofdata

keys

that

are

the

closesttheclosestnumerically.numerically.DatalocationRoutingtableEach

node

holds

a

segmentof

data

keys

betweenpredecessor

and

itself.lookup(k)

successor(k)Successor

set

+fingerslookup(k)

nearest(k)

lookup(k)

nearest(k)7neighbors 5neighbors?

??14Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionOverlay

Networks:

a

generic

model15Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionOverlay

Networks:

criteria,

issues

or

topics16Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionCan

one

network

be

modified

as

a

P2P

overlay

network?Ordered

Key

Space:

a

necessary

measurement

of

distance.

Convergent

Routing

Algorithm:

arriving

at

the

destination

afterfixed

number

of

stepsResilient

Connection

Pattern:

node

maintain

continuousconnections

to

neighbors.Factors

affecting

the

performance

of

P2P

systemsDegree:

the

number

of

neighborsRouting

length:

the

number

of

hopsfault

tolerance:

what

fraction

of

nodes

can

fail

Maintenance

overhead:

how

many

messages

are

passed

tomaintain

coherenceload

balance:

how

evenly

keys

are

distributed,

how

often

eachnode

works

as

an

intermediate

node

for

other

routs.Security

and

ProtectionTrustAnonymityReputationIntelligent

Agents/Web-based

ServicesMatchmakingService

DescriptionDistributed

DatabasesQuery

DecompositionQuery

DistributionMediationP2PSociometry

Small

World

PhenomenaPower-Law

NetworksBusiness

andLegal

IssuesBusiness

ModelsIntellectual

Property

RightsDistributed

DataStructures

Distributed

Hash

TablesScalable

DistributedData

StructuresP2P

IssuesNetwork

Architectureand

DesignNetwork

TopologyRoutingOverlay

Networks17Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionP2P

Issues18Why

P

2

PGeneric

ModelProblems

1

s

t

Generatio2

n

d

GenerationConclusionWhat

topologies

can

be

used

for

P2P

systems?How

to

determine

the

dime