[freehaven-cvs] reworking the text and explanations to reflect the

[feamster@seul.org (Nick Feamster)]

Update of /home/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/tmp/cvs-serv340

Modified Files:
	routing-zones.tex 
Log Message:
reworking the text and explanations to reflect the 
(forthcoming) graphs



Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.51
retrieving revision 1.52
diff -u -d -r1.51 -r1.52
--- routing-zones.tex	29 Jan 2004 04:15:23 -0000	1.51
+++ routing-zones.tex	29 Jan 2004 04:45:56 -0000	1.52
@@ -122,11 +122,10 @@
 likely to be ineffective at achieving jurisdictional independence.
 
 Next, we measure the jurisdictional independence of paths inside the mix
-network. We find that given existing mix network topologies, the
-Mixmaster and Tor path selection algorithms will nearly always create
-paths that can be observed by a single AS in multiple locations for
-paths shorter than four hops.  Fortunately, we observe that longer mix
-paths significantly reduce the likelihood that a single AS can observe a
+network. We find that, given existing mix network topologies, the
+Mixmaster and Tor node selection algorithms will frequently create paths
+that can be observed by a single AS.  Fortunately, longer mix paths
+significantly reduce the likelihood that a single AS can observe a
 significant fraction of links in the path.
 
 Finally, using a model of typical senders and receivers in anonymity
@@ -724,8 +723,8 @@
 \hfill
 \begin{minipage}[ht]{5.75cm}
 \mbox{\epsfig{figure=as_observe_75,width=6cm}}
-\caption{Fraction of paths where a single AS can observe at least 3/4
-  of the links on the mix network path.\protect\footnotemark
+\caption{Fraction of paths where a single AS can observe all but one
+  of the links on the mix network path.%\protect\footnotemark
 }  
 \label{fig:as_observe_75}
 \end{minipage}
@@ -785,10 +784,10 @@
 type of path, we ran 10,000 trials and counted the number of times the
 mix network path traversed the same AS more than once.
 
-\footnotetext{The fraction is lower for 4-hop (i.e., 3-link) paths than
-  for 5-hop paths as an artifact of discretization: ``at least $3/4$ of
-  the links on a 3-hop path'' is all 3 links, ``at least $3/4$ of the
-  links on a 4-hop path'' is 3 out of 4 links.}
+%% \footnotetext{The fraction is lower for 4-hop (i.e., 3-link) paths than
+%%   for 5-hop paths as an artifact of discretization: ``at least $3/4$ of
+%%   the links on a 3-hop path'' is all 3 links, ``at least $3/4$ of the
+%%   links on a 4-hop path'' is 3 out of 4 links.}
 
 
 
@@ -852,29 +851,36 @@
 
 
 Figure~\ref{fig:as_observe} shows the probability that a single AS will
-be able to observe all of the links along the mix network
-path, for mix network paths of different lengths (paths of length one
+be able to observe all of the links along the mix network path, for mix
+network paths of different lengths.  Figure~\ref{fig:as_observe_75}
+shows the probability that a single AS will be able to observe all but
+one of the links along a path of a certain length.  Paths of length one
 and two have less than two links and, thus, are never observed by the
-same AS twice).  Figure~\ref{fig:as_observe_75} shows the probability
-that a single AS will be able to observe at least three-fourths of the
-links along a path of a certain length.  The figures show results for
-both the Tor and Mixmaster network topologies, with two different node
-selection schemes: (1)~allowing the same mix node to be used twice along
-the mix path, as long as the same mix node is not used for two
-consecutive hops (``with replacement'', as in {\em remailer networks})
-and (2)~allowing each mix node to be used only once (``without
-replacement'', as in {\em onion routing}).  Figure~\ref{fig:as_observe}
-shows two interesting results.  First, for all mix paths shorter than
-four hops, a single AS can observe all of of the links on the mix
-network path.  Second, Tor's node selection algorithm (i.e., the onion
-routing scheme) provides significant protection against observation at
-multiple links, but this node selection scheme helps Mixmaster less.
-For example, a four-hop onion routing path in Tor will be observed by a
-single AS on every edge with probability 0.06, whereas a four-hop
-remailer path will be observed with probability 0.23.  This result makes
-sense: because Tor has only 14 nodes, random node selection is much more
-likely to result in the same hop being used twice along a single mix
-path, if this is not explicitly prevented.
+same AS twice.  The AS that contains the second node in a three-hop path
+will always observe all links in the path because it is incident on both
+links on the path; for the same reason, the ASes of the second and third
+hops in a four-hop path will always be able to observe all but one link
+in the path.
+
+The figures show results for both the Tor and Mixmaster
+network topologies, with two different node selection schemes:
+(1)~allowing the same mix node to be used twice along the mix path, as
+long as the same mix node is not used for two consecutive hops (``with
+replacement'', as in {\em remailer networks}) and (2)~allowing each mix
+node to be used only once (``without replacement'', as in {\em onion
+routing}).  Figure~\ref{fig:as_observe} shows two interesting results.
+First, for all mix paths shorter than four hops, a single AS can observe
+all of of the links on the mix network path.  Second, Tor's node
+selection algorithm (i.e., the onion routing scheme) provides
+significant protection against observation at multiple links, but this
+node selection scheme helps Mixmaster less.  For example, a four-hop
+path constructed from Tor nodes without node replacement will be
+observed by a single AS on all links with probability 0.06, whereas a
+four-hop path constructed with node replacement will be observed with
+probability 0.23.  This result makes sense: because Tor has only 14
+nodes, random node selection is much more likely to result in the same
+hop being used twice along a single mix path, if this is not explicitly
+prevented.  
 
 \subsection{Jurisdictional Independence of Entry and Exit Paths}
 
@@ -1011,10 +1017,12 @@
   sufficient to achieve jurisdictional independence.
 
 \item We analyzed the AS-level path properties of existing mix networks
-  and found the likelihood of crossing the same AS more than once along
-  a mix network path to be a near certainty.  Mix paths that are shorter
-  than four nodes will almost certainly be observed by a single AS on
-  all links on that path.
+  and found that certain tier-1 ISPs are prevalent on many mix network
+  paths.  If node replacement is used in path selection, the probability
+  that a single AS observes all links on a four-hop path through the mix
+  is between 0.1 and 0.2; if node replacement is not used, this
+  probability is less than 0.05 for both the Tor and Mixmaster
+  topologies.
 
 \item We have analyzed common entry and exit paths to existing mix
   network topologies and shown that, in general, given random entry and

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/