Subject: TORA Observations

From: "Keith J. Koval" <[email-masked]>
Date: Wed, 2 Sep 1998 11:55:07 -0400

Hello all,

I've been working on some simulations of TORA on a simulator designed at
the Mitre Corporation.  The tests were basically done in an "omnipotent"
i.e. non-distrubuted mode, with synchronous transmissions and receptions. 
The basic purpose of these tests was to se what routes TORA would discover
for a given network architecture.

The observations can be found (in pdf format) at

www.rpi.edu/~kovalk/MANET/TORA.htm

Regards,

- Keith Koval

---

From: "Vincent D. Park" <[email-masked]>
Date: Wed, 02 Sep 1998 15:46:19 -0400

>www.rpi.edu/~kovalk/MANET/TORA.htm

Keith,

I have a couple quick comments on your observations.

(1) As you point out, TORA does not guarantee that multiple routes are
created. However, unlike traditional shortest path routing protocols it
does provide multiple routes in many cases. The connectivity of the network
can greatly effect the number of nodes which have multiple routes to a
given destination. Constructing a directed acyclic graph (DAG) rooted at a
given destination over a tree topology, results only one route from each
node to the given destination. Similarly, constructing the DAG over a ring
topology as in your example (i.e., one step up from the most degenerative
case) only provides one node (not the source in your particular example)
with two routes to the given destination. It would be helpful to illustrate
the DAG in your example to make this point clear. For more densely
connected network topologies, a larger percentage of the nodes will
typically have multiple downstream links to the destnation. In any case the
effect is to reduce the frequency and scope of TORA's reactions to
topological changes, thus minimizing its bandwidth consuption.

(2) You correctly point out a case where a link can become improperly
directed, based on the description of TORA in the INFOCOM 97 paper and in
section 2.2.4.1 of the internet draft. Those descriptions failed to point
out that the link state array must be updated; however, the procedure is
correctly stated in section 3.7.6 of the internet draft. The QRY reception
procedure is also correct in the simulations of TORA that we did, and in
the simulation code/flowcharts that we provided to Mitre last year.
Unfortunately, its too late to correct the INFOCOM paper, but I will make a
correction to section 2.2.4.1 of the internet draft. Thanks.

(3) I disagree with the statement that "an advantaged node can adversely
affect the performance of TORA." Although it is difficult to see in your
example (since you do not show the DAG), an advantaged node with a high
degree of connectivity typically results in a large fraction of the nodes
in the network having multiple downstream paths to the given destination.
As described in (1) above, this tends to reduce the frequency and scope of
TORA's reactions to topological changes (i.e., good for performance not
bad). If I didn't know better, I would guess that selected a "source" node
to illustrate the possibility that there is only one path. For example,
assume that when routes were constructed, all nodes that are one-hop from
the destination set their delta values to one, and all nodes that are two
hops from the destination set their delta values to two. Then, for your
example to be correct, the yellow node must have a lower node ID than all
three of its neighbors that are also one-hop from the destination, and the
blue node must have a lower node ID than all three of its neighbors that
are also two hops from the destination. Finally, if this is true, then all
six of the neighbors described above would have at least two downstream
links for routing to the destination. I don't think your example clearly
illustrates this point. As for traffic concentration, TORA does not specify
how the forwarding decision should be made (given multiple paths). In our
simulations we tried two alternatives (random and lowest neighbor). In any
case, the availability of multiple paths (even for only some sources)
provides a better capability to balance traffic load, than with a
shortest-path algorithm that provides only a single route. Obviously,
shortest-path routing algorithms would heavily favor the advantage node;
TORA need not.

Hope this is helpful,

-Vince

 Vincent D. Park                 
 Information Technology Division 
 Naval Research Laboratory       
 4555 Overlook Avenue SW             
 Washington, DC 20375-5000