[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 04:38:48

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

Log message:
        Power-law networks

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.88 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.89
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.88       Thu Feb 
27 04:21:00 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 27 
04:38:48 2003
@@ -234,10 +234,18 @@
 other Peer-to-Peer networks, 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 local knowledge. Figure 
\ref{fig:gnutella_overlay}
-illustrates how Peers can form an overlay network. Initially, peer 1 creates 
the overlay, since
+illustrates how peers form an overlay network. Initially, peer 1 creates the 
overlay, since
 it's the first participating peer. Then, repeatly new peers join the network 
and connects to
 other nodes in a random manner. Thus, gnutella can be considered as a 
\emph{random graph}.
 
+\begin{figure}
+\centering
+\includegraphics[width=6cm, height=6cm]{gnutella_overlay.eps}
+\caption{Basic loosely structured overlay's ad hoc connectivity graph}
+\label{fig:gnutella_overlay}
+\end{figure}
+
+
 In Gnutella, each participating peer maintains local index of its own shared 
content. Also,
 each peer has a few connections to other peer, i.e., peer's \emph{neighbors}. 
Basic gnutella
 data lookup works as follows: peer broadcasts a query request to its neighors, 
which in turn
@@ -249,6 +257,14 @@
 are TTL hops away from the query originator will forward the query or respond 
to the query. 
 In Gnutella network, search results are fast, because breadt-First traversal 
sends queries to 
 every possible neighbor. On the other hand, this method wastes resources and 
doesn't scale well.
+Figure \ref{fig:gnutella_query} shows the query lookup process of Gnutella 
network.
+
+\begin{figure}
+\centering
+\includegraphics[width=8cm, height=6cm]{gnutella_query.eps}
+\caption{Basic Gnutella query}
+\label{fig:gnutella_query}
+\end{figure}
 
 According to \cite{lv02searchreplication}, Gnutella's way to perform data 
lookups, \emph{flooding}, has
 following limitations. First, choosing the approriate TTL in practice is not 
easy. If the
@@ -256,8 +272,8 @@
 low, the query originator might not find the desired data even it's available 
somewhere
 in the network. Second, there are many duplicate messages generated by 
flooding, especially
 in high connectivity graphs. It is obvious that with these limitations, 
flooding creates 
-significant message processing overhead for each query. Furthermore, as a 
result, 
-flooding may increase the load on participating to the point, where it has to 
leave the network. 
+significant message processing overhead for each query. Furthermore, flooding 
may increase 
+the load on participating to the point, where it has to leave the network. 
 
 
 
@@ -267,20 +283,32 @@
 networks\footnote{In power-law networks only a few peers have high number of 
neighbor 
 links and major of peers have low nuber of neighbor links.} and they have 
found that by 
 instructing peers forwarding queries to select high degree peers the data 
lookup's 
-performance increases signficantly. However, it's not clear whether this 
algorithm
-is scalable or not.
-.
-
-
+performance increases signficantly. As a result, some of the most recent 
loosely
+structured Peer-to-Peer system have adopted this method with some modifications
+\cite{gnutella2url}, \cite{shareazaurl}, \cite{fasttrackurl}, 
\cite{morpheusurl}, 
+\cite{kazaaurl}. Figures \ref{fig:gnutella_overlay_supernodes} and 
\ref{fig:gnutella_overlay_cluster}
+illustrated two possible variations of power-law overlay networks. However, 
it's 
+not clear whether this algorithm is scalable or not, as majority of the query
+request are sent only to the high degree peers, making them stress the overhead
+of nearly entire system. 
 
 
 \begin{figure}
 \centering
-\includegraphics[width=6cm, height=6cm]{gnutella_overlay.eps}
-\caption{Basic loosely structured overlay's ad hoc connectivity graph}
-\label{fig:gnutella_overlay}
+\includegraphics[width=8cm, height=6cm]{gnutella_overlay_supernodes.eps}
+\caption{Power-law network overlay with super peers.}
+\label{fig:gnutella_overlay_supernodes}
 \end{figure}
 
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=6cm]{gnutella_overlay_clusters.eps}
+\caption{Power-law network overlay with 2-redundant super node clusters}
+\label{fig:gnutella_overlay_cluster}
+\end{figure}  
+
+
+
 
 
 power-law disribution
@@ -360,11 +388,7 @@
 \cite{nips02-Kleinberg}
 \cite{ganesan02yappers}
 \cite{gnutellaurl}
-\cite{gnutella2url}
-\cite{shareazaurl}
-\cite{fasttrackurl}
-\cite{morpheusurl}
-\cite{kazaaurl}
+
 \cite{jxtaurl}
 \cite{jxtaoverview}
 \cite{botros01jxtasearch}
@@ -375,27 +399,10 @@
 
 \subsection{Super peers and Super peer clusters}
 
-\begin{figure}
-\centering
-\includegraphics[width=8cm, height=6cm]{gnutella_overlay_supernodes.eps}
-\caption{Loosely structured overlay's ad hoc connectivity graph with super 
nodes}
-\label{fig:gnutella_overlay_supernodes}
-\end{figure}
 
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=6cm]{gnutella_overlay_clusters.eps}
-\caption{Loosely structured overlay's ad hoc connectivity with 2-redundant 
super node clusters}
-\label{fig:gnutella_overlay_cluster}
-\end{figure}
 
 
-\begin{figure}
-\centering
-\includegraphics[width=8cm, height=6cm]{gnutella_query.eps}
-\caption{Basic Gnutella query}
-\label{fig:gnutella_query}
-\end{figure}
+