Author: hobx
Date: 2006-03-11 17:15:55 +0000 (Sat, 11 Mar 2006)
New Revision: 8229
Modified:
trunk/docs/fnet.tex
Log:
some more fixes
Modified: trunk/docs/fnet.tex
===================================================================
--- trunk/docs/fnet.tex 2006-03-11 17:14:29 UTC (rev 8228)
+++ trunk/docs/fnet.tex 2006-03-11 17:15:55 UTC (rev 8229)
@@ -242,18 +242,16 @@
derive the private key needed to insert other data under the same
name.}
-% OSKARS LATEST PASS REACHED HERE
-
\subsection{Data formats and encryption}
An important aspect of Freenet, that has been carried over from the
previous versions to the current, is a complete system for encrypting,
-splitting, handling data. This occurs at a higher level than the
+splitting, presenting data. This occurs at a higher level than the
Freenet nodes, in what has been designated the client (though in the
spirit of peer-to-peer, the node and client are often the same
-program), and is thus unaffected by the change in how we treat the
-network. The Freenet nodes which route for, store, and fetch data only
-ever see atomic, encrypted, documents, which are processed by the
+program), and is thus unaffected by the recent changes in network
+architecture. The Freenet nodes which route for, store, and fetch data
+only ever see atomic, encrypted, documents, which are processed by the
client into plaintext reconstructed versions.
Encryption of the data is typically done using symmetric encryption,
@@ -263,21 +261,20 @@
the key itself is normally derived from the data's original hash.
The client also handles splitting and padding of data. As a basic
-measure to help a little againts profiling and traffic analysis,
-documents in Freenet are a fixed size - 32kB for CHKs, and 1kB for SSKs.
-Clients ensure this by padding, and also by splitting larger documents
-into many smaller parts. The latter process is also a performance
-enhancement: because the parts are inserted under different keys, they
-spread throughout the network which allows for effective multi-source
-downloading (in the style of newer peer-to-peer programs such as
-bittorrent) when downloading.
+measure againts profiling and traffic analysis, documents in Freenet
+are a fixed size - 32kB for CHKs, and 1kB for SSKs. Clients ensure
+this by padding and by splitting larger documents into many smaller
+parts. The latter process is also an enhancement to performance and
+reliability. Because the parts are inserted under different keys, they
+are spread throughout the network which allows for effective
+multi-source downloading (in the style of newer peer-to-peer programs
+such as bittorrent) when downloading. Splitting also provides an
+additional layer of redundancy, since the clients can use erasure
+codes to make sure that not all the parts are necessary to recreate
+the document. Freenet currently makes use of Vandermonde Forward Error
+Correction codes.
-As part of the splitting there is also an additional layer of
-redundancy, since the clients can use erasure codes to make sure that
-not all the parts are necessary to recreate the document. Freenet
-currently makes use of Vandermonde Forward Error Correction codes.
-
\section{Routing in the Network}
Under the trusted connection model, we have to assume that the graph of
@@ -291,13 +288,12 @@
of the network. If there is no short path between two nodes, it will
not be possible for a document inserted at one to be reachable at
another in a short number of steps, regardless of how well we route.
-Thus the possibility of a system the one proposed working depends
-crucially on network having certain properties.
+Thus the possibility of the system working depends crucially on
+network having certain properties.
-In order to hope that the system can function, we must thus rely on
-certain observations about the network of trusted connection that we
-may use. In particular, it is a subgraph of the of the world's social
-network, the dynamics which has been the subject of much study,
+We must thus rely on certain observations about the network of trusted
+connections. In particular, it is a subgraph of the of the world's
+social network, the dynamics which has been the subject of much study,
initially by sociologists and experimental psychologists
[ref][ref][ref], and increasingly by mathematical means [ref][ref].
In particular, it is generally accepted that the worlds social network
@@ -320,9 +316,10 @@
to choose them from the same space as the keys, and then try to route
queries for a particular key to those nodes whose identities most
closely match the key value. This technique is used by all current DHT
-systems, and will be used by us as well. In light of the observation
-described in Figure \ref{fig:route} the identities of each node can be
-selected quite randomly.
+systems. In light of the observation described in Figure
+\ref{fig:route} the identities of each node can be selected quite
+randomly, though their assignment will need to reflect the network in
+some respect.
Once each node has an identity, one could imagine calculating the all
pairs shortest path for the graph, and keeping a routing table at each
@@ -332,71 +329,85 @@
at each node, neither or which is desirable. More crucially, it would
require one to recalculate the entire routing able every time a node
joins or leaves the network, which is an impossibility under the
-intended algorithm.
+intended usage.
Instead, we use a method which draws off the small world models of Jon
Kleinberg [ref]. The routing we perform is purely greedy: at each
-step, the ``desirability'' of the neighbors is ordered by the
-proximity of their identities to the route key $K$ (seen as floating
-point number between 0 and 1 with period boundary). The question then
-becomes one of trying affect the randomized assignment of identities
-such that this becomes an efficient way of routing. The method we have
-chosen for doing this is described in detail in [ref]. In a nutshell,
-nodes start with randomly selected identities seen as numbers between
-0 and 1, but switch with each other so that nodes that are ``close''
-in the network topology also have nearby identities (it is only when
-this property holds that greedy routing makes sense in anything but
-the final step).
+step, the desirability of the neighbors is ordered by the proximity of
+their identities to the route key $K$ (seen as floating point number
+between 0 and 1 with periodic boundary\footnotemark). The question
+then becomes one of trying affect the randomized assignment of
+identities such that this becomes an efficient way of routing. The
+method we have chosen for doing this is described in detail in
+\cite{sandberg:distributed}. In our implementation nodes start with
+randomly selected identities seen as numbers between 0 and 1, and then
+switch with each other using the described method, causing nodes that
+are in some sense close in the network topology to also have nearby
+identities. (It is only when this property holds that greedy routing
+makes sense in anything but the final step.)
+\footnotetext{That is circular distance, so the distance between 0.9
+ to 0.0 is 0.1.}
+
Ideally, one would hope to be able to assign the identities so that
every step in a route for $K$ brings us to a node whose identity is
-close to $K$ than the last. In practice, this may not always be
-possible, but we still use this as heuristic to show us when to
-terminate a route. Currently the route continues until $m$ steps have
-gone without finding a node closer to $K$ then the best seen so far. A
-value of $m = 10$ is used, which is motivated by attempting to balance
-a thorough search while limiting resource usage.
+closer to $K$ than the last, until we have found the best node on the
+network. In practice, this may not always be possible, but we still
+use this as heuristic to show us when to terminate a route. Currently
+the route continues until $m$ steps have gone without finding a node
+closer to $K$ than the best seen so far. A value of $m = 10$ is used,
+which is motivated by attempting to balance a thorough search while
+limiting resource usage.
\section{Joining and Leaving the Network}
-The system for joining and leaving the network is very
-simple. Nodes choose an identity at random, and then connect to those
-peers with whom they have a pre-established trusted relationship. To
-protect against man in the middle attacks, the connections are
-initiated by the exchange of certificates between users - the certificates
-include both contact information (in practice, the nodes current IP
-address and port number) and cryptographic identifiers for the nodes.
+The procedure for nodes when joining and leaving the network is very
+straightforward. When joining, nodes choose an identity at random, and
+then connect to those peers with whom they have a pre-established
+trusted relationship. To protect against man in the middle attacks,
+the connections are initiated by the exchange of certificates between
+users - the certificates include both contact information (in
+practice, the nodes current IP address and port number) and
+cryptographic identifiers for the nodes.
When a user imports a certificate his node will adds the certificate's
-host as a trusted peer, and attempt to contact it. The other node will
-only respond if it has the certificate of the node attempting to
-contact it. On failure to connect, nodes try again, letting the time
-between subsequent attempts increase exponentially.
+node as a trusted peer, and attempt to contact it. The other node will
+only respond if it has previously the certificate of the node
+attempting to contact it. On failure to connect, nodes try again,
+letting the time between subsequent attempts increase exponentially.
-Once a new node has established connections to a set of trusted peers,
-it can start taking part in the routing. It starts taking part in the
-switching procedure described above so as to get an identity which
-suits it's position in the network and those of it's neighbors. Nodes
-may initially switch at a higher rate, so that they can be come useful
-to the routing as soon as possible.
+Once a new node has established its connections to a set of trusted
+peers, it can start taking part in the routing. It starts taking part
+in the switching procedure described above so as to get an identity
+which suits its position in the network and those of its neighbors.
+Nodes may initially switch between identities at a higher rate, so
+that they can become useful to the routing as soon as possible.
In practice, it is of course unrealistic to expect nodes to join the
network fully formed, with a complete set of trusted peers. One of the
most important and difficult aspects of the project, from a usability
perspective, is to make it sufficiently easy and profitable for users
to create connections that the overlay graph really does reflect the
-underlyign social network. If, for instance, users only ever connect
-to one person when joining the network, the graph will become a tree,
-and the routing algorithm will fail completely. In the current, early,
-versions of the software, we are depending only on the promise of
-increased performance to encourage people to authenticate and connect
-to as many trusted peers as possible, but in the future other ways of
-encouraging this may be necessary (for example allowing the software
-to be used as an instant messaging client and/or file-sharing client
-with those one has authenticated).
+underlying social network. If, for instance, new users only ever
+connect to one person when joining the network, the graph will become
+a tree, and the routing algorithm will fail completely. In the
+current, early, versions of the software, we are depending only on the
+promise of increased performance to encourage people to authenticate
+and connect to as many trusted peers as possible, but in the future
+other ways of encouraging may be necessary (for example allowing the
+software to be used as an instant messaging client and/or file-sharing
+client with those one has authenticated).
\section{Implementation}
+
+\begin{figure}
+ \centering
+ \resizebox{3.0in}{!}{\includegraphics{freenet_real.eps}}
+ \caption{A (small) realization of the actual Freenet network.}
+ \label{fig:route}
+\end{figure}
+
We have an early implementation of this new algorithm. So far it appears
to function, but the network is far too small, and the load on it is
far too low, to draw any certain conclusions. Also so far this has not
@@ -449,17 +460,19 @@
We have described a new version of Freenet based on constructing an
overlay using only trusted connections to build a distributed
hashtable for use as a censorship resistant information publishing
-system. Much work still lies ahead in constructing this system,
+system. Much work still lies remains constructing this system,
especially in testing it with a large user base, and seeing if peoples
trusted connections in practice sufficiently match the small-world of
theory to make communication in the network practical.
Many questions remain as to the viability of operating software like
-Freenet in the real world. The
-difficulty of performing denial of service attacks by attempting to
-affect the routing in various ways needs to be studied, and similarly
-attacks by flooding and spamming in order to decrease the avilability
-of legitimate data. However, we see our design as a proof of concept
+Freenet in the real world. Other open question regard the security and
+anonynity provided by the model. The difficulty of performing denial
+of service attacks by attempting to affect the routing in various ways
+needs to be studied, and similarly attacks by flooding and spamming in
+order to decrease the avilability of legitimate data.
+
+However, we see our design as a proof of concept
of an entirely new form of peer-to-peer overlay, which ensures privacy
for all participants, while offering a robust alternative for building
free communication networks even where they are not desired by all.
