[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/05 09:56:30

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

Log message:
        More on distance funcions

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.116 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.117
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.116      Wed Mar 
 5 08:59:25 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Wed Mar  5 
09:56:29 2003
@@ -382,10 +382,21 @@
 in the identifier space. Distance can be measured by numerical
 difference between identifiers (e.g., Chord \cite{stoica01chord}), the number 
of
 same prefix bits between identifiers (e.g., Pastry \cite{rowston01pastry} and 
Tapestry \cite{zhao01tapestry}),
-bit-wise exclusive or (XOR) (e.g., Kademlia \cite{maymounkov02kademlia}). 
However, in all
-previously schemes each hop in the overlay shortens the path
-between current peer working with query and the key which was
-looked up.
+bit-wise exclusive or (XOR) (e.g., Kademlia \cite{maymounkov02kademlia}).
+Because of XOR-metric, Kademlia's distance function is both unidirectional
+(for a given point $p_i$ in the identifier space and distance $d$ > 0, there
+is exactly one point $p_j$ in way that the distance between $p_i$ and $p_j$
+is $d$) and symmetric (the distance from $p_i$ to $p_j$ is same as the
+distance from $p_j$ to $p_i$) \cite{maymounkov02kademlia}. On the other
+hand, Chord's \cite{stoica01chord} distance function does have the property 
+of unidirection, but doesn't have symmetry. Pastry's \cite{rowston01pastry} 
distance 
+function supports symmetry, but doesn't support unidirection. As a 
concequence, 
+Kademlia's \cite{maymounkov02kademlia} 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 previously schemes each 
+hop in the overlay shortens the distance between current peer working with 
query 
+and the key which was looked up in the identifier space. 
 
 Skip Graphs and Swan employ a key space very similar to a tightly structured
 overlay, but in which queries are routed  to \emph{keys}. In these systems
@@ -1826,21 +1837,37 @@
 is limited to certain area of overlay\footnote{The area depends on where the 
query
 originator is located in the overlay.}.
 
-For Fenfire's special needs for locating data, the most important advantage of 
+For Fenfire's special needs for \emph{locating} data, the most important 
advantage of 
 tightly structured approach over loosely structured approach is that tightly 
 structured systems use location-independent, globally unique identifiers for 
 identifying data in the system. Indeed, this 
 feature is almost analogical to Fenfire's (and xanalogical storage model's) 
way of 
 handling data. Another key feature of tightly structured overlays is that they 
are able
-to provide general purpose \emph{interface} for Reference Resolution 
Services\footnote{
-Currently, Domain Name Service (DNS) \cite{rfc1101} is widely used RRS system 
in the Internet.}
- (RRS) \cite{balakrishnan03semanticfree}. Authors argue that next generation 
RRS must be 
+to provide general purpose \emph{interface} for Reference Resolution Services 
(RRS)\footnote{
+Currently, Domain Name System (DNS) \cite{rfc1101} is widely used RRS system 
in the Internet.}
+ \cite{balakrishnan03semanticfree}. Authors argue that next generation RRS 
must be 
 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.
 
+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 
+not be optimal, when obtaining large amounts of data from the Peer-to-Peer 
overlay, for 
+instance videos, images or music. In this case, multisource downloads can be 
very useful 
+for better efficiency \cite{maymounkov03ratelesscodes}, \cite{bittorrenturl}. 
Furthermore, 
+multisource downloads can be used for decreasing load of certain peer, thus 
avoiding query 
+hotspots in the system \cite{ratnasamy02routing}. Current mplementation 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 a scroll block. In face of multisource downloads, Fenfire must support
+tree-based hash\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, e.g., a 
file) from 
+other source.}, such as \cite{merkle87hashtree}, \cite{mohr02thex} for 
reliable and efficient 
+data validation.
+
 Currently, 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, 
@@ -1850,29 +1877,6 @@
 systems would perform in real Peer-to-Peer environment. However, we believe 
that issues are 
 solved, since there is a strong and wide research community towards to tightly 
structured 
 overlays \cite{projectirisurl}.
-
-  
-
-\section{Fetching data} 
-
-Since Storm uses SHA-1 hash function for creating globally unique
-identifiers, if necessary, we can check the integrity of a scroll
-block by re-computing hash value for a scroll block, once fetched
-form the network. Indeed, all scroll blocks' identifiers are
-self-certifying. However, this not very efficient if we want to
-obtain large amounts of data. One possibility is to use tree-based
-hash techiques (e.g., \cite{merkle87hashtree}, \cite{mohr02thex}), 
-which makes possible multisource downloads. Tree based hash functions can be 
used 
-to verify fixed length segments of data file, instead of whole data file. 
-Currently, Shareaza \cite{shareazaurl}, Overnet \cite{overneturl} and 
-eDonkey2000 \cite{edonkey2kurl} uses tree based hashing for validating 
-segments of a data file. Another option, for more efficient data
-fething, is use to standard multisource downloading \cite{bittorrenturl} and 
-online codes \cite{maymounkov03ratelesscodes}.
-
-Multisource downloads can be very useful when media such as video, images 
-or sound is stored under Storm storage model. However, further research is
-required.
 
       
 \section{Analysis}
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.97 
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.98
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.97   Tue Mar  4 
07:25:17 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib        Wed Mar  5 
09:56:30 2003
@@ -1205,7 +1205,7 @@
 
 %Tangler publishing system
 @inproceedings{502002,
-       author = {Marc Waldman and David Mazières},
+       author = {Marc Waldman and David Mazi?res},
        title = {Tangler: a censorship-resistant publishing system based on 
document entanglements},
        booktitle = {Proceedings of the 8th ACM conference on Computer and 
Communications Security},
        year = {2001},
@@ -1419,7 +1419,7 @@
        title = "Self-Organization in Peer-to-Peer Systems",
        author = "Jonathan Ledlie and Jacob Taylor and Laura Serban and Margo 
Seltzer",
        booktitle = {In Proceedings of the 10th ACM SIGOPS European Workshop},
-       location = {Saint-Émilion, France},
+       location = {Saint-?milion, France},
        month = {September},    
        year = {2002},
        url = {http://www.eecs.harvard.edu/~jonathan/p2p/sigops02abstract.pdf}
@@ -1603,7 +1603,7 @@
 }
 
 @misc{benja02urn5,
-       author = {University of Jyväskylä Hyperstructure Group, Benjamin 
Fallenstein},
+       author = {University of Jyv?skyl? Hyperstructure Group, Benjamin 
Fallenstein},
        title = {urn-5 namespace registration},
        month = {Aug},
        year = {2002},
@@ -1819,7 +1819,7 @@
 
 %Schema based access control
 @misc{nejdl03accesscontrol,
-       author = {Wolfgang Nejdl and Wolf Siberski and Martin Wolpers and 
Alexander Löser},
+       author = {Wolfgang Nejdl and Wolf Siberski and Martin Wolpers and 
Alexander L?ser},
        title = {Information Integration in Schema-Based Peer-To-Peer Networks},
        booktitle = {Submitted at the 15th Conference On Advanced Information 
Systems Engineering(CAiSE)},
        year = {2003},
@@ -1932,7 +1932,7 @@
 
 
 @inproceedings{fallenstein03storm,
-       author = {Toni Alatalo and Benja Fallenstein and Hermanni Hyytiälä and 
Tuomas Lukka},
+       author = {Toni Alatalo and Benja Fallenstein and Hermanni Hyyti?l? and 
Tuomas Lukka},
        title = {Storm: Supporting data mobility though location-independent 
identifiers},
        booktitle = {Submitted for publication (The fourteenth conference on 
Hypertext and Hypermedia (Hypermedia '03))},
        year = {2003}   
@@ -2112,3 +2112,12 @@
 }
 
 
address@hidden,
+       AUTHOR = {R. Fielding and J. Gettys and J. Mogul and H. Frystyk and T. 
Berners-Lee},
+       TITLE = {Hypertext Transfer Protocol -- HTTP/1.1},
+       INSTITUTION = {IETF Network Working Group},
+       TYPE = {RFC},
+       MONTH = jan,
+       YEAR = 1997,
+       NUMBER = 2068
+}