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

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/01/20 04:32:39

Modified files:
        Documentation/misc/hemppah-progradu: research_problems 

Log message:
        more formal definitions

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.21&tr2=1.22&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.21 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.22
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.21      Mon Jan 
20 02:39:12 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Mon Jan 20 
04:32:39 2003
@@ -601,26 +601,72 @@
 
 2.9 Models
 
-This sections presents formal models for various p2p architectures.
+This sections presents formal models for various p2p architectures. 
 
 2.9.1. Centralized
--this category: Napster
+-this category: e.g. Napster
+-resources are kept locally
+-centralized index of all available resources in a a system
+-a service request is totally based on centralized index
+
+Formal definition
+-let S be the aggregate of all services s in system (data, service, computing 
power)
+-let P be the aggregate of all peers (providers) p in system (all physical 
entities participating)
+-let SE be the aggregate of all servers se in system (all physical central 
server participating)
+-let I be the aggregate of all index entries ie in system (index of all 
services in system)
+-for each service s 'mathematical belongs to' S, there is a index entry in 
some se 'mathematical belongs to' SE , expressed as 'ie = indexentry(s)'
+-for each service s 'mathematical belongs to' S, there is a provider of the 
service, expressed as 'p = provider(s)'
+-every p has only one neighbor, named as p_centralized_neigbor, which is P = 
{p 'mathematical belongs to' P: 'mathematical there exists at least one' 
p_centralized_neighbor, which is some se 'mathematical belongs to' SE}
 
 2.9.2. Decentralized, but structured
--this category: DHTs, SWANs, Skip Graphs, hierarchical Gnutella's (superpeers, 
clusters)
+-this category: DHTs, SWANs, Skip Graphs
+
+a) DHTs, SWAN and Skip Graphs
+DHT
+-service is data block, node/peer is a physical computer
+-*servers* self-organize towards a lookup network
+-DHTs can be thought as a 'structured overlay random graphs'
+-There is a explicit metric space in every DHT. Term 'closeness' differs 
between existing DHTs: it can be XOR/numerical/eucklidean difference between 
identifiers
+-Resource can *be* a resource, or a *pointer* to a resource
+-a service request is routed towards service based on node's local knowledge
+-identifiers are expected to be distributed uniformly
+-DHTs require a knowledge of identifier space's size initially
+-resembles a balanced tree structure
+
+SWAN and Skip Graphs
+-in this scheme, node = service
+-*key-value pairs* self-organise towards a lookup network
+-There is a explicit metric space. Term 'closeness' differs between existing 
DHTs: it can be XOR/numerical/eucklidean difference between identifiers
+-Resource can *be* a resource, or a *pointer* to a resource
+-a service request is routed towards service based on node's local knowledge
+-services can be hosted locally (opposite to DHTs)
+-identifiers are expected to be distributed uniformly
 
-a) DHT
-(in our case, service is data block)
--let S be the aggregate of all services s in system
--let P be the aggregate of all peers (providers) p in system
--let I be the aggregate of all identifiers i in system
--let C be the aggregate of all coordinate points c in system
+Formal definition
+-let S be the aggregate of all services s in system (data, service, computing 
power)
+-let P be the aggregate of all peers (providers) p in system (all physical 
entities participating)
+-let I be the aggregate of all identifiers i in system (All possible unique 
identifiers, based on e.g. SHA-1)
+-let IS be the aggregate of all identifier points ip in system (entity, where 
'closeness' of services are calculated, e.g. XOR/numerical metrics, based on 
identifiers)
 -for each service s 'mathematical belongs to' S, there is a provider of the 
service, expressed as 'p = provider(s)'
--service's identifier is defined as 'i = identifier(s)'
--metric space is defined as a pair '(C,d)', where d is the distance between 
coordinate points c
--hash function is defined as 'hash: K -> C', and coordinate point as 'c = 
hash(identifier(s))', which maps service, expressed by a identifier to 
coordinate point c in '(C,d)'
--peer p is mapped onto a set C = {c 'mathematical belongs to' C: 'mathematical 
there exists at least one' s 'mathematical belongs to' S, c = 
hash(identifier(s)) 'boolean AND' (provider(s) = p)}
+-service's identifier is defined as 'i = identifier(s)' (in our case, 
SHA-1(content of data block))
+-metric space is defined as a pair '(IS,d)', where d is the distance between 
two coordinate points ip in IS space
+-mapping function is defined as 'map: I -> IS', and coordinate point as 'ip = 
map(identifier(s))', which maps service, expressed by a identifier to 
coordinate point ip in '(IS,d)'
+-In DHT, peer's p resources are mapped onto a set IS = {ip 'mathematical 
belongs to' IS: 'mathematical there exists at least one' s 'mathematical 
belongs to' S, ip = map(identifier(s)) 'boolean AND' (provider(s) = p)}, which 
means
+that resources that a peer provides into the system, are not kept locally. 
This is a important feature of DHTs (to be specific, feature of 'map: I -> 
IS')! In SWAN and Skip Graphs, resources are can be kept locally, if wanted!
+-every p has neighbor(s), named as p_neighbor, which are P = {p 'mathematical 
belongs to' P: 'mathematical there exists at least one' p_neighbor, where 
'difference(p,p_neighbor)= 'close'', where 'close' is minimal difference d in 
'(IS,d'}
+
+
 
 2.9.2  Decentralized and unstructured
--this category: Gnutella
+-this category: Gnutella, hierarchical Gnutella's (superpeers, clusters)
+-a service request is routed randomly to all/specific neighbors
+-system doesn't have *any* knowledge, where service is located (opposite to 
centralized and decentralized but structured)
 
+Formal definition
+-let S be the aggregate of all services s in system (data, service, computing 
power)
+-let P be the aggregate of all peers (providers) p in system (all physical 
entities participating)
+-for each service s 'mathematical belongs to' S, there is a provider of the 
service, expressed as 'p = provider(s)'
+-hierarchical gnutellas: let DI be the aggregate of all decentralized index 
entries die in system (decentralized index of all services in system)
+-hierarchical gnutellas: define super peer, which hosts the indices of other 
peers, as a 'sp = summaryindex(provider(s))'
+-every p has neighbor(s), named as p_neigbor, which is P = {p 'mathematical 
belongs to' P: 'mathematical there exists at least one' p_neighbor, which is 
'randomly' chosen from p_neighbor 'mathematical belongs to'}
+-hierarchical gnutellas: for each peer reqular peer, p_regular, there is super 
peer, p_super, P = {p 'mathematical belongs to' P: 'mathematical there exists 
at least one' p_super, where p_super = summaryindex(provider(s)) 'boolean AND' 
(p_regular = provider(s))}