[Top][All Lists]
[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 04:16:53 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 03/03/26 04:16:53
Modified files:
Documentation/misc/hemppah-progradu: masterthesis.tex
Log message:
Double verified the comments
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.191&tr2=1.192&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.191
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.192
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.191 Tue Mar
25 11:22:34 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Wed Mar 26
04:16:53 2003
@@ -256,10 +256,10 @@
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
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 systems
have adopted this method to improve the data lookup model of loosely structured
+degree peers. Some of the most recent loosely structured Peer-to-Peer
protocols have adopted this method to improve the data lookup model of loosely
structured
systems \cite{gnutella2url, fasttrackurl}. Both protocols use high degree
peers to optimize the data lookup model of the
-system. Shareaza \cite{shareazaurl} uses the Gnutella2 protocol
\cite{gnutella2url} in data lookups, Morpheus \cite{morpheusurl}
-and KaZaa \cite{kazaaurl} use the FastTrack protocol \cite{fasttrackurl}.
+system. Shareaza \cite{shareazaurl} uses the Gnutella2-based flooding protocol
\cite{gnutella2url} in data lookups, Morpheus \cite{morpheusurl}
+and KaZaa \cite{kazaaurl} use the FastTrack-based flooding protocol
\cite{fasttrackurl}.
It is not clear whether the power-law method is scalable or not,
as the majority of the query requests are sent only to the high degree peers
while making
these peers to bear the load of the entire system.
@@ -323,7 +323,7 @@
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., \cite{fips-sha-1}) over the contents
of a data item.
+using a cryptographic content hash (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}
@@ -340,7 +340,41 @@
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
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.
+table represent peer's neighbors in the overlay network.
+
+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.
+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.
+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.
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=6cm]{structured_query.eps}
+\caption{Chord's simplified data lookup process on top of tightly structured
overlay.}
+\label{fig:structured_query}
+\end{figure}
+
+Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and
Tapestry
+\cite{zhao01tapestry} uses balanced $k$-trees to implement the overlay. 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
+efficiency. Koorde \cite{kaashoek03koorde}, a recent modification of Chord,
uses de Bruijn graphs
+\cite{debruijn46graph} to maintain local routing tables. Koorde
\cite{kaashoek03koorde} requires
+each peer to have only about two links to other peers to provide $O(\log{n})$
performance.
+
+
+\begin{figure}
+\centering
+\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
@@ -349,16 +383,6 @@
\label{fig:structured_hashing}
\end{figure}
-Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed four
requirements
-for tightly structured overlays\footnote{Authors use the term 'DHT' in their
text, but in this context
-it doesn't matter as they list \emph{general} properties of tightly structured
overlays.} which have to be addressed in order
-to perform efficient data lookups in tightly structured overlays.
-First, mapping of keys to peers must be done in a load-balanced
-way. Second, the overlay must be able to forward a data lookup for a
-specific key to an appropriate peer. Third, overlay must
-support efficient distance function. Finally, routing tables for each peer
-must be constructed and maintained adaptively.
-
Currently, there are only three higher level abstractions which tightly
structured overlays provide
\cite{zhao03api}. Each of these abstractions represent a storage layer in the
overlay, but
have semantical differences in the \emph{usage} of the overlay.
@@ -423,42 +447,8 @@
\label{fig:Strucutred_lookup_using_DOLR_model}
\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.
-For example, Chord \cite{stoica01chord}, Skip graphs \cite{AspnesS2003} and
SkipNet \cite{harvey03skipnet2} maintain a
-distributed data structure which resembles Skip lists \cite{78977}.
-In figure \ref{fig:structured_query}, we present an overview of Chord's 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.
-
-\begin{figure}
-\centering
-\includegraphics[width=10cm, height=6cm]{structured_query.eps}
-\caption{Chord's simplified data lookup process on top of tightly structured
overlay.}
-\label{fig:structured_query}
-\end{figure}
-
-Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and
Tapestry
-\cite{zhao01tapestry} uses balanced $k$-trees to implement the overlay. 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
-efficiency. Koorde \cite{kaashoek03koorde}, a recent modification of Chord,
uses de Bruijn graphs
-\cite{debruijn46graph} to maintain local routing tables. Koorde
\cite{kaashoek03koorde} requires
-each peer to have only about two links to other peers to provide $O(\log{n})$
performance.
-
-\begin{figure}
-\centering
-\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}
-
-
-All messages are routed across the overlay towards peers, whose
+In tightly structured system, 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
@@ -492,6 +482,16 @@
overlays, i.e., $O(\log{n})$ space required for maintaining information about
other peers in
the system and $O(\log{n})$ data lookup efficiency.
+Balakrishnan et al. \cite{balakrishanarticle03lookupp2p} have listed four
requirements
+for tightly structured overlays\footnote{Authors use the term 'DHT' in their
text, but in this context
+it doesn't matter as they list \emph{general} properties of tightly structured
overlays.} which have to be addressed in order
+to perform efficient data lookups in tightly structured overlays.
+First, mapping of keys to peers must be done in a load-balanced
+way. Second, the overlay must be able to forward a data lookup for a
+specific key to an appropriate peer. Third, overlay must
+support efficient distance function. Finally, routing tables for each peer
+must be constructed and maintained adaptively.
+
Additionally, authors argue in \cite{balakrishnan03semanticfree} that tightly
structured systems
are suitable for next generation Reference Resolutions Services (RRS)\footnote{
Domain Name System (DNS) \cite{rfc1101} is a widely used RRS system in the
Internet.}. They present
@@ -522,12 +522,13 @@
whether all proposed algorithms can preserve logarithmic efficiency and
scalability properties
in real-life applications or not; several tightly structured systems
assume that participating peers are homogeneous, and the rate of join or leave
operation is low \cite{gurmeet03symphony,
-libennowell01observations}.
+libennowell01observations, rowston03controlloingreliability}.
To end user, the biggest difference between these systems is how data lookups
are performed. Loosely
structured systems provide more rich and user friendly way of searching data
than tightly structured systems
-as they have a support for keyword searches. Tightly structured
-systems support only exact key lookups since each data item is identified by
globally unique keys.
+as they have a support for keyword searches \cite{yang02efficientsearch,
lv02searchreplication}. Tightly structured
+systems support only exact key lookups since each data item is identified by
globally unique keys \cite{balakrishanarticle03lookupp2p,
+harren02complex, ansaryefficientbroadcast03}.
Table \ref{table_comparison_approach} lists the key differences between the
loosely structured
approach and the tightly structured approach.
@@ -582,17 +583,13 @@
\parbox{100pt}{Yes}
\\ \hline
-\parbox{90pt}{Construction and maintenance of the overlay} &
-\parbox{100pt}{Uncontrolled and ad hoc} &
-\parbox{100pt}{Controlled and structured}
-\\ \hline
-\parbox{90pt}{Scalable query lookup model} &
+\parbox{90pt}{Scalable data lookup model} &
\parbox{100pt}{No} &
\parbox{100pt}{Yes}
\\ \hline
-\parbox{90pt}{Data item mapped into the overlay} &
+\parbox{90pt}{Data items mapped into the overlay} &
\parbox{100pt}{No} &
\parbox{100pt}{Yes}
\\ \hline
@@ -829,8 +826,8 @@
In this chapter, we discuss open problems in Peer-to-Peer research.
Note that the open problems list considered here is not meant
to be an exhaustive survey of \emph{all} open problems in Peer-to-Peer domain;
-we focus our attention to some security, scalability, usability and
performance related
-issues only.
+we focus our attention to some issues related security, scalability, usability
and performance.
+
\section{Overview}
@@ -846,8 +843,8 @@
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
-systems are the lack of keyword searches, support for heterogeneous peers and
load balancing
-\cite{balakrishanarticle03lookupp2p}.
+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}
@@ -867,29 +864,28 @@
the Distributed Denial of Service attack.
In the Sybil attack model \cite{douceur02sybil}, a hostile entity presents
multiple
-entities, i.e., when a peer selects a subset of entities to perform a
operation, a peer can select the same
-hostile entity multiple times. Therefore, one hostile entity can control a
large fraction of Peer-to-Peer system thereby
-repressing the redundancy of the system. Unfortunately, currently there are no
realizable techniques for against the Sybil
-attack: 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 \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.
+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
+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
+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
+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}.
In the Fail-stop attack model, cited in \cite{naor03simpledht}, a faulty peer
is deleted from the Peer-to-Peer system. Thus,
a specific data item can be lost from the system temporaraly (or permanently).
The reason for the faultiness of a peer can be a
-software failure or a hostile attack. The Byzantine attack model \cite{357176}
is closely related to Fail-stop model. The Byzantine model can
-be seen as more severe than Fail-stop model as there are no restrictions over
the behavior of faulty peers; for instance,
-the cooperation between multiple malicious faulty peers is possible
\cite{357176}. A practical solution for the Byzantine failures have been
-proposed by Castro et al. \cite{296824}.
+software failure or a hostile attack. The Byzantine attack model \cite{357176}
is closely related to Fail-stop model. In the Byzantine attack model
+$3f + 1$ is the minimum number of peers that allow system to provide the
safety and liveness properties when up to $f$ peers are faulty \cite{357176}.
+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.
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.
-Possible solution against this attack is that peer should not trust a single
entity. Instead, a peer should get
-information from multiple entities and trust on the majority's opinion. This
method requires more messages to be
-sent to the network while increasing the system load. However, if the Spam
attack is combined with the Sybil attack, obviously
-the previously mentioned solution doesn't work. Naor et al.
\cite{naor03simpledht} have proposed a partial solution against Spam attack
-in a \emph{faulty} peer environment (not hostile).
+Naor et al. \cite{naor03simpledht} have proposed a partial solution against
Spam attack in a \emph{faulty} peer environment (not hostile).
Overloading of targeted peers is a form of Distributed Denial of Service
attack (DDoS) (see, e.g., \cite{372148}). For instance,
a hostile entity can attempt to burden targeted peers with garbage network
packets. As a consequence, peers may act incorrectly or
@@ -905,7 +901,7 @@
According to \cite{aberer01trust}, mutual trust ''...allows agents to
cooperate in a game-theoretic situation that corresponds
to the repeated prisoners dilemma and leads in the long term to an increased
aggregated utility for the participating agents''.
They define \emph{trust management} as a mechanism that allows to establish
mutual trust. Furthermore, \emph{reputation} is a measure
-that is derived from knowledge on interactions in the past
\cite{aberer01trust} In this subsection, we discuss mechanisms to maintain
+that is derived from knowledge on interactions in the past
\cite{aberer01trust}. In this subsection, we discuss mechanisms to maintain
trust in Peer-to-Peer systems.
Trust in Peer-to-Peer systems is based on \emph{reputation}. Little research
has been done on reputation models in Peer-to-Peer
@@ -958,7 +954,7 @@
distributed systems which are able to provide some level of anonymity (e.g.,
\cite{mneturl}).
Even if many existing Peer-to-Peer systems are able to provide some of the
types of anonymity, there is no
-such a system which is able to provide all types of anonymity. Specifically,
the conflicts
+such a system which is able to provide complete anonymity. Specifically, the
conflicts
between anonymity and other properties of Peer-to-Peer system require more
research work.
@@ -978,7 +974,8 @@
\subsection{Hostile entities}
-One serious problem in Peer-to-Peer systems is the inability to identify
hostile entities.
+One serious problem in Peer-to-Peer systems is the inability to distinguish
hostile entities from regular entities
+trustworthy.
One possible solution is to use a self-monitoring system, such as SOMO
\cite{zhang03somo}, in which a self-monitoring overlay
constantly analyses the Peer-to-Peer overlay. Self-monitoring overlay is built
on top of Peer-to-Peer overlay. Authors in
\cite{sit02securitycons} suggest the use of system invariants. They emphasize
that system invariants should be veriable, and if
@@ -995,8 +992,8 @@
\subsection{Secure query routing}
-By secure routing, we mean that a Peer-to-Peer system is able to deliver a
network message
-thoughout the overlay to a correct destination.
+Secure query routing is essential to any Peer-to-Peer system. By secure
routing in this context, we mean that a Peer-to-Peer system
+is able to deliver a network message thoughout the overlay to a correct
destination efficiently.
Aspnes et al. in \cite{aspnes02faultrouting} and Kaashoek et al. in
\cite{kaashoek03koorde} formally
prove the lower and upper bounds for the space requirements of locating a
specific data item reliable in a
@@ -1638,20 +1635,18 @@
\section{Xanalogical storage model}
Xanalogical storage model \cite{nelson99xanalogicalneeded} is a different kind
of model for
-presenting data and relationships between data. \emph{Enfilade},
-can be considered as a mutable ''virtual file'' (or part of one), which is a
list
+presenting data and relationships between data, e.g., while in the World Wide
Web links are
+between \emph{documents}, in xanalogical storage model links are between
individual
+\emph{characters}. \emph{Enfilade},can be considered as a mutable ''virtual
file'' (or part of one), which is a list
of fluid media content. Fluid media is the smallest units of data in
xanalogical storage
model. \emph{Transclusion} is an inclusion in
enfilade of contents already used in another enfilade. With the transclusion,
a system
-implementing xanalogical storage model is able to show all data content that
share the same
-fluid media with current data content (e.g., all documents in a system
containing a specific
-document's text).
-
-While in the World Wide Web links are
-between \emph{documents}, in xanalogical storage model links are between
individual
-\emph{characters}. Figure \ref{fig:xanalogical_model}
+implementing xanalogical storage model is able to show \emph{all} data content
that share the same
+fluid media with current data content (e.g., all documents in a system
containing document's text).
+Figure \ref{fig:xanalogical_model}
illustrates xanalogical storage model with documents, text and characters.
-Links between data are external
+
+In xanalogical storage model, links between data are external
and bidirectional. A link is shown between any two data contents
containing a specific \emph{fluid media unit} (e.g., a character) that the
link connects.
Each fluid media unit in xanalogical storage model has a
@@ -1691,7 +1686,7 @@
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
-change to the byte sequence would change block's hash value (globally unique
identifier).
+change to the byte sequence would change block's hash value (i.e., globally
unique identifier).
Support for immutable data is built on the immutable abstraction. Storm uses
\emph{pointers} and \emph{diffs} for dealing with this kind of data. Using
diffs
@@ -1700,16 +1695,16 @@
More information about diffs can be found from \cite{fallenstein03storm}.
\emph{Pointer} \cite{benja02urn5, fallenstein03storm} is a semantic-free
updatable reference to
-Storm data block, i.e., Storm scroll block. Pointer is unique reference to the
data and it is usually
-represented as a random string. Storm pointers are rather a \emph{concept} of
data (e.g., ''The first page of the most recent
+Storm data block. Pointer is a unique reference to the data and it is usually
+represented as a random string. Storm pointers are rather a \emph{concept} of
data (e.g., ''The front page of the most recent
version of New York Times newspaper'') whereas scroll blocks \emph{contain}
the data
(''New York Times newspaper, 10.10.2002, version 1.0'').
-Figure \ref{fig:storm_model} illustrates simplified Storm storage model with
pointers.
+Figure \ref{fig:storm_model} illustrates Storm storage model with pointers.
-Each pointer is associated with a collection of \emph{pointer blocks}.
+Each pointer is \emph{linked} to a collection of \emph{pointer blocks}.
Pointers can be created by a user, before the creation of scroll blocks.
Pointer blocks
-are created automatically by Storm when a scroll block is associated with a
pointer
-(e.g., by a user when creating a concept of ''The first page of the most
recent
+are created automatically by Storm when a scroll block is created and
associated with a pointer
+(e.g., a user creates a scroll block associated with the concept ''The front
page of the most recent
version of New York Times newspaper''). Pointer block has always a single
target (i.e., a scroll block)
for the pointer, saying that pointer $P$ targets block $B$. In addition to
this, pointer block
may contain a list of zero or more obsoleted pointer blocks: when a new
version of pointer
@@ -1741,10 +1736,11 @@
\chapter{Evaluation of Peer-to-Peer for Fenfire}
In this chapter we evaluate Fenfire in Peer-to-Peer environment.
-We start by giving a problem overview. Then, we define Fenfire's special needs
and evaluate existing
+We start by giving a problem overview. Then, we define special needs and
evaluate existing
Peer-to-Peer approaches in light of these requirements. After that, we propose
a combination
of Peer-to-Peer techniques reviewed in this thesis to be used with Fenfire and
present simple methods to perform data
-lookups (data lookups are required by Alph module). In the end of this
chapter, we discuss possible problems of using Fenfire
+lookups. Data lookups are required by Alph module which implements the
xanalogical storage model in Fenfire.
+In the end of this chapter, we discuss possible problems of using Fenfire
in Peer-to-Peer environment.
@@ -1765,18 +1761,17 @@
participants responded whether Peer-to-Peer systems are suitable for hypermedia
publishing or not.
-
In Peer-to-Peer environment, our objectives are simple but yet hard to fulfill.
First, as discussed in chapter 4, xanalogical document is a ''virtual
file'', in which parts of the document are fetched from a
\emph{global} data repository\footnote{Global repository is not a requirement.
Locally constructed xanalogical
-documents are feasible and they can be assembled without any global data.}.
Thus, system implementing xanalogical storage model \emph{must}
+documents are feasible and they can be assembled without global data
repository.}. Thus, system implementing xanalogical storage model \emph{must}
support global data lookups order to assemble the ''virtual file'' from
fragments of data.
-Specifically, our task is to locate and fetch (i.e., obtain) \emph{all} Storm
scroll blocks, associated to a specific ''virtual
-file'' from the Peer-to-Peer once the construction of ''virtual'' file
-is resolved (i.e., we know what scroll blocks are required to assemble the
''virtual file''). Also, in addition to the
-\emph{direct} scroll block obtaining using globally unique identifier of Storm
scroll block,
-we also must support the \emph{indirect} obtaining of Storm scroll block using
the pointers.
+Specifically, our task is to locate and fetch (i.e., obtain) \emph{all} Storm
blocks\footnote{These blocks are called \emph{scroll} blocks.},
+associated to a specific ''virtual file'' from the Peer-to-Peer once the
construction of ''virtual'' file
+is resolved (i.e., we know what blocks are required to assemble the ''virtual
file''). Also, in addition to the
+\emph{direct} block obtaining using globally unique identifier of Storm block,
+we also must support the \emph{indirect} obtaining of Storm block using the
pointer mechanism.
Second, we want that users' operations in Fenfire
are location transparent: data lookups have to be efficient, since
constructing
one ''virtual file'' may need obtaining several Storm blocks, which are
distributed
@@ -1858,7 +1853,7 @@
hot spots in the system \cite{ratnasamy02routing}. Current client-server
implementation of Fenfire uses
standard single source downloads (HTTP) and SHA-1 \cite{fips-sha-1}
cryptographic content
hash for verifying the integrity of data by recomputing the content hash
-for block. In face of multisource downloads, Fenfire must support
+for Storm block. In face of multisource downloads, Fenfire must support
tree-based hashes\footnote{With multisource downloads, tree-based hash
functions can be used
to verify fixed length segments of data. If hash value of data segment is
incorrect,
we need only to fetch \emph{segment} of data (instead of whole data) from
@@ -1874,12 +1869,7 @@
severe problems with load balancing in a highly heterogeneous environment
\cite{rao03loadbalancing}. The problem is caused by peers
which may not be able to store relatively large blocks, assigned randomly by
the mapping function of the overlay.
-In our method, each peer maintains the following local data structures for
local operations: a data structure for listing all
-key-value pairs which are assigned by the overlay; a data structure for
listing all key-value pairs which are assigned by the overlay
-in the chronological order (the most recent block is topmost). We use Storm
blocks' identifiers and pointers
-as \emph{keys} of the overlay.
-
-We assume that we have resolved the construction of the ''virtual file''
before locating any Storm blocks, i.e.,
+For simplicity, we assume that we have resolved the construction of the
''virtual file'' before locating any Storm blocks, i.e.,
when assembling the ''virtual file'' we know all the Storm blocks, which are
required to complete the ''virtual file''.
Also, we don't respond to the security issues related to Peer-to-Peer systems,
since there is no working solution
available yet. Thus, we either assume that Fenfire has a reliable technique
for identifying individual entities, or
@@ -1888,33 +1878,33 @@
\begin{itemize}
-\item Data lookup with a given identifier of Storm scroll block.
+\item Data lookup with a given identifier of Storm block.
\begin{enumerate}
-\item Submit the data lookup using scroll block's identifier.
-\item Each peer forwards the data lookup to a closer peer which hosts the
given scroll block identifier instructed by the overlay.
+\item Submit the data lookup using block's identifier.
+\item Each peer forwards the data lookup to a closer peer which hosts the
given block identifier instructed by the overlay.
\item The pointer peer returns value (e.g., the IP address of provider peer)
to the query originator throughout the overlay.
-\item The query originator requests the provider peer to return the scroll
block.
+\item The query originator requests the provider peer to return the block.
\end{enumerate}
\end{itemize}
\begin{itemize}
-\item Data lookup with a given pointer returning most recent scroll block.
+\item Data lookup with a given pointer returning most recent block.
\begin{enumerate}
\item The query originator locally computes a hash over given pointer.
\item Each peer forwards the data lookup to a closer peer which hosts the
given hash of pointer instructed by the overlay.
\item The pointer peer returns most recent pointer block's key-value pair
(e.g., the IP address of provider peer) to the query originator, using pointer
block's own indexing schemes throughout the overlay.
-\item The query originator requests the provider peer to return the scroll
block.
+\item The query originator requests the provider peer to return the block.
\end{enumerate}
\end{itemize}
\begin{itemize}
-\item Data lookup with a given pointer returning scroll block(s) for a given
date or time range.
+\item Data lookup with a given pointer returning block(s) for a given date or
time range.
\begin{enumerate}
\item The query originator locally computes a hash over given pointer.
\item Each peer forwards the data lookup to a closer peer which hosts the
given hash of pointer instructed by the overlay.
\item Pointer peer returns pointer block's key-value pair(s) (e.g., the IP
address of provider peer) to the query originator, using pointer block's own
indexing schemes throughout the overlay.
-\item The query originator requests the provider peer to return the scroll
block.
+\item The query originator requests the provider peer to return the block.
\end{enumerate}
\end{itemize}
@@ -1937,7 +1927,7 @@
security technologies. For the Fenfire system, one security related problem
occurs when a user wants to
perform a global data lookup with a given pointer; how the user is able to
verify
the correctness of the search results, i.e., how she or he knows which one is
the
-correct Storm scroll block ? Another problem related to the Fenfire's
+correct Storm block ? Another problem related to the Fenfire's
security is that if a user downloads data from the network to local computer
and after a network disconnection, user wants to verify \emph{off line} the
authenticity of data. Finally, if a data lookup is performed by a user, but
there is no reply
@@ -1978,8 +1968,8 @@
Our future work includes a support for searching transclusions and xanalogical
links in Peer-to-Peer environment. Preliminary analysis have shown
-that these questions are rather different than locating scroll or pointer
-blocks from Peer-to-Peer environment. Techniques used in distributed
+that these questions are rather different than locating Storm blocks
+from Peer-to-Peer environment. Techniques used in distributed
database systems may prove to be useful. Some fundamental results
regarding Peer-to-Peer and database systems have already been
presented in \cite{gribble01p2pdatabase}.
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., (continued)
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/25
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/26
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/27
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/27
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert..., Hermanni Hyytiälä, 2003/03/27