[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/19 04:56:45

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

Log message:
        More updates

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.157 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.158
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.157      Wed Mar 
19 04:25:48 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Wed Mar 19 
04:56:45 2003
@@ -192,9 +192,9 @@
 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}
-illustrates the overlay network of Gnutella network. The Gnutella network can 
be considered as a variation of \emph{scale-free
-graph}. In scale-free graphs (also known as power-law graphs) only a few peers 
have high number of neighbor 
-links and the majority of peers have low number of neighbor links.
+illustrates the overlay network of Gnutella network. The Gnutella network can 
be considered as a variation of scale-free
+graph \cite{albert-02-statistical}. In scale-free graphs only a few peers have 
high 
+number of neighbor links and the majority of peers have low number of neighbor 
links.
 
 \begin{figure}
 \centering
@@ -205,17 +205,18 @@
 
 
 In Gnutella, each participating peer maintains a local index of its own shared 
content. Also,
-each peer has a few connections to other peers, i.e., peer's \emph{neighbors}. 
Basic Gnutella
-data lookup works as follows: peer broadcasts a query request to its 
neighbors, which in turn
+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
-in the network can grow with $O(n^{2})$, where $n$ is the number of 
participating peers in
-Gnutella network. To limit the amount of network traffic, Gnutella uses 
Time-To-Live-limited
-(TTL) flooding to distribute queries. Therefore, Gnutella uses a 
Breadth-First-Search (BFS) algorithm
+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
+(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. 
-In Gnutella network, search results are fast, because BFS sends queries to 
+In the Gnutella network, search results are fast, because BFS sends queries to 
 every possible neighbor. Clearly, this method wastes resources and doesn't 
scale well.
-Figure \ref{fig:gnutella_query} shows the data lookup process of the Gnutella 
network.
+
 
 \begin{figure}
 \centering
@@ -225,29 +226,28 @@
 \end{figure}
 
 According to \cite{lv02searchreplication}, Gnutella's way to perform data 
lookups, \emph{flooding}, has the
-following limitations. First, choosing the appropriate TTL in practice is not 
easy. If the
-TTL is too high, query originator may unnecessarily strain the network. If the 
TTL is too
+following limitations. First, choosing the appropriate TTL is not easy. If the
+TTL is too high, the query originator may unnecessarily strain the network. If 
the TTL is too
 low, the query originator might not find the desired data even if it is 
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 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 deeply 
researched.
+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 with some 
modifications
-\cite{gnutella2url, shareazaurl, fasttrackurl, morpheusurl, kazaaurl, 
waterhouse02searchp2p, botros01jxtasearch, 
-ganesan02yappers}.
-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. 
+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, 
-as the majority of the query requests are sent only to the high degree peers, 
making 
-them stress the load of entire system.
+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
@@ -1396,7 +1396,8 @@
 \parbox{90pt}{Efficient and scalable data discovery 
\cite{lv02searchreplication, osokine02distnetworks, yang02improvingsearch, 
lv02gnutellascalable, 
 ganesan02yappers, adamic02localsearch, adamic01powerlawsearch, 
ripeanu02mappinggnutella, milgram67smallworld, adamic99small, 
 ramanathan02goodpeers, kleinberg99small, nips02-Kleinberg, zhang02using, 
watts00dynamics, karger02findingnearest, 
-brinkmann02compactplacement, rhea02probabilistic, castro02networkproximity, 
ng02predicting, pias03lighthouse}} &
+brinkmann02compactplacement, rhea02probabilistic, castro02networkproximity, 
ng02predicting, pias03lighthouse, waterhouse02searchp2p, botros01jxtasearch, 
+ganesan02yappers}} &
 \parbox{110pt}{Find resources efficiently, if resource exists (loosely 
structured)} &
 \parbox{110pt}{Super peers, peer clusters, caching techniques} &
 \parbox{110pt}{More efficient, less network traffic, not comparable to the 
efficiency of tightly structured systems}