[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 05:41:47

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

Log message:
        Loosely structured ready

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.89 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.90
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.89       Thu Feb 
27 04:38:48 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 27 
05:41:47 2003
@@ -284,14 +284,16 @@
 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. As a result, some of the most recent 
loosely
-structured Peer-to-Peer system have adopted this method with some modifications
+structured Peer-to-Peer systems 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. 
-
+\cite{kazaaurl}, \cite{jxtaurl}, \cite{jxtaoverview}, 
\cite{botros01jxtasearch},
+\cite{ganesan02yappers}.
+Figures \ref{fig:gnutella_overlay_supernodes} and 
\ref{fig:gnutella_overlay_cluster}
+illustrated two possible variations of power-law overlay networks. All the 
systems
+share the property of that high degree peers maintain index of all other peers 
+they know about. 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
@@ -307,8 +309,46 @@
 \label{fig:gnutella_overlay_cluster}
 \end{figure}  
 
+Additionally, there has been other improvements also. In iterative deepening 
+\cite{yang02improvingsearch}, multiple breadt-first searches are initiated
+with successively larger TTL depth limits, until either the query is 
satisfied, 
+or the maximumum depth $D$ has been reached. To perform a data lookup, query
+originator starts a flood with small TTL value. If the search is not succesful,
+the query originator increases the TTL value and performs another flood. This 
+process is repeated until the desired data is found or maximumum depth $D$ 
+has been reached. Expanding ring, proposed by Shenker et al., 
\cite{lv02searchreplication}, 
+is similar to iterative deepening techique. With these techniques, search 
+may not be fast when desired data item requires many consecutive flooding 
rounds.
+
+Directed breadt-first search \cite{yang02improvingsearch} optimizes the 
original 
+breadt-first searche in way that peer selects neighbors with many quality 
results
+may be reached, thereby maintaining the the quality of costs and decreasing 
the amount
+of messages sent to network. Alpine Peer-to-Peer system \cite{alpineurl} uses
+somewhat similar method when performing data lookups.
+
+Local indices \cite{yang02improvingsearch} in one variation of active caching. 
+In this scheme, each peer maintains an index over the data of all nodes within 
+$h$ hops of itself, where $h$ is a system-wide variable, called radius of the
+index\footnote{In normal BFS case, the value of $h$ is 0, as peer only has 
index
+over its local content.}. Mutual index caching architecture, as proposed in 
+\cite{osokine02distnetworks}, is one variation of local indices techique. 
+
+In random walk approach \cite{lv02searchreplication}, peer forwards a query to 
+randomly selected neighbor. The basic random walk approach decreases the
+overhead generated by messages. On the other hand, basic random walk approach
+has poor response time. As suggested in \cite{lv02searchreplication},
+random walk approach can be done more effective by introducing
+multiple ''walkers''. Freenet \cite{clarke00freenet} Peer-to-Peer system uses 
+random walk searches in query lookups. Indeed, Freenet's query resembles
+depth-first traversal and peers' routing tables are dynamically built
+using caching. This is an outcome of Freenet's main design priciples, 
+i.e., anonymity.
+
+Previously presented improvements are only partial solutions. Obviously, more
+research is required to make loosely structured approach's data lookup more
+scalable and effective. 
 
-
+principles
 
 
 power-law disribution
@@ -337,21 +377,8 @@
 before forwarding the query to another neighbor (if query not ok), or 
forwarding results back 
 to the query source (if query ok)
 
-BFS
--Search results are fast, because BFS sends queries to every possible nodes
--Wastes resources, because BFS sends queries to every possible nodes
-
-
-DFS
--Poor response time, beecause each node processes the query sequentially...
--...and thereby minimazing cost
-
-
-
 
 
-\cite{yang02comparinghybrid}
-
 \subsection{Formal definition}
 
 -let S be the aggregate of all services s in system (data, service, computing 
power)
@@ -378,22 +405,19 @@
 -with every lookup query, a node determines how proficient a given node is to 
another node's objectives
 
 
-Freenet \cite{clarke00freenet}
+
 Improve Freenet performance with small worlds \cite{zhang02using}
-Milgram's small world experiment \cite{milgram67smallworld}
-Small worlds \cite{adamic99small}
+
 \cite{ramanathan02goodpeers}
 \cite{kleinberg99small}
 \cite{watts00dynamics}
 \cite{nips02-Kleinberg}
-\cite{ganesan02yappers}
-\cite{gnutellaurl}
 
-\cite{jxtaurl}
-\cite{jxtaoverview}
-\cite{botros01jxtasearch}
+
+
+
 \cite{kato02gisp}
-\cite{alpineurl}
+
 \cite{joseph02neurogrid}