[Gzz-commits] storm/doc/pegboard/attacking_gisp--hemppah peg.rst

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/storm
Module name:    storm
Branch:         
Changes by:     Hermanni Hyytiälä <address@hidden>      03/06/17 03:53:31

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

Log message:
        further fixes and updates

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

Patches:
Index: storm/doc/pegboard/attacking_gisp--hemppah/peg.rst
diff -u storm/doc/pegboard/attacking_gisp--hemppah/peg.rst:1.38 
storm/doc/pegboard/attacking_gisp--hemppah/peg.rst:1.39
--- storm/doc/pegboard/attacking_gisp--hemppah/peg.rst:1.38     Tue Jun 17 
02:57:13 2003
+++ storm/doc/pegboard/attacking_gisp--hemppah/peg.rst  Tue Jun 17 03:53:31 2003
@@ -4,8 +4,8 @@
 
 :Authors:  Hermanni Hyytiälä
 :Date-Created: 2003-06-05
-:Last-Modified: $Date: 2003/06/17 06:57:13 $
-:Revision: $Revision: 1.38 $
+:Last-Modified: $Date: 2003/06/17 07:53:31 $
+:Revision: $Revision: 1.39 $
 :Status:   Incomplete
 
 .. :Stakeholders:
@@ -247,9 +247,17 @@
   
 - In a GISP network, when fraction f of the peers are "dumb" and a "dumb" peer 
   do not provide a "RESULT" message for a "QUERY" message, the probability of 
-  routing successfully "QUERY" message between two regular peers is (1-f)^h-1, 
-  where h is the routing hops used in the overlay. 
-
+  routing successfully a "QUERY" message between two regular peers is 
+  (1-f)^h-1, where h is the routing hops used in the overlay (i.e, O(log n)).
+  
+- It is expected that fraction f of all network traffic is "lost" in 
+  a static GISP network since the current GISP implementation do not handle 
+  "dumb" peers properly. More specifically, if there are n peers and fraction 
+  f are "dumb" (i.e., do not process regular messages, replies only to "SEEN" 
+  messages), the overlay has O(log n) average path length and all 
+  peers perform n-1 lookups (i.e., worst case: have to lookup every other peer
+  in the network), then the estimated total number of lost packets is 
+  [f^((log n)-1)]*[n((n-1)(log n))]. 
   
     
 - - -
@@ -260,11 +268,7 @@
   
 .. more specific, what effects cache has, distributions, formula ?
   
-- It is expected that fraction f of all network traffic k is "lost" in 
-  a static GISP network and therefore may have negative influence to network's
-  behaviour, since the current GISP implementation do not handle "dumb" peers 
-  properly, i.e., "dumb" peers reply to "alive"-queries but do 
-  not process or forward queries at all
+
   
 .. more specific, create a formula (?)
    
@@ -278,12 +282,22 @@
   fraction of f all peers become "dumb", same fraction f of all lookups will 
   fail.  
 
-  n peers, O(log n) path length, all peers perform n lookups. Then the total
-  number of packets is n((n-1)(log n))
+  Notes:
+  
+  n peers, O(log n) path length, all peers perform n-1 lookups (i.e., worst 
+  case: have to lookup every other peer). Then the total number of packets 
+  is n((n-1)(log n))
+  
+  n peers, O(log n) path length, random fraction of peers, r, perform rl 
+  lookups. Then the total number of packets is r((rl)(log n))
+
+  GISP network:  n peers, O(log n) path length, all peers perform n-1 lookups 
+  (i.e., worst case: have to lookup every other peer). Then the total number 
+  of packets is n((n-1)(log n))
   
   n peers where fraction f are hostile, O(log n) path length, all peers 
-  perform n lookups. Then the total number of lost packets is 
-  [f^((log n)-1)]*[n((n-1)(log n))]
+  perform n-1 lookups (i.e., worst case: have to lookup every other peer). 
Then 
+  the total number of lost packets is  [f^((log n)-1)]*[n((n-1)(log n))]
   
   
 .. No, you should not say "expect similar" - it's far too vague.