[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/03/20 03:43:18

Modified files:
        Documentation/misc/hemppah-progradu: masterthesis.tex 

Log message:
        More reorg

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.160&tr2=1.161&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.160 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.161
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.160      Thu Mar 
20 03:22:50 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Mar 20 
03:43:18 2003
@@ -352,6 +352,15 @@
 \label{fig:Strucutred_lookup_using_DOLR_model}
 \end{figure}
 
+Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed four 
requirements
+for tightly structured overlays which have to be addressed in order 
+to perform efficient data lookups in tightly structured overlays. 
+First, mapping of keys to peers must be done in a load-balanced
+way. Second, the overlay must be able to forward a lookup for a 
+specific key to an appropriate peer. Third, overlay must have
+support for a efficient distance function. Finally,  routing tables for each 
peer
+must be constructed and maintained adaptively.
+
 To store data into a tightly structured overlay, each application-specific
 unique key (e.g., SHA-1 \cite{fips-sha-1}) is \emph{mapped} uniformly (e.g., 
using consistent
 hashing \cite{258660}) by the overlay to an existing peer in the overlay. 
Thus, tightly 
@@ -369,14 +378,6 @@
 \label{fig:structured_hashing}
 \end{figure}
 
-Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} which have to be 
-addressed in order to perform efficient data lookups in tightly structured 
overlays. 
-First, mapping of keys to peers must be done in a load-balanced
-way. Second, the overlay must be able to forward a lookup for a 
-specific key to an appropriate peer. Third, overlay must have
-support for a efficient distance function. Finally,  routing tables for each 
peer
-must be constructed and maintained adaptively.
-
 Currently, all proposed tightly structured overlays provide at least 
 poly--logarithmical data lookup operations. However, there are some key 
 differences in the data structure that they use as a routing table. For 
example, Chord 
@@ -394,6 +395,23 @@
 \label{fig:structured_query}
 \end{figure} 
 
+Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and 
Tapestry 
+\cite{zhao01tapestry} uses balanced $k$-trees as routing table's data 
structure. Figure 
+\ref{fig:kademlia_lookup} shows the process of Kademlia's
+data lookup. Viceroy \cite{malkhi02viceroy} maintains a butterfly data 
structure (e.g., \cite{226658}), 
+which requires only a constant number of neighbor peers while providing 
$O(\log{n})$ data lookup
+efficiency. Koorde \cite{kaashoek03koorde}, a recent modification of Chord, 
uses de Bruijn graphs 
+\cite{debruijn46graph} to maintain local routing tables. Koorde 
\cite{kaashoek03koorde} requires 
+each peer to have only about two links to other peers to provide $O(\log{n})$ 
performance.
+
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=8cm]{kademlia_lookup.eps}
+\caption{Kademlia's simplified data lookup process on top of tightly 
structured overlay.}
+\label{fig:kademlia_lookup}
+\end{figure}
+
 
 All messages are routed across the overlay towards peers, whose
 peer identifier is gradually ''closer'' to the key's identifier
@@ -428,25 +446,6 @@
 as other tightly structured overlays, i.e., $O(\log{n})$ space required
 for maintaining information about other peers in the system and 
 $O(\log{n})$ data lookup efficiency.
-
-Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and 
Tapestry 
-\cite{zhao01tapestry} uses balanced $k$-trees as routing table's data 
structure. Figure 
-\ref{fig:kademlia_lookup} shows the process of Kademlia's
-data lookup. Viceroy \cite{malkhi02viceroy} maintains a butterfly data 
structure (e.g., \cite{226658}), 
-which requires only a constant number of neighbor peers while providing 
$O(\log{n})$ data lookup
-efficiency. Koorde \cite{kaashoek03koorde}, a recent modification of Chord, 
uses de Bruijn graphs 
-\cite{debruijn46graph} to maintain local routing tables. Koorde 
\cite{kaashoek03koorde} requires 
-each peer to have only about two links to other peers to provide $O(\log{n})$ 
performance.
-
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=8cm]{kademlia_lookup.eps}
-\caption{Kademlia's simplified data lookup process on top of tightly 
structured overlay.}
-\label{fig:kademlia_lookup}
-\end{figure}
-
-
 
 
 \subsection{Sketch of a formal definition}