[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/06 04:16:41

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.119&tr2=1.120&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.119 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.120
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.119      Wed Mar 
 5 10:01:54 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Thu Mar  6 
04:16:41 2003
@@ -888,7 +888,7 @@
 approach. However, people often misunderstand the scalability problem of 
loosely structured 
 approach; \emph{network} of loosely structured systems is scalable, but the 
\emph{query model} is not. 
 The main concern of tightly structured system is to make overlay's data lookup 
-routing more flexible againts hostile attacks. Another key problems in tightly 
structured 
+routing more flexible againts hostile attacks. Another key problem in tightly 
structured 
 approach are the lack of keyword searches and support for heterogeneous peers.
 
 To make Peer-to-Peer systems even more popular (e.g., in industry), 
Peer-to-Peer domain
@@ -927,9 +927,10 @@
 Spam generating attack is another known attack model againts Peer-to-Peer 
system. In Spam
 attack, hostile or faulty peer may produce false information of the data. 
Possible solution againts this attack
 is that peer should not trust to single entity. Instead peer should get 
information from multiple entities and trust 
-on majority's opinion. However, Spam attack is combined with Sybil attack, 
obviously previously mentioned solution
-won't work. Again, more research is required to solve this attack model 
reliability. Naor et al. \cite{naor03simpledht}
- has proposed a partial solution againts Spam attack with \emph{faulty} peers 
(not hostile).
+on majority's opinion. This methods requires more messages to be sent to 
network increasing the load of system. 
+However, if Spam attack is combined with Sybil attack, obviously previously 
mentioned solution doesn't work. 
+Again, more research is required to solve this attack model reliability. Naor 
et al. \cite{naor03simpledht} has 
+proposed a partial solution againts Spam attack with \emph{faulty} peers (not 
hostile).
 
 Traditional overload of targeted peers is best known form of distrubuted 
Denial of Service attack (DDoS). For example, 
 hostile entity can attempt to burden targetted peers with garbage packets. As 
a implication, peers may act
@@ -1723,8 +1724,11 @@
 
 Storm (for \emph{STORage Module}) is a software module, which is used in 
Fenfire for
 implementing basic data storage operations. Storm stores all data as 
\emph{scroll blocks}, which
-are immutable byte sequences. SHA-1 cryptographic content hash 
\cite{fips-sha-1} is used
-for creating locatiotion-independent, globally unique identifiers for blocks. 
Storm
+are immutable byte sequences. SHA-1\footnote{SHA-1 is considered a collision 
free 
+hash function. Therefore, it is very unlikely that two different Storm scroll 
blocks 
+would have same identifier.} cryptographic content hash \cite{fips-sha-1} is 
used
+for creating locatiotion-independent, globally unique identifiers for blocks. 
Additionally,
+SHA-1 \cite{fips-sha-1} is used for verifying the integrity of scroll blocks. 
Storm
 blocks have much in common with regular files, except Storm blocks are 
\emph{immutable} as
 any change to the byte sequence would the change block's hash value, i.e., 
unique 
 identifier. This mechanism creates a basis for implementing xanalogical model 
in our
@@ -1783,9 +1787,7 @@
 In the xanalogical storage model, each fragment of data is identified by a 
globally 
 unique identifier. In Fenfire, data fragments are scroll blocks, generated by 
Storm storage module.
 As we discussed already in chapter 4, Fenfire's Storm design 
-uses SHA-1 \footnote{SHA-1 is considered a collision free hash function. 
Therefore, it is 
-very unlikely that two different Storm scroll blocks would have same 
identifier.} 
-\cite{fips-sha-1} hash over the contents of a scroll block for creating 
globally unique 
+uses SHA-1 \cite{fips-sha-1} hash over the contents of a scroll block for 
creating globally unique 
 identifiers for each scroll block.  In our scenario, fragments of data is 
distributed 
 throughout the Peer-to-Peer overlay. Our task is to locate and fetch 
 (i.e. obtain) \emph{all} Storm scroll blocks, associated to a specific 
''virtual 
@@ -1818,16 +1820,9 @@
 participants responded whether Peer-to-Peer systems are suitable for hypermedia
 publishing or not. 
 
-In the following sections we assume that we know the structure of ''virtual 
file'' before hand, 
-i.e. when assmbling a ''virtual file'', we know all Storm scroll/pointer 
blocks, which are required
-when building the ''virtual file''. Also, we don't respond to security issues 
related to Peer-to-Peer
-systems. We assume that Fenfire has a reliable techique for identifying 
invidual entities, or
-there are no hostile entities among participating peers.
-
-
 \section{Evaluation of Peer-to-Peer approaches with regard to Fenfire}
 
-In chapter 2 we discussed main differences between loosely and tightly 
structured 
+In chapter 2, we discussed main differences between loosely and tightly 
structured 
 approaches. As stated, the most significant difference is that tighly 
structured 
 approach has logarithmical properties in all interal operations, while loosely 
 structured approach doesn't have always even linear properties. Furthermore, 
the
@@ -1849,8 +1844,8 @@
 application-independent and references itself should be \emph{unstructured} 
and 
 \emph{semantic free}. To summarize, these aspects may be the most important 
features 
 of Peer-to-Peer infrastructure with regard to Fenfire as a \emph{distributed} 
hypermedia system.
-Thus, we see the tightly structured approach the best alternative to Fenfire's
-needs.
+Thus, we see the tightly structured approach the best alternative to locate 
data in Peer-to-Peer
+environment.
 
 Once located, for \emph{fetching} Fenfire related data from the overlay, we 
can use reqular 
 TCP/IP-protocols, such as Hypertext Transfer protocol (HTTP) \cite{rfc2068}. 
However, HTTP-protocol may 
@@ -1868,7 +1863,7 @@
 other source.}, such as \cite{merkle87hashtree} and \cite{mohr02thex} for 
reliable and efficient 
 data validation.
 
-Currently, there are open issues with tightly structured systems which have to 
be
+Again, there are open issues with tightly structured systems which have to be
 addressed, as described in chapter 3. The main concerns include decreased 
performance and fault 
 tolerance when system in flux-state, non-optimal distance functions in 
identifier space, 
 proximity routing, hostile entities and flexible search 
\cite{balakrishanarticle03lookupp2p}.
@@ -1879,69 +1874,78 @@
 overlays \cite{projectirisurl}.
 
       
-\section{Analysis}
+\section{Algorithm proposals}
+
+In this section we propose yet simple but effective algorithms for obtaining 
Fenfire data from
+Peer-to-Peer environment. In the following subsections we assume that we know 
the structure of 
+''virtual file'' before hand, i.e. when assmbling a ''virtual file'', we know 
all Storm 
+scroll/pointer blocks, which are required when building the ''virtual file''. 
Also, we don't 
+respond to security issues related to Peer-to-Peer systems, since there is no 
working solution
+available yet; we either assume that Fenfire has a reliable techique for 
identifying invidual entities, or
+there are no hostile entities among participating peers.
 
-In this section we analyse the costs of locating Storm block with a given 
identifier 
-and urn-5 random string. 
+\subsection{System model}
 
-\subsection{Assumptions}
-In our analysis, we use tightly structured ovelay's DOLR method. Each peer 
hosts the data, 
-overlay maintains only the \emph{pointers} to the data. Furthermore, each peer 
maintains 
-following data structures for local operations: one data structure for listing 
all 
-key/value-pairs; one data structure for listing all key/value-pair in 
chronological order
-(the most recent block is topmost). Every key/value-pairs consists of a hash 
of urn-5 
-random string (pointer blocks) or a hash of block's content (scroll blocks) as 
a key. 
-Value is always a reference to a hosting peer (e.g. IP-address). Finally, we 
assume 
-that all local operations can be done in a constant time.
+We use DOLR model of tightly of structured approach, i.e. each participating 
peer hosts 
+the data and overlay maintains only the \emph{pointers} to the data. We 
descided to use DOLR in our
+model, since DOLR systems locate date without specifiying a storage policy 
explicity \cite{rhea03benchmarks}. 
+DHT based storage systems, such as CFS \cite{dabek01widearea} and PAST 
\cite{rowstron01storage}, have
+critical problems with load balancing in highly heterogeneous environment. 
This is caused by peers which may not able
+to store relative great amount of data with key/value pair, assigned randomly 
by mapping function of the overlay. 
+
+In our model, each peer maintains following data structures for local 
operations: data structure for listing all 
+key/value-pairs which peer maintains; data structure for listing all 
key/value-pair in 
+chronological order (the most recent block is topmost) which peer maintains. 
We use Storm blocks' identifiers
+as \emph{keys} of the overlay. Every key/value-pairs consists of either a hash 
of pointer random string 
+(pointer blocks), or a hash of block's content (scroll blocks) as a key. Value 
is always a reference to a hosting 
+peer (e.g. IP address). Finally, we assume that all local operations can be 
done in a constant time.
 
 \subsection{Algorithms}
 
 
 \begin{itemize}
-\item Data lookup with a given scroll block's identifier
+\item Data lookup with a given identifier of Storm scroll block.
 \begin{enumerate}
-\item Submit query using scroll block's identifier
-\item Repeat until hosting node is found: each peer forwards the query to a 
closer peer which hosts the given scroll block identifier 
-\item Pointer peer returns most recent pointer block's value (e.g., hosting 
peer's IP-address) to query originator 
-\item Query originator requests hosting node to return the scroll block 
+\item Submit query using scroll block's identifier.
+\item Repeat until hosting node is found: each peer forwards the query to a 
closer peer which hosts the given scroll block identifier.
+\item Pointer peer returns most recent pointer block's value (e.g., hosting 
peer's IP-address) to query originator.
+\item Query originator requests hosting node to return the scroll block.
 \end{enumerate}
 \end{itemize}
 
-Figure \ref{fig:storm_query_blockid} illustrates how scroll block is located 
-in a tightly structured overlay using DOLR method, where scroll block's
-identifier is known.
+Figure \ref{fig:storm_query_blockid} illustrates how Storm scroll block is 
located 
+in a tightly structured overlay using DOLR method, where identifier of Storm 
scroll 
+block is known.
 
 
 \begin{itemize}
-\item Data lookup with a given urn-5 random string returning most recent 
scroll block
+\item Data lookup with a given pointer random string returning most recent 
scroll block.
 \begin{enumerate}
-
-\item Query originator locally compute a hash for given urn-5 random string
-\item Repeat until hosting node is found: each peer forwards the query to a 
closer peer which hosts the given hash of urn-5
-\item Pointer peer returns most recent pointer block's key/value-pair (e.g., 
hosting peer's IP-address) to query originator, using pointer block's own 
indexing schemes 
-\item Query originator requests hosting node to return the scroll block
+\item Query originator locally compute a hash for given urn-5 random string.
+\item Repeat until hosting node is found: each peer forwards the query to a 
closer peer which hosts the given hash of pointer random string.
+\item Pointer peer returns most recent pointer block's key/value-pair (e.g., 
hosting peer's IP-address) to query originator, using pointer block's own 
indexing schemes. 
+\item Query originator requests hosting node to return the scroll block.
 \end{enumerate}
 \end{itemize}
 
 \begin{itemize}
-\item Data lookup with a given urn-5 random string returning scroll block(s) 
for a given date and time range
+\item Data lookup with a given pointer random string returning scroll block(s) 
for a given date and time range.
 \begin{enumerate}
 
-\item Query originator locally compute a hash for given urn-5 random string
-\item Repeat until hosting node is found: each peer forwards the query to a 
closer peer which hosts the given hash of urn-5
-\item Pointer peer returns pointer block's key/value-pair(s) (e.g., hosting 
peer's IP-addresses) to query originator, using pointer block's own indexing 
schemes 
-\item Query originator requests hosting node to return the scroll block
+\item Query originator locally compute a hash for given urn-5 random string.
+\item Repeat until hosting node is found: each peer forwards the query to a 
closer peer which hosts the given hash of pointer random string.
+\item Pointer peer returns pointer block's key/value-pair(s) (e.g., hosting 
peer's IP-addresses) to query originator, using pointer block's own indexing 
schemes. 
+\item Query originator requests hosting node to return the scroll block.
 \end{enumerate}
 \end{itemize}
 
-Figure \ref{fig:storm_query_urn5} illustrates how scroll block is located 
+Figure \ref{fig:storm_query_urn5} illustrates how Storm scroll block is 
located 
 in a tightly structured overlay using DOLR method, where urn-5 is known.
 
-Each of these algortihms can locate a specific scroll block in 
$\Theta(\log{n})$ time;
-$\Theta(\log{n})$ time for query routing to pointer peer and constant time for 
-locating hosting peer with a given reference link.     
-               
-
+Each of these algortihms can locate Fenfire related data in $\Theta(\log{n})$ 
time:
+$(\log{n})$ time for query routing to pointer peer and constant time for 
+locating hosting peer with a given reference link. Time required for 
transferring
+the data is not included.
 
 
 \begin{figure}