[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:15:52

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

Log message:
        Started tightly structured overlays

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.91 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.92
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.91       Thu Feb 
27 07:08:58 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 27 
08:15:52 2003
@@ -366,6 +366,51 @@
 
 \section{Tightly structured}
 
+In recents months, several tightly structured overlays has been proposed.
+This list includes CAN \cite{ratnasamy01can}, Chord \cite{stoica01chord}, 
+Kademlia \cite{maymounkov02kademlia}, Kelips \cite{gupta03kelips}, 
+Koorde \cite{kaashoek03koorde}, ODHDHT \cite{naor03simpledht}, 
+Pastry \cite{rowston01pastry}, Peernet \cite{eriksson03peernet}, 
+Skip Graphs \cite{AspnesS2003}, SkipNet \cite{harvey03skipnet2}, 
+Symphony \cite{gurmeet03symphony}, SWAN \cite{bonsma02swan}, Tapestry 
+\cite{zhao01tapestry} and Viceroy \cite{malkhi02viceroy}. While there
+are significat differences among proposed systems, they all have in common
+that participating peers are assigned \emph{peer identifiers} from
+a large \emph{identifier space}. Furthermore, application-specific
+data items are also assigned globally unique identifiers, \emph{keys}, 
+which are selected from the same identifier space. The form of identifier
+space differs between proposed systems. Circular identifier space (and 
variants) 
+is most widely used. For instance, Chord, Koorde, Pastry, SWAN, Tapestry
+and Viceroy use a circular identifier space of $n$-bit integers modulo 
$2^{n}$. The
+value of $n$ varies among approaches. Again, CAN uses a $d$-dimensional 
cartesian 
+to implement identifier space.
+
+To store data into tightly structured overlay, each application-specific
+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} 
+illustrates the process of data to key mapping in tightly strucuted overlays.
+
+\begin{figure}
+\centering
+\includegraphics[width=12cm, height=6cm]{structured_overlay.eps}
+\caption{Basic idea of structured overlay}
+\label{fig:structured_hashing}
+\end{figure}
+
+All messages are routed across overlay links towards peers, whose
+peer identifier is gradually ''closer'' to the key's identifier
+in the identifier space. Distance can be measured by numerical
+difference between identifiers (e.g., Chord), the number of
+same prefix bits between identifiers (e.g., Pastry and Tapestry),
+bit-wise exclusive or (XOR) (e.g., Kademlia). However, in all
+previously schemes, each hop in the overlay shortens the path
+between current peer working with query and the key which was
+looked up.
+
+
+
 -service is data block, node/peer is a physical computer
 -*servers* self-organize towards a lookup network
 -DHTs can be thought as a 'structured overlay random graphs'
@@ -460,32 +505,22 @@
 load balance
 
 
-\cite{zhao01tapestry}
 
-\cite{rowston01pastry}
 
-\cite{stoica01chord}
 
-\cite{ratnasamy01can}
-
-\cite{maymounkov02kademlia}
 
 \cite{freedman02trie}
 
 \cite{plaxton97accessingnearby}
 
-\cite{malkhi02viceroy}
 
-\cite{bonsma02swan}
 
-\cite{AspnesS2003}
+
 \cite{78977}
 
-\cite{gurmeet03symphony}
 
-\cite{eriksson03peernet}
 
-\cite{harvey03skipnet2}
+
 
 
 \cite{garciamolina03sil}
@@ -498,11 +533,7 @@
 
 \cite{pias03lighthouse}
 
-\cite{naor03simpledht}
 
-\cite{gupta03kelips}
-
-\cite{kaashoek03koorde}
 \cite{debruijn46graph}
 
 
@@ -542,13 +573,6 @@
 
 \cite{kubiatowicz00oceanstore}
 
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=6cm]{structured_overlay.eps}
-%\includegraphics[width=10cm, height=6cm]{structured_query.eps}
-\caption{Basic idea of structured overlay}
-\label{fig:structured_hashing}
-\end{figure}