[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/02/27 08:52:24

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

Log message:
        More text

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.92 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.93
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.92       Thu Feb 
27 08:15:52 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 27 
08:52:24 2003
@@ -389,7 +389,7 @@
 key is \emph{mapped} by the overlay to a existing peer in the overlay. Each
 peer in the structured overlay maintains a \emph{routing table}, which consists
 of identifiers and IP addresses of other peers in the overlay. These are peer's
-neighbors in the overlay network.Figure \ref{fig:structured_hashing} 
+neighbors in the overlay network. Figure \ref{fig:structured_hashing} 
 illustrates the process of data to key mapping in tightly strucuted overlays.
 
 \begin{figure}
@@ -409,6 +409,46 @@
 between current peer working with query and the key which was
 looked up.
 
+Stoica et al. \cite{balakrishanarticle03lookupp2p} have listed 
+four requirements for tightly structured overlays, which have to be 
+addressed in order to perform 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 approriate peer. Third, overlay must have a
+support for a distance function. Finally,  routing tables for each peer
+must be constructed and maintained adaptively.
+
+Currently, all proposed tightly structured overlays provide at least 
+poly-logaritmical data lookup operations. However, there are some key 
+differences in routing algoritms. For example, Chord, Skip graphs and 
+Skipnet maintain a local data structure which resembles skip lists 
\cite{78977}.
+In figure \ref{fig:structured_query}, we present overview of Chord's lookup 
process.
+On the left side of Chord's lookup process, we show the same data lookup 
process
+as binary-tree abstraction.  We can notice, that in each step, the distance 
between
+the query originator and the target in both methods is halved. Thus, the 
+locarithmic efficiency. Kademlia, Pastry and Tapestry uses balanced tree-like 
+data structures. Figure \ref{fig:kademlia_lookup} shows the process of Kademlia
+data lookup. Viceroy maintains a butterfly data structure, which requires 
+only constant number of neighbor peers while providing $O(\log{n})$ data lookup
+efficiency. Koorde, recent modification of Chord, uses de Bruijn graphs to 
maintain
+local routing tables. Koorde requires each peer to have only about two links 
to other
+peers to to provide $O(\log{n})$ performance. 
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=6cm]{structured_query.eps}
+\caption{Simplified structured system's query}
+\label{fig:structured_query}
+\end{figure}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=8cm]{kademlia_lookup.eps}
+\caption{Kademlia's lookup process}
+\label{fig:kademlia_lookup}
+\end{figure}
+
 
 
 -service is data block, node/peer is a physical computer
@@ -576,20 +616,7 @@
 
 
 
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=6cm]{structured_query.eps}
-\caption{Simplified structured system's query}
-\label{fig:structured_query}
-\end{figure}
-
 
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=8cm]{kademlia_lookup.eps}
-\caption{Kademlia's lookup process}
-\label{fig:kademlia_lookup}
-\end{figure}
 
 \section{Summary}