[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/21 08:34:15

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

Log message:
        Updates

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.168 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.169
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.168      Fri Mar 
21 06:25:56 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Fri Mar 21 
08:34:14 2003
@@ -167,19 +167,33 @@
 overlay network.
 
 In the end, however, we observe that there are only two approaches in which 
all modern Peer-to-Peer
-systems fall: the loosely structured approach and the tightly structured 
approach. By structure, we refer to
-the topology of the overlay network, i.e., how the connections between 
participating peers are created
-and maintained. By data lookup model, we mean the methods which are used for 
finding data from the overlay. 
+systems fall: the loosely structured approach and the tightly structured 
approach. 
+By structure, we refer to the topology of the overlay network, i.e., how the 
connections between participating peers are created
+and maintained. By data lookup model, we mean the methods which are used for 
finding data from the overlay.
+In the following sections, we will discuss in more detail the properties of 
these approaches. 
+
+
+\section{Loosely structured}
+
 In the loosely structured approach the construction and the maintenance of the 
overlay is controlled 
 loosely. The placement of services and topology of the overlay is random. The 
data lookup model in loosely structured systems is
-not very efficient, because of unstructured properties of the overlay. On the 
other hand, in the tightly structured
-approach the overlay is constructed determistically, which all participating 
peers have to follow. The topology of the
-overlay and the placement of services is controlled tightly therefore enabling 
more scalable and efficient data lookup model.
+not very efficient, because of unstructured properties of the overlay.
 
-In the following sections, we will discuss in more detail the properties of 
these approaches.
+\subsection{Sketch of a formal definition}
 
+In this subsection we formalize loosely structured overlay's main components. 
This
+model is based on original Gnutella overlay network with power-law 
improvements.
+
+Let $S$ be the aggregate of all services $s$ in system. Let $P$ be the 
aggregate of 
+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))$.
+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))$\}
 
-\section{Centralized}
+\subsection{Systems}
 
 Napster\footnote{We decided to include Napster in this section only because it 
has
 historical value (see previous section).} \cite{napsterurl}  was designed to 
allow 
@@ -188,11 +202,7 @@
 Peers in the Napster network made requests to the central directory server to 
find 
 other peers hosting desirable content. Since service requests were totally 
based on a 
 centralized index, Napster didn't scale well because of constantly updated 
central 
-directory, and had a single point of failure. 
-
-
-\section{Loosely structured}
-
+directory, and had a single point of failure.
 
 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.
@@ -213,10 +223,12 @@
 In Gnutella, each participating peer maintains a local index of its own shared 
content. Also,
 each peer has some connections to other peers, i.e., the peer's 
\emph{neighbors}. Basic Gnutella
 data lookup works as follows: a peer broadcasts a query request to its 
neighbors, which in turn
-forward the query to their neighbors. This leads to a situation where the 
number of messages
+forward the query to their neighbors. The number of messages
 in the network can grow with $O(n^{2})$ where $n$ is the number of 
participating peers in the
 Gnutella network. Figure \ref{fig:gnutella_query} illustrates why Gnutella's 
data lookup model has
-exponential properties. To limit the amount of network traffic, Gnutella uses 
Time-To-Live-limited
+$O(n^{2})$ properties. 
+
+To limit the amount of network traffic, Gnutella uses Time-To-Live-limited
 (TTL) flooding to distribute queries. Therefore, Gnutella's data lookup 
algorithm is a Breadth-First-Search (BFS)
 with depth limit $T$ (e.g., 7), where $T$ is the system-wide maximum TTL of a 
message in hops. Thus, 
 only peers that are TTL hops away from the query originator will forward the 
query or respond to the query. 
@@ -240,72 +252,72 @@
 significant message processing overhead for each data lookup. Even worse, 
flooding may increase 
 the load on participating peer to the point where it has to leave the network. 
 
-Lately, Gnutella's data lookup efficiency and scalability has been researched.
 Adamic et al. \cite{adamic99small, adamic02localsearch, 
adamic01powerlawsearch} 
 have studied different data lookup methods in power-law networks and have 
found that by 
 instructing the peers that forward data lookups to select high degree peers, 
the performance of data lookup 
-increases significantly. As a result, some of the most recent loosely
-structured Peer-to-Peer systems have adopted this method to improve Gnutella's 
data lookup model. Improvements 
-to the original Gnutella protocol \cite{gnutellaurl} include 
\cite{gnutella2url, shareazaurl} and improvements to the 
-FastTrack protocol \cite{fasttrackurl} include \cite{morpheusurl, kazaaurl}. 
Figures \ref{fig:gnutella_overlay_supernodes} 
-and \ref{fig:gnutella_overlay_cluster} illustrates simplified variations of 
power-law overlay networks. 
-Figure \ref{fig:gnutella_powerlaw} presents pure topology of power-law 
network. 
-
-It is not clear whether this algorithm is scalable or not, 
+increases significantly. Figure \ref{fig:gnutella_powerlaw} presents an 
example topology of power-law network with three high
+degree peers. Some of the most recent loosely structured Peer-to-Peer systems 
have adopted this method to improve the data lookup model of loosely structured
+systems \cite{gnutella2url, fasttrackurl}. Both protocols use high degree 
peers to optimize the data lookup model of the
+system. Shareaza \cite{shareazaurl} uses the Gnutella2 protocol 
\cite{gnutella2url} in data lookups, Morpheus \cite{morpheusurl}
+and KaZaa \cite{kazaaurl} use the FastTrack protocol \cite{fasttrackurl}.
+It is not clear whether the power-law method is scalable or not, 
 as the majority of the query requests are sent only to the high degree peers 
while making 
 these peers to bear the load of the entire system.
 
-\begin{figure}
-\centering
-\includegraphics[width=8cm, height=6cm]{gnutella_overlay_supernodes.eps}
-\caption{Variation of power-law overlay topology with super peers.}
-\label{fig:gnutella_overlay_supernodes}
-\end{figure}
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=6cm]{gnutella_overlay_clusters.eps}
-\caption{Variation of power-law overlay topology with 2-redundant super peer 
clusters.}
-\label{fig:gnutella_overlay_cluster}
-\end{figure}
+%\begin{figure}
+%\centering
+%\includegraphics[width=8cm, height=6cm]{gnutella_overlay_supernodes.eps}
+%\caption{Variation of power-law overlay topology with super peers.}
+%\label{fig:gnutella_overlay_supernodes}
+%\end{figure}
+
+%\begin{figure}
+%\centering
+%\includegraphics[width=10cm, height=6cm]{gnutella_overlay_clusters.eps}
+%\caption{Variation of power-law overlay topology with 2-redundant super peer 
clusters.}
+%\label{fig:gnutella_overlay_cluster}
+%\end{figure}
 
 \begin{figure}
 \centering
 \includegraphics[width=10cm, height=8cm]{gnutella_powerlaw.eps}
-\caption{Pure power-law network overlay topology with three super peers.}
+\caption{Pure power-law network overlay topology with three high degree peers.}
 \label{fig:gnutella_powerlaw}
 \end{figure}    
 
-Previously presented improvements are only partial solutions. More advanced 
techniques 
-to improve data lookup of loosely structured systems are discussed in chapter 
3.
+Above presented improvements are only partial solutions. More advanced 
techniques 
+to improve data lookup of loosely structured systems are discussed in chapter 
3. Yet, however, 
+techniques presented in chapter 3 are not adopted in any loosely structured 
system.
 
-\subsection{Sketch of a formal definition}
+\section{Tightly structured}
 
-In this subsection we formalize loosely structured overlay's main components. 
This
-model is based on original Gnutella overlay network with scale-free 
improvements.
+Partly due to scalability problems of loosely structured systems, several 
tightly 
+structured overlays have been proposed. In the tightly structured
+approach the overlay is constructed determistically, which all participating 
peers have to follow. The topology of the
+overlay and the placement of services is controlled tightly therefore enabling 
more scalable and efficient data lookup model.
 
-Let $S$ be the aggregate of all services $s$ in system. Let $P$ be the 
aggregate of 
-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))$.
-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))$\}
+\subsection{Sketch of a formal definition}
 
-\section{Tightly structured}
+In this subsection, we formalize the main features of tightly structured 
overlay, i.e., 
+identifiers, identifier space and the mapping function.
 
-Partly due to scalability problems of loosely structured systems, several 
tightly 
-structured overlays have been proposed.
-The list includes CAN \cite{ratnasamy01can}, Chord \cite{stoica01chord}, 
-Kademlia \cite{maymounkov02kademlia}, Kelips \cite{gupta03kelips}, 
-Koorde \cite{kaashoek03koorde}, Overlapping Distance Halving Distributed 
Hashtable 
-(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}, Viceroy \cite{malkhi02viceroy} and others 
\cite{freedman02trie}. 
+Let $S$ be the aggregate of all services $s$ in the system. Let $P$ be the 
aggregate of 
+all peers $p$ in system. Let $I$ be the aggregate of all identifiers $i$ in 
system. 
+Let $IS$ be the aggregate of all identifier points $ip$ in system. Then, 
$\forall s \in S$, 
+there is a provider of the service, expressed as $p = \delta(s)$. Service's 
identifier 
+is defined as $i = \iota(s)$. Coordinate point is defined as $ip = 
\zeta(\iota(s))$.
+Metric space is defined as a pair $(IS,d)$, where $d$ is the distance between 
two coordinate 
+points $ip_i$, $ip_j$ in $IS$ space. Mapping function is defined as $\zeta: I 
\longmapsto IS$,  
+which maps data items, expressed by an identifier to coordinate point $ip$ in 
$(IS,d)$. Peer's $p$ 
+resources are mapped onto a set $IS$ = \{$ip \in IS: \exists s \in S$, $ip = 
\zeta(\iota(s)) \wedge (\delta(s) = p)$\}.
+Every $p$ has neighbor(s), named as $p_n$, $P$ = \{$p \in P: \exists p_n$, 
+where $\theta(p,p_n) = ''close''$, where $''close''$ is small difference $d$ 
in $(IS,d)$\}.
+
+\subsection{Systems}
+ 
 The biggest difference compared to the loosely structured approach is that 
with tightly structured systems,
-it is now feasible to perform \emph{global} data lookups in the overlay.
+it is now feasible to perform \emph{global} data lookups in the overlay. By 
global lookup, we mean
+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 
@@ -452,24 +464,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.
-
-
-\subsection{Sketch of a formal definition}
-
-In this subsection, we formalize the main features of tightly structured 
overlay, i.e., 
-identifiers, identifier space and the mapping function.
-
-Let $S$ be the aggregate of all services $s$ in the system. Let $P$ be the 
aggregate of 
-all peers $p$ in system. Let $I$ be the aggregate of all identifiers $i$ in 
system. 
-Let $IS$ be the aggregate of all identifier points $ip$ in system. Then, 
$\forall s \in S$, 
-there is a provider of the service, expressed as $p = \delta(s)$. Service's 
identifier 
-is defined as $i = \iota(s)$. Coordinate point is defined as $ip = 
\zeta(\iota(s))$.
-Metric space is defined as a pair $(IS,d)$, where $d$ is the distance between 
two coordinate 
-points $ip_i$, $ip_j$ in $IS$ space. Mapping function is defined as $\zeta: I 
\longmapsto IS$,  
-which maps data items, expressed by an identifier to coordinate point $ip$ in 
$(IS,d)$. Peer's $p$ 
-resources are mapped onto a set $IS$ = \{$ip \in IS: \exists s \in S$, $ip = 
\zeta(\iota(s)) \wedge (\delta(s) = p)$\}.
-Every $p$ has neighbor(s), named as $p_n$, $P$ = \{$p \in P: \exists p_n$, 
-where $\theta(p,p_n) = ''close''$, where $''close''$ is small difference $d$ 
in $(IS,d)$\}.
 
 
 \section{Summary}