gzz-commits
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

 From: Hermanni Hyytiälä Subject: [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert... Date: Wed, 26 Mar 2003 07:47:02 -0500

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/03/26 07:47:02

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

Log message:
Updates

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.194
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.195
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.194      Wed Mar
26 05:36:39 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Wed Mar 26
07:47:02 2003
@@ -92,12 +92,13 @@
and ad hoc nature of Peer-to-Peer improves scalability and avoids single
points of failure.

The Fenfire project is an attempt to build a hyperstructured, seamlessly
interoperating desktop
-environment. In the Fenfire, all data is stored in same format, i.e., data
blocks.
-Each data block have a globally unique identifier and it can be referred, by
pointer blocks.
+environment. In the Fenfire system, all data is stored as blocks.
+Each block has a globally unique identifier and it can be referred, by pointer
blocks.
Other features of the Fenfire include innovative user
-interfaces for viewing data and the use of Peer-to-Peer networking for network
transparency.
+interfaces for viewing data. The applicability of Peer-to-Peer networking with
Fenfire for network
+transparency is currently under investigation.

-There are three research problems discussed in this thesis: first, finding the
most efficient
+Three research problems are discussed in this thesis: first, finding the most
efficient
way to locate and fetch Fenfire data blocks from a Peer-to-Peer network, when
the block's
identifier is given. Second, we want to find the most efficient way to locate
and fetch the most
recent Fenfire data block from a Peer-to-Peer network referred by a pointer.
The third problem
@@ -109,18 +110,18 @@
algorithms and their key properties. Our insight is that despite the great
amount of proposed
Peer-to-Peer systems, we are able to classify \emph{all} systems either to
loosely or
tightly structured approach. We also discuss open problems in
-Peer-to-Peer systems and divide problems into three sub-categories: security,
performance, and miscellaneous
+Peer-to-Peer research and divide problems into three sub-categories: security,
performance, and miscellaneous
problems. We attempt to comprehensively summarize existing algorithms and open
problems in
-Peer-to-Peer domain, this thesis doesn't give detailed information about
reviewed algorithms nor
+Peer-to-Peer domain. This thesis doesn't give detailed information about
reviewed algorithms nor
open problems. More detailed information can be found from the references.

-Then, we give an overview of the Fenfire project, and evaluate Peer-to-Peer
approaches to Fenfire's
+Finally, we give an overview of the Fenfire project, and evaluate Peer-to-Peer
approaches to Fenfire's
needs. Finally, we propose simple but yet efficient methods to be used for
data lookups in Peer-to-Peer
environment.

\chapter{Peer-to-Peer architectures}
In this chapter we will give a brief history and overview of Peer-to-Peer
networks,
-review most the important Peer-to-Peer algorithms and list key differences
between the
+review the most important Peer-to-Peer algorithms and list key differences
between the
two main approaches.

\section{Brief history and overview}
@@ -135,7 +136,7 @@

The most popular form of modern Peer-to-Peer computing is file-sharing. In
this scenario,
participants of Peer-to-Peer network share their file resources with other
participants.
-This can be seen as a variant of distributed file system (e.g.,
\cite{levy90distributedfilesystems}).
+This is a form of distributed file system (e.g.,
\cite{levy90distributedfilesystems}).
A modern Peer-to-Peer system is composed of an \emph{application} level
overlay network, i.e.,
network operates at the application level and forms a logical network overlay
on top of physical
network. Figure \ref{fig:application_level} illustrates the Peer-to-Peer
application level overlay network.
@@ -154,7 +155,7 @@

-In the development of modern Peer-to-Peer systems, lot of influence has been
derived from
+In the development of modern Peer-to-Peer systems, lot of influences have been
derived from
outside of computer science. First, it is interesting to realize that chemical
properties of biological cells, the Internet, ad hoc
Peer-to-Peer systems, and social network self-organize based on the same
principles \cite{albert-02-statistical, albert-00-tolerance, watts00dynamics}.
Second, the
@@ -169,15 +170,14 @@
In the end, however, we observe that there are only two approaches in which
all modern Peer-to-Peer
systems fall: the loosely structured approach and the tightly structured
approach.
By structure, we refer to the topology of the overlay network, i.e., how the
connections between participating peers are created
-and maintained. By data lookup model, we mean the methods which are used for
finding data from the overlay.
-In the following sections, we will discuss in more detail the properties of
these approaches.
-
+and maintained. In the following sections, we will discuss in more detail the
properties of these approaches.

\section{Loosely structured}

In the loosely structured approach the construction and the maintenance of the
overlay is controlled
-loosely. The placement of services and topology of the overlay is random. The
data lookup model in loosely structured systems is
-not very efficient, because of unstructured properties of the overlay.
+loosely. The placement of services and the topology of overlay is random. The
data lookup model in loosely structured systems is
+not very efficient, because of unstructured properties of the overlay. Data
lookup model is a combination of methods which
+are used for finding data from the overlay.

\subsection{Definition}

@@ -202,15 +202,16 @@
Peers in the Napster network made requests to the central directory server to
find
other peers hosting desirable content. Since service requests were totally
based on a
centralized index, Napster didn't scale well because of constantly updated
central
-directory, and had a single point of failure.
+directory and had a single point of failure.

Gnutella \cite{gnutellaurl} is a well-known example of loosely structured
overlay system. Gnutella
is a pure Peer-to-Peer network as no peer is more important than any other
peer in the network.
The construction and maintenance of Gnutella network is extremely ad hoc,
since participating
-peers can form the overlay network based on \emph{local} knowledge. Figure
\ref{fig:gnutella_overlay}
+peers can form the overlay network based on \emph{local} knowledge (i.e., a
peer has no knowledge
+of global state of the system). Figure \ref{fig:gnutella_overlay}
illustrates the overlay network of Gnutella network. The Gnutella network can
be considered as a variation of power-law
-graph \cite{albert-02-statistical}. In power-law graphs only a few peers have
high
-number of neighbor links and the majority of peers have low number of neighbor
links.
+graph \cite{albert-02-statistical}. In power-law graphs only few peers have
high
+number of neighbor connections and the majority of peers have low number of
neighbor connections.

\begin{figure}
\centering
@@ -233,7 +234,7 @@
with depth limit $T$ (e.g., 7), where $T$ is the system-wide maximum TTL of a
message in hops. Thus,
only peers that are TTL hops away from the query originator will forward the
query or respond to the query.
In the Gnutella network, search results are fast, because BFS sends queries to
-every possible neighbor. Clearly, this method wastes resources and doesn't
scale well.
+every possible neighbor.

\begin{figure}
@@ -254,7 +255,7 @@

Adamic et al. \cite{adamic99small, adamic02localsearch,
adamic01powerlawsearch}
have studied different data lookup methods in power-law networks and have
found that by
-instructing the peers that forward data lookups to select high degree peers,
the performance of data lookup
+instructing peers that forward data lookups to select high degree peers, the
performance of data lookup
increases significantly. Figure \ref{fig:gnutella_powerlaw} presents an
example topology of power-law network with three high
degree peers. Some of the most recent loosely structured Peer-to-Peer
protocols have adopted this method:
Shareaza \cite{shareazaurl} uses the Gnutella2-based flooding protocol
\cite{gnutella2url}, Morpheus \cite{morpheusurl}
@@ -292,12 +293,12 @@

Partly due to scalability problems of loosely structured systems, several
tightly
structured overlays have been proposed. In the tightly structured
-approach the overlay is constructed determistically, which all participating
peers have to follow. The topology of the
-overlay and the placement of services is controlled tightly therefore enabling
more scalable and efficient data lookup model.
+approach the overlay is constructed determistically, which all participating
peers have to follow; the topology of the
+overlay and the placement of services is controlled tightly.

\subsection{Definition}

-In this subsection, we formalize the main features of tightly structured
overlay, i.e.,
+In this subsection, we formalize the main features of tightly structured
overlay such as
identifiers, identifier space and the mapping function.

Let $S$ be the aggregate of all services $s$ in the system. Let $P$ be the
aggregate of
@@ -314,15 +315,14 @@

\subsection{Systems}

-The biggest difference compared to the loosely structured approach is that
with tightly structured systems,
-it is now feasible to perform \emph{global} data lookups in the overlay. By
global lookup, we mean
-that the system is able to find a service from the overlay efficiently, if it
exists in the overlay.
+With tightly structured systems, it is feasible to perform \emph{global} data
lookups in the overlay efficiently. By global lookup, we mean
+that the system is able to find a service from the overlay, if it exists in
the overlay.
While there are significant differences among proposed tighty structured
systems, they all have in common
that \emph{peer identifiers} are assigned to participating peers from
a large \emph{identifier space} by the overlay. Globally unique identifiers
are also assigned to application-specific data items, \emph{keys},
which are selected from the same identifier space. For instance, globally
unique keys can be created
-using a cryptographic content hash (e.g., SHA-1 \cite{fips-sha-1}) over the
contents of a data item.
+using a cryptographic content hash function (e.g., SHA-1 \cite{fips-sha-1})
over the contents of a data item.
The form of identifier space differs between proposed systems. Geometrical
circular form of identifier space (and variants)
is most widely used. For instance, Chord \cite{stoica01chord}, Koorde
\cite{kaashoek03koorde},
Pastry \cite{rowston01pastry}, SWAN \cite{bonsma02swan}, Tapestry
\cite{zhao01tapestry}
@@ -335,18 +335,24 @@
hashing \cite{258660}) by the overlay to an existing peer in the overlay.
Thus, tightly
structured overlay assigns a subset of all possible keys to every
participating peer.
We say that a peer is \emph{responsible} for the keys which are assigned by
the overlay.
-Figure \ref{fig:structured_hashing} illustrates the
-process of data to key mapping in a tightly structured overlay.
-Also, each peer in the tightly structured overlay maintains a \emph{routing
table}, which
+Figure \ref{fig:structured_hashing} illustrates this
+process. Also, each peer in the tightly structured overlay maintains a
\emph{routing table}, which
consists of identifiers and IP addresses of other peers in the overlay.
Entries of the routing
table represent peer's neighbors in the overlay network.

+\begin{figure}
+\centering
+\includegraphics[width=12cm, height=7cm]{structured_overlay_new.eps}
+\caption{Principal idea of tightly structured overlays.}
+\label{fig:structured_hashing}
+\end{figure}
+
Currently, all proposed tightly structured overlays provide at least
-poly--logarithmical data lookup operations. However, there are some key
-differences in the data structures representing the identifier space.
+poly--loga-rithmical data lookup operations. However, there are some key
+differences between the data structures representing the identifier space.
For example, Chord \cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and
SkipNet \cite{harvey03skipnet2} maintain a
-distributed data structure which resembles Skip list \cite{78977}.
-In figure \ref{fig:structured_query}, we present an overview of Chord's lookup
process.
+distributed data structure which resembles the Skip list \cite{78977}.
+In figure \ref{fig:structured_query}, we present an overview of Chord's data
lookup process.
On the right side of Chord's lookup process, the same data lookup process
is shown as a binary-tree abstraction.  It can be noticed, that in each step,
the distance
decreases with a logarithmic efficiency.
@@ -359,7 +365,7 @@
\end{figure}

Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and
Tapestry
-\cite{zhao01tapestry} uses balanced $k$-trees to implement the overlay. Figure
+\cite{zhao01tapestry} uses balanced $k$-trees to implement the data structure
of identifier space. Figure
\ref{fig:kademlia_lookup} shows the process of Kademlia's
data lookup. Viceroy \cite{malkhi02viceroy} maintains a butterfly data
structure (e.g., \cite{226658}),
which requires only a constant number of neighbor peers while providing
$O(\log{n})$ data lookup
@@ -373,13 +379,6 @@
\includegraphics[width=10cm, height=8cm]{kademlia_lookup.eps}
\caption{Kademlia's simplified data lookup process on top of tightly
structured overlay.}
\label{fig:kademlia_lookup}
-\end{figure}
-
-\begin{figure}
-\centering
-\includegraphics[width=12cm, height=7cm]{structured_overlay_new.eps}
-\caption{Principal idea of tightly structured overlays.}
-\label{fig:structured_hashing}
\end{figure}

Currently, there are only three higher level abstractions which tightly
structured overlays provide
@@ -395,7 +394,7 @@
\item \texttt{remove(key)}: remove a data item with a given key.
\end{itemize}

-DHT's \emph{interface} is generic; values can be any size and type (e.g.,
content hash over a file or IP address). In the
+DHT's \emph{interface} is generic; values can be any size and type (e.g.,
content hash over a file). In the
DHT abstraction, the overlay itself stores the data items. Figure
\ref{fig:Structured_lookup_using_DHT_model} shows the DHT abstraction
of the tightly structured overlay.

@@ -412,15 +411,14 @@

The key difference between the DHT and the DOLR abstraction is that in the
DOLR abstraction the overlay maintains only the \emph{pointers} to the data.
Also, the DOLR abstraction routes overlay's messages to a nearest available
peer, hosting a specific data item. This form of locality
-is not supported by DHT. DOLR's interface is similar to the DHT's interface,
i.e., values can be any size and type
-(e.g., content hash over a file or IP address).
+is not supported by DHT. DOLR's interface is similar to the DHT's interface,
i.e., values can be any size and type.

Third, tightly structured overlay can be used for scalable group multicast or
anycast operations (CAST) (see e.g., \cite{zhuang01bayeux}).
The basic operations include:

\begin{itemize}
-\item \texttt{join(groupIdentifier)}: join to a group with a given group
identifer.
-\item \texttt{leave(groupIdentifier)}: leave a group with a given group
identifier.
+\item \texttt{join(groupIdentifier)}: join group with a given group identifer.
+\item \texttt{leave(groupIdentifier)}: leave group with a given group
identifier.
\item \texttt{multicast(message, groupIdentifier)}: multicast a message to a
group with a given group identifier.
\item \texttt{anycast(message, groupIdentifier)}: anycast a message to a group
with a given group identifier.
\end{itemize}
@@ -446,8 +444,7 @@
\label{fig:Strucutred_lookup_using_DOLR_model}
\end{figure}

-
-In tightly structured system, messages are routed across the overlay towards
peers, whose
+In tightly structured systems, messages are routed across the overlay towards
peers, whose
peer identifier is gradually ''closer'' to the key's identifier
in the identifier space. The distance can be measured by numerical
difference between identifiers (e.g., Chord \cite{stoica01chord}), number of
@@ -463,7 +460,7 @@
XOR-based metric doesn't need stabilization (like in Chord
\cite{stoica01chord}) and backup links
(like in Pastry \cite{rowston01pastry}) \cite{balakrishanarticle03lookupp2p}.
However, in all above schemes each hop in the overlay shortens the distance
between
-current peer working with the data lookup and the key which was looked up in
the identifier space.
+current peer working with the data lookup and the key which was looked up in
the identifier space.

Skip Graphs \cite{AspnesS2003} and SWAN \cite{bonsma02swan} employ a
identifier space
in which queries are routed to \emph{keys}. In these systems
@@ -496,9 +493,8 @@
Domain Name System (DNS) \cite{rfc1101} is a widely used RRS system in the
Internet.}. They present
two requirements about the nature of reference resolution. First, there should
be a general-purpose
and application-indepedent substrate for reference resolution. Second, the
references themselves
-should be unstructured and semantic-free. Authors emphasize that tightly
structured systems (specifically
-DHT-based) provide an elegant platform for RRS. In this context, we define
unstructured reference
-as a reference that it doesn't expose the target in any way and semantic-free
reference as a reference
+should be unstructured and semantic-free. In this text, we define unstructured
reference
+as a reference that doesn't expose the target in any way and semantic-free
reference as a reference
that there are no directives in the reference itself which would expose how
the reference should be processed.

@@ -509,12 +505,12 @@
important than any other in the Peer-to-Peer network. Fault tolerance
\emph{may}
be an area, in which approaches have similar properties (e.g., no single point
of failure) \cite{milojicic02peertopeer}.
Fault tolerance properties of both approaches are currently only initial
calculations, or
-experimented in simulation environments. In real-life, however, measuring
fault tolerance is a much more
+experimented in simulation environments. In real-life, however, measuring
fault tolerance is much more
challenging task and requires more research to get reliable answers.

-The most important difference between approaches is performance and
scalability properties \cite{balakrishanarticle03lookupp2p}.
-Generally tightly structured systems can perform all internal operations in a
poly-logarithmic time
-while the performance of loosely structured systems is not always even linear.
+The most important differences between approaches are the performance and
scalability properties.
+Generally tightly structured systems can perform all internal operations in
poly--logarithmic time
+while the performance of loosely structured systems is not always even linear
\cite{balakrishanarticle03lookupp2p}.
Moreover, loosely structured systems scale to millions of peers,
whereas tightly structured systems are able to cope with billions of
concurrent
peers \cite{osokine02distnetworks}, \cite{kubiatowicz00oceanstore}. However,
it is unknown
@@ -621,14 +617,13 @@
the properties of different Peer-to-Peer systems. However, we dropped
out fault tolerance and load balancing properties, since they are hard to
measure
in face of real life requirements. Additionally, however, we decided to include
-the number of \emph{real} network connections for each peer in the overlay.
-
-Here, we describe the listed properties of Peer-to-Peer algorithms:
+the number of \emph{real} network connections for each peer in the overlay.
Next,
+we describe the listed properties of Peer-to-Peer algorithms:

\begin{itemize}
\item \textbf{Lookup}: the number of messages required when a data lookup is
performed.
\item \textbf{Space}: the number of other peers which peer knows about
(neighbors).
-\item \textbf{Insert/delete}: the number of messages required when a peer
joins or leaves the network.
+\item \textbf{Insert/delete}: the number of network messages required when a
peer joins or leaves the system.
\item \textbf{Number of network connections}: the number of concurrent
network connections required to maintain correct neighbor information.
\end{itemize}

@@ -834,18 +829,18 @@
open problems to be solved. Also, many techniques developed for traditional
distributed
systems may no longer apply with Peer-to-Peer systems, e.g., load balancing
techiques \cite{byers03dhtbalancing}.

-Different problem apply to both the loosely structured and the tightly
structured approach have their own specific problems.
+Different problems apply to both the loosely structured and the tightly
structured approach have their own specific problems.
Since the introduction of Gnutella \cite{gnutellaurl}, the main concern has
been the scalability problem of loosely structured
systems. However, the scalability problem of the loosely structured is often
misunderstood;
\emph{the network overlay} of loosely structured systems is scalable, but the
\emph{data lookup model} is not as
the data lookup process creates lot of extra network traffic (e.g.,
\cite{yang02improvingsearch}).

-In tightly structured system the main concern is to make overlay's data lookup
process
-more fault tolerant against hostile attacks. Other key problems in tightly
structured
+In tightly structured systems the main concern is to make overlay's data
lookup process
+more fault tolerant against hostile attacks (e.g.,
\cite{castro02securerouting}). Other key problems in tightly structured
systems are the lack of keyword searches \cite{harren02complex,
ansaryefficientbroadcast03}, support for heterogeneous peers
\cite{rowston03controlloingreliability} and load balancing
\cite{balakrishanarticle03lookupp2p, byers03dhtbalancing}.

-\section{Security problems in Peer-to-Peer}
+\section{Security problems}

In this section we describe security problems related to Peer-to-Peer domain.
First, we discuss attacks
and lack of trust in Peer-to-Peer systems. Then, we describe anonymity, access
control, hostile entities
@@ -855,21 +850,20 @@

As stated in \cite{naor03simpledht}, an important aspect is that when it comes
to different attack models in
any Peer-to-Peer system, there should be a clear distinction between attacks
on the
-algorithms assuming the construction of the overlay is correct, and attacks on
the construction itself. Clearly, Sybil
-and Spam attacks belong to the first category, and the rest of the attacks to
the latter category.
+algorithms assuming the construction of the overlay is correct, and attacks on
the construction itself.

There are five known attack models against Peer-to-Peer systems: the Sybil
attack \cite{douceur02sybil},
-the Fail-stop attack, the Spam attack \cite{naor03simpledht}, the Byzantine
attack \cite{357176} and \cite{296824}, and
+the Fail-stop attack, the Spam attack \cite{naor03simpledht}, the Byzantine
attack \cite{357176, 296824}, and
the Distributed Denial of Service attack.

In the Sybil attack model \cite{douceur02sybil}, a hostile entity presents
multiple
entities, i.e., when a peer communicates with a subset of other participating
entities to perform a operation, a peer communicates
-only with the same hostile entity. Therefore, one hostile entity can control a
large fraction of Peer-to-Peer system while
+only with the same hostile entity. Hostile entity can control a large fraction
of Peer-to-Peer system while
repressing the redundancy of the system. Authors argue in
\cite{douceur02sybil} that without a centralized authority, Sybil attacks are
always possible in a Peer-to-Peer
-system except under extreme and unrealistic assumptions of resource parity and
coordination among entities. According to \cite{douceur02sybil}, u
-nrealistic assumptions include: all entities should be nearly homogeneous, all
identities can be validated simultaneously by all
+system except under extreme and unrealistic assumptions of resource parity and
coordination among entities. Unrealistic assumptions include: all entities
+should be nearly homogeneous, all identities can be validated simultaneously
by all
entities across the system and when accepting identities that are not directly
validated, the required number of certificates exceeds
-the number of systemwide failures. Castro et al. \cite{castro02securerouting}
suggest the use of cryptographic content hashes in the
+the number of systemwide failures \cite{douceur02sybil}. Castro et al.
\cite{castro02securerouting} suggest the use of cryptographic content hashes in
the
creation process of peer identifier against the Sybil attack. According to
authors, in this technique the IP address of a peer can be verified by the
other peer.
They call this method as a one form of \emph{self-certifying data}.

@@ -880,7 +874,7 @@
The Byzantine model can be seen as more severe than Fail-stop model as there
are no restrictions over the behavior of faulty peers, e.g., the cooperation
between multiple \emph{malicious} faulty peers is possible \cite{357176}. A
practical solution for the Byzantine failures have been
proposed by Castro et al. \cite{296824}. Authors use in their work replication
algorithm to tolerate Byzantine faults and cryptographic
-certificate techniques to prevent spoofing and replays and to detect corrupted
messages.
+certificate techniques to prevent spoofing and replays to detect corrupted
messages.

The Spam generating attack \cite{naor03simpledht} is an another known attack
model against Peer-to-Peer system. In the Spam
attack, a hostile or faulty peer may produce false information of the data, or
refuses to (or is not able to) reply to requests.
@@ -1153,7 +1147,7 @@

-\section{Performance and usability problems in Peer-to-Peer}
+\section{Performance and usability problems}

In this section, we discuss performance and usability issues regarding
Peer-to-Peer systems. We start
by describing techniques to improve data lookups in Peer-to-Peer systems.
Then, we focus on web-like
@@ -1457,7 +1451,7 @@
\normalsize

-\section{Miscellaneous problems in Peer-to-Peer}
+\section{Miscellaneous problems}

In this section we discuss miscellaneous problems in Peer-to-Peer systems.

@@ -1681,7 +1675,7 @@
content hash function\footnote{SHA-1 is
considered as a collision free hash function. Therefore, it is very unlikely
that two different Storm data blocks
would have same identifier.} \cite{fips-sha-1} is used
-for creating location-independent, globally unique identifiers for blocks.
Because of SHA-1
+for creating semantic-free, globally unique identifiers for blocks. Because of
SHA-1
content hash, all identifiers are directly the data verifiers as well. The
uniquess of blocks creates
a basis for implementing xanalogical storage model in the Fenfire system.
Storm blocks have much in common with regular files as they
both contain the data. The main difference is that Storm blocks are
\emph{immutable} since any



reply via email to

 [Prev in Thread] Current Thread [Next in Thread]