[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert... |
Date: |
Tue, 10 Dec 2002 06:48:36 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 02/12/10 06:48:35
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
progradu.bib
Log message:
Review of existing DHTs
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.18&tr2=1.19&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.26&tr2=1.27&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.18
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.19
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.18 Thu Dec
5 05:50:40 2002
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Tue Dec 10
06:48:35 2002
@@ -165,12 +165,12 @@
-Anonymity and Autonomy
-Self-organization
-Cost Of ownership
-ad-hoc connectivity
-accountability
-reputation
+Anonymity and Autonomy\
+Self-organization\
+Cost Of ownership\
+ad-hoc connectivity\
+accountability\
+reputation\
\subsection{Adaptations of Peer-to-Peer}
@@ -206,13 +206,67 @@
\chapter{Summary of existing Peer-to-Peer file sharing systems}
+In this section, we review briefly existing algorithms used in existing
Peer-to-Peer systems.
+
+\section{Distributed Hash Tables}
+
+In DHT approach, each value is associated with a key in an m-bit virtual
address space. The virtual
+address space is partitioned into sections, which form adjoining regions of
this address space. In general,
+either a single computer or multiple computers is assigned to each section of
the virtual address space. Each
+computer is assigned one or more sections, and they maintains copies of those
key-value bindings whose key values
+lie within its assigned cell. The allocation of the address space and the
assigment of computers to sections
+is dynamic. Therefore, everytime when a node joins or leaves the network, the
address space is reallocated.
+
+\subsection{Plaxton Algorithm}
+Plaxton \cite{plaxton97accessingnearby} developed the first routing algorithm,
which can be used with DHTs.
+The algorithm is not designed to be used in dynamic distributed systems,
because Plaxton algorithm
+assumes a proportional static node population. However, algorithm provides
very efficient routing for search
+lookups. In Plaxton's approach, the routing works as follows: if a node number
e.g. 88768 received a lookup with key
+88797, which matches the first three digits, then the routing algorithm
forwards the query to a node which matches
+the first four digits. To accomplish this, a each node forwards a packet to a
neighbor whose label matches (from left
+to right) incrementally the destination label in one more digit than its own
label does. For a system with $n$ nodes,
+Plaxton's algorithm routes in $O(log n)$ hops and requires a routing table
size of $O(log n)$.
+
+
+\subsection{Tapestry}
+Tapestry \cite{zhao01tapestry} is a adaption of Plaxton's algorithm
\cite{plaxton97accessingnearby}. Tapestry
+routes queries with path lengths of $O(log n)$, and each node, for a systems
with $n$ nodes, maintains routing table
+size of $O(log n)$.
+
+\subsection{Pastry}
+In Pastry \cite{rowston01pastry}, the key space is considered as a virtual
circle. Each node is responsible for keys
+which are closest numerically. The neighbors consist of leaf set, which is the
set of $|L|$ closest nodes. In addition,
+Pastry has another set of neighbors randomly spread out in the key space for
more efficient routing. As in Plaxton approach,
+Pastry also forwards the query to the neighbor which have the longest shared
prefix of the key. Pastry routes within
+the pathlength of $O(log n)$ and each node has $O(log n)$ neighbors.
+
+\subsection{CAN}
+In the CAN model \cite{ratnasamy01can}, nodes are mapped into a virtual
$d$-dimensional coordinate key space. Each node
+is associated with a hypercubal blocks of this keyspace and every block keeps
information on its immediate hypercubal
+neighbors. In CAN, nodes have $O(d)$ neighbors and expected pathlengths are
$O(dn^\frac{1}{d})$. Setting
+$d = log_2(n)/2$, CAN provides similar scalability as Plaxton approach.
+
+\subsection{Chord}
+Chord \cite{stoica01chord} uses virtual circle as the key space. As Pastry,
Chord also threats node's neighbors as leaf sets.
+However, in Chord, there are two sets of neighbors: each node has a successor
list of k nodes which immediately follows the node
+in the key space. For better efficiency, each node has additional finger list
of $O(log n)$ nodes placed around the key space.
+In a $n$ node network, each node maintains information about $O(log n)$
neighbors, and a lookup is performed within $O(log n)$
+hops. Additionally in Chord, a join or leave requires $O(log^2 n)$ messages.
+
+
+\subsection{Kademlia}
+
+Kademlia \cite{maymounkov02kademlia} is based on a XOR-based metric topology.
In this approach, every query (message) exchanged conveys
+useful contact information. Furthermore, Kademlia uses this information to
send parallel query messages. XOR-metrics are used to calculate
+distances between points in key space. XOR is symmetric, allowing nodes to
receive lookup queries from the same distribution of nodes
+contained in the key space. Routing table contains ''contact buckets'', which
allows to accommodate temporarily used nodes more
+efficiently than other DHT approaches. For a system with $n$ nodes, Kademlia's
algorithm routes in $O(log n)$ hops and requires
+a routing table size of $O(log n)$.
+
+
+
\section{Gnutella}
-\section{Plaxton}
\section{OceanStore}
-\section{Tapestry}
-\section{Pastry}
-\section{Chord}
-\section{CAN}
\section{GISP}
\section{Coral}
\section{Yappers}
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.26
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.27
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.26 Thu Dec 5
05:50:40 2002
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib Tue Dec 10
06:48:35 2002
@@ -1179,3 +1179,18 @@
booktitle = {In Proc. Systemics, Cybernetics and Informatics (SCI)}
(2002)},
year = {2002}
}
+
+%DIET system (small world network)
address@hidden,
+ author = {Cefn Hoile and Fang Wang and Erwin Bonsma and Paul Marrow},
+ title = {Core specification and experiments in DIET: a decentralised
ecosystem-inspired mobile agent system},
+ booktitle = {Proceedings of the first international joint conference on
Autonomous agents and multiagent systems},
+ year = {2002},
+ isbn = {1-58113-480-0},
+ pages = {623--630},
+ location = {Bologna, Italy},
+ doi = {http://doi.acm.org/10.1145/544862.544890},
+ publisher = {ACM Press},
+}
+
+
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/05
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/10
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/11
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/11
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2002/12/12