Onion Routing

Results of the Intermediate Node Algorithm on a Tree

The following graph is a connected, undirected binary tree. It is a binary tree because each node has a degree (number of children) at most 2. The topology of this graph is NOT likely to be typical, but we wanted to analyze each of the algorithms under such odd topologies.

Tree


The following bar chart is loaded with information, so take your time reading it.

The significance of this graph is that even if a given source and destination frequently (or even always) traverse an edge (and thus two nodes), this should be considered in light of how frequently all other communicating endpoints utilize the edge. For example, suppose source X and destination Y use the edge(U,V) 100% of the time. If many other source and destination pairs use this same edge with equal (or close to) frequencies, then our concern is diminished. However, if other source and destination pairs rarely use the edge, then the fact that X and Y continuously utilize the edge might be problematic. Recall, this algorithm was executed 1000 times.

Edge Utilization



The following tables display the results obtained from 1000 executions of two cases. The first set of tables corresponds to 1000 executions where I is the source node communicating with various destination nodes, and the second set of tables corresponds to 1000 executions where L is the source node communicating with various destination nodes. Each table shows the number of times a given path was selected for a source to communicate with a destination node. It also shows the actual path taken. Note, the actual path displayed is shown in reverse order (destination to source).

This information was collected for all source-destination pairs, but we did not display all of them for obvious reasons. If there are particular source-destination pairs that you would like to see the tables, please send mail to syverson@itd.nrl.navy.mil and it will be included.

SOURCE I TO DESTINATION J:

FREQUENCY PATH
57 J I G F E K L M N O N M L K E F G I
50 J I G H G I
54 J I G F E D C B C D E F G I
59 J I G F E K L M L K E F G I
56 J I G F E K L M N Q R Q N M L K E F G I
55 J I G F E K L M N M L K E F G I
43 J I G F E K E F G I
50 J I G F E K L M N Q S T S Q N M L K E F G I
60 J I G F E F G I
62 J I G F E K L M N Q S Q N M L K E F G I
62 J I G F E K L M N O P O N M L K E F G I
53 J I G F G I
52 J I G F E D C B A B C D E F G I
59 J I G F E K L K E F G I
51 J I G F E K L M N Q N M L K E F G I
53 J I G I
74 J I G F E D C D E F G I
50 J I G F E D E F G I


SOURCE I TO DESTINATION K:
FREQUENCY PATH
56 K L M N O N M L K E F G I
51 K L M N Q S T S Q N M L K E F G I
56 K E D C B C D E F G I
47 K E F G H G I
59 K L M L K E F G I
44 K L M N M L K E F G I
59 K L M N O P O N M L K E F G I
55 K L M N Q R Q N M L K E F G I
167 K E F G I
55 K E D C B A B C D E F G I
56 K L K E F G I
67 K L M N Q S Q N M L K E F G I
51 K L M N Q N M L K E F G I
61 K E F G I J I
61 K E D C D E F G I
55 K E D E F G I


SOURCE I TO DESTINATION L:
FREQUENCY PATH
53 L M N O N M L K E F G I
51 L M N Q S T S Q N M L K E F G I
58 L K E D C B C D E F G I
50 L K E F G H G I
68 L K E D C D E F G I
50 L M N M L K E F G I
212 L K E F G I
60 L M N O P O N M L K E F G I
59 L M N Q N M L K E F G I
54 L K E D C B A B C D E F G I
76 L M N Q S Q N M L K E F G I
52 L M L K E F G I
55 L K E F G I J I
47 L M N Q R Q N M L K E F G I
55 L K E D E F G I


SOURCE I TO DESTINATION M:
FREQUENCY PATH
60 M L K E D C B A B C D E F G I
54 M N Q S T S Q N M L K E F G I
55 M N O N M L K E F G I
60 M L K E D C B C D E F G I
57 M L K E F G H G I
65 M L K E D C D E F G I
253 M L K E F G I
59 M N O P O N M L K E F G I
52 M N M L K E F G I
51 M N Q N M L K E F G I
76 M N Q S Q N M L K E F G I
48 M N Q R Q N M L K E F G I
51 M L K E F G I J I
59 M L K E D E F G I


SOURCE I TO DESTINATION N:
FREQUENCY PATH
309 N M L K E F G I
60 N Q S T S Q N M L K E F G I
55 N O N M L K E F G I
65 N M L K E D C B A B C D E F G I
59 N M L K E D C D E F G I
54 N M L K E D C B C D E F G I
65 N M L K E F G H G I
54 N O P O N M L K E F G I
53 N Q N M L K E F G I
67 N Q S Q N M L K E F G I
62 N M L K E D E F G I
48 N M L K E F G I J I
49 N Q R Q N M L K E F G I


SOURCE I TO DESTINATION O:
FREQUENCY PATH
368 O N M L K E F G I
62 O N Q S T S Q N M L K E F G I
68 O N M L K E D E F G I
55 O N M L K E D C B A B C D E F G I
59 O N M L K E D C D E F G I
54 O N M L K E D C B C D E F G I
62 O N M L K E F G H G I
55 O P O N M L K E F G I
48 O N Q N M L K E F G I
76 O N Q S Q N M L K E F G I
44 O N M L K E F G I J I
49 O N Q R Q N M L K E F G I


SOURCE I TO DESTINATION P:
FREQUENCY PATH
442 P O N M L K E F G I
51 P O N Q R Q N M L K E F G I
51 P O N M L K E D C B A B C D E F G I
59 P O N M L K E D C D E F G I
57 P O N M L K E D C B C D E F G I
47 P O N M L K E F G I J I
59 P O N M L K E D E F G I
61 P O N M L K E F G H G I
49 P O N Q N M L K E F G I
70 P O N Q S Q N M L K E F G I
54 P O N Q S T S Q N M L K E F G I


SOURCE I TO DESTINATION Q:
FREQUENCY PATH
375 Q N M L K E F G I
56 Q R Q N M L K E F G I
56 Q N M L K E D C B A B C D E F G I
54 Q N M L K E D C B C D E F G I
50 Q N M L K E F G I J I
56 Q N M L K E F G H G I
58 Q S Q N M L K E F G I
60 Q N M L K E D E F G I
61 Q N O N M L K E F G I
60 Q N M L K E D C D E F G I
56 Q N O P O N M L K E F G I
58 Q S T S Q N M L K E F G I


SOURCE I TO DESTINATION R:
FREQUENCY PATH
53 R Q N M L K E D C D E F G I
446 R Q N M L K E F G I
55 R Q N M L K E D C B A B C D E F G I
59 R Q N M L K E D C B C D E F G I
52 R Q N M L K E F G I J I
45 R Q N M L K E F G H G I
60 R Q N M L K E D E F G I
54 R Q S Q N M L K E F G I
57 R Q N O N M L K E F G I
61 R Q S T S Q N M L K E F G I
58 R Q N O P O N M L K E F G I


SOURCE I TO DESTINATION S:
FREQUENCY PATH
47 S Q N M L K E D C D E F G I
70 S Q R Q N M L K E F G I
450 S Q N M L K E F G I
57 S Q N O P O N M L K E F G I
56 S Q N M L K E D C B A B C D E F G I
53 S Q N M L K E D C B C D E F G I
52 S Q N M L K E F G I J I
44 S Q N M L K E F G H G I
59 S Q N M L K E D E F G I
57 S Q N O N M L K E F G I
55 S T S Q N M L K E F G I


SOURCE I TO DESTINATION T:
FREQUENCY PATH
50 T S Q N M L K E D C D E F G I
75 T S Q R Q N M L K E F G I
495 T S Q N M L K E F G I
60 T S Q N O P O N M L K E F G I
58 T S Q N M L K E D C B A B C D E F G I
55 T S Q N M L K E D C B C D E F G I
49 T S Q N M L K E F G I J I
49 T S Q N M L K E F G H G I
58 T S Q N M L K E D E F G I
51 T S Q N O N M L K E F G I


The following tables correspond to communicating endpoints where L is the source node.

SOURCE L TO DESTINATION M:
FREQUENCY PATH
56 M L K E D C B A B C D E K L
63 M L K E F G H G F E K L
59 M L K E D C D E K L
47 M N Q R Q N M L
52 M N Q S Q N M L
53 M L K E D E K L
62 M N Q S T S Q N M L
55 M N M L
47 M L K E F G F E K L
74 M N O N M L
57 M N Q N M L
57 M L K E F G I J I G F E K L
65 M N O P O N M L
41 M L K E D C B C D E K L
63 M L K E F G I G F E K L
47 M L K E K L
45 M L K E F E K L
57 M L K L


SOURCE L TO DESTINATION N:
FREQUENCY PATH
52 N M L K E D C B A B C D E K L
64 N M L K E F G H G F E K L
52 N M L K E D C D E K L
60 N M L
56 N Q S Q N M L
52 N M L K E D E K L
64 N Q S T S Q N M L
51 N M L K E F G F E K L
72 N O N M L
46 N Q N M L
54 N M L K E F G I J I G F E K L
57 N O P O N M L
64 N M L K E F G I G F E K L
46 N Q R Q N M L
53 N M L K E K L
49 N M L K E F E K L
65 N M L K L
43 N M L K E D C B C D E K L


SOURCE L TO DESTINATION O:
FREQUENCY PATH
61 O N M L K E D C B A B C D E K L
55 O N M L K E F E K L
111 O N M L
64 O N M L K E F G H G F E K L
49 O N Q S Q N M L
50 O N Q S T S Q N M L
52 O N M L K E F G F E K L
48 O N M L K E D C D E K L
42 O N Q N M L
56 O P O N M L
53 O N M L K E D E K L
73 O N M L K E F G I G F E K L
49 O N Q R Q N M L
59 O N M L K E K L
66 O N M L K L
52 O N M L K E D C B C D E K L
60 O N M L K E F G I J I G F E K L


SOURCE L TO DESTINATION P:
FREQUENCY PATH
56 P O N M L K E D C B A B C D E K L
58 P O N M L K E F E K L
166 P O N M L
58 P O N M L K E F G H G F E K L
67 P O N M L K E F G I G F E K L
47 P O N Q R Q N M L
51 P O N Q S Q N M L
55 P O N M L K E F G F E K L
49 P O N M L K E D C D E K L
46 P O N Q S T S Q N M L
55 P O N M L K E D E K L
61 P O N M L K L
57 P O N M L K E D C B C D E K L
69 P O N M L K E F G I J I G F E K L
65 P O N M L K E K L
40 P O N Q N M L


SOURCE L TO DESTINATION Q:
FREQUENCY PATH
59 Q N M L K L
64 Q N M L K E F E K L
111 Q N M L
47 Q R Q N M L
58 Q N M L K E D E K L
67 Q N M L K E F G I G F E K L
55 Q N M L K E F G I J I G F E K L
59 Q N M L K E F G F E K L
63 Q N O N M L
46 Q N M L K E D C D E K L
46 Q S T S Q N M L
57 Q N M L K E F G H G F E K L
36 Q N O P O N M L
61 Q S Q N M L
49 Q N M L K E D C B A B C D E K L
59 Q N M L K E D C B C D E K L
63 Q N M L K E K L


SOURCE L TO DESTINATION R:
FREQUENCY PATH
63 R Q N M L K L
65 R Q N M L K E F E K L
154 R Q N M L
55 R Q S T S Q N M L
59 R Q N M L K E D E K L
59 R Q N M L K E F G I G F E K L
37 R Q N O P O N M L
68 R Q N M L K E K L
46 R Q N M L K E D C D E K L
55 R Q N O N M L
65 R Q S Q N M L
59 R Q N M L K E F G F E K L
43 R Q N M L K E D C B A B C D E K L
63 R Q N M L K E D C B C D E K L
51 R Q N M L K E F G H G F E K L
58 R Q N M L K E F G I J I G F E K L


SOURCE L TO DESTINATION S:
FREQUENCY PATH
60 S Q N M L K L
57 S Q N M L K E F E K L
164 S Q N M L
41 S Q R Q N M L
58 S Q N M L K E D E K L
58 S Q N M L K E F G I G F E K L
82 S Q N M L K E K L
60 S Q N M L K E D C B C D E K L
48 S Q N O N M L
54 S T S Q N M L
52 S Q N M L K E D C D E K L
57 S Q N M L K E F G F E K L
40 S Q N O P O N M L
51 S Q N M L K E F G H G F E K L
67 S Q N M L K E F G I J I G F E K L
51 S Q N M L K E D C B A B C D E K L


SOURCE L TO DESTINATION T:
FREQUENCY PATH
53 T S Q N M L K L
50 T S Q N O P O N M L
45 T S Q R Q N M L
63 T S Q N M L K E D E K L
61 T S Q N M L K E F G I G F E K L
228 T S Q N M L
77 T S Q N M L K E K L
55 T S Q N M L K E D C B C D E K L
57 T S Q N O N M L
52 T S Q N M L K E F E K L
48 T S Q N M L K E D C D E K L
57 T S Q N M L K E F G F E K L
54 T S Q N M L K E F G I J I G F E K L
49 T S Q N M L K E F G H G F E K L
51 T Q N M L K E D C B A B C D E K L






Historical page reflecting onion-router.net as of 2005, not regularly maintained. Address questions to Paul Syverson.