[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu gradu2....
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu gradu2.... |
Date: |
Tue, 08 Apr 2003 05:25:03 -0400 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 03/04/08 05:25:03
Modified files:
Documentation/misc/hemppah-progradu: gradu2.cls masterthesis.tex
progradu.bib
Log message:
Tommi K's comments
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/gradu2.cls.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.200&tr2=1.201&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.116&tr2=1.117&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/gradu2.cls
diff -u gzz/Documentation/misc/hemppah-progradu/gradu2.cls:1.2
gzz/Documentation/misc/hemppah-progradu/gradu2.cls:1.3
--- gzz/Documentation/misc/hemppah-progradu/gradu2.cls:1.2 Thu Mar 13
04:55:51 2003
+++ gzz/Documentation/misc/hemppah-progradu/gradu2.cls Tue Apr 8 05:25:03 2003
@@ -13,7 +13,8 @@
\fitrue
\newif\ifcopyright
-\copyrighttrue
+%\copyrighttrue
+\copyrightfalse
\newif\ifnumbib
\numbibtrue
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.200
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.201
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.200 Thu Mar
27 09:20:37 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex Tue Apr 8
05:25:03 2003
@@ -138,7 +138,8 @@
This is a form of distributed file system (e.g.,
\cite{levy90distributedfilesystems}).
A modern Peer-to-Peer system is composed of an \emph{application} level
overlay network, i.e.,
network operates at the application level and forms a logical network overlay
on top of physical
-network. Figure \ref{fig:application_level} illustrates the Peer-to-Peer
application level overlay network.
+network with regard to the ISO-OSI reference model (e.g., \cite{800902}).
Figure \ref{fig:application_level}
+illustrates the Peer-to-Peer application level overlay network.
Compared to ARPANET's Peer-to-Peer functionality, modern Peer-to-Peer systems
are \emph{ad hoc}, i.e., peers join and leave the system constantly. Thus,
this property
poses challenges for efficient construction and maintenance
@@ -178,9 +179,9 @@
not very efficient, because of unstructured properties of the overlay. Data
lookup model is a combination of methods which
are used for locating data in the overlay.
-\subsection{Definition}
+\subsection{Skecth of definition}
-In this subsection we formalize loosely structured overlay's main components.
This
+In this subsection, we try to introduce a \emph{sketch} of formal definition
of the loosely structured overlay. This
model is based on original Gnutella overlay network with power-law
improvements.
Let $S$ be the aggregate of all services $s$ in system. Let $P$ be the
aggregate of
@@ -200,8 +201,8 @@
index was centralized and the distribution of storage and serving of files was
distributed.
Peers in the Napster network made requests to the central directory server to
find
other peers hosting desirable content. Since service requests were totally
based on a
-centralized index, Napster didn't scale well because of constantly updated
central
-directory and had a single point of failure.
+centralized index, Napster didn't scale because of constantly updated central
+directory, and had a single point of failure.
Gnutella \cite{gnutellaurl} is a well-known example of loosely structured
overlay system. Gnutella
is a pure Peer-to-Peer network as no peer is more important than any other
peer in the network.
@@ -297,7 +298,7 @@
\subsection{Definition}
-In this subsection, we formalize the main features of tightly structured
overlay such as
+In this subsection, we try to introduce a \emph{sketch} of formal definition
of the tightly structured overlay, such as
identifiers, identifier space and the mapping function.
Let $S$ be the aggregate of all services $s$ in the system. Let $P$ be the
aggregate of
@@ -315,7 +316,7 @@
\subsection{Systems}
With tightly structured systems, it is feasible to perform \emph{global} data
lookups in the overlay efficiently. By global lookup, we mean
-that the system is able to find a service from the overlay, if it exists in
the overlay.
+that the system is able to find a service from the overlay, if it exists.
While there are significant differences among proposed tightly structured
systems, they all have in common
that \emph{peer identifiers} are assigned to participating peers from
a large \emph{identifier space} by the overlay. Globally unique identifiers
@@ -331,7 +332,7 @@
To store data into a tightly structured overlay, each application-specific
unique key (e.g., SHA-1 \cite{fips-sha-1}) is \emph{mapped} uniformly (e.g.,
using consistent
-hashing \cite{258660}) by the overlay to an existing peer in the overlay.
Thus, tightly
+hashing \cite{258660}) to an existing peer in the overlay. Thus, tightly
structured overlay assigns a subset of all possible keys to every
participating peer.
We say that a peer is \emph{responsible} for the keys which are assigned by
the overlay.
Figure \ref{fig:structured_hashing} illustrates this
@@ -364,12 +365,12 @@
\end{figure}
Kademlia \cite{maymounkov02kademlia}, Pastry \cite{rowston01pastry} and
Tapestry
-\cite{zhao01tapestry} uses balanced $k$-trees to implement the data structure
of identifier space. Figure
+\cite{zhao01tapestry} use balanced $k$-trees to implement the data structure
of the identifier space. 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
+\cite{debruijn46graph} to maintain local routing tables. It requires
each peer to have only about two links to other peers to provide $O(\log{n})$
performance.
@@ -380,7 +381,7 @@
\label{fig:kademlia_lookup}
\end{figure}
-Currently, there are only three higher level abstractions which tightly
structured overlays provide
+Currently, there are only three higher level abstractions which are provided
by the tightly structured overlays
\cite{zhao03api}. Each of these abstractions represent a storage layer in the
overlay, but
have semantical differences in the \emph{usage} of the overlay.
@@ -408,7 +409,7 @@
\end{itemize}
-The key difference between the DHT and the DOLR abstraction is that in the
DOLR abstraction the overlay maintains only the \emph{pointers} to the data.
+The key difference between the DHT and the DOLR abstraction is that in the
DOLR abstraction the overlay maintains only \emph{pointers} to the data.
Also, the DOLR abstraction routes overlay's messages to a nearest available
peer, hosting a specific data item. This form of locality
is not supported by DHT. DOLR's interface is similar to the DHT's interface,
i.e., values can be any size and type.
@@ -454,10 +455,10 @@
is exactly one point $p_j$ in a way that the distance between $p_i$ and $p_j$
is $d$), but doesn't have symmetry (the distance from $p_i$ to $p_j$ is same
as the
distance from $p_j$ to $p_i$). Pastry's \cite{rowston01pastry} distance
function supports
-symmetry, but doesn't support unidirection. Because of XOR-metric, Kademlia's
distance
-function is both unidirectional and symmetric. Moreover, Kademlia's
\cite{maymounkov02kademlia}
+symmetry, but doesn't support unidirection. According to
\cite{balakrishanarticle03lookupp2p}, because
+of XOR-metric, Kademlia's distance function is both unidirectional and
symmetric. Moreover, 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}.
+(like in Pastry \cite{rowston01pastry}).
However, in all above schemes each hop in the overlay shortens the distance
between
current peer working with the data lookup and the key which was looked up in
the identifier space.
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.116
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.117
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.116 Tue Mar 25
09:23:59 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib Tue Apr 8
05:25:03 2003
@@ -2196,3 +2196,14 @@
publisher = {Springer-Verlag}
}
address@hidden,
+ author = {R. Popescu-Zeletin},
+ title = {Implementing the ISO-OSI reference model},
+ booktitle = {Proceedings of the eigth Data Communications Symposium},
+ year = {1983},
+ isbn = {0-89791-113-X},
+ pages = {56--66},
+ location = {North Falmouth, Massachusetts, United States},
+}
+
+
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu gradu2....,
Hermanni Hyytiälä <=