[Gzz-commits] gzz/Documentation/misc/hemppah-progradu Misc_No...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      02/11/07 03:25:49

Modified files:
        Documentation/misc/hemppah-progradu: Misc_Notes 
                                             existing_systems_overview 

Log message:
        More content to Freenet and Gnutella + intoduction text.

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/Misc_Notes.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/existing_systems_overview.diff?tr1=1.4&tr2=1.5&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/Misc_Notes
diff -u gzz/Documentation/misc/hemppah-progradu/Misc_Notes:1.2 
gzz/Documentation/misc/hemppah-progradu/Misc_Notes:1.3
--- gzz/Documentation/misc/hemppah-progradu/Misc_Notes:1.2      Thu Nov  7 
02:21:43 2002
+++ gzz/Documentation/misc/hemppah-progradu/Misc_Notes  Thu Nov  7 03:25:49 2002
@@ -102,7 +102,7 @@
 searches
 
 Misc. 2: In Freenet system, however, the basic concept of search mechanism
-relies on Depth-First algorithm 
+relies on Depth-First algorithn
 
 
 
Index: gzz/Documentation/misc/hemppah-progradu/existing_systems_overview
diff -u gzz/Documentation/misc/hemppah-progradu/existing_systems_overview:1.4 
gzz/Documentation/misc/hemppah-progradu/existing_systems_overview:1.5
--- gzz/Documentation/misc/hemppah-progradu/existing_systems_overview:1.4       
Fri Nov  1 04:43:12 2002
+++ gzz/Documentation/misc/hemppah-progradu/existing_systems_overview   Thu Nov 
 7 03:25:49 2002
@@ -1,8 +1,27 @@
-[This document is meant to be an overview of existing p2p systems. 
-Document is related to address@hidden's Master Thesis project.
-
-Please notice that document's contents are updated constantly.]
-
address@hidden's Master Thesis project. 
+Text is based on bibliography, which can be found from progradu.bib file.
+Please notice that document's contents are updated constantly.
+There are no bibliography reference in the text yet...
+]
+
+0. Introduction
+
+-There are two approaches for distributed key/value lookup operation in
+p2p environment: broadcast searches (e.g. Gnutella and Freenet) and 
location-deterministic
+ algorithms (e.g. CAN, Pastry, Chord, Tapestry and Kademlia)
+-Additionally, there is method which is based on Distributed Trie
+-Lookup algorithms deploy a lookup structure (e.g. hash table, trie, binary 
tree, B-tree etc.)
+-Distributed lookup algorithm trades between the efficiency of lookup and the 
maintenance of lookup structure
+-Lookup structures maintenace is needed by either key/value pair insert or by 
node join/delete operation
+-Replication is one way to make lookups more effiecinet. However, maintenance 
is slow because all peers
+ must keep their local lookup structure updated (replicas have to be 
consistent)
+-Gnutella and Freenet eliminates the lookup structure and thus requires no 
maintenance. Lookups, however, are
+implemented by a broadcase-like search on all know peers which costs 
efficiency and scalability
+-Location-deterministic techiques partitions the lookup structure and 
distributes a small subset of partitions
+ on each peer. Maintenance updates only are tycally localized, peers update 
only a smaller number of partition
+ replicas. The system assigns partitions to peers either statically or 
dynamically In the static method, peer
+ addresses map to the key space and each node replicates only those partitions 
which are close enough to node's
+ ID. In the dynamic approach, peers replicate only partitions that they 
frequently access.
 
 
 1. A summary of algorithms used in existing systems
@@ -25,7 +44,7 @@
 Search: 
 Number of messages when an object lookup is performed
 
-The table above has been presented in [1].
+The table above has been presented in.
 
 2. A brief description of existing systems
 
@@ -50,7 +69,7 @@
 using global hash funktions
 -Queries are routed along axes in this space until they reach their 
 destination.
--Consistent hashing (distributed hash table)
+-Routing on a d-dimensional torus (distributed hash table)
 
 2.3. Tapestry
 
@@ -58,6 +77,7 @@
 -Distributed data structure
 -Employs randomness to achieve both load distribution and routing 
 locality
+-Based on Plaxton trees
 
 2.4. Pastry
 
@@ -65,16 +85,27 @@
 -Peer-to-Peer anonymous storage
 -Location protocol sharing many similarities with Tapestry
 -Objects are replicated without any permission of the owner
-
-
+-Based on Plaxton trees
 
 2.3. Gnutella
 
 -Bounded broadcast mechanism used for searching
 -Power law degree distribution
+-Gnutella makes a trade-off between a much greater search effort in return
+ for optimal paths and better worst-case performance
+-Link distribution: Poisson distribution
+-Fault tolerance: Random: Highly connected nodes are less factor than in 
Freenet. Targeted: Not a bib problem,
+ because of link distribution (Poisson distribution)
+ 
 
 2.4. FreeNet
-
+-Freenet is based on the small-world effect
+-Freenet has good average performance but poor worstcase performance in object 
lookups. This
+ is because a few bad local routing decisions can throw a request off the track
+-In Freenet, distribution of links follows the power law theory
+-Network growth: at the beginning, random routing should find the data quicly. 
As the network grows,
+ the request pathlength remains low
+-Fault tolerance: Random removing of nodes: not a big problem. Targeted 
attach: bigger problem.
 -Chaotic routing scheme where objects are published to a few nearest 
 neighbors
 -Queries follow gradients generated by object pointers
@@ -85,9 +116,9 @@
 -Key types are defined with URI: freenet:address@hidden
 -Content Hash Key (CHK), Keyword Signed Key (KSK), Signature
 Verification Key (SVK)
--Write more about these key techiques later !!
 
-3. Different architectures for p2p networks [2]:
+
+3. Different architectures for p2p networks:
 
 3.1 Centralized
 
@@ -134,18 +165,4 @@
 Miscellaneous notes:
 
 -Object's popularity: studies have shown that Napster, Gnutella and Web 
-queries follow Zipf-like distributions (1/2, 1/3, 1/4 etc.) [3, 4]
-
-
-Bibliography:
-
-[1] Hildrum Kirsten, Kubiatowicz John D., Rao Satish and Zhao Ben Y., 
-Distributed Object Location in a Dynamic Network
-
-[2] Lv, Qin, Cao Pei, Cohen Edith, Li Kai, Shenker Scott, Search and 
-Replication in Unstructured Peer-to-Peer Networks
-
-[3] Aiello W., A Random graph model for massive graphs
-
-[4] Sripanidkulchai K., The popularity of gnutella queries and its 
-implications on scalability
+queries follow Zipf-like distributions (1/2, 1/3, 1/4 etc.)