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.

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

Along the x-axis, we have all possible source-destination pairs. We can omit all permutations since order does not matter. For example, we don't need both A to B and B to A.
Along the y-axis, is the frequency that a given edge (as denoted in the legend at the bottom) was traversed for a given source and destination.

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.

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.