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

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/02/25 04:48:14

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

Log message:
        Algorithms

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.67 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.68
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.67       Tue Feb 
25 04:01:51 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Feb 25 
04:48:13 2003
@@ -1353,19 +1353,7 @@
 \end{figure}
 
 
-\begin{figure}
-\centering
-\includegraphics[width=11cm, height=8cm]{storm_query_blockid.eps}
-\caption{Locating owner peer for a given block ID}
-\label{fig:storm_query_blockid}
-\end{figure}
 
-\begin{figure}
-\centering
-\includegraphics[width=11cm, height=8cm]{storm_query_urn5.eps}
-\caption{Locating owner peer for a given urn-5}
-\label{fig:storm_query_urn5}
-\end{figure}
 
 
 
@@ -1661,7 +1649,7 @@
          
 \parbox{90pt}{Query traffic} &
 \parbox{100pt}{$O(n)/O(n^{2})$}  &
-\parbox{100pt}{$O(1)/O(log n)$} 
+\parbox{100pt}{$O(1)/O(\log{n})$} 
 \\ \hline
 
 \parbox{90pt}{Guaranteed data lookup} &
@@ -1792,7 +1780,90 @@
 
 -for DHTs and SWNs:
 
-Please notice: In this approach, DHT doesn't store the actual block, only the 
values for locating the data from the system
+
+      
+\section{Analysis}
+
+In this section we analyse the costs of locating Storm block with a given 
identifier 
+and urn-5 random string. 
+
+\subsection{Assumptions}
+We use tightly structured ovelay's DOLR method. Each peer hosts the data, 
+overlay maintains the \emph{pointers} of 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 scroll blocks; one data structure for
+pointer blocks. Key/value-pairs are as follows: 
+
+For scroll blocks
+
+
+\subsection{Algorithms}
+
+
+
+\begin{itemize}
+\item Data lookup with a given scroll block's identifier
+\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 
+\end{enumerate}
+\end{itemize}
+
+
+\begin{itemize}
+\item Data lookup with a given urn-5 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
+\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
+\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
+\end{enumerate}
+\end{itemize}
+
+
+
+
+       Req. 1:
+       -each node maintains a local hash-table based data structure (urn-5 
name -> most recent local block ID) for every urn-5 names
+       which node hosts. The most recent block is topmost --> we don't have to 
check all blocks and their urn-5 associations to get the most recent
+       Req. 2:
+       -all urn-5 name mappings are stored as <key, value[ ]>, where the key 
is urn-5 name's hash and value is a record containing
+       block ID and timestamp of that block. So, when we store a block in our 
system first time, we have to create a new key-value: 
+       %<hash_of_urn_5_name, [block id, block timestamp]> and route this 
mapping to node which is "closest" to a hash value. Now when we want to find 
the most 
+       recent block associated with a specific urn-5 name, we do:
+       
+               
+               
+       In this approach, we don't have to perform additional searching and 
sorting of mappings. And of course, we know that for given urn-5, only one node
+       hosts *all* the block information ("block history") for the urn-5, 
since mappings are mapped to a single node, closest to urn-5 hash value.
+       Again, this should work fine under existing DHTs (and SWTs ?).
+       
+       Some simple analysis: 
+       -there are more key-value pairs in the system for additional urn-5 --> 
block associations
+       -however, I don't think this is an issue, since data's size is small
+       -efficiency: find node which hosts urn-5 names + find node which hosts 
blocks associated with urn-5 name: logn + logn = 2logn (logarithmical)
+       
+-for FBS and others:
+       -there is no very efficient (simple) methods for finding urn-5 name 
associated with the most recent block
+       -one simple proposal is that when we visit to each node (first idea 
above), get only the most recent one and compare them (or greedy approach: 
dismiss currently 
+       most recent block as we visit to nodes, if newer block have been found)
+       
+       
+       Please notice: In this approach, DHT doesn't store the actual block, 
only the values for locating the data from the system
 
        Req. 1:
        -each node maintains a local hash-table based data structure (urn-5 
name -> most recent local block ID) for every urn-5 names
@@ -1817,8 +1888,21 @@
        -there is no very efficient (simple) methods for finding urn-5 name 
associated with the most recent block
        -one simple proposal is that when we be that we visit to each node 
(first idea above), get all blocks which matches to given properties
       
-      
-\section{Analysis}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=11cm, height=8cm]{storm_query_blockid.eps}
+\caption{Locating owner peer for a given block ID}
+\label{fig:storm_query_blockid}
+\end{figure}
+
+\begin{figure}
+\centering
+\includegraphics[width=11cm, height=8cm]{storm_query_urn5.eps}
+\caption{Locating owner peer for a given urn-5}
+\label{fig:storm_query_urn5}
+\end{figure}
 
 \section{Open issues and future work}