[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 07:52:20 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 02/12/10 07:52:20
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
Log message:
DHT updates
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.21&tr2=1.22&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.21
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.22
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.21 Tue Dec
10 07:32:28 2002
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Tue Dec 10
07:52:20 2002
@@ -234,27 +234,27 @@
\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)$.
+size of $O(log n)$. When a node leaves or joins to network, $O(log^2 n)$
messages are required.
\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.
+the pathlength of $O(log n)$, each node has $O(log n)$ neighbors and departure
or joining of node requires $(log^2 n)$ messages.
\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.
+neighbors. In CAN, nodes have $O(d)$ neighbors and expected pathlengths are
$O(dn^\frac{1}{d})$. Node insertion or deletion affects
+$O(number of dimensions)$ existing nodes. 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.
+hops. Additionally in Chord, a node join or leave requires $O(log^2 n)$
messages.
\subsection{Kademlia}
- [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ä, 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ä <=
- [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