[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] section 6.2
Update of /home/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/tmp/cvs-serv13842
Modified Files:
routing-zones.tex
Added Files:
as_observe.eps
Log Message:
section 6.2
--- NEW FILE: as_observe.eps ---
%!PS-Adobe-2.0 EPSF-2.0
%%Title: analysis.eps
%%Creator: gnuplot 3.7 patchlevel 2
%%CreationDate: Tue Jan 27 12:23:50 2004
%%DocumentFonts: (atend)
%%BoundingBox: 50 50 410 302
%%Orientation: Portrait
%%EndComments
/gnudict 256 dict def
gnudict begin
/Color true def
/Solid false def
/gnulinewidth 5.000 def
/userlinewidth gnulinewidth def
/vshift -50 def
/dl {10 mul} def
/hpt_ 31.5 def
/vpt_ 31.5 def
/hpt hpt_ def
/vpt vpt_ def
/M {moveto} bind def
/L {lineto} bind def
/R {rmoveto} bind def
/V {rlineto} bind def
/vpt2 vpt 2 mul def
/hpt2 hpt 2 mul def
/Lshow { currentpoint stroke M
0 vshift R show } def
/Rshow { currentpoint stroke M
dup stringwidth pop neg vshift R show } def
/Cshow { currentpoint stroke M
dup stringwidth pop -2 div vshift R show } def
/UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def
/hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def
/DL { Color {setrgbcolor Solid {pop []} if 0 setdash }
{pop pop pop Solid {pop []} if 0 setdash} ifelse } def
/BL { stroke userlinewidth 2 mul setlinewidth } def
/AL { stroke userlinewidth 2 div setlinewidth } def
/UL { dup gnulinewidth mul /userlinewidth exch def
dup 1 lt {pop 1} if 10 mul /udl exch def } def
/PL { stroke userlinewidth setlinewidth } def
/LTb { BL [] 0 0 0 DL } def
/LTa { AL [1 udl mul 2 udl mul] 0 setdash 0 0 0 setrgbcolor } def
/LT0 { PL [] 1 0 0 DL } def
/LT1 { PL [4 dl 2 dl] 0 1 0 DL } def
/LT2 { PL [2 dl 3 dl] 0 0 1 DL } def
/LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def
/LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def
/LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def
/LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def
/LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def
/LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def
/Pnt { stroke [] 0 setdash
gsave 1 setlinecap M 0 0 V stroke grestore } def
/Dia { stroke [] 0 setdash 2 copy vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V closepath stroke
Pnt } def
/Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V
currentpoint stroke M
hpt neg vpt neg R hpt2 0 V stroke
} def
/Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V closepath stroke
Pnt } def
/Crs { stroke [] 0 setdash exch hpt sub exch vpt add M
hpt2 vpt2 neg V currentpoint stroke M
hpt2 neg 0 R hpt2 vpt2 V stroke } def
/TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V closepath stroke
Pnt } def
/Star { 2 copy Pls Crs } def
/BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V closepath fill } def
/TriUF { stroke [] 0 setdash vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V closepath fill } def
/TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V closepath stroke
Pnt } def
/TriDF { stroke [] 0 setdash vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V closepath fill} def
/DiaF { stroke [] 0 setdash vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V closepath fill } def
/Pent { stroke [] 0 setdash 2 copy gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
closepath stroke grestore Pnt } def
/PentF { stroke [] 0 setdash gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
closepath fill grestore } def
/Circle { stroke [] 0 setdash 2 copy
hpt 0 360 arc stroke Pnt } def
/CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def
/C0 { BL [] 0 setdash 2 copy moveto vpt 90 450 arc } bind def
/C1 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 90 arc closepath fill
vpt 0 360 arc closepath } bind def
/C2 { BL [] 0 setdash 2 copy moveto
2 copy vpt 90 180 arc closepath fill
vpt 0 360 arc closepath } bind def
/C3 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 180 arc closepath fill
vpt 0 360 arc closepath } bind def
/C4 { BL [] 0 setdash 2 copy moveto
2 copy vpt 180 270 arc closepath fill
vpt 0 360 arc closepath } bind def
/C5 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 90 arc
2 copy moveto
2 copy vpt 180 270 arc closepath fill
vpt 0 360 arc } bind def
/C6 { BL [] 0 setdash 2 copy moveto
2 copy vpt 90 270 arc closepath fill
vpt 0 360 arc closepath } bind def
/C7 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 270 arc closepath fill
vpt 0 360 arc closepath } bind def
/C8 { BL [] 0 setdash 2 copy moveto
2 copy vpt 270 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C9 { BL [] 0 setdash 2 copy moveto
2 copy vpt 270 450 arc closepath fill
vpt 0 360 arc closepath } bind def
/C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill
2 copy moveto
2 copy vpt 90 180 arc closepath fill
vpt 0 360 arc closepath } bind def
/C11 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 180 arc closepath fill
2 copy moveto
2 copy vpt 270 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C12 { BL [] 0 setdash 2 copy moveto
2 copy vpt 180 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C13 { BL [] 0 setdash 2 copy moveto
2 copy vpt 0 90 arc closepath fill
2 copy moveto
2 copy vpt 180 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/C14 { BL [] 0 setdash 2 copy moveto
2 copy vpt 90 360 arc closepath fill
vpt 0 360 arc } bind def
/C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill
vpt 0 360 arc closepath } bind def
/Rec { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto
neg 0 rlineto closepath } bind def
/Square { dup Rec } bind def
/Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def
/S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def
/S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def
/S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
/S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def
/S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
/S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill
exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
/S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def
/S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill
2 copy vpt Square fill
Bsquare } bind def
/S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def
/S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def
/S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill
Bsquare } bind def
/S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill
Bsquare } bind def
/S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def
/S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
2 copy vpt Square fill Bsquare } bind def
/S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
/S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def
/D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def
/D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def
/D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def
/D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def
/D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def
/D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def
/D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def
/D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def
/D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def
/D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def
/D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def
/D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def
/D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def
/D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def
/D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def
/D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def
/DiaE { stroke [] 0 setdash vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V closepath stroke } def
/BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V closepath stroke } def
/TriUE { stroke [] 0 setdash vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V closepath stroke } def
/TriDE { stroke [] 0 setdash vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V closepath stroke } def
/PentE { stroke [] 0 setdash gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
closepath stroke grestore } def
/CircE { stroke [] 0 setdash
hpt 0 360 arc stroke } def
/Opaque { gsave closepath 1 setgray fill grestore 0 setgray closepath } def
/DiaW { stroke [] 0 setdash vpt add M
hpt neg vpt neg V hpt vpt neg V
hpt vpt V hpt neg vpt V Opaque stroke } def
/BoxW { stroke [] 0 setdash exch hpt sub exch vpt add M
0 vpt2 neg V hpt2 0 V 0 vpt2 V
hpt2 neg 0 V Opaque stroke } def
/TriUW { stroke [] 0 setdash vpt 1.12 mul add M
hpt neg vpt -1.62 mul V
hpt 2 mul 0 V
hpt neg vpt 1.62 mul V Opaque stroke } def
/TriDW { stroke [] 0 setdash vpt 1.12 mul sub M
hpt neg vpt 1.62 mul V
hpt 2 mul 0 V
hpt neg vpt -1.62 mul V Opaque stroke } def
/PentW { stroke [] 0 setdash gsave
translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
Opaque stroke grestore } def
/CircW { stroke [] 0 setdash
hpt 0 360 arc Opaque stroke } def
/BoxFill { gsave Rec 1 setgray fill grestore } def
/Symbol-Oblique /Symbol findfont [1 0 .167 1 0 0] makefont
dup length dict begin {1 index /FID eq {pop pop} {def} ifelse} forall
currentdict end definefont
end
%%EndProlog
gnudict begin
gsave
50 50 translate
0.050 0.050 scale
0 setgray
newpath
(Helvetica) findfont 150 scalefont setfont
1.000 UL
LTb
765 450 M
63 0 V
6117 0 R
-63 0 V
675 450 M
( 0) Rshow
765 1332 M
63 0 V
6117 0 R
-63 0 V
-6207 0 R
( 0.2) Rshow
765 2214 M
63 0 V
6117 0 R
-63 0 V
-6207 0 R
( 0.4) Rshow
765 3096 M
63 0 V
6117 0 R
-63 0 V
-6207 0 R
( 0.6) Rshow
765 3978 M
63 0 V
6117 0 R
-63 0 V
-6207 0 R
( 0.8) Rshow
765 4860 M
63 0 V
6117 0 R
-63 0 V
-6207 0 R
( 1) Rshow
765 450 M
0 63 V
0 4347 R
0 -63 V
765 300 M
( 1) Cshow
2825 450 M
0 63 V
0 4347 R
0 -63 V
0 -4497 R
( 2) Cshow
4885 450 M
0 63 V
0 4347 R
0 -63 V
0 -4497 R
( 3) Cshow
6945 450 M
0 63 V
0 4347 R
0 -63 V
0 -4497 R
( 4) Cshow
1.000 UL
LTb
765 450 M
6180 0 V
0 4410 V
-6180 0 V
765 450 L
150 2655 M
currentpoint gsave translate 90 rotate 0 0 M
(Probability of one AS seeing more than 1/2 of Edges) Cshow
grestore
3855 75 M
(Number of Mix Hops) Cshow
1.000 UP
1.000 UL
LT0
6252 1038 M
(Tor w/Duplicate Nodes) Rshow
6342 1038 M
423 0 V
765 450 M
2825 2529 L
4885 3873 L
2060 987 V
765 450 Pls
2825 2529 Pls
4885 3873 Pls
6945 4860 Pls
6553 1038 Pls
1.000 UP
1.000 UL
LT1
6252 888 M
(Tor w/o Duplicates) Rshow
6342 888 M
423 0 V
765 450 M
2825 2239 L
4885 3494 L
6945 4860 L
765 450 Crs
2825 2239 Crs
4885 3494 Crs
6945 4860 Crs
6553 888 Crs
1.000 UP
1.000 UL
LT2
6252 738 M
(Mixmaster w/Duplicate Nodes) Rshow
6342 738 M
423 0 V
765 450 M
2825 2468 L
4885 3552 L
6945 4860 L
765 450 Star
2825 2468 Star
4885 3552 Star
6945 4860 Star
6553 738 Star
1.000 UP
1.000 UL
LT3
6252 588 M
(Mixmaster w/o Duplicates) Rshow
6342 588 M
423 0 V
765 450 M
2825 2468 L
4885 3552 L
6945 4860 L
765 450 Box
2825 2468 Box
4885 3552 Box
6945 4860 Box
6553 588 Box
stroke
grestore
end
showpage
%%Trailer
%%DocumentFonts: Helvetica
Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- routing-zones.tex 27 Jan 2004 07:49:04 -0000 1.21
+++ routing-zones.tex 27 Jan 2004 17:48:33 -0000 1.22
@@ -1,7 +1,7 @@
\documentclass{llncs}
-\usepackage{pst-all}
+\usepackage{pst-all,epsfig}
\newpsobject{showgrid}{psgrid}{subgriddiv=2,griddots=10,gridlabels=6pt}
\newenvironment{tightlist}{\begin{list}{$\bullet$}{
@@ -670,10 +670,18 @@
\end{tabular}
\end{center}
\end{scriptsize}
-\caption{Characterizing jurisdictional independence in Mixmaster and Tor.}
+\caption{Characterizing jurisdictional independence in Tor and Mixmaster.}
\label{tab:path_ind}
\end{table}
+\begin{figure}[t]
+\centering\epsfig{file=as_observe.eps, height=2in}
+\caption{Fraction of paths where a single AS can observe more than half
+ of the hops in the mix network path.}
+\label{fig:as_observe}
+\end{figure}
+
+
%% \begin{table}[t]
%% \begin{tabular}{r|p{1.25in}|p{0.5in}p{0.5in}p{0.5in}p{0.5in}}
@@ -689,13 +697,51 @@
%% \label{tab:path_ind}
%% \end{table}
-Fraction/number of mix paths with overlapping ASes for each network.
-Note that increasing mix path length doesn't necessarily mean more
-anonymity. Table~\ref{tab:path_ind}.
+Table~\ref{tab:path_ind} shows the extent of jurisdictional 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,
+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,
+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
+network, and (2)~fundamental properties of the AS-level topology.
+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
+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
+of paths to and from Internet2 destinations.
-\subsubsection{Effects of Membership Diversity}
+Second, many paths in the Internet, particularly those between edge
+networks, will traverse at least one large ``tier-1'' ISP (i.e., an ISP
+that operates its own backbone and does not by upstream service from
+another ISP). Not surprisingly, Table~\ref{tab:path_ind} shows that
+many of the ASes that are between a large number of mix node pairs are
+tier-1 ISPs (e.g., UUNet, Qwest, Global Crossing, AT\&T, AOL, Verio, and
+Abovenet).
+The prevalence of certain ISPs between mix node pairs suggests that, as
+the length of a mix network path increases, the likelihood that an AS
+will be able to observe the mix network at more than one location
+increases. Figure~\ref{fig:as_observe} shows the probability that an AS
+will be able to observe more than half of the edges along the mix
+network path, for mix network paths of different lengths. The figure
+shows results for both the Tor and Mixmaster networks, 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 (Mixmaster's node selection scheme) and
+(2)~allowing each mix node to be used only once (Tor's scheme).
+Figure~\ref{fig:as_observe} shows two interesting results. First, for
+all mix paths longer than four hops, some AS can observe at least half
+of the edges along the mix network path. Second, Tor's node selection
+algorithm seems to defend it slightly against observation at multiple
+edges, but this node selection scheme helps Mixmaster less. This result
+makes sense: because Tor only as 14 nodes, random node selection is much
+more likely to result in the same hop being used twice along a single
+mix path, if a constraint preventing this is not imposed.
\subsection{Jurisdictional Attacks on Entry and Exit Paths}
@@ -723,7 +769,7 @@
-\subsection{Remarks on Mix Node Placement}
+\subsection{Improving Jurisdictional Independence with Node Placement}
B. How do these results change as we change our assumptions
about the set of nodes from which you can select:
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/