[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:22:51

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

Log message:
        Reorg

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.159 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.160
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.159      Thu Mar 
20 03:14:20 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Mar 20 
03:22:50 2003
@@ -188,6 +188,7 @@
 
 \section{Loosely structured}
 
+
 Gnutella \cite{gnutellaurl} is a well-known example of loosely structured 
overlay network. Gnutella
 is a pure Peer-to-Peer network as no peer is more important than any other 
peer in the network.
 The construction and maintenance of Gnutella network is extremely ad hoc, 
since participating
@@ -273,7 +274,6 @@
 Previously presented improvements are only partial solutions. More advanced 
techniques 
 to improve data lookup of loosely structured systems are discussed in chapter 
3.
 
-
 \subsection{Sketch of a formal definition}
 
 In this subsection we formalize loosely structured overlay's main components. 
This
@@ -288,7 +288,6 @@
 peer's content, specifically $sp$, $P$ = \{$p \in P: \exists sp$, 
 where $sp$ = $\delta(\gamma(\delta(s))) \wedge (p = \delta(s))$\}
 
-
 \section{Tightly structured}
 
 Partly due to scalability problems of loosely structured systems, several 
tightly 
@@ -314,6 +313,45 @@
 value of $n$ varies among systems. Again, CAN \cite{ratnasamy01can} uses a 
$d$-dimensional Cartesian 
 model to implement identifier space.
 
+There are three higher level abstractions which tightly structured overlays 
provide
+\cite{zhao03api}. Each of these abstractions fulfill a storage layer in an 
overlay, but
+they have semantical differences in the \emph{usage} of overlay. First, 
Distributed Hash 
+Table (DHT) (see e.g., \cite{dabek01widearea}, \cite{rowstron01storage}),  
+implements three operations: \texttt{lookup(key)}, \texttt{remove(key)} and 
+\texttt{insert(key)}. As the name suggests, DHT implements the same 
functionality 
+as a regular hash table, by storing the mapping between a key and a value. 
DHT's 
+\emph{interface} is generic; values can be any size and type. Figure 
\ref{fig:Structured_lookup_using_DHT_model}
+shows the DHT abstraction of the tightly structured overlay. Second, 
Decentralized 
+Object Location (DOLR) (see e.g., \cite{kubiatowicz00oceanstore}, 
\cite{iyer02squirrel}) is a distributed 
+directory service. DOLR stores \emph{pointers} to data items throughout the 
overlay. DOLR's main 
+operations are \texttt{publish(key)}, \texttt{removePublished(key)} and 
\texttt{sendToObject(key)}. The key 
+difference between DHT and DOLR abstraction is that DOLR routes overlay's 
messages
+to nearest available peer, hosting a specific data item. This form of locality
+is not supported by DHT. Finally, tightly structured overlay can be used for
+scalable group multicast/any cast operations (CAST) (see e.g., 
\cite{zhuang01bayeux}).
+The basic operations are \texttt{join(groupIdentifier)}, 
\texttt{leave(groupIdentifier)},
+\texttt{multicast(message, groupIdentifier)},  \texttt{anycast(message, 
groupIdentifier)}.
+Participating peers may join and leave the group and send multicast messages to
+the group, or anycast message to a specific member of the group. DOLR and CAST 
abstractions
+have in common that they both use network proximity techniques
+to optimize their operations in the overlay. Figure 
\ref{fig:Strucutred_lookup_using_DOLR_model}
+presents the DOLR abstraction. 
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=7cm]{DHT_lookup.eps}
+\caption{Distributed Hash Table (DHT) abstraction of tightly structured 
overlay.}
+\label{fig:Structured_lookup_using_DHT_model}
+\end{figure}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=7cm]{DOLR_lookup.eps}
+\caption{Decentralized Object Location (DOLR) abstraction of tightly 
structured overlay.}
+\label{fig:Strucutred_lookup_using_DOLR_model}
+\end{figure}
+
 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 
@@ -331,6 +369,32 @@
 \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 
+\cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and SkipNet 
\cite{harvey03skipnet2} maintain a local 
+data structure which resembles Skip lists \cite{78977}.
+In figure \ref{fig:structured_query}, we present an overview of Chord's lookup 
process.
+On the right side of Chord's lookup process, the same data lookup process
+is shown as a binary-tree abstraction.  It can be noticed, that in each step, 
the distance 
+decreases with a logarithmic efficiency.
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=6cm]{structured_query.eps}
+\caption{Chord's simplified data lookup process on top of tightly structured 
overlay.}
+\label{fig:structured_query}
+\end{figure} 
+
+
 All messages are routed across the overlay towards peers, whose
 peer identifier is gradually ''closer'' to the key's identifier
 in the identifier space. The distance can be measured by numerical
@@ -365,24 +429,6 @@
 for maintaining information about other peers in the system and 
 $O(\log{n})$ data lookup efficiency.
 
-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 
-\cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and SkipNet 
\cite{harvey03skipnet2} maintain a local 
-data structure which resembles Skip lists \cite{78977}.
-In figure \ref{fig:structured_query}, we present an overview of Chord's lookup 
process.
-On the right side of Chord's lookup process, the same data lookup process
-is shown as a binary-tree abstraction.  It can be noticed, that in each step, 
the distance 
-decreases with a logarithmic 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
@@ -392,13 +438,6 @@
 \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=6cm]{structured_query.eps}
-\caption{Chord's simplified data lookup process on top of tightly structured 
overlay.}
-\label{fig:structured_query}
-\end{figure}
-
 
 \begin{figure}
 \centering
@@ -408,44 +447,6 @@
 \end{figure}
 
 
-There are three higher level abstractions which tightly structured overlays 
provide
-\cite{zhao03api}. Each of these abstractions fulfill a storage layer in an 
overlay, but
-they have semantical differences in the \emph{usage} of overlay. First, 
Distributed Hash 
-Table (DHT) (see e.g., \cite{dabek01widearea}, \cite{rowstron01storage}),  
-implements three operations: \texttt{lookup(key)}, \texttt{remove(key)} and 
-\texttt{insert(key)}. As the name suggests, DHT implements the same 
functionality 
-as a regular hash table, by storing the mapping between a key and a value. 
DHT's 
-\emph{interface} is generic; values can be any size and type. Figure 
\ref{fig:Structured_lookup_using_DHT_model}
-shows the DHT abstraction of the tightly structured overlay. Second, 
Decentralized 
-Object Location (DOLR) (see e.g., \cite{kubiatowicz00oceanstore}, 
\cite{iyer02squirrel}) is a distributed 
-directory service. DOLR stores \emph{pointers} to data items throughout the 
overlay. DOLR's main 
-operations are \texttt{publish(key)}, \texttt{removePublished(key)} and 
\texttt{sendToObject(key)}. The key 
-difference between DHT and DOLR abstraction is that DOLR routes overlay's 
messages
-to nearest available peer, hosting a specific data item. This form of locality
-is not supported by DHT. Finally, tightly structured overlay can be used for
-scalable group multicast/any cast operations (CAST) (see e.g., 
\cite{zhuang01bayeux}).
-The basic operations are \texttt{join(groupIdentifier)}, 
\texttt{leave(groupIdentifier)},
-\texttt{multicast(message, groupIdentifier)},  \texttt{anycast(message, 
groupIdentifier)}.
-Participating peers may join and leave the group and send multicast messages to
-the group, or anycast message to a specific member of the group. DOLR and CAST 
abstractions
-have in common that they both use network proximity techniques
-to optimize their operations in the overlay. Figure 
\ref{fig:Strucutred_lookup_using_DOLR_model}
-presents the DOLR abstraction. 
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=7cm]{DHT_lookup.eps}
-\caption{Distributed Hash Table (DHT) abstraction of tightly structured 
overlay.}
-\label{fig:Structured_lookup_using_DHT_model}
-\end{figure}
-
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=7cm]{DOLR_lookup.eps}
-\caption{Decentralized Object Location (DOLR) abstraction of tightly 
structured overlay.}
-\label{fig:Strucutred_lookup_using_DOLR_model}
-\end{figure}
 
 
 \subsection{Sketch of a formal definition}