[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu DHT_loo...
|
From: |
Hermanni Hyytiälä |
|
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu DHT_loo... |
|
Date: |
Fri, 21 Mar 2003 09:48:16 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 03/03/21 09:48:15
Modified files:
Documentation/misc/hemppah-progradu: DHT_lookup.eps
DOLR_lookup.eps
masterthesis.tex
Log message:
More updates
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/DHT_lookup.eps.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/DOLR_lookup.eps.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.169&tr2=1.170&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/DHT_lookup.eps
diff -u gzz/Documentation/misc/hemppah-progradu/DHT_lookup.eps:1.2
gzz/Documentation/misc/hemppah-progradu/DHT_lookup.eps:1.3
--- gzz/Documentation/misc/hemppah-progradu/DHT_lookup.eps:1.2 Thu Mar 13
04:55:50 2003
+++ gzz/Documentation/misc/hemppah-progradu/DHT_lookup.eps Fri Mar 21
09:48:14 2003
@@ -1,11 +1,11 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Title: DHT_lookup.dia
%%Creator: Dia v0.90
-%%CreationDate: Thu Mar 13 11:42:27 2003
+%%CreationDate: Fri Mar 21 16:36:43 2003
%%For: a user
%%Magnification: 1.0000
%%Orientation: Portrait
-%%BoundingBox: 0 0 572 382
+%%BoundingBox: 0 0 576 379
%%Pages: 1
%%EndComments
%%BeginProlog
@@ -77,7 +77,7 @@
%%BeginSetup
%%EndSetup
28.346000 -28.346000 scale
--6.770730 -16.850010 translate
+-6.639680 -16.750010 translate
1.000000 1.000000 1.000000 srgb
n 7.895000 7.750000 1.000000 1.000000 0 360 ellipse f
@@ -137,9 +137,9 @@
n 22.445000 10.600000 1.000000 1.000000 0 360 ellipse cp s
[ /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
- /O /w /n /e /r /R /q /u /xi /xi /s /t /one /period /space /Q
- /y /b /m /i /two /F /o /a /d /three /l /k /p /g /four /five
- /c /h /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
+ /P /r /o /v /i /d /e /R /xi /xi /q /u /s /t /one /period
+ /space /Q /y /b /m /two /F /w /a /three /n /l /k /p /g /four
+ /five /c /h /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
@@ -161,12 +161,12 @@
currentdict end
definefont pop
/Helvetica_e0 ff 0.700000 scf sf
-( !"#$) sw
-2 div 7.887230 ex sub 15.536300 m ( !"#$)
+( !"#$%&!) sw
+2 div 8.037230 ex sub 15.536300 m ( !"#$%&!)
gs 1 -1 sc sh gr
/Helvetica_e0 ff 0.700000 scf sf
-(%#&'#*+#$) sw
-2 div 25.200000 ex sub 5.850000 m (%#&'#*+#$)
+('&*+&,-&!) sw
+2 div 25.200000 ex sub 5.850000 m ('&*+&,-&!)
gs 1 -1 sc sh gr
0.100000 slw
[0.200000] 0 sd
@@ -176,8 +176,8 @@
0 slj
n 17.860138 4.811063 m 17.550000 5.650000 l 18.407232 5.394748 l f
/Helvetica_e0 ff 0.700000 scf sf
-(,-./'#$0.*'123+) sw
-2 div 19.987800 ex sub 6.136290 m (,-./'#$0.*'123+)
+(./01+&!20,+34$-) sw
+2 div 19.987800 ex sub 6.136290 m (./01+&!20,+34$-)
gs 1 -1 sc sh gr
0.100000 slw
[0.200000] 0 sd
@@ -194,12 +194,12 @@
0 slj
n 14.441314 12.701523 m 15.000000 13.400000 l 15.223569 12.533965 l f
/Helvetica_e0 ff 0.700000 scf sf
-(4-.56$!7$8*) sw
-2 div 17.651900 ex sub 10.636300 m (4-.56$!7$8*)
+(5/06"!78!%,) sw
+2 div 17.651900 ex sub 10.636300 m (5/06"!78!%,)
gs 1 -1 sc sh gr
/Helvetica_e0 ff 0.700000 scf sf
-(9-.53"8*.87+7.:66;'<.+7$=#+) sw
-2 div 11.701900 ex sub 16.586300 m (9-.53"8*.87+7.:66;'<.+7$=#+)
+(9/06$:%,0%8-80;""<+=0-8!>&-) sw
+2 div 11.701900 ex sub 16.586300 m (9/06$:%,0%8-80;""<+=0-8!>&-)
gs 1 -1 sc sh gr
0.100000 slw
[0.200000] 0 sd
@@ -209,8 +209,8 @@
0 slj
n 20.550659 4.551316 m 21.350000 4.150000 l 20.549343 3.751317 l f
/Helvetica_e0 ff 0.700000 scf sf
-(>-.%#*<6"*#) sw
-2 div 12.753800 ex sub 9.386290 m (>-.%#*<6"*#)
+(?/0'&,=":,&) sw
+2 div 12.753800 ex sub 9.386290 m (?/0'&,=":,&)
gs 1 -1 sc sh gr
0.100000 slw
[0.200000] 0 sd
@@ -220,7 +220,7 @@
0 slj
n 8.456779 11.555002 m 8.750000 12.400000 l 9.250066 11.658425 l f
/Helvetica_e0 ff 0.700000 scf sf
-(address@hidden) sw
-2 div 14.200000 ex sub 4.050000 m (address@hidden)
+(@/06&-AB0%8-8) sw
+2 div 14.200000 ex sub 4.050000 m (@/06&-AB0%8-8)
gs 1 -1 sc sh gr
showpage
Index: gzz/Documentation/misc/hemppah-progradu/DOLR_lookup.eps
diff -u gzz/Documentation/misc/hemppah-progradu/DOLR_lookup.eps:1.2
gzz/Documentation/misc/hemppah-progradu/DOLR_lookup.eps:1.3
--- gzz/Documentation/misc/hemppah-progradu/DOLR_lookup.eps:1.2 Thu Mar 13
04:55:50 2003
+++ gzz/Documentation/misc/hemppah-progradu/DOLR_lookup.eps Fri Mar 21
09:48:14 2003
@@ -1,11 +1,11 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Title: DOLR_lookup.dia
%%Creator: Dia v0.90
-%%CreationDate: Thu Mar 13 11:47:47 2003
+%%CreationDate: Fri Mar 21 16:37:00 2003
%%For: a user
%%Magnification: 1.0000
%%Orientation: Portrait
-%%BoundingBox: 0 0 574 412
+%%BoundingBox: 0 0 574 409
%%Pages: 1
%%EndComments
%%BeginProlog
@@ -77,7 +77,7 @@
%%BeginSetup
%%EndSetup
28.346000 -28.346000 scale
--2.457030 -15.450010 translate
+-2.457030 -15.350010 translate
1.000000 1.000000 1.000000 srgb
n 3.650600 6.350000 1.000000 1.000000 0 360 ellipse f
@@ -139,7 +139,7 @@
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/P /o /i /n /t /e /r /R /xi /xi /q /u /s /one /period /space
/Q /y /b /m /two /F /w /a /d /three /l /k /p /g /four /quotesingle
- /five /c /h /O /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
+ /five /c /h /v /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
/xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi /xi
@@ -225,7 +225,7 @@
2 div 12.800000 ex sub 1.950000 m (@./5%$AB/87$7)
gs 1 -1 sc sh gr
/Helvetica_e0 ff 0.700000 scf sf
-(C6#%&) sw
-2 div 6.536700 ex sub 5.236290 m (C6#%&)
+( &!C"8%&) sw
+2 div 6.536700 ex sub 5.236290 m ( &!C"8%&)
gs 1 -1 sc sh gr
showpage
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.169
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.170
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.169 Fri Mar
21 08:34:14 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Fri Mar 21
09:48:14 2003
@@ -188,7 +188,7 @@
all peers $p$ in system. Then, $\forall s \in S$, there is a provider of the
service,
expressed as $p = \delta(s)$. Every $p$ has neighbor(s), named as $p_n$, which
is $P$ = \{$p \in P: \exists neighbor$, which is randomly chosen from $P$\}.
-Summary index maintains indices of other peers, $si = \gamma(\delta(s))$.
+Summary index maintains indices of other peers, $si o= \gamma(\delta(s))$.
Then, $\forall$ regular peer $p$, there is a super peer, $sp$, and it has a
index of
regular peer's content $P$ = \{$p \in P: \exists sp$,
where $sp$ = $\delta(\gamma(\delta(s))) \wedge (p = \delta(s))$\}
@@ -204,7 +204,7 @@
centralized index, Napster didn't scale well because of constantly updated
central
directory, and had a single point of failure.
-Gnutella \cite{gnutellaurl} is a well-known example of loosely structured
overlay network. Gnutella
+Gnutella \cite{gnutellaurl} is a well-known example of loosely structured
overlay system. 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
peers can form the overlay network based on \emph{local} knowledge. Figure
\ref{fig:gnutella_overlay}
@@ -320,53 +320,33 @@
that the system is able to find a service from the overlay efficiently, if it
exists in the overlay.
While there are significant differences among proposed tighty structured
systems, they all have in common
that \emph{peer identifiers} are assigned to participating peers from
-a large \emph{identifier space} by the overlay. Furthermore, globally unique
identifiers
+a large \emph{identifier space} by the overlay. Globally unique identifiers
are also assigned to application-specific data items, \emph{keys},
-which are selected from the same identifier space. The form of identifier
-space differs between proposed systems. Circular identifier space (and
variants)
+which are selected from the same identifier space. For instance, globally
unique keys can be created
+using a cryptographic content hash (e.g., \cite{fips-sha-1}) over the contents
of a data item.
+The form of identifier space differs between proposed systems. Geometrical
circular form of identifier space (and variants)
is most widely used. For instance, Chord \cite{stoica01chord}, Koorde
\cite{kaashoek03koorde},
Pastry \cite{rowston01pastry}, SWAN \cite{bonsma02swan}, Tapestry
\cite{zhao01tapestry}
-and Viceroy \cite{malkhi02viceroy} use a circular identifier space of $n$-bit
integers modulo $2^{n}$. The
-value of $n$ varies among systems. Again, CAN \cite{ratnasamy01can} uses a
$d$-dimensional Cartesian
-model to implement the identifier space.
-
-There are three higher level abstractions which tightly structured overlays
provide
-\cite{zhao03api}. Each of these abstractions fulfill a storage layer in the
overlay, but
-have semantical differences in the \emph{usage} of the 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 the DHT and the DOLR abstraction is that the DOLR
abstraction routes overlay's messages
-to a 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 or anycast 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. The DOLR and
the 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}
+and Viceroy \cite{malkhi02viceroy} use a circular form of identifier space of
$n$-bit integers modulo $2^{n}$. The
+value of $n$ varies among systems. Again, CAN \cite{ratnasamy01can} uses a
$d$-dimensional geometrical torus
+model to implement the form of identifier space.
+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
+structured overlay assigns a subset of all possible keys to every
participating peer.
+We say that a peer is \emph{responsible} for the keys which are assigned by
the overlay.
+Figure \ref{fig:structured_hashing} illustrates the
+process of data to key mapping in a tightly structured overlay.
+Also, each peer in the tightly structured overlay maintains a \emph{routing
table}, which
+consists of identifiers and IP addresses of other peers in the overlay.
Entries of the routing
+table represent peer's neighbors in the overlay network.
\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}
+\includegraphics[width=12cm, height=7cm]{structured_overlay_new.eps}
+\caption{Principal idea of tightly structured overlays.}
+\label{fig:structured_hashing}
\end{figure}
Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed four
requirements
@@ -378,28 +358,74 @@
support 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
-structured overlay assigns a subset of all possible keys to every
participating peer.
-We say that a peer is \emph{responsible} for the keys which are assigned by
the overlay.
-Figure \ref{fig:structured_hashing} illustrates the
-process of data to key mapping in a tightly structured overlay.
-Also, each peer in the tightly structured overlay maintains a \emph{routing
table}, which
-consists of identifiers and IP addresses of other peers in the overlay.
Entries of the routing
-table represent peer's neighbors in the overlay network.
+Currently, there are only three higher level abstractions which tightly
structured overlays provide
+\cite{zhao03api}. Each of these abstractions represent a storage layer in the
overlay, but
+have semantical differences in the \emph{usage} of the overlay.
+
+First, Distributed Hash Table (DHT) (see e.g., \cite{dabek01widearea},
\cite{rowstron01storage}),
+implements the same functionality as a regular hash table by storing the
mapping between a key and a value:
+
+\begin{itemize}
+\item \texttt{lookup(key)}: perform a data lookup with a given key.
+\item \texttt{insert(key)}: insert a data item with a given key.
+\item \texttt{remove(key)}: remove a data item with a given key.
+\end{itemize}
+
+DHT's \emph{interface} is generic; values can be any size and type (e.g.,
content hash over a file or IP address). In the
+DHT abstraction, the overlay itself stores the data items. 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:
+
+\begin{itemize}
+\item \texttt{publish(key)}: announce availability of a data item.
+\item \texttt{removePublished(key)}: remove a data item.
+\item \texttt{sendToObject(key)}: deliver a data item to a nearby peer hosting
the replica of data item.
+\end{itemize}
+
+
+The key difference between the DHT and the DOLR abstraction is that in the
DOLR abstraction the overlay maintains only the \emph{pointers} to the data.
+Also, the DOLR abstraction routes overlay's messages to a nearest available
peer, hosting a specific data item. This form of locality
+is not supported by DHT. DOLR's interface is similar to the DHT's interface,
i.e., values can be any size and type
+(e.g., content hash over a file or IP address).
+
+Third, tightly structured overlay can be used for scalable group multicast or
anycast operations (CAST) (see e.g., \cite{zhuang01bayeux}).
+The basic operations include:
+
+\begin{itemize}
+\item \texttt{join(groupIdentifier)}: join to a group with a given group
identifer.
+\item \texttt{leave(groupIdentifier)}: leave a group with a given group
identifier.
+\item \texttt{multicast(message, groupIdentifier)}: multicast a message to a
group with a given group identifier.
+\item \texttt{anycast(message, groupIdentifier)}: anycast a message to a group
with a given group identifier.
+\end{itemize}
+
+The DOLR and the 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=12cm, height=7cm]{structured_overlay_new.eps}
-\caption{Principal idea of tightly structured overlays.}
-\label{fig:structured_hashing}
+\includegraphics[width=10cm, height=7cm]{DHT_lookup.eps}
+\caption{Distributed Hash Table (DHT) abstraction of tightly structured
overlay. In the
+DHT abstraction a data item is located directly from the provider peer.}
+\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.
+In the DOLR abstraction, a data item is located indirectly, using the pointer
peer.}
+\label{fig:Strucutred_lookup_using_DOLR_model}
\end{figure}
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
+differences in the data structures representing the identifier space.
+For example, Chord \cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and
SkipNet \cite{harvey03skipnet2} maintain a
distributed 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