[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/27 07:08:58

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

Log message:
        Formal definitions

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.90 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.91
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.90       Thu Feb 
27 05:41:47 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Feb 27 
07:08:58 2003
@@ -275,8 +275,6 @@
 significant message processing overhead for each query. Furthermore, flooding 
may increase 
 the load on participating to the point, where it has to leave the network. 
 
-
-
 Lately, there has been done lot of research to improve Gnutella's data lookup 
efficiency 
 and scalability. Adamic et. all \cite{adamic99small}, 
\cite{adamic02localsearch}, 
 \cite{adamic01powerlawsearch} has been studied different random walk methods 
in power-law 
@@ -287,7 +285,7 @@
 structured Peer-to-Peer systems have adopted this method with some 
modifications
 \cite{gnutella2url}, \cite{shareazaurl}, \cite{fasttrackurl}, 
\cite{morpheusurl}, 
 \cite{kazaaurl}, \cite{jxtaurl}, \cite{jxtaoverview}, 
\cite{botros01jxtasearch},
-\cite{ganesan02yappers}.
+\cite{ganesan02yappers}, \cite{kato02gisp}.
 Figures \ref{fig:gnutella_overlay_supernodes} and 
\ref{fig:gnutella_overlay_cluster}
 illustrated two possible variations of power-law overlay networks. All the 
systems
 share the property of that high degree peers maintain index of all other peers 
@@ -323,8 +321,8 @@
 Directed breadt-first search \cite{yang02improvingsearch} optimizes the 
original 
 breadt-first searche in way that peer selects neighbors with many quality 
results
 may be reached, thereby maintaining the the quality of costs and decreasing 
the amount
-of messages sent to network. Alpine Peer-to-Peer system \cite{alpineurl} uses
-somewhat similar method when performing data lookups.
+of messages sent to network. Alpine \cite{alpineurl} and NeuroGrid 
\cite{joseph02neurogrid} 
+Peer-to-Peer system use somewhat similar method when performing data lookups.
 
 Local indices \cite{yang02improvingsearch} in one variation of active caching. 
 In this scheme, each peer maintains an index over the data of all nodes within 
@@ -348,85 +346,20 @@
 research is required to make loosely structured approach's data lookup more
 scalable and effective. 
 
-principles
-
-
-power-law disribution
-
-+own resources are not mapped into the network
-+keyword/fuzzy search possible
--based on FBNt technique, 
-+solves some of the Gnutella's scalability issues by introducing ``Super 
nodes'' (a superNode acts like a local hub, building an index 
-of the resources being shared by each node connected to it and proxying lookup 
queries on behalf of other nodes)
-+this kind of structure reduces network traffic in comparison to a original 
broadcast query algorithm employed on the Gnutella system
--not scalable
--huge network traffic
--not fast routing 
--no guarantee that all data will be located
-
--this category: Gnutella, Freenet, 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) (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)
-
-
 
 \subsection{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))}
-
-
-\subsection{Protocols}
-
-
-%-SWNs require O(log^2 n) hops to reach arbitrary destinations, assuming 
(*only and only if* !!!) that 
-links between nodes are constructed in the way that they are uniformly 
distributed over all distances 
-in the network (Kleinberg)
-
-1.5  Social Discovery Systems (SDS)
-Notice: pros and cons are not presented here
--nodes continually discover new nodes to communicate with and determine which 
properties each node have. 
--every node has a total control over the connections in the
--as in real social life, nodes who have returned relevant results in the past, 
will have a high quality value in future query lookups
--with every lookup query, a node determines how proficient a given node is to 
another node's objectives
-
-
-
-Improve Freenet performance with small worlds \cite{zhang02using}
-
-\cite{ramanathan02goodpeers}
-\cite{kleinberg99small}
-\cite{watts00dynamics}
-\cite{nips02-Kleinberg}
-
-
-
-
-\cite{kato02gisp}
-
-\cite{joseph02neurogrid}
-
-
-\subsection{Super peers and Super peer clusters}
-
-
-
-
+In this subsection we formalize loosely strucured overlays main components. 
This
+model is based on original Gnutella overlay network with power-law 
improvements.
 
+Let $S$ be the aggregate of all services $s$ in system. Let $P$ be the 
aggregate of 
+all peers $p$ in system. Then, $\forall s \in S$, there is a provider of the 
service, 
+expressed as $p = provider(s)$. Every $p$ has neighbor(s), named as 
$neighbor$, which 
+is $P$ = \{$p \in P: \exists neighbor$, which is randomly chosen from $P$\}.
+Super peer is a peer, which hosts the indices of other peers, $sp = 
summaryindex(provider(s))$.
+Morover, $\forall$ reqular peer, $p$, there is super peer, which has has a 
index of regular
+peer's content, specifically $ps$, $P$ = \{$p \in P: \exists ps$, 
+where $ps$ = $summaryindex(provider(s)) \bigwedge (p = provider(s))$\}
 
 
 
@@ -498,18 +431,19 @@
 
 \subsection{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)' (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'}
-
+Let $S$ be the aggregate of all services $s$ in system. Let $P$ be the 
aggregate of 
+all peers $p$ in system. Let $I$ be the aggregate of all identifiers $i$ in 
system. 
+Let $IS$ be the aggregate of all identifier points $ip$ in system. Then, 
$\forall s \in 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 $(IS,d)$, 
where $d$
+is the distance between two coordinate points $ip_i$, $ip_j$ in $IS$ space. 
Mapping 
+function is defined as $map: I \longmapsto IS$, and coordinate point as 
+$ip = map(identifier(s))$, which maps service, expressed by a identifier to 
coordinate 
+point $ip$ in $(IS,d)$. Peer's p resources are mapped onto a set $IS$ = \{$ip 
\in IS: 
+\exists s \in S$, $ip = map(identifier(s)) \bigwedge (provider(s) = p)$\}., 
+which means that resources that a peer provides into the system are not kept 
locally.
+Every $p$ has neighbor(s), named as $neighbor$, which are $P$ = \{$p \in P: 
\exists neighbor$, 
+where $difference(p,p_neighbor)= close$, and  $close$ is minimal difference 
$d$ in $(IS,d)$\}.
 
 \subsection{Protocols}
 
@@ -1017,6 +951,10 @@
 \cite{CuencaAcuna2002DSIWorkshop}
 \cite{Bhattacharjee03resultcache}
 \cite{chord:om_p-meng}
+
+\cite{ramanathan02goodpeers}
+
+Improve Freenet performance with small worlds \cite{zhang02using}
 
 \subsection{System management}