[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:01:54

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

Log message:
        More evaluation

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.66 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.67
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.66       Mon Feb 
24 08:44:42 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Feb 25 
04:01:51 2003
@@ -485,97 +485,7 @@
 \subsection{Differences}
 
 
-\scriptsize
-\begin{longtable}{|l|l|l|}
-
-\caption[Comparison of Broadicasting and Structured approaches]{Comparison of 
Broadicasting and Structured approaches} 
-\label{table_comparison_approach} 
-
-
-\\ \hline 
-\multicolumn{1}{|c|}{\textbf{Property}} &
-\multicolumn{1}{c|}{\textbf{Unstructured}} & 
-\multicolumn{1}{c|}{\textbf{Structured}}  
- 
-\\ \hline 
-\endfirsthead
-
-\multicolumn{3}{c}%
-{{\tablename\ \thetable{} -- continued from previous page}} \\
-\hline 
-\multicolumn{1}{|c|}{\textbf{Property}} &
-\multicolumn{1}{c|}{\textbf{Loosely structured}} &
-\multicolumn{1}{c|}{\textbf{Tightly structured}}
-\\ \hline 
-\endhead
-
-\endfoot
-
-
-
-\parbox{90pt}{Queries} &
-\parbox{100pt}{Uncontrolled} &
-\parbox{100pt}{Controlled}  
-\\ \hline
-
-\parbox{90pt}{A way for performing queries} &
-\parbox{100pt}{Keywords} &
-\parbox{100pt}{Exact keys} 
-\\ \hline
-         
-\parbox{90pt}{Query traffic} &
-\parbox{100pt}{$O(n)/O(n^{2})$}  &
-\parbox{100pt}{$O(1)/O(log n)$} 
-\\ \hline
-
-\parbox{90pt}{Guaranteed data lookup} &
-\parbox{100pt}{Not necessarily} &
-\parbox{100pt}{Yes} 
-\\ \hline
-
-\parbox{90pt}{Overlay's structure} &
-\parbox{100pt}{Uncontrolled and ad hoc}  &
-\parbox{100pt}{Controlled and structured}
-\\ \hline
-                 
-\parbox{90pt}{Max. number of nodes} &
-\parbox{100pt}{Millions} &
-\parbox{100pt}{Billions} 
-\\ \hline
-                       
-\parbox{90pt}{Data placement} &
-\parbox{100pt}{Local} &
-\parbox{100pt}{Not local} 
-\\ \hline
-                 
-\parbox{90pt}{Support for heterogeneity} &
-\parbox{100pt}{Yes} &
-\parbox{100pt}{No} 
-\\ \hline
-       
-\parbox{90pt}{Support for locality} &
-\parbox{100pt}{Yes} &
-\parbox{100pt}{Partial}        
-\\ \hline
-         
-\parbox{90pt}{Possibility for routing hotspots} &
-\parbox{100pt}{No} &
-\parbox{100pt}{Yes} 
-\\ \hline
-       
-\parbox{90pt}{Design/Implementation complexity} &
-\parbox{100pt}{Low} &
-\parbox{100pt}{High} 
-\\ \hline
 
-\parbox{90pt}{Fault-tolerant} &
-\parbox{100pt}{High} &
-\parbox{100pt}{High}
-\\ \hline
-
-
-\end{longtable}
-\normalsize
 
 
 \subsection{Protocols}
@@ -1668,38 +1578,145 @@
 
 \section{Evaluation}
 
-2.1.5. Answers to research problem
--the most efficient algorithm: O(log n)
-       -DHTs requires O(log n) hops, log n neighbors, except Viceroy (however, 
robustness suffers)
-       %-SWNs requires O(log^2 n) hops, much less neighbors (constant, is not 
depedent of n)
--in DHTs and SWNs, it is possible to locate data in constant time, BUT it 
requires knowing all n neighbors!!!
--in basic scenario, DHTs and SWTs assume that we have to know value's key 
beforehand
--in this case, DHTs and SWNs require little bandwidth, because "network knows 
where the block resides"
--in this case, FBNs, Hybrids, Social Discovery require much bandwidth, since 
there is no benefit from the block's ID at all (they have to ask constantly)
--SWNs and FBSs require less memory than DHTs, since in these approaches, there 
are less connections to other nodes
--SWNs relies less to neighbor nodes than DHTs
--there are different kinds of uses of DHTs, e.g. DHT actually stores the data, 
or DHT only stores 
-the values, which are used for locating the data
--existing systems mainly uses the latter method
--both have pros and cons: 
-       -in the value use, several hostile nodes might say that they hosts the 
value, but refuse to serve any host
-       -in the storage use, hostile node might say that someone must save data 
block size of 1TB for her computer
-       -however, there are methods for preventing these kinds of actions (look 
below)
--DHTs and SWNs are very robust to failures: e.g. 20% of the nodes 
simultaneously fail, less than 0.1% of the data retrievals are failed 
-(each node has "enough neighbors for alternative routing path)
--however, in other approaches, the network infracstructure is very vulnerable: 
usually FBNs/hybrid networks follows the power-law distribution, 
-in which, there are many nodes connected to one node. So, when this "super 
node" is under DoS attach, the performance of the network suffers a lot --> 
-most of data retrievals could fail
--when locating data blocks, the basic difference between DHTs/SWNs is that in 
DHT/SWN approach, systems "knows", where the desired data block resides
-       -based on data block ID's, nodes gives "hints" (routes more close to ID 
in the key space) constantly to a query lookup until 
-       the specific node is found which hosts the block
-       -no extra network traffic
--so in a way, DHT/SWNs are structured entities
--instead, in other approaches, system doesn't "know" where the data block 
resides
-       -we have to ask from any participating node, if they have the data block
-       -very much extra network traffic
--proposol: most efficient approaches for this research problem are DHTs and 
SWNs, since they are based on key-value pairs (Storm has a key as block ID)
--research challenges for DHTs/SWNs:
+There are major differences between loosely and tightly structured approaches.
+Perhaps the most significant difference is that tighly structured approach
+has $\Theta\log{n}$ properties, where as loosely structured approach doesn't
+have always even linear properties. Moreover, tightly structured overlays
+scale much better than loosely structured overlays, since construction and
+maintenance of overlay is controlled.
+
+For Storm, the most important aspect in tightly structured overlays is
+that they use unique keys as identifying data in the network. This is almost
+analogical to Storm's (and xanalogical model's) way of handling data. 
Furthermore,
+as authors cite in \cite{balakrishnan03semanticfree}, tightly structured 
overlays
+provide general purpose \emph{interface} for Reference Resolution Services 
(RRS) 
+(like DNS \cite{rfc1101}) and semantic-free referencing. Authors argue that 
next 
+generation RRS must be application-independent and references itself should be
+\emph{unstructured} and \emph{semantic free}. Indeed, these cases are one of 
the 
+objectives of our Storm design.
+
+On the other hand, however, tightly structured approach doesn't have large 
scale,
+real world experiments yet. Therefore, we can't say for sure, how well tightly
+structured overlay would perform in every day use. The main concerns are 
decreased
+performance, support for heterogeneity and load balancing in system in flux (as
+cited in \cite{liben-nowell02observatorionsp2p}). Other issues of tighly 
structured
+approach are lack of richness (exact keys) when performing queries and 
locality 
+(hashing). We don't see this as a problem. First, our Storm design uses unique 
+identifiers (keys) for identifying data. This is Storm's natural (and 
xanalogical
+model's) way to refer a specific piece of data. Second, by using tightly 
structured
+approaches' DOLR method, we hash the \emph{pointers} of data not the data 
itself. This
+method allows data to be hosted on local computer (if wanted). Of course, for 
+mirroring purposes for instance, Storm is able to use DHT method occasionally 
to 
+move \emph{data} in the network. Finally, we believe that issues related to 
tightly 
+structured approach are solved, since there is strong and wide commitment in 
+research community tightly structured overlays \cite{projectirisurl}. 
Therefore, 
+loosely structured overlays' good support for performing queries 
+(keyword/fuzzy search) and locality properties are not important to our goals.
+
+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,
+which are essential to xanalogical model to be usable in distributed 
environment.
+
+Table \ref{table_comparison_approach} lists the key feature of both approaches.
+
+\scriptsize
+\begin{longtable}{|l|l|l|}
+
+\caption[Comparison of loosely structured and tightly structured 
approaches]{Comparison of loosely structured and tighly structured approaches} 
+\label{table_comparison_approach} 
+
+
+\\ \hline 
+\multicolumn{1}{|c|}{\textbf{Property}} &
+\multicolumn{1}{c|}{\textbf{Unstructured}} & 
+\multicolumn{1}{c|}{\textbf{Structured}}  
+ 
+\\ \hline 
+\endfirsthead
+
+\multicolumn{3}{c}%
+{{\tablename\ \thetable{} -- continued from previous page}} \\
+\hline 
+\multicolumn{1}{|c|}{\textbf{Property}} &
+\multicolumn{1}{c|}{\textbf{Loosely structured}} &
+\multicolumn{1}{c|}{\textbf{Tightly structured}}
+\\ \hline 
+\endhead
+
+\endfoot
+
+
+
+\parbox{90pt}{Queries} &
+\parbox{100pt}{Uncontrolled} &
+\parbox{100pt}{Controlled}  
+\\ \hline
+
+\parbox{90pt}{A way for performing queries} &
+\parbox{100pt}{Keywords} &
+\parbox{100pt}{Exact keys} 
+\\ \hline
+         
+\parbox{90pt}{Query traffic} &
+\parbox{100pt}{$O(n)/O(n^{2})$}  &
+\parbox{100pt}{$O(1)/O(log n)$} 
+\\ \hline
+
+\parbox{90pt}{Guaranteed data lookup} &
+\parbox{100pt}{Not necessarily} &
+\parbox{100pt}{Yes} 
+\\ \hline
+
+\parbox{90pt}{Overlay's structure} &
+\parbox{100pt}{Uncontrolled and ad hoc}  &
+\parbox{100pt}{Controlled and structured}
+\\ \hline
+                 
+\parbox{90pt}{Max. number of nodes} &
+\parbox{100pt}{Millions} &
+\parbox{100pt}{Billions} 
+\\ \hline
+                       
+\parbox{90pt}{Data placement} &
+\parbox{100pt}{Local} &
+\parbox{100pt}{Not local} 
+\\ \hline
+                 
+\parbox{90pt}{Support for heterogeneity} &
+\parbox{100pt}{Yes} &
+\parbox{100pt}{No} 
+\\ \hline
+       
+\parbox{90pt}{Support for locality} &
+\parbox{100pt}{Yes} &
+\parbox{100pt}{Partial}        
+\\ \hline
+         
+\parbox{90pt}{Possibility for routing hotspots} &
+\parbox{100pt}{No} &
+\parbox{100pt}{Yes} 
+\\ \hline
+       
+\parbox{90pt}{Design/Implementation complexity} &
+\parbox{100pt}{Low} &
+\parbox{100pt}{High} 
+\\ \hline
+
+\parbox{90pt}{Fault-tolerant} &
+\parbox{100pt}{High} &
+\parbox{100pt}{High}
+\\ \hline
+
+
+\end{longtable}
+\normalsize
+
+
+
+
+
 
 
 2.2.3. Existing approaches and this specific research problem
@@ -1800,6 +1817,8 @@
        -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}
 
 \section{Open issues and future work}
 
@@ -1807,12 +1826,7 @@
 
 \chapter{Conclusions}
 
--Currently, DHT is the best alternative for Gzz P2P, because:
-       +blocks have unique IDs, they can be used as keys in DHT, it's a 
natural choice
-       +DHT will find a resource, if it exists in a network
-       +for a specific urn-5, we could find all associated block information 
from a single peer
-       -for every urn-5, there is one permanent pointer block (with ID)
-       -for every version of block, there is one permanent ID
+
         
 
 
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.81 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.82
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.81   Mon Feb 24 
08:24:41 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Tue Feb 25 
04:01:51 2003
@@ -1953,3 +1953,10 @@
        pages = {369--378}
 }
 
+
address@hidden,
+       key = {IRIS: Infrastructure for Resilient Internet Systems},
+       title = {IRIS: Infrastructure for Resilient Internet Systems},
+       howpublished = {http://project-iris.net/}
+}
+