Subject: Re: Simulation parameters for comparative results?

From: [email-masked] (Noel Chiappa)
Date: Fri, 25 Jul 97 10:22:40 -0400

From: "Bevan N. Das" <[email-masked]>

    "what is important is the protocol's average performance which is only
    obtainable from simulation." However, there is no common ground to
    compare the simulation results from different authors

Indeed! It can be hard to compare the work done on different algorithms. (I
prefer to think, and talk, about 'algorithms', rather than 'protocols', for
a number of reasons, such as encouraging people to draw lessons that are
more broadly applicable than a specific protocol.) I'll comment on your
specific suggestion below, but before I do that, here's one thing to keep in
mind - and I apologize if you're already well aware of this.

To me, one of the most important results to convey is something about the
*shape* of the stabilization time (i.e. the time it takes to produces
stable, fully adapted routes after a topology change) curve, not just a
single average. For example, a routing algorithm that stabilizes in time T
98% of the time, and 100T the other 2%, is going to show a nice "average" of
about 3T - but would not really be acceptable in service.

I don't know whether simply giving a standard deviation would be good
enough, or whether you'd need more of a graphical result - but a single
number is *definitely* not good enough.

The way I would suggest measuring it is to take a given 'sample' topology,
and measure the stabilization times for each potential topology change. (It
might be interesting to run the simulation a number of times for the *same*
topology change, and see how much the stabilization time varies. If you get
a lot of divergence there, that would also be interesting to know. This
assumes that you have some randomization in your model, to account for real
world things like the effects of competition from user data for access to
transmission facilities, etc.) After producing a curve, try it for a
different topology, and see if you get a very different curve. If you do,
that's also an interesting thing to know.

    parameters for simulation scenarios ...

    -network size

A good one. What is especially interesting to know is if the *shape* of the
curve stays the same, offset by some factor (perhaps a polynomial) of the
network size, or if increasing size causes negative changes in the *shape*
of the curve, e.g. increasing the length of the tail.

    -network topology, such as average degree/connectivity of nodes

Graph theory says that as you increase the degree, average path length in a
network should decline. This is more likely to have radical effects in
routing algorithms in which the path selection part of the algorithm is
distribute(e.g. distance vecetor, path vector), as opposed to algorithms in
which path selection is done in parallel, locally (e.g. link state).
Probably less intersting than the first, though - but the same comments
about seeing if the shape changes apply.

    -physical considerations, such as area covered, transmission range,
    received power, bandwidth constraints.

I would think some of these are less likely to affect the results than
others, but it would be interesting to try a few to see. Are you considering
them only from the point of local, mobile, networks, or are you thinking of
results that have broader applicabilty?

E.g. bandwidth issues (e.g. from interference with user data traffic, as
well as actual transmission delays for routing data, for those classes of
algorithms that have to ship lots of data around when a change with
significant impact happens, such as most destination vector algorithms) are
probably less significant in the network as a whole than in over-the-air
networks of limited bandwidth. Conversely, physical end-end speed-of-light
transmission delays are more important in continental and global networks
than they would be in local networks.

(I am particularly interested in SOL issues as they are *increasingly*
important as other speeds (processor, memory and link) decline, while SOL
delays are constant, and will, I believe, come to be an important factor in
the "equation" of stabilization time for the network as a whole.)

    - mobility model, such as the rate of change

This is less interesting to model, as if you know the shape of the
stabilization curve, you can more or less predict where you are going to get
into trouble - when the average stabilization time is more than the mean
time between topology changes - at which point the routing starts to chase
its own tail.

    the choice of static topology with random failures vs. mobile topology
    with random movement

I'm not sure this is really a difference, at least for anything you're
likely to program. The latter just looks like links that have been down
"forever" coming up - and as far as most path selection algorithms are
concerned, a topology change is a TC is a TC, as far as what the algorithm
has to do to respond.

If you had a large enough network that you needed to use aggregation to
limit the routing overhead, you have an interesting thing where after enough
topology changes, you might have to re-do abstraction boundaries on the fly,
and rename nodes, but I don't think you're likely to simulate this.

    In summary, what would make a "good" simulation scenario that would be a
    basis for comparison?

I think you need to be able to either i) feed in an actual topology, or ii)
have it simulate one. (In fact, maybe the topology generator could be a
separate program, so the actual simulator doesn't have to know what the
source is.) I have my suspicions that "randomly generated" topologies have
different characteristics than real networks. For one, I think there is
quite likely a different "spacing" (this is a graph theory term I invented
to describe the *kind* of connectivity a node has, local or distant, as
opposed to just the *degree* - but it turns out to be much the same as
"diameter", for a given graph, when you think about it) in real networks and
in purely random graphs. In fact, there's an interesting piece of research
right there: try some real networks, and random ones, and see if they *do*
differ in their actual results, so in future we'll know whether we have to
use real connectivity data, or can generate random ones.

I also think it's less critical that you generate numerical data that can be
compared with other models (e.g. "algorithm X with Y nodes stabilizes in Z
seconds"), than you do internal comparisons, with curve outputs which can be
interpreted directly (e.g. "algorithm X produces this kind of curve, and it
stays the same shape as the network gets larger, and algorithm Y produces
this shape curve").

This is all kind of a gloss on a very complex topic, actually, but hopefully
these quick jottings will be of some use.

	Noel

---

From: "Vincent D. Park" <[email-masked]>
Date: Fri, 25 Jul 1997 12:31:32 -0400

I have a couple comments.

>number is *definitely* not good enough.
I assume when you say *shape* you are refering to somthing like a pdf
curve, which clearly illustrates how a given parameter is distributed. I
agree that the mean does not give much insight into how a parameter is
distributed.  The variance (or standard deviation) can add an indication of
how "spread out" the data is (which is helpful).  Of course, if the data
has a very gaussian distribution, the mean and variance completely describe
the distribution. But, if the data is not very gaussian other parameters
may be appropriate. The are many methods/tests to determine is data
approximates a given distribution. I suspect that most of us are not (a
don't want to become) experts in statistical analysis (thus the mean and
variance will probably suffice for most). I have found that a "picture" can
provide a lot of insight. The pdf can be approximated with a histogram.
This can give you a warm fuzzy as to how well behaved the data is (i.e. how
many modes? bell shape?).

>that's also an interesting thing to know.

A couple words of caution. Not all protocols/algorithms react to every
topological change. TORA (V. Park/M. S. Corson) only reacts to certain link
failures and has no explicit reaction to link activations. Additionally,
some reactions a triggered by message traffic (i.e. the need for a route to
a given destination). Also, I believe DSR (D. Johnson) does not have
explicit reactions to either link failures or link activations. All
reactions are driven by message traffic.

Measuring the reaction to a single failure at a time, may not be
sufficient. In a highly dynamic topology, there may be insufficient time
for an algorithm to converge between reactions triggered by multiple
separate events. The degree to which the various protocols "merge" multiple
reactions will vary.

>concerned, a topology change is a TC is a TC, as far as what the algorithm

A fixed topology as described can be a appropriate model for protocols
which do not benefit from any space-time correlation. DSR (D. Johnson) is a
protocol which would potentially benefit from a model where nodes do not
move, since the nodes essentially cache full-path routes and reactions are
driven by message traffic. How well/poorly the protocol performs would
likely be dependent on the relationship between the message traffic pattern
and the rate of topological changes.

>stays the same shape as the network gets larger, and algorithm Y produces

I agree that a relative comparison is probably the most usefull. By
limiting to a relative comparison, one can make some simplifying
assumptions in the model (taking care not to favor a given protocol).
Reasoning/justification for any assumptions should be given. Such
simplifictions can make simulation of larger networks at higher rates of
topological change more feasible.

-Vince

Vincent D. Park
Center for High Assurance Computer Systems
Naval Research Laboratory

---

From: "M. Scott Corson" <[email-masked]>
Date: Sat, 26 Jul 1997 20:08:41 -0400 (EDT)

On Fri, 25 Jul 1997, Noel Chiappa wrote:

Noel,

Lots of good points.  Some comments.

> number is *definitely* not good enough.

The *shape* (or pdf/empirical histogram) of the algorithm's response
is very important.   One reason TORA [Park-Corson, INFOCOM '97] 
was developed was that a prior algorithm [Corson-Ephremides, Wireless 
Networks, Feb '95] had the potential to exhibit exactly the type of 
behavior you describe--fast convergence most of the time, but with the
potential to exhibit periods of near-instability.  The frequency of
these periods was determined to be too high for the protocol to be
implementable in real systems.

Also of importance is the *nature* of the algorithm's response.  
In other words, it is conceivable that two algorithms might
have identical stabilization-time *shapes*, yet have a different *forms*
of reaction.  One algorithm may be better in that it permits some positive 
action to take place during the algorithm's reaction (or prevents
some negative action) whereas another algorithm does not.
In other words, while the outcome of the two algorithms might be the
same in every respect, their computations may have *side effects* that 
favor one approach over another.

For example, a given approach for supporting QoS may perform 
better on top of one algorithm than another 
because of a dependency on a side effect.  Such dependencies can sometimes
be removed through very loose protocol coupling (something akin to 
a strictly layered approach) at the potential cost of a loss in 
performance.  In this light, judging the relative merits of protocols can be 
quite difficult as many present and future dependencies may be unknown.
There appears to be no substitute for reasoned judgement in some cases.

> the "equation" of stabilization time for the network as a whole.)

Agreed.  SOL is increasingly important in the Internet as a whole.

Unfortunately...
radio and battery technologies (when compared with the effects of Moore's
law in processing and memory technologies) are progressing relatively slowly.
In mobile ad hoc networks, bandwidth (link) and oftentimes energy  
are the scarcest resources.

-Scott

*******************************************************************************

M. Scott Corson                                 Institute for Systems Research
[email-masked]                              A.V. Williams Bldg. (115)
Phone: 301-405-6630 (Rm. 2205 AVW)              University of Maryland     
Fax:   301-314-8586                             College Park, MD  20742

*******************************************************************************