[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/20 06:57:32

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

Log message:
        More text

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.54 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.55
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.54       Thu Feb 
20 06:48:00 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 20 
06:57:32 2003
@@ -72,6 +72,31 @@
 
 \section{Research problems}
 
+ a)* Mist? riippuu ja kuinka nopeaa nykyisill? algoritmeilla
+           on tietyn storm-blokin haku mist? tahansa?
+
+       --> Distributed hash, esim. CAN, Chord jne. (Overview)
+
+           - summarize current research, specifically on problems
+             where we cannot trust any servers, and where 
+             probability distributions for the blocks are used.
+             Bibtex references.
+        
+        b)* Mist? riippuu ja kuinka nopeaa nykyisill? algoritmeilla
+           on tiettyyn urn-5 -nimeen liitetyn uusimman blokin haku
+           (jossa uusin blokki allekirjoitettu annetulla avaimella)
+
+        c)* Mist? riippuu ja kuinka nopeaa nykyisill? algoritmeilla
+           on tiettyyn urn-5 -nimeen liitetyn annettuna aikana
+           olleen blokin haku ("Hesarin etusivu 3.6.-02")?
+           (jossa blokki allekirjoitettu annetulla avaimella)
+
+       *=Näiden jälkeen voidaan miettiä, voidaanko systeemiä tehdä
+       ilman hierarkiaa (Tumbler).
+       
+       "Mistä riippuu" = Skaalautuvuus (verkokoko, datamäärä, levinneisyys, 
verkon kytkeytyvyys)
+
+
 \section{Thesis overview}
 
 definition \cite{p2pworkinggroup}
@@ -111,6 +136,13 @@
 -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}
 
@@ -143,6 +175,24 @@
 -system doesn't have *any* knowledge, where service is located (opposite to 
centralized and decentralized but structured) (Gnutellas)
 -system doesn't not necessary find the service, if it exists
 
+-Gnutella: Uses a breadt-First traversal (BFS) with depth limit L, where L is 
the system-wide
+maximum TTL of a message in hops. Every node receiving a query will forward 
the message 
+to all of its neighbour nodes, unless the message has reached the TTL limit
+-Freenet: a depth-first traversal (DFS) with depth limit L. Each node forwards 
the query 
+to a single neighbor (determined by ID) and waits for a definite response from 
the neighbor 
+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
+
+
 \begin{figure}
 \centering
 \includegraphics[width=6cm, height=6cm]{gnutella_overlay.eps}
@@ -825,6 +875,32 @@
 
 
 \subsection{Efficient data lookup}
+
+-Object's popularity: studies have shown that Napster, Gnutella and Web 
+queries follow Zipf-like distributions (1/2, 1/3, 1/4 etc.)
+
+
+Proposals (Yand et all):
+
+Iterative Deepening
+In Iterative Deepening, multiple BFS are initiated with successively larger
+depths limits, until either they query is satisfied, or the maximum depth L
+ has been reached
+ 
+Directed BFS
+Implements a strategy where a source sends a query messages to just a subset 
+of neighbours and selecting neighbors through which nides with many quality 
results
+ may be reached. Node may select a neighbor that has produced or forwarded 
many 
+ many quality results in the past, on the premise that past performance is a 
good 
+ indication of future performance.
+
+Local Indices
+In this method, each node N maintains an index over the data of all nodes 
within h hops 
+of itself, where h is a system-wide variable known as radius of the index (h=0 
is th  BFS case).
+ When a node receives a query message, it can process the query on behalf of 
every node within
+ r hops.
+
+
 \cite{ratnasamy02routing}
 \cite{hildrum02distributedobject}
 \cite{adamic02localsearch}
@@ -1388,6 +1464,16 @@
 -since each new downloader introduces a new upload capacity, eventually the 
upload overhead for the original server/node/computer bandwidth is reasonable 
small
 -uses SHA-1 for checking data integrity (suits for us very well!)
 -we don't have to create 'mini-blocks' for Gzz p2p, since bitTorrent itself 
partitions data into several blocks for us
+
+5.1 The Merkle Hash Tree
+
+The Merkle Hash Tree, invented by Ralph Merkle, is a hash construct that has 
very nice properties for 
+verifying the integrity of files and file subranges in an incremental or 
out-of-order fashion. This 
+document describes a binary serialization format for hash trees that is 
compact and optimized for both 
+sequential and random access. This memo has two goals:
+
+   1. To describe Merkle Hash Trees and how they are used for file integrity 
verification.
+   2. To describe a serialization format for storage and transmission of hash 
trees.
 
 \section{Overview}