[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 03:26:09

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

Log message:
        Napster, basic gnutella

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.86 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.87
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.86       Wed Feb 
26 09:31:07 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 27 
03:26:09 2003
@@ -215,41 +215,56 @@
 sections, we discuss in more detail both approaches, they disadvantages and 
advantages, and
 key differences. 
 
-\cite{balakrishanarticle03lookupp2p}
 
+\section{Centralized}
 
+Napster \cite{napsterurl} \footnote{We decided to include Napster in this 
section only because it has
+historical value (see previous section).}  was designed to to allow people to 
share music. 
+It was a hybrid Peer-to-Peer file-sharing system, i.e., the search index was 
centralized 
+and the distribution storage and serving of files was distributed. Peers in 
the Napster 
+network performed requests to the central directory server to find other peers 
hosting 
+desirable content. Since service requests was totally based on centralized 
index, 
+Napster didn't scale well because of constantly updated central directory, and 
had a 
+possibility to single point of failure. 
 
 
+\section{Loosely structured}
 
-\section{Centralized}
+Gnutella \cite{gnutellaurl} is well-known example of loosely structured 
overlay network. As in
+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
+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}.
+
+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
+forwards the query to their neighbors. This leads in the situation where 
number of messages
+in the network can grow with $O(n^{2})$, where $n$ is the number of 
participating peers in the
+Gnutella network. To limit the amount of network traffic, Gnutella uses 
Time-To-Live-limited
+(TTL) flooding to distributed queries. Therefore, only peers that are TTL hops 
away from the
+query originator will forward the query or respond to the query.
+
+ 
+
+Recently, however, there has been done research on topology properties of the 
Internet \cite{adamic99small}
+and the Gnutella network \cite{adamic02localsearch}, 
\cite{adamic01powerlawsearch}. Studies show
+that both networks has a power law distribution of links, i.e., a few peers 
have high connectivity
+and major of peers have low connectivity. 
+peers prefential attach
+to popular peers
 
--this category: e.g. Napster
--resources are kept locally
--centralized index of all available resources in a a system
--a service request is totally based on centralized index
--system doe find the service, if it exists
-
--These kind of systems have a constantly updated database/directory 
-which is hosted at central locations.
--Nodes in the p2p networks performs a requests to the central directory 
-server to find other nodes and/or files
--Do not scale well
--Have a single point of failure
--Example: Napster
-
-\subsection{Formal definition}
-
--let S be the aggregate of all services s in system (data, service, computing 
power)
--let P be the aggregate of all peers (providers) p in system (all physical 
entities participating)
--let SE be the aggregate of all servers se in system (all physical central 
server participating)
--let I be the aggregate of all index entries ie in system (index of all 
services in system)
--for each service s 'mathematical belongs to' S, there is a index entry in 
some se 'mathematical belongs to' SE , expressed as 'ie = indexentry(s)'
--for each service s 'mathematical belongs to' S, there is a provider of the 
service, expressed as 'p = provider(s)'
-%-every p has only one neighbor, named as p_centralized_neigbor, which is P = 
{p 'mathematical belongs to' P: 'mathematical there exists at least one' 
p_centralized_neighbor, which is some se 'mathematical belongs to' SE}
 
-\cite{napsterurl}
 
-\section{Loosely structured}
+\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}
+
 
 
 power-law disribution
@@ -288,12 +303,7 @@
 -...and thereby minimazing cost
 
 
-\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}
+
 
 
 \cite{yang02comparinghybrid}