[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/03/04 06:56:31

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

Log message:
        Updates

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.108 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.109
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.108      Tue Mar 
 4 06:05:58 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Mar  4 
06:56:30 2003
@@ -39,7 +39,7 @@
 
 
 \abstract{
-In this thesis, we review existing Peer-to-Peer approaches, protocols and their
+In this thesis, we review existing Peer-to-Peer approaches, algorithms and 
their
 key properties. We summarize open problems in Peer-to-Peer networks and divide
 problems into three sub-categories. We observe that there are many
 problems, which have not solutions at all, or problems have proposed
@@ -104,7 +104,7 @@
 One of the most important properties of any distributed computing system are 
efficient 
 data lookup and security. In this thesis, we\footnote{Use of the plural is 
customary even if research paper is authored solely.}
 focus on these aspects in Peer-to-Peer domain.
-Specifically, we review existing Peer-to-Peer approaches, protocols and their 
properties. We observe
+Specifically, we review existing Peer-to-Peer approaches, algorithms and their 
properties. We observe
 that despite of greate amount of proposed Peer-to-Peer systems, all systems 
fall either
 loosely structured approach or tightly structured approach. Then, we discuss 
open problems in 
 Peer-to-Peer networks and divide problems into three sub-categories: security 
related problems, 
@@ -120,7 +120,7 @@
 algortihms to be used  with our Fenfire system in Peer-to-Peer environment. 
 
 To our knowledge, this thesis is the most comprehensive work with regard to 
summarizing 
-existing Peer-to-Peer protocols and open problems in Peer-to-Peer domain. 
However, this
+existing Peer-to-Peer algorithms and open problems in Peer-to-Peer domain. 
However, this
 thesis is not meant to be detailed work. More detailed information can be 
found from genuine
 publications written by original authors.
 
@@ -134,14 +134,14 @@
 is otherwise same as the second problem, except we want to locate and fetch 
all Fenfire
 related data from the Peer-to-Peer network, where given date and/or time range 
is given.
 
-When comparing different Peer-to-Peer approaches and protocols, we will 
examine their
+When comparing different Peer-to-Peer approaches and algorithms, we will 
examine their
 scalability, efficiency, space requirements for neighbor connections and 
overhead
 associated with system maintenance. When we have solutions to our research
 problems, we will use best solutions as examples in our algorithm proposals.
 
 \section{Thesis overview}
 This thesis is structured as follows. In next chapter, we give an overview of
-existing Peer-to-Peer approaches, protocols and key differences. In chapter 3, 
we
+existing Peer-to-Peer approaches, algorithms and key differences. In chapter 
3, we
 address open problems in Peer-to-Peer domain and divide problems into three
 sub-categories. Chapter 4 gives an overview of our Fenfire system. In chapter
 5 we evaluate existing Peer-to-Peer approaches with regard to Fenfire system 
and
@@ -151,7 +151,7 @@
 
 \chapter{Peer-to-Peer architectures}
 In this chapter we give brief history and overview of Peer-to-Peer networks, 
-review most important Peer-to-Peer protocols and list key differences between 
+review most important Peer-to-Peer algorithms and list key differences between 
 two main approaches.
 
 \section{Overview}
@@ -336,8 +336,8 @@
 Pastry \cite{rowston01pastry}, Peernet \cite{eriksson03peernet}, 
 Skip Graphs \cite{AspnesS2003}, SkipNet \cite{harvey03skipnet2}, 
 Symphony \cite{gurmeet03symphony}, SWAN \cite{bonsma02swan}, Tapestry 
-\cite{zhao01tapestry} and Viceroy \cite{malkhi02viceroy}. While there
-are significat differences among proposed systems, they all have in common
+\cite{zhao01tapestry}, Viceroy \cite{malkhi02viceroy} and others 
\cite{freedman02trie}. 
+While there are significat differences among proposed systems, they all have 
in common
 that participating peers are assigned \emph{peer identifiers} from
 a large \emph{identifier space}. Furthermore, application-specific
 data items are also assigned globally unique identifiers, \emph{keys}, 
@@ -349,12 +349,13 @@
 to implement identifier space.
 
 To store data into tightly structured overlay, each application-specific
-unique key (e.g., SHA-1 \cite{fips-sha-1}) is \emph{mapped} by the overlay to 
a 
-existing peer in the overlay. Thus, tightly structured overlay assigns a 
subset of all 
-possible keys to every participating peer. Furtermore, each peer in the 
structured 
-overlay maintains a \emph{routing table}, which consists of identifiers and IP 
addresses 
-of other peers in the overlay. These are peer's neighbors in the overlay 
network. 
-Figure \ref{fig:structured_hashing} illustrates the process of data to key 
mapping in tightly strucuted overlays.
+unique key (e.g., SHA-1 \cite{fips-sha-1}) is \emph{mapped} uniformly (e.g., 
using consistent
+hashing \cite{258660}) by the overlay to a existing peer in the overlay. Thus, 
tightly 
+structured overlay assigns a subset of all possible keys to every 
participating peer. 
+Furtermore, each peer in the structured overlay maintains a \emph{routing 
table}, which 
+consists of identifiers and IP addresses of other peers in the overlay. These 
are peer's 
+neighbors in the overlay network. Figure \ref{fig:structured_hashing} 
illustrates the 
+process of data to key mapping in tightly strucuted overlays.
 
 \begin{figure}
 \centering
@@ -381,6 +382,14 @@
 assigned keys.} keys is removed at the cost of each peer maintaining one 
 ''resource node'' in the overlay network for each resource item pair it 
publishes.
 
+PeerNet differs from other tightly structured overlays in that it operates
+at the \emph{network} level layer. Peernet makes an explicit distinction 
+between peer identity and address, which is supported by standard
+TCP/IP-algorithms. Otherwise, PeerNet has same performance properties
+as other tightly structured overlays, i.e. $O(\log{n})$ space required
+for maintaining information about other peers in the system and 
+$O(\log{n})$ data lookup efficieny.
+
 Stoica et al. \cite{balakrishanarticle03lookupp2p} have listed 
 four requirements for tightly structured overlays, which have to be 
 addressed in order to perform data lookups in tightly structured overlays. 
@@ -392,7 +401,7 @@
 
 Currently, all proposed tightly structured overlays provide at least 
 poly--logaritmical data lookup operations. However, there are some key 
-differences in routing algoritms. For example, Chord, Skip graphs and 
+differences in the data structure that they use as a routing table. For 
example, Chord, Skip graphs and 
 Skipnet maintain a local data structure which resembles skip lists 
\cite{78977}.
 In figure \ref{fig:structured_query}, we present overview of Chord's lookup 
process.
 On the left side of Chord's lookup process, we show the same data lookup 
process
@@ -400,8 +409,8 @@
 the query originator and the target in both methods is halved. Thus, the 
 locarithmic efficiency. 
 
-Kademlia, Pastry and Tapestry uses balanced tree-like 
-data structures. Figure \ref{fig:kademlia_lookup} shows the process of Kademlia
+Kademlia, Pastry and Tapestry uses balanced $k$-trees  
+as routing table's data structure. Figure \ref{fig:kademlia_lookup} shows the 
process of Kademlia
 data lookup. Viceroy maintains a butterfly data structure (see e.g., 
\cite{226658}), 
 which requires only constant number of neighbor peers while providing 
$O(\log{n})$ data lookup
 efficiency. Koorde, recent modification of Chord, uses de Bruijn graphs to 
maintain
@@ -623,7 +632,7 @@
 
 \subsection{Algorithms}
 
-Table \ref{table_Peer-to-Peer_protocols} lists proposed Peer-to-Peer 
algorithms 
+Table \ref{table_Peer-to-Peer_algorithms} lists proposed Peer-to-Peer 
algorithms 
 and their key properties with regard to performance and scalability. List 
 includes algorithms from two main approaches. However, majority of the 
algorithms 
 listed above belongs to tightly structured approach since there has been 
active 
@@ -662,7 +671,7 @@
 \multicolumn{6}{c}%
 {{\tablename\ \thetable{} -- continued from previous page}} \\
 \hline 
-\multicolumn{1}{|c|}{\textbf{Protocol}} &
+\multicolumn{1}{|c|}{\textbf{Algorithm}} &
 \multicolumn{1}{c|}{\textbf{Insert/Delete}} &
 \multicolumn{1}{c|}{\textbf{Space}} &
 \multicolumn{1}{c|}{\textbf{Lookup}} &
@@ -730,7 +739,7 @@
 \parbox{37pt}{$O(1)$ or $O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$ or $O(\frac{\log{n}}{\log{}\log{n}})$} &
 \parbox{85pt}{$2(\log{n})$} &
-\parbox{85pt}{Based on Chord protocol, uses de Bruijn graphs for better 
efficiency/fault-tolerance}
+\parbox{85pt}{Based on Chord algorithm, uses de Bruijn graphs for better 
efficiency/fault-tolerance}
 \\ \hline
 
 \parbox{37pt}{ODHDHT \cite{naor03simpledht}} &
@@ -825,115 +834,14 @@
 \\ \hline
 
 
-\caption{Different Peer-to-Peer lookup protocols. In this table $n$ is the 
number of peers in the system.} 
-\label{table_Peer-to-Peer_protocols}
+\caption{Different Peer-to-Peer lookup algorithms. In this table $n$ is the 
number of peers in the system.} 
+\label{table_Peer-to-Peer_algorithms}
 
  
 \end{longtable}
 \normalsize
 
-
--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
--system does find the service, if it exists
-
-
-+fast routing (aka searching)
-%+scalable (10^9 users, 10^14 data items)
-+robust
-+little network traffic
--own resources are mapped into the network (not necessary!!)
--keyword/fuzzy search not possible yet
--routing/query hotspots
--ASSUME THAT ALL NODES HAVE IDENTICAL CABABILITIES! However, in real life, p2p 
enviroment is extremely heterogeneous!
-
--the basic idea behind many DHTs is the fact that they perform operations in a 
binary-like tree
--more space/node --> the search arity is higher --> k is higher in k-ary trees
--DHTs' performance efficiency is derived from these tree based operations 
(e.g. split to half the previous scope)
-
-Skip graphs
-+fast routing (aka searching)
-+scalable
-+little network traffic (however, more than DHTs)
-+support *data* locality, opposite to DHTs where data is spread out evenly, 
destroying locality. In skip graphs, hashing is not requires, only *keys* 
matters (which we already have)
-+support for partial repair mechanism/self-stabilization (DHTs lack of repair 
mechanism/self-stabilization)
-+the most robust algorithm up to date, tolerance of adversial faults (DHTs 
support only of random faults)
-+adaptive: doesn't need to know keyspace size before hand, instead of many 
DHTs, which require a priori knowledge about the size of the system or its 
keyspace
-+support for range queries, e.g. natural for version control: 'find latest 
news from yesterday', 'find largest key < news:12/12/2002', 'find all related 
objects nearby'
-(in DHTs this is a open problem)
-+There are not hotspots in skip graphs (query/routing hotsports)
--not network/geographical locality
--for our purposes, Skip Graps could be used (sensible) only for block IDs, not 
for URNs: in Skip Graps, there have to be total order for data elements --> for 
URNs, there cannot be a total order
--for range queries, we would have to use local sensitive hashing, *if* we want 
fetch blocks like 'next block = i + 1'. SHA-1 is a (secure) random hash of 
content (it won't help for us in this case)
-
-Peernet
--Peernet is a p2p based *network layer* for large networks
--Peernet makes an explicit distinction between node identity and address
--requires no manual configuration (plug-and-play)
--can support wireless or wireline infrastructure
--log(n) routing table, log(n) search  
-
-\cite{aspnes02faultrouting}
-\cite{ratnasamy02ght}
-\cite{236713}
-\cite{258660}
-
-\cite{freedman02trie}
-
-\cite{plaxton97accessingnearby}
-
-
-
-
-\cite{78977}
-
-
-
-
-
-
-\cite{garciamolina03sil}
-
-\cite{rowston03controlloingreliability}
-
-
-
-\cite{byers03dhtbalancing}
-
-\cite{pias03lighthouse}
-
-
-\cite{debruijn46graph}
-
-
-
-\cite{Gribble:2000:SDD}
-
-
-
-\cite{harrisoncircle}
-
-
-
--CFS splits files into blocks (<50Kb), PAST distributed whole files
-
-
-
+  
 
 \chapter{Open Problems in Peer-to-Peer}
 
@@ -1161,26 +1069,7 @@
 
 \section{Performance and usability problems in Peer-to-Peer}
 
-In this section we review open problems regarding performance and usability.
-
-1) Which one is more important: short path length or overhead associated with 
keeping routing tables updated, e.g. number of state updates whenever 
join/leave occurs
- (number of neighbors)
-2) Are we able to achieve reasonably pathlenghts with less neigbors (Viceroy) ?
-3) How big is the difference between optimal path length and worst case path 
length ?
-4) How difficult is to recover from total routing mislead and the cost of it ?
-5) Can we choose better neighbors by using network latencies instead of 
closeness of IDs in the ID space ? What are the effects doing so ?
-6) Can we choose IDs (globally) based on the geographical location/distance ? 
Is there a working model for doing so ?
-7) How do we should work with node heterogeneity; how big changes have to be 
made to existing algorithms for better support to heterogeneity ?
-
-Principles on scalable search in decentralized, and unstructured networks 
\cite{lv02searchreplication}:
-1) system must support adaptive termination 
-2) message duplication should be minimized
-3) each additional step during search should not significantly increase the 
number of nodes visited
-
-Network proximity: 
--\cite{pias03lighthouse}, \cite{ng02predicting}
-
-
+In this section, we discuss performance related issues regardin Peer-to-Peer 
systems.
 
 \subsection{Efficient data lookup}
 
@@ -1220,17 +1109,19 @@
 random walk searches in query lookups. Indeed, Freenet's query resembles
 depth-first traversal and peers' routing tables are dynamically built
 using caching. This is an outcome of Freenet's main design priciples, 
-i.e., anonymity.
+i.e., anonymity. Additional improvements to Freenet's data lookup using
+''small-world phenomenon'' has been proposed by Zhang et al. 
\cite{zhang02using}.
+
 
 Since tightly structured systems have efficient data lookup at the application 
level overlay,
-current research efforts are focused on proximity based data lookup. In 
proximity based data lookup,
-peers try to choose routing-tables refering to other peers that are 
\emph{nearby} in
-the underlying network. In this way, tightly structured systems are able to
-decrease actual lookup \emph{latency}. CAN, Kademlia, Pastry and Tapestry have 
a advanced
-heuristics for proximity based routing. Additionally, most recent version of 
Chord uses
-proximity based routing inspired by Karger and Ruhl 
\cite{karger02findingnearest}. Skipnet
-\cite{harvey03skipnet1} uses combination of proximity and application level 
overlay routing 
-when performing data lookups. Authors call this feature \emph{constrained load 
balancing}.
+current research efforts are focused on proximity based data lookup. In 
proximity based data lookup, 
+peers try to choose routing-tables refering to other peers that are 
\emph{nearby} in the 
+underlying network. In this way, tightly structured systems are able to 
decrease actual 
+lookup \emph{latency}. CAN, Kademlia, Pastry and Tapestry have a advanced 
heuristics for 
+proximity based routing. Additionally, most recent version of Chord uses 
proximity based 
+routing inspired by Karger and Ruhl \cite{karger02findingnearest}. Skipnet 
\cite{harvey03skipnet1} 
+uses combination of proximity and application level overlay routing when 
performing data 
+lookups. Authors call this feature \emph{constrained load balancing}.
 
 Research related to proximity based routing include 
\cite{karger02findingnearest}, 
 \cite{hildrum02distributedobject}, \cite{brinkmann02compactplacement}, 
\cite{rhea02probabilistic},
@@ -1238,21 +1129,6 @@
 more research is required to make latency heuristic more effective and 
practical.
 
 
-\cite{ripeanu02mappinggnutella}
-
-
-
-
-
-
-
-
-
-
-Locality \cite{keleher-02-p2p}
-
-
-
 \subsection{Fast and usable search}
 
 To make Peer-to-Peer systems usable in a large, these systems have to support 
flexible, efficient
@@ -1287,8 +1163,6 @@
 more research is required to make indexing and searching more efficient.
 
 
-Improve Freenet performance with small worlds \cite{zhang02using}
-
 \subsection{System management}
 
 Adaptive system management and self-organization are essential properties
@@ -1399,58 +1273,10 @@
 
 \section{Summary}
 
-\cite{daswani03openproblems}
-
-\cite{sit02securitycons}
-
-Main problems in different approaches (own conclusions, based on research 
efforts):
-1) Decentralized, but structured
--make routing/system more flexible againts adversial attacks
-       -e.g. -there is a single point of routing failure in these approaches 
(h hops, little amount f of system are adversial) 
--make searching/query model more flexible (keyword searching)
-       -use keywords/range searches instead of exact keys
-       -proposal for range searches: Scalable, Efficient Range Queries for 
Grid Information Services \cite{andrzejak02rangequeries}
-       -proposal for broadcast operation in DHT-based systems 
\cite{ansaryefficientbroadcast03} (insight: k-ary tree is a spanning tree, 
traverse spanning tree)
-       -proposal for complex queries in DHTs \cite{harren02complex} (insight: 
use SQL-like mechanisms)
-
-2) Decentralized, but unstructured
--make routing more scalable: reach more nodes, create less traffic
--remember mention: when people talk about Gnutella's scalability issues
-they jumble apples and oranges: *Gnutella* itself is scalable, but query model 
-is not scalable, since searching creates a lot of traffic!
-
-3) Centralized
--no recent research efforts/no interests
--not suitable for real p2p, as Napster case showed
-
-Current research with regard to p2p security:
--lot of done has been done on persistence
--little has been done on distinctness (sybil attack)
--computational puzzles for preventing DDOS attacks (force attacker perform 
more work than victim)
--puzzles can be used for accountability (Dingeline, in Peer-to-Peer: 
Harnessing...), but can dangerous
--some research has been done on on-line identities for humans. However, they 
often has a direct relation to phychical world
-
-
-5.3. General security issues related to decentralized, but structured 
strategies
-
-Secure routing requires \cite{castro02securerouting}:
-1) a secure assignment of node identifiers
-2) secure routing table maintenance
-3) secure message forwarding
-
-General security considerations \cite{sit02securitycons}
-1) Define verifiable system invariants (and verify them!)
-2) Allow querier to observe lookup progress
-3) Assign keys to nodes in a verifiable way
-4) Server selection in routing may be abused
-5) Cross-check routing tables using random queries
-6) Avoid single points of respinsability
-
--security summary: 
-       -problem: attacker denies service, attacker return incorrect data and 
attacker denies data exists:
-       -solution: redundancy (replication, caching)
-       -problem: sybil attack (attacker creates multiple identities and foils 
the redundancy)
-       -solution: need a way to control creation of node IDs (ID = 
SHA-1(ip-address), challange node verify its ID)
+In this section we summarize open problems in Peer-to-Peer systems. All open 
problems entries 
+listed in this section are not necessarily mentioned in the previous sections. 
This is because
+we discussed only the most significant problems earlier. Problems listed here 
are variations
+of previously mentioned problems, or otherwise related to them.
 
 
 
@@ -1670,7 +1496,7 @@
 
 \parbox{90pt}{System in flux \cite{libennowell01observations}, \cite{571863}, 
\cite{ledlie02selfp2p}, \cite{albert-02-statistical}} &
 \parbox{110pt}{Nodes join and leave system constantly. What about load 
balancing and performance ?} &
-\parbox{110pt}{Half-life phenomenon (for analysis), simple overlay maintenance 
and construction protocol} &
+\parbox{110pt}{Half-life phenomenon (for analysis), simple overlay maintenance 
and construction algorithm} &
 \parbox{110pt}{Initial theoretical analysis have been created, but not 
comprehensive model for analysing different system states and its variations 
(e.g. complex usage patterns)}
 \\ \hline
 
@@ -1682,14 +1508,14 @@
 
 \parbox{90pt}{Fail Stop} &
 \parbox{110pt}{A faulty node stops working} &
-\parbox{110pt}{Failure detectors, informing protocols} &
+\parbox{110pt}{Failure detectors, informing algorithms} &
 \parbox{110pt}{Creates more network traffics, node's information can be 
outdated, failure detectors not reliable}
 \\ \hline
 
 
 \parbox{90pt}{Byzantine faults \cite{296824}} &
 \parbox{110pt}{Faulty nodes may behave arbitrarily} &
-\parbox{110pt}{Byzantine replication protocols -> get information from 
multiple entities, trust majority's opinion} &
+\parbox{110pt}{Byzantine replication algorithms -> get information from 
multiple entities, trust majority's opinion} &
 \parbox{110pt}{Much research has been done on this field, practical solutions, 
decreases system's, performance slighly}
 \\ \hline
 
@@ -1779,8 +1605,6 @@
 \normalsize
 
 
-
-
 \chapter{Fenfire hypermedia system}
 
 In this chaper we give an overview of Fenfire system and its objectives. We 
also 
@@ -2100,7 +1924,7 @@
 For the previous mentioned reasons, we see tightly structured approach the
 better alternative to our needs. Both Storm and tightly structured overlays 
uses
 globally unique identifiers for locating data. Furthermore, tightly structured
-overlays provides guaranteed data lookup and has very efficient lookup 
protocols,
+overlays provides guaranteed data lookup and has very efficient lookup 
algorithms,
 which are essential to xanalogical model to be usable in distributed 
environment.
 Table \ref{table_comparison_approach} lists the key feature of both approaches.
 
@@ -2308,7 +2132,7 @@
 
 \chapter{Conclusions}
 
-In this thesis, we have reviewed existing Peer-to-Peer approaches, protocols 
and
+In this thesis, we have reviewed existing Peer-to-Peer approaches, algorithms 
and
 their properties. Currently, two main Peer-to-Peer overlay approaches
 exist: loosely and tightly structured ovelrays. We discussed approaches'
 differences, disadvantages and advantages.
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.95 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.96
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.95   Tue Mar  4 
06:05:58 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Tue Mar  4 
06:56:30 2003
@@ -2101,6 +2101,7 @@
 
 @article{504642,
         title = {Difficulties in simulating the internet},
+        author = {Sally Floyd and Vern Paxson},
         journal = {IEEE/ACM Transactions on Networking (TON)},
         volume = {9},
         number = {4},