Transcript Here is the Power Point Presentation on Chord

Structure Overlay
Networks and Chord
Presentation by Todd Gardner
Figures from: Ion Stoica, Robert Morris, David LibenNowell, David R. Karger, M. Frans Kaashoek, Frank
Dabek, Hari Balakrishnan, Chord: A Scalable Peer-topeer Lookup Protocol for Internet Applications. To
Appear in IEEE/ACM Transactions on Networking
Peer-to-peer networks, History


The first large peer-to-peer network
was Napster
As we went over in class, Napster
relied on a central server to store all
routing information, so it was only
sort of peer-to-peer
Peer-to-peer networks, History


The later peer-to-peer networks, like
Gnutella, are fully distributed, but
don’t have the guarantees Napster
had for finding files
If a file lay beyond your number of
hops on the network, you might not
find it
Structure Overlay Networks



Introducing Chord (and others)
The idea is to build a peer to peer
network, but to offer guarantees
about finding data if it is on the
network
This is accomplished by enforcing a
topology on the network
What do I mean by enforcing a
topology?


This is where it gets complicated
Nodes in a Gnutella-like network join
willy-nilly, using a reference to a
node on the network, and having a
potentially inefficient topology for
searching:
Attempting to correct the problem


A simple solution would just be to
publish well known nodes
This is just recreating Napster
Chord’s Approach



Whenever a node joins a Chord-type
network, it joins a “ring”
All members of the network are on
the same ring
Your position in the ring is
determined by a Key (in most
applications, this key will be your IP
address)
An example ring
Knowledge of the ring from the
Node’s perspective


The node should know about the
next node in the ring – the node’s
successor
The node should have a table of log
n (n is the number of total keys)
other nodes around the ring, with
exponentially increasing keys – the
node’s finger table
Other information


The node stores the previous node in
the ring, it’s predecessor
The node stores values for the
distributed hash table
Storing/Retrieving Data


Data is inserted into the ring with a
Key, which is hashed to be put onto a
node in the table
When one wants to get data, one
takes the key, applies the hash
function to find the Key of the node
it’s on, and uses it’s knowledge of
the table
Best shown by example
So, what does this get us?



If the node’s successors are correct,
it is guaranteed to find the correct
node
If the node’s finger table is correct, it
can do it in logarithmic time.
The protocol includes functions to
update these constantly
Example: DNS

Russ Cox, Athicha Muthitacharoen, Robert T.
Morris, Serving DNS using a Peer-to-Peer Lookup
Service, In the proceedings of the First
International Workshop on Peer-to-Peer Systems
(IPTPS '02), March, 2002; Cambridge, MA.