[freehaven-cvs] fix numbers, conclusions, etc. in Section 6 to refle...

[feamster@seul.org (Nick Feamster)]

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

Modified Files:
	routing-zones.tex 
Log Message:
fix numbers, conclusions, etc. in Section 6 to reflect new tables, graphs, etc.
added a paragraph on the asymmetric properties of location independence,
suggesting that a user may wish to pick different fwd and rev mix level paths
in some cases



Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.72
retrieving revision 1.73
diff -u -d -r1.72 -r1.73
--- routing-zones.tex	17 Jun 2004 18:49:24 -0000	1.72
+++ routing-zones.tex	17 Jun 2004 23:59:29 -0000	1.73
@@ -697,7 +697,9 @@
 and Mixmaster nodes are located in the same AS.  We also examine the
 AS-level path properties between pairs of existing mix nodes and
 quantify the extent to which the AS-level paths between two mix nodes
-traverse common ASes.
+traverse common ASes.  We examine the likelihood of mix-level paths
+traversing common ASes in both the forward (i.e., sender to recipient)
+and reverse (i.e., recipient's reply to sender) directions.
 
 \subsubsection{Node properties}
 
@@ -748,8 +750,8 @@
 \begin{center}
 \begin{tabular}{r|l|p{0in}r|l} \\ 
 & {\bf Tor} & & & {\bf Mixmaster} \\ \hline
-\# of AS-disjoint node pairs & 961 & & & 1764 \\ \hline\hline 
-\multicolumn{5}{c}{{\bf\# of node pairs with common AS}} \\
+\# of AS-disjoint mix node pairs & 961 & & & 1764 \\ \hline\hline 
+\multicolumn{5}{c}{{\bf\# of mix node pairs with common AS}} \\
 AS 3356 (Level 3 Communications, LLC) & 276 (28.7\%) & & AS 3356 (Level 3 Communications, LLC) & 291 (16.5\%)\\
 AS 6461 (Abovenet Communications, Inc) & 249 (25.9\%) & & AS 6461 (Abovenet Communications, Inc) & 251 (14.2\%)\\
 AS 2914 (Verio, Inc) & 65 (6.8\%) & & AS 7018 (AT\&T WorldNet Services) & 234 (13.3\%)\\
@@ -783,10 +785,10 @@
 %% \end{table}
 
 Table~\ref{tab:path_ind} shows the extent of location independence
-in Mixmaster and Tor.  Tor has 14 nodes that are located in 12 distinct
-ASes, for a total of 144 AS-disjoint mix node pairs; similarly,
+in Mixmaster and Tor.  Tor has 35 nodes that are located in 31 distinct
+ASes, for a total of 961 AS-disjoint mix node pairs; similarly,
 Mixmaster has 49 nodes located in 42 distinct ASes, or 1764 AS-disjoint
-node pairs.  The most striking statistic is that AS 3356 appears on 42,
+node pairs.  The most striking statistic is that AS 3356 appears on 276,
 or nearly 30\% of Tor's AS-disjoint paths; AS 3356 also appears on about
 17\% of Mixmaster's AS-disjoint paths.  The reason for this prevalence
 can be explained by two factors: (1)~the location of nodes in the mix
@@ -794,7 +796,7 @@
 
 First, many of both Tor's and Mixmaster's nodes are located in {\em
 edge} networks; this means that, for some nodes, the path both two and
-from that node will cross the same AS a lot of the time.  This
+from that node will cross the same AS much of the time.  This
 phenomenon is especially true for nodes that are located on edge
 networks with a single preferred upstream ISP; for example, the nodes at
 MIT use AS 3356 for most inbound and outbound paths, with the exception
@@ -854,7 +856,8 @@
 \begin{minipage}[ht]{6.75cm}
 \mbox{\epsfig{figure=as_observe_75_rev_log.eps,width=7.75cm}}
 \caption{Fraction of paths where a single AS can observe all but one
-  of the links in the {\em reverse} mix network path.%\protect\footnotemark
+  of the links in the {\em reverse} mix network path. ({\em Note:}
+  slightly different $y$-axis scale.)%\protect\footnotemark
 }  
 \label{fig:as_observe_75_rev}
 \end{minipage}
@@ -870,7 +873,7 @@
 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.
 (Figures~\ref{fig:as_observe_rev} and~\ref{fig:as_observe_75_rev} show
-the same properties for the reverse paths through the mix network.)
+the same properties for the {\em reverse} paths through the mix network.)
 Paths of length one 
 and two have less than two links and, thus, are never observed by the
 same AS twice.  The AS that contains the second node in a three-hop path
@@ -879,25 +882,28 @@
 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 the links in 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 the Mixmaster topology 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.  
+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 the
+links in the mix network path.  Second, Tor's node selection algorithm
+(i.e., the onion routing scheme) provides significant protection against
+observation at multiple links for both the the Tor and Mixmaster network
+topologies.  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.10, whereas a four-hop path constructed with node
+replacement will be observed with probability 0.16.  This result makes
+sense: random node selection with replacement is much more likely to
+result in the same hop being used twice along a single mix path, if this
+is not explicitly prevented.  Figures~\ref{fig:as_observe_rev}
+and~\ref{fig:as_observe_75_rev} also seem to indicate that reverse paths
+through the mix network (i.e., paths from Web servers to cable modem-type
+users) are slightly more vulnerable to observation on both entry and
+exit than vice versa.
 
 \subsection{Location Independence of Entry and Exit Paths}
 
@@ -1254,10 +1260,11 @@
 from the sender to receiver through both the Mixmaster and Tor
 topologies.  
 
-To do this, we generated a list of 10,000 random entry and exit pairs
+To do this, we generated 10,000 random entry and exit pairs
 for each network and, for each sender/receiver pair, observed the number
-of times the path from the sender to the entry node traversed at least
-one AS on both paths.  Tables~\ref{tab:as_obs_ee_tor}
+of times the path from the sender to the entry node traversed at least one
+one AS on both paths; we performed this analysis for both forward and
+reverse paths through the mix network.  Tables~\ref{tab:as_obs_ee_tor}
 and~\ref{tab:as_obs_ee_mm} show the probability, for each sender and
 receiver, of this event. We see that
 each pair of sender and receiver has at least some subset of entry and
@@ -1271,7 +1278,7 @@
 exit paths that traverse the same AS.  They also suggest that it is
 certainly {\em possible} for an intelligent sender to select entry and
 exit nodes such that the entry and exit paths do not traverse the same
-AS on entry and exit (e.g., between Speakeasy and Google, only 8\% of
+AS on entry and exit (e.g., between Speakeasy and Google, only 7\% of
 Tor entry/exit node pairs result in entry and exit paths that cross the
 same AS on both entry and exit).  However, a careless sender that does
 not pay attention to the AS-level topology may well be eavesdropped by a
@@ -1279,7 +1286,19 @@
 1668) as her ISP and attempts to connect to {\tt cnn.com} (AS 5662), a
 single AS (i.e., AS 1668) will observe both the entry and exit paths
 with absolute certainty, because AOL Time Warner owns Turner
-Broadcasting (AS 5662), which includes CNN.
+Broadcasting (AS 5662), which includes CNN.  
+
+Location independence for pairs oof senders and receivers can be highly
+asymmetric.  For example, in the Tor network topology, from Comcast
+(AS~22909) to indymedia (AS~22489), 45\% of the entry/exit node pairs
+result in paths that traverse the same AS on both entry and exit; from
+indymedia to Comcast, on the other hand, random entry and exit node
+selection is much less susceptible to observation on both paths.  This
+result suggests that, in certain cases, {\em a user may wish to establish
+different mix-level paths for forward and reverse traffic} to minimize
+the possibility that a single AS can observe both entry and exit
+traffic.  This finding is not entirely unexpected, given the asymmetric
+path properties of the Internet.
 
 Interestingly, these tables also show that location independence
 is high when either the sender, the receiver, or both are located in a

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