HS P2P Liao

Information about HS P2P Liao

Published on June 19, 2007

Author: Mahugani

Source: authorstream.com

Content

Chord - A Distributed Hash Table:  Chord - A Distributed Hash Table Yimei Liao Outline:  Outline Lookup problem in Peer-to-Peer systems and Solutions Chord Algorithm Consistent Hashing Scalable Key Location Node joins Stabilization Summary Peer-to-Peer Systems:  Peer-to-Peer Systems Peer-to-Peer System: self-organizing system of equal, autononous entities (peers) decentralized resource usage decentraliced self-organization where to store? where to get? Solutions centralized servers flooding search distributed Hash Tables Solutions to lookup problem:  Solutions to lookup problem centralized servers Maintain the current location of data items in a central server Search complexity O(1) Central server becomes crucial Best for simple and small applications flooding search Broadcast a request for an item among the nodes No additional routing informations High bandwidth consumption Search complexity O(N2) Results are not guaranteed Solutions to lookup problem:  Solutions to lookup problem distributed hash tables A global view of data distributed among many nodes. Mapping nodes and data items into a common address space Each DHT node manages a small number of references to other nodes Queries are routed via a small number of nodes to the target node Load for retrieving items should be balanced equally among all nodes Robust against random failure and attacks Provides a definitive answer about results Chord Algorithm – Consistent Hashing:  Chord Algorithm – Consistent Hashing supports just one operation: given a key, it maps the key onto a node. Consistent Hashing Assign each node and key an m-bit identifier using a base hash function such as SHA-1 Identifiers are ordered in an identifier circle modulo 2m (Chord ring) Key k is assigned to the first node whose identifier is equal to or follows k. Chord Algorithm – Consistent Hashing:  Chord Algorithm – Consistent Hashing identifier space : m=3 node key 0 1 3 1 2 6 1 identifier circle Chord Algorithm – Simple Key Lookup:  Chord Algorithm – Simple Key Lookup Simple Key Lookup 1 2 6 Queries are passed around the circle via successor pointers Requires traversing all Nodes to find the appropriate mapping successor(1) = 3 successor(3) = 6 successor(6) = 0 successor(0) = 1 Node 0 sends a query for key 6 Chord Algorithm – Scalable Key Location:  Chord Algorithm – Scalable Key Location Finger Table Each node n maintains a routing table with up to m entries The ith entry in the table at node n contains the identifier of the first node s that succeeds n by at least 2i-1 on the identifier circle.(s = successor(n+2i-1)). s is called the ith finger of node n. Definition of variables for node n Chord Algorithm – Scalable Key Location:  Chord Algorithm – Scalable Key Location Finger table m = 3, each node n maintains at most 3 entries finger table keys 0+20 0+21 0+22 1 2 4 [1,2) 3 3 6 [2,4) [4,0) finger table keys 3+20 3+21 3+22 4 5 7 [4,5) 6 6 0 [5,7) [7,3) 1 2 finger table keys 6+20 6+21 6+22 7 0 2 [7,0) 0 0 3 [0,2) [2,6) 5 Chord Algorithm – Scalable Key Location:  Chord Algorithm – Scalable Key Location Pseudocode to find the successor node of an identifier Walk clockwise to find the node which precedes id and whose successor succeeds id Start with the mth finger of node n See if it comes between node n and the id, if not, check the m-1th finger until we find one wich does. This is the closest node preceding id among all the fingers of n Find id’s successor by finding the immediate predecessor of the id Chord Algorithm – Scalable Key Location:  Chord Algorithm – Scalable Key Location id=5 n=7 finger table keys finger table keys 1 2 finger table keys 6 4 Successor 0 Predecessor 4 3 Successor 3 Predecessor 7 Successor Predecessor 0 finger table keys Successor Predecessor 3 7 4 7 7 successor(5) = 7 4 O(logN) Chord Algorithm - Node joins:  Chord Algorithm - Node joins Invariants to be preserve Each node’s successor is correctly maintained For every key k, node successor(k) is responsible for k It is desirable for the finger tables to be correct Tasks to be performed by Chord Initialize the predecessor and fingers of node n Update the fingers and predecessor of existing nodes to reflect the addition of n Notify the higher layer software so that it can transfer state associated with keys that node n is now responsible for Chord Algorithm - Node joins:  Chord Algorithm - Node joins finger table keys finger table keys 1 2 finger table keys 6 4 Successor 0 Predecessor 3 5 Successor 3 Predecessor 6 Successor 6 Predecessor 0 finger table keys 7 7 3 Successor Predecessor 7 3 Initializing fingers and predecessor find_successor(6); Chord Algorithm - Node joins:  Chord Algorithm - Node joins finger table keys 5 finger table keys 5 1 2 finger table keys 6 4 Successor 0 Predecessor 3 5 Successor 3 Predecessor 6 Successor 7 Predecessor 0 5 finger table keys 7 7 3 Successor Predecessor 7 3 5 Updating fingers of existing nodes 3 3 P = find_predecessor(n-2i-1) i = 1, P = find_predecessor(4) i = 2, P = find_predecessor(3) i = 3, P = find_predecessor(1) 3 O(log2N) Chord Algorithm - Node joins:  Chord Algorithm - Node joins finger table keys 6 finger table keys 5 1 2 finger table keys 6 4 Successor 0 Predecessor 3 5 Successor 3 Predecessor 6 Successor 6 Predecessor 0 5 finger table keys 7 7 3 Successor Predecessor 7 3 5 Transferring Keys Chord Algorithm – node joins:  Chord Algorithm – node joins Pseudocode for the node join operation Chord Algorithm - Stabilization:  Chord Algorithm - Stabilization Stabilization Correctness and performance Keep node‘s successor pointers up to date Use successor pointers to verify correct finger table entries Chord Algorithm - Stabilization:  Chord Algorithm - Stabilization Pseudocode for stabilization Join does not make the rest of the network aware of n Every node runs stabilize periodically, to verify the successor Use successor pointers to update finger tables. Node n asks its successor for the successor’s predecessor x. See if x should be n’s successor instead. (happens if x recently joined the system) Notify n’s successor of n’s exist. Successor changes its predecessor to n if it knows no closer predecessor than n. Chord Algorithm – Node Failure:  Chord Algorithm – Node Failure Node Failure Successor-list If successor fails, replaces it with the first live entry in the list Later run stabilize to correct finger table and successor-list Summary:  Summary Characteristics of Chord Load balance distributed hash table Decentralization fully distributed Scalability cost of lookup grows logarithmic Availability automatically adjusts internal tables Flexible naming no constrains on the structure of the keys References:  References I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149–160, 2001. R. Steinmetz, K. Wehrle (Edt.): 'Peer-to-Peer Systems and Applications', LNCS 3485, Springer, Chapter 7-8, 2005. http://www.wikipedia.org http://www.google.com Slide23:  Thank You Questions?

Related presentations


Other presentations created by Mahugani

Exploring the Deep Web
12. 03. 2008
0 views

Exploring the Deep Web

Moving Mountains
02. 10. 2007
0 views

Moving Mountains

dustbowl
10. 10. 2007
0 views

dustbowl

The Internet China
12. 10. 2007
0 views

The Internet China

shen 1
12. 10. 2007
0 views

shen 1

Triumph of Bolshevism
12. 10. 2007
0 views

Triumph of Bolshevism

Kukovecz
15. 10. 2007
0 views

Kukovecz

09 Panama s ppt
22. 10. 2007
0 views

09 Panama s ppt

Common By Product Feeds
04. 10. 2007
0 views

Common By Product Feeds

Dissertation Writing comms ug
27. 11. 2007
0 views

Dissertation Writing comms ug

TT
27. 11. 2007
0 views

TT

black holes v2
28. 11. 2007
0 views

black holes v2

Production of Calla Lily
07. 12. 2007
0 views

Production of Calla Lily

Water Track 8 7 15 051
07. 11. 2007
0 views

Water Track 8 7 15 051

PVC Toronto talk
16. 11. 2007
0 views

PVC Toronto talk

2022lecture2
19. 11. 2007
0 views

2022lecture2

Robertson
03. 10. 2007
0 views

Robertson

20050922 Crafoord Symposium
29. 08. 2007
0 views

20050922 Crafoord Symposium

field mmr naga
31. 12. 2007
0 views

field mmr naga

Anthony Kelly International
02. 01. 2008
0 views

Anthony Kelly International

fy2004 mfc construction
04. 01. 2008
0 views

fy2004 mfc construction

NASC PresentHanson
08. 08. 2007
0 views

NASC PresentHanson

Nicosia Raymond Pawson
08. 08. 2007
0 views

Nicosia Raymond Pawson

Methamphetamine final10 05
08. 08. 2007
0 views

Methamphetamine final10 05

ppt43
16. 10. 2007
0 views

ppt43

McCarthy Mitchell
29. 08. 2007
0 views

McCarthy Mitchell

Update FutureDirection LRago
22. 10. 2007
0 views

Update FutureDirection LRago

gef 160306
23. 10. 2007
0 views

gef 160306

IT Trends 2005 2010
14. 11. 2007
0 views

IT Trends 2005 2010

rec pond mgnt compressed
07. 01. 2008
0 views

rec pond mgnt compressed

Sci Case II
29. 08. 2007
0 views

Sci Case II

markenklima index q1 2005
05. 01. 2008
0 views

markenklima index q1 2005

yalenov2006
29. 08. 2007
0 views

yalenov2006

media 4917
08. 08. 2007
0 views

media 4917

gatorsncrocs
12. 10. 2007
0 views

gatorsncrocs

Eradicating Systemic Poverty
29. 11. 2007
0 views

Eradicating Systemic Poverty

Kennedy obesity 0904
08. 08. 2007
0 views

Kennedy obesity 0904

jsimon santacruz
29. 08. 2007
0 views

jsimon santacruz

9 0568 rusack r
20. 11. 2007
0 views

9 0568 rusack r

soc100ch10Corepwrpt
19. 02. 2008
0 views

soc100ch10Corepwrpt

Edward Albee
24. 02. 2008
0 views

Edward Albee

AFCEA NOVA Breakfast7Sept07v1
06. 03. 2008
0 views

AFCEA NOVA Breakfast7Sept07v1

Lakeside2
26. 03. 2008
0 views

Lakeside2

sHansen
29. 08. 2007
0 views

sHansen

Tectonics Terrestrial Planets2
07. 04. 2008
0 views

Tectonics Terrestrial Planets2

Sept SECC
02. 11. 2007
0 views

Sept SECC

Hercules
28. 03. 2008
0 views

Hercules

deprez presentation 12 1 05
30. 03. 2008
0 views

deprez presentation 12 1 05

HARIPARSAD Ishwarie 2
09. 04. 2008
0 views

HARIPARSAD Ishwarie 2

Beaulieu
10. 04. 2008
0 views

Beaulieu

sings2mw
29. 08. 2007
0 views

sings2mw

molgas twong
29. 08. 2007
0 views

molgas twong

newman1
14. 04. 2008
0 views

newman1

session 25 V2
17. 04. 2008
0 views

session 25 V2

Citel
22. 04. 2008
0 views

Citel

icra02
19. 06. 2007
0 views

icra02

ICHEP 04 Barr Higgs
19. 06. 2007
0 views

ICHEP 04 Barr Higgs

IBERs and e Theses
19. 06. 2007
0 views

IBERs and e Theses

he b
19. 06. 2007
0 views

he b

HB2004
19. 06. 2007
0 views

HB2004

Hartenstein Oerebro03 pt1
19. 06. 2007
0 views

Hartenstein Oerebro03 pt1

Grid InteropSupport
19. 06. 2007
0 views

Grid InteropSupport

Grid Interop
19. 06. 2007
0 views

Grid Interop

grid 06talk
19. 06. 2007
0 views

grid 06talk

wednesday
29. 08. 2007
0 views

wednesday

comer5e ch08 HO
15. 11. 2007
0 views

comer5e ch08 HO

SAG YinG 9 Jan New
03. 01. 2008
0 views

SAG YinG 9 Jan New

02 Cattle2
26. 11. 2007
0 views

02 Cattle2

Grid Shib uk april05
19. 06. 2007
0 views

Grid Shib uk april05

J Acar
14. 03. 2008
0 views

J Acar

20061130 woodling
30. 12. 2007
0 views

20061130 woodling

ch02exoh
07. 01. 2008
0 views

ch02exoh

Choose your way carefully
03. 10. 2007
0 views

Choose your way carefully

4 vista
16. 06. 2007
0 views

4 vista

33233 11162218 S
16. 06. 2007
0 views

33233 11162218 S

23
16. 06. 2007
0 views

23

2007 tips tricks
16. 06. 2007
0 views

2007 tips tricks

19b
16. 06. 2007
0 views

19b

EPL Membership
16. 06. 2007
0 views

EPL Membership

Entire Gra duation Slideshow
16. 06. 2007
0 views

Entire Gra duation Slideshow

elley web graphics
16. 06. 2007
0 views

elley web graphics

A Loose Confederation
14. 12. 2007
0 views

A Loose Confederation

employee 2004
16. 06. 2007
0 views

employee 2004

Obesity 1
08. 08. 2007
0 views

Obesity 1

Active Kill Disk
19. 06. 2007
0 views

Active Kill Disk

teall cost 3 ch16
24. 02. 2008
0 views

teall cost 3 ch16

CFA05
29. 08. 2007
0 views

CFA05

gemini sab
29. 08. 2007
0 views

gemini sab

NINDS Audience Report
08. 08. 2007
0 views

NINDS Audience Report

mm1
29. 08. 2007
0 views

mm1

ENGD POWERPOINT
16. 06. 2007
0 views

ENGD POWERPOINT

I3C BSML July2002
19. 06. 2007
0 views

I3C BSML July2002

igt 3
04. 03. 2008
0 views

igt 3

MassesofGalaxies
29. 08. 2007
0 views

MassesofGalaxies