[Gzz-commits] storm/doc/pegboard/storm_gisp_simulation--hempp...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/storm
Module name:    storm
Changes by:     Hermanni Hyytiälä <address@hidden>      03/06/04 08:34:15

Modified files:
        doc/pegboard/storm_gisp_simulation--hemppah: peg.rst 

Log message:
        tuning

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/storm/storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst.diff?tr1=1.10&tr2=1.11&r1=text&r2=text

Patches:
Index: storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst
diff -u storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst:1.10 
storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst:1.11
--- storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst:1.10      Wed Jun 
 4 08:01:51 2003
+++ storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst   Wed Jun  4 
08:34:14 2003
@@ -5,8 +5,8 @@
 
 :Authors:  Hermanni Hyytiälä
 :Date-Created: 2003-06-02
-:Last-Modified: $Date: 2003/06/04 12:01:51 $
-:Revision: $Revision: 1.10 $
+:Last-Modified: $Date: 2003/06/04 12:34:14 $
+:Revision: $Revision: 1.11 $
 :Status:   Incomplete
 
 .. :Stakeholders:
@@ -16,9 +16,9 @@
 .. Affect-PEGs:
 
 
-For determining whether Storm with unmodified GISP P2P protocol is practical, 
-we want increase our understanding GISP's scalability properties. Also, we 
want 
-to know how GISP performs against different threats such as network 
+For determining whether Storm with unmodified GISP_ P2P protocol is practical 
and
+useful, we want increase our understanding GISP's scalability properties. 
Also, we 
+want to know how GISP performs against different threats such as network 
 partition or security attacks. 
 
 This PEG discusses research problems, hypotheses, the theoretical 
@@ -61,7 +61,7 @@
     
     - According to Benja, "...since it's written in Java" :)
     - Easy implementation (and it's already implemented)
-    - (belief that) GISP is a Kademlia implementation (which
+    - (belief that) GISP is a Kademlia_ implementation (which
       is not true - only distance function is similar)
      
     It is good to mention that there is also a Python 
@@ -70,20 +70,22 @@
     What properties does it share with others, to such a degree
     that its performance might be deduced from theirs?
     
-    GISP's routing table is based on Chord's routing 
-    table - O(log^2 n) messages are required to join/leave 
+    GISP's routing table is based on Chord_'s routing 
+    table -- O(log^2 n) messages are required to join/leave 
     operations and O(log n) for lookup efficiency (according to 
     original Chord publication). GISP extends Chord's routing
     table to have more space for cached data (peer information).
     Chord's routing table maintains information about O(log n)
-    peers. GISP publication does not (nor the protocol specification) 
-    describe how much more space a GISP peer maintain compared 
-    to Chord's O(log n). Instead, for example, the protocol
-    specification states that "A peer should keep as much other
-    peer information as possible for cache".
+    peers. 
     
-    However, neither the original GISP publication nor the GISP
+    GISP publication does not (nor the protocol specification) 
+    describe how much more space a GISP peer maintain compared 
+    to Chord's O(log n). Instead, the protocol specification 
+    states that "A peer should keep as much other
+    peer information as possible for cache". However, neither 
+    the original GISP publication nor the GISP
     protocol specification do not provide any lookup properties.
+    
     In the publication, the author states that GISP is more efficient
     than a "broadcasting system".    
        
@@ -94,28 +96,26 @@
     
     RESOLVED:
     
-    - very early (theoretical) experiments
-     - small amount of uncontrolled (real life), great amount of
-       controlled (simulation environment)
+    - mainly theoretical/best case experiments/simulations
+    - small amount of uncontrolled (real life), great amount of
+      controlled (simulation environment)
     - simulations have been rather static and are often favored the 
-      proposed algorithm
-    - not much real life experiments
-     - somewhat controlled experiments
-     - very fast connections between peers
-    - some form of formal analyses ("proofs") are used with, 
-      e.g., Chord and Kademlia
-    - number of peers commonly used in simulations: from 2^7 to 2^20 
+      proposed algorithm    
+    - in "real life" experiments, there have been very fast connections 
+      between peers
+    - some form of formal analyses ("proofs") are used, 
+      e.g., with Chord and Kademlia
+    - distribution of number of peers used in simulations: from 2^7 to 2^20 
     
 Plan
 ====
 
 First of all, we will create a PEG document (this document) which 
-discusses general/theoretical aspects of the research problems. Then, 
+discusses general and theoretical aspects of the research problems. Then, 
 if necessary, we program (rather short) test cases which will test 
 the GISP/Storm P2P properties, as discussed in this document. Finally, we will 
 collect and analyse test cases' information and publish any interesting 
-discoveries.
- 
+discoveries. 
 
 The GISP protocol
 =================
@@ -125,7 +125,7 @@
 function is based on the XOR-metric, which is similar to Kademlia's XOR-metric 
 (unsigned integer of XOR). The GISP protocol specification paper describes the 
 XOR-metric but the original GISP publication describes only numerical 
-metric (which is little confusing since Chord_ uses numerical distance
+metric (which is little confusing since Chord uses numerical distance
 metric).
 
 GISP extends Chord's routing table to have more peer information as a cache.
@@ -159,7 +159,7 @@
 - What about GISP's lookup effieciency when the network grows ?
 
 - GISP does not use Kademlia's binary-tree abstraction - does it have 
influences 
-  and if it does, what are the influences ? 
+  and if it does what are the influences ? 
   
 - How much better/worse pure Kademlia implementation (e.g. Kashmir) is over 
the GISP 
   protocol in face performance and fault-tolerance ?
@@ -187,9 +187,10 @@
 ==========
 
 In this section we introduce few hypothesis related to research problems.
-Hypothesis are based on the simulation processes which are used in the 
-literature. Also, values presented here (e.g., 1000-10000) are widely used
-in simulation processes.
+Hypothesis' claims (goodness/badness) are based on the features of other DHTs 
+and their simulation results (which can be found from the literature).
+Also, values presented here (e.g., 1000-10000) are widely used in DHTs' 
+simulation processes. 
 
 
 - GISP's overlay can scale rather well when peers join and leave the system at 
a 
@@ -203,23 +204,21 @@
   blocks and 1000 Storm-servers. 1-10 peer(s) joins/leaves every 1-10 
second(s), 
   at a given time suddenly 100-900 peers joins/leaves randomly).
    
-- GISP's data lookup is efficient and can scale if lookup's length grows with 
a 
+- GISP's data lookup is efficient and can scale well if lookup length grows 
with a 
   logarithmic growth inspite that the number of Storm-servers increases 
   linearly (e.g. 10-10000 Storm-servers, 10000 Storm blocks, with 10-10000
   Storm-servers perform 10000 lookups randomly)
      
-- A GISP peer is not able to handle all request properly when great amount 
-  of query requests are performed towards a single peer/few peers (a peer is 
-  responsible for a given key). Thus, there can be query/routing hotspots
-  in the system and load balancing properties may not scalable/tolerance
-  against a hostile attack (e.g., 1000 Storm-server system, each server 
-  hosting 1-10 Storm block(s), 1-900 peers (randomly chosen) queries a 
-  single key every 1-10 second(s); calculate average block request 
-  failure, average lookup length, number of timed-out lookups and
+- A there can be query/routing hotspots in the system and load balancing 
properties 
+  may not scalable/tolerance against a hostile attack if a GISP peer is not 
able
+  to handle all request (a peer is responsible for a given key) (e.g., 1000 
+  Storm-server system, each server hosting 1-10 Storm block(s), 1-900 peers 
+  (randomly chosen) queries a single key every 1-10 second(s); calculate 
average 
+  block request failure, average lookup length, number of timed-out lookups and
   the distribution of lookup messages processed per peer).
      
-- GISP is is rather fault-tolerant if 80% of lookups are succesful when 20% of
-  peers die (This is Chord's simulation result) (e.g., 1000 Storm blocks are 
+- We can say that GISP is is rather fault-tolerant if 80% of lookups are 
succesful 
+  when 20% of peers die (this is Chord's simulation result) (e.g., 1000 Storm 
blocks are 
   insterted into a 1000 Storm-server system. After insertions, 1-99% of 
   servers die randomly or in a controlled way. Before GISP starts rebuilding 
   routing tables, perform 1000 Storm block fetches; calculate average block 
@@ -246,4 +245,4 @@
 .. _GISP: http://gisp.jxta.org
 .. _Kademlia: http://kademlia.scs.cs.nyu.edu
 .. _Chord: http://www.pdos.lcs.mit.edu/chord/
-.. _Kahsmir: http://khashmir.sourceforge.net/
+.. _Kashmir: http://khashmir.sourceforge.net/