Subject: [Ospf-manet] evaluation plan for OSPF MANET

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 28 Nov 2005 08:50:55 -0800

Note:  This message is intended to start new discussions.  Replies
**only** to [email-masked].

Now that we have established a list for this activity, I would like to
suggest that the first order of business should be to agree upon a fair
process whereby the OSPF WG is in a position to move forward on an OSPF
MANET design by the March meeting.    

A first step should be to agree upon what we are trying to decide.  I
believe that we are trying to decide upon whether the basis for
efficient flooding and topology control for OSPF MANET should be a
source-independent connected dominating set (specifically, Ogier's MDR
proposal) or a source-dependent connected dominating set (specifically,
Overlapping Relays with Smart Peering).  

I also believe that, unless it is proven that the two current designs
have significant performance differences in different operating
environments, we are trying to downselect to one OSPF MANET design, not
to define the operating regions most applicable to two separate designs.

A second step should be to agree on evaluation criteria and scenarios,
to address the comments at the WG meeting that the previously used
scenarios were too narrow.  This should be agreed upon within the next
month or so, based on list discussion.  The scenarios/criteria need to
be feasible to achieve in the timeframe of this evaluation.

A third step should be to allow time for the interested parties to study
the proposed approaches in light of the above criteria.  Simulation or
implementation experiments can be used to support arguments, but are not
required in any or all cases.  I will take the action item to integrate
the new Cisco code and post a new evaluation software release.

A fourth step is to have any interested party submit a short position
draft on the issue at hand.  The position draft should be page limited
(e.g., 10 pages) so that it is more accessible to a wider WG review,
although it may reference additional supporting material.  It would be
recommended but not required that any simulation or implementation
scripts used to justify the arguments be made available at this time as
well (private simulation results should probably be treated with less
confidence by the WG).  Drafts should not be allowed later than the I-D
cutoff date, and the publishing of such a draft should be required to
make a formal presentation on this topic at the Dallas meeting. 

The fifth step is to have discussion on the list between the I-D cutoff
and the meeting, and presentations and discussions at the Dallas
meeting.

Comments?

Tom

_______________________________________________
Ospf-manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-manet

---

From: Richard Ogier <[email-masked]>
Date: Mon, 28 Nov 2005 13:50:20 -0800

Tom and all,

Below, I suggest some guidelines for scenarios and performance measures.
First, I have a few suggestions regarding the evaluation process.

To avoid having someone announce a major enhancement just before the
next IETF meeting, there needs to be a deadline for submitting code
that will be used in any simulation results that can be presented at
the next meeting.  You mentioned that scenarios and performance measures
should be agreed on "within the next month or so".
I think we need to be more specific about the deadline for both the
scenarios/measures, and for the code itself. I suggest January 15 for
the scenarios, and February 1 for the protocol code.

I think position drafts are a good idea, but I think there should
be two phases of position drafts.
A second-phase position draft is submitted by the I-D cutoff
and can include a rebuttal of a position draft submitted
at the end of the first phase.
The reason for such a rebuttal is that a position draft might
include arguments that look good on the surface, but do not
hold up under closer examination.
To prevent someone from submitting *only* a second-phase position
draft (thus avoiding a rebuttal), a first-phase draft must be
submitted by the first-phase deadline (say two weeks before the
I-D cutoff) as a requirement for submitting a second-phase draft.

One might say that rebuttals can be done in the fifth step, i.e.,
via a discussion on the list, but including the rebuttal
in a position draft is more organized and easier to judge.

Another possibility is to allow a 10-page rebuttal to be submitted
no later than one week before the day of the meeting.
Any such rebuttal would be considered "required reading" by
the OSPF-MANET list (thus providing some organization in the
fifth step).  (Otherwise, I might post a 20-page rebuttal
on the list that nobody will read. :-))

Below, I suggest some guidelines for presenting simulation results.
The main idea is to achieve a fair comparison, and to avoid
presenting only the scenarios and performance measures that make
one protocol look better than another protocol.

1. The set of scenarios presented should include both sparse and dense
   networks, where the densest scenario should be almost fully connected
   (since such scenarios are practical and useful).
   To limit the number of scenarios, one could limit to the following
   two transmission ranges: 0.25 and 0.50 times the length of the region
   (assuming the region is a square).  Or, one could consider
   0.20, 0.30, 0.40, and 0.50, for example. The point is to avoid
   excluding either dense scenarios or sparse scenarios.
   (If the range is less than 0.25, then I think the network is
   partitioned most of the time if there are 50 nodes.)

2. Boeing has already run scenarios with more than 100 nodes (for
   OSPF-MDR), and it appears that even larger networks can be supported.
   Therefore, it is important for 100-node scenarios to be run since
   they represent the most challenging scenarios that we can simulate.
   If protocol A performs about the same as protocol B with 50 nodes,
   but protocol A performs significantly better than protocol B
   with 100 nodes, this is an important consideration.

3. The set of scenarios presented should include both slow mobility
   and fast mobility.  One possible range for average node speed is
   from 5 to 30 meters per sec (11 to 67 mph).  To limit the total
   number of scenarios, one could consider the 12 scenarios obtained
   by taking all combinations of the following parameter values:

   - Number of nodes: 50 and 100
   - Radio range: .25 and .50 times the length of the region
   - Average node speed: 5, 15, and 25 m/s

   Note: Scenarios with less than 50 nodes may also be presented,
   but they are less challenging.  To obtain a trend curve, one
   could run simulations with 25, 50, 75, and 100 nodes.

4. Related to item 3, protocol parameters should be adjusted to make
   sense for the node speed.  For example, for fast node speeds,
   a smaller Hello interval should be used (e.g., 1 second instead of
   2 seconds).  One rule of thumb is to make the Hello interval small
   enough so that the delivery ratio is at least 90%, since a smaller
   delivery ratio would usually be considered unnaceptable (especially
   if it can be increased simply by using a smaller Hello interval).
   (Another way to increase delivery ratio is to implement link-layer
   failure detection.)

5. The performance measures should include at least (1) overhead,
   (2) delivery ratio, and (3) average path length in hops.
   (Suboptimal path length is an important source of overhead.)
   Average end-to-end delay of UDP packets would also be a useful
   measure.

6. Any technique that is used by one protocol, and can be used by
   both protocols to improve performance, should be used by
   both protocols.  If a given technique can be used
   (to improve performance) by one protocol but not the other,
   then the technique MAY be used by the one protocol.

7. Of course, the code needs to be made available to others, so that
   others can run their own simulations and verify the results.

Just as an example (and not to criticize), the simulation
results for smart peering presented at the IETF meeting focused
on a small subset of the scenario ranges suggested above:
up to 50 nodes, a radio range of up to 200 m, which is only .40 times
the length of the region, only one choice of node speed, and
average path length was not presented (but was included in the
detailed data).

Richard

---

From: Richard Ogier <[email-masked]>
Date: Mon, 28 Nov 2005 15:26:47 -0800

I would like to add one more comment.
Since partial-topology LSAs have been shown to reduce
overhead substantially, simulations with partial-topology LSAs
should be performed for both protocols.
One cannot simply assume that if a protocol performs well
with full-topology LSAs, then it will perform well with
partial-topology LSAs.  For example, it is not clear how
using partial-topology LSAs will affect MPR selection
(which depends on 2-hop neighbor information obtained from
neighbors' LSAs).

I don't think Cisco's protocol can use MPRs to create partial-topology
LSAs that provide min-hop paths, since MPRs based on partial-topology
LSAs will generally not provide min-hop paths. (This is one of the
reasons OSPF-MDR uses Hellos to learn 2-hop neighbor info.)
However, Cisco's protocol can use the min-cost LSAs of the OSPF-MDR
draft to provide min-hop paths.

Richard

---

From: Acee Lindem <[email-masked]>
Date: Tue, 29 Nov 2005 14:29:51 -0500

> (which depends on 2-hop neighbor information obtained from

I think full topology LSAs are the most interesting since they optimize
the data path (assuming you advertise all reachable neighbors as >=
2-way state as proposed in both proposals).

> LSAs that provide min-hop paths, 

I don't think this is trivial problem in any case. This isn't 
implemented in the
current GTNetS - correct?

> since MPRs based on partial-topology

I think I agree. Basically, what you're saying is that hello discovery of
2-hop neighborhood is a necessary condition to use partial topology LSAs.
However, personally I'm not a big fan of partial topology LSAs.

Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Tue, 29 Nov 2005 12:11:41 -0800

> 2-way state as proposed in both proposals).

It is possible to calculate min-cost paths without using full-topology
LSAs, and requiring full-topology LSAs definitely prevents a scalable
solution. (Boeing's simulation results show that the overhead is nearly
linear in the number of nodes if partial-topology LSAs are used, but
not if full-topology LSAs are used.)  The min-cost LSAs of OSPF-MDR
provide min-cost routing if the metric depends only on the interface
(i.e., is the same for all neighbors on a given interface), or min-hop
routing if all metrics are the same.

Note that we can allow both full-topology and partial-topology LSAs
in the same implementation, since they are interoperable with each
other. Thus, allowing partial-topology LSAs just provides more
flexibility which allows scalability to a larger number of nodes.

> current GTNetS - correct?

If you mean the creation of partial-topology LSAs that provide min-hop
paths, OSPF-MDR does this with its min-cost LSAs. (This is novel in
the sense that it is a new idea that I have not seen before I added
it to the OSPF-MDR draft about a year ago.)
MPRs could be used to create partial-topology LSAs that provide min-hop
paths (the router LSA would include all MPR selectors), but only if MPRs
are based on full 2-hop neighbor information (e.g., via Hellos).

> 2-hop neighborhood is a necessary condition to use partial topology LSAs.

It is not necessary, but it helps.  As I said, Cisco's protocol can use
the min-cost LSAs of OSPF-MDR even though it uses LSAs to learn 2-hop
neighbor info. But Hello discovery of 2-hop neighbor info is necessary
if you want to use full 2-hop neighbor info (e.g., to select MPRs that
provide min-hop paths) even if you only generate partial-topology LSAs.

Richard

---

From: Russ White <[email-masked]>
Date: Wed, 30 Nov 2005 08:15:07 -0500

> be feasible to achieve in the timeframe of this evaluation.

This presupposes emulations are "the" way to evaulate the proposals. In 
fact, I believe we need to do more traditional work here, such as 
examining pathological cases. For instance:

o Is there a point in the mobility graph where the protocol mechanism 
simply won't converge when real rachability should be available in the 
network?

o Is there a specific event that will cause a long outage in 
reachability when physical reachability still exists?

o How much change to existing code do the proposed mechanisms cause? One 
of the reasons we're using OSPF here is to reuse as much of a known 
working protocol as possible in a different environment. If the proposed 
changes change entire sections of the OSPF code (1,000 lines sounds 
trivial, until you realize that most OSPF implementations are probably 
only 12,000 lines of code, and 1/12th doesn't sound so trivial any 
longer), then we don't want to mess with it--better to use a new protocol.

o How extensible, into the future, are the proposed changes? Are they 
currently "at the end of the line," as optimal as they will ever get, or 
are there other areas of exploration to be done? If one mechanism has 
optimized all it can, and another shows similar improvements, but has 
many more possible optimizations, it's better to go with one that can be 
further optimized.

These are the sorts of things we normally look at when examining a 
protocol change, rather than basing the change simply on simulation 
results. We all realize implementations have a huge impact on 
performance (you can implement SPF as n^2, or n(log n), for instance), 
and that you learn how to improve performance over time. Basing an 
initial modification based on simple performance in a simulator is the 
wrong way to work at the problem. Imagine the IETF choosing between 
IS-IS and OSPF based on simulation work (!).

Simulations are interesting, but they don't indicate much of anything, 
until you get to simulating on real routers, and possibly even real 
radios (although I'm not so certain about that part, for various reasons).

:-)

Russ

- -- 
[email-masked] CCIE <>< Grace Alone

---

From: Richard Ogier <[email-masked]>
Date: Wed, 30 Nov 2005 08:50:39 -0800

(I am replying only to [email-masked] as requested by Tom.)

>longer), then we don't want to mess with it--better to use a new protocol.

I am not sure I agree with the above reasoning.  I am not sure it is
better to use a new protocol just because 1/12 of the code must be changed.
The goal is to extend OSPF, so that we have something that performs
well in MANETs and interoperates with existing OSPF. It might be
necessary to change 1/12 of the code to achieve this goal.

In judging how much OSPF is being changed, I think it is better
to examine the changes at a conceptual level, rather than count the
number of lines of code that must be changed.
For example, OSPF reduces the number of adjacencies in a broadcast
network by having each DR Other form adjacencies with the DR
and BDR.  This can be generalized to MANETs by using a CDS
(where MDRs are used instead of the DR) and having each
MDR Other form adjacencies with two MDR/BMDR neighbors.

One possible test is the following:  When the OSPF extension is
applied to a fully connected (fixed) network, how similar is it to
an OSPF broadcast network?  OSPF has already done a good job
of reducing overhead in this case, so it should not be necessary
to use something very different. (Of course, the extension must
also perform well in general MANETs.)

Regarding simulations, they are not perfect, but they are useful
and are better than making "educated guesses".
Simulations are like analysis, but allow more complex models
than paper analysis.  For example, someone might guess that
protocol A is more robust than protocol B because protocol A
uses more backup relays.  It is hard for the guesser to take
into account all of the factors that affect robustness, but
simulations do a much better job of this.

Richard

---

From: Abhay Roy <[email-masked]>
Date: Wed, 30 Nov 2005 14:19:25 -0800 (PST)

Richard,

I think you make some excellent suggestions below on what things we 
should compare. Some comments inline..

>   partitioned most of the time if there are 50 nodes.)

If you want to cover the spectrum of "fully connected" you would 
need a 1.0 data point too. So I would suggest 0.25 0.50 0.75 and 1.0.

>   with 100 nodes, this is an important consideration.

I have reservations about this. For one, it's extremely time 
consuming to run just a single set of 100 node simulation (many 
days?). So if we are trying to make changes to the algorithms, the 
turn around time for the results is almost unacceptable.

And then what is so magical about 100? Why not 200? or 500? IMHO, 
when someone attempts to scale networks to higher numbers, they will 
likely have some other strategies to break them apart in say "areas" 
(or something equivalent) to hide the churn and complexities of 
link-state protocols.

So my recommendation will be to limit it to 20,30,40,50 node cases.

>   - Average node speed: 5, 15, and 25 m/s

I like the 5,15,25 m/s data points..

>   (Another way to increase delivery ratio is to implement link-layer

If you mean that the delivery ratio should at least be 90%, I am not 
so sure, if we can achieve that for all the variations. Of course, 
if you can't deliver packets, there is not much point in reducing 
the control plane overhead. So the goal should be to strive to keep 
the delivery ratio as high as possible.

>   then the technique MAY be used by the one protocol.

This is a good idea, and I think we have brought this up in the 
past. If only we can find some volunteer coders to do this 
mix-n-match ;)

Regards,
-Roy-

---

From: Abhay Roy <[email-masked]>
Date: Wed, 30 Nov 2005 14:22:16 -0800 (PST)

If it seems valuable to use the 2-hop information from the Hello's 
(say for partial-topology), I think we can easily adapt ORCAs to use 
the Hello's v/s Router-LSAs.

Regards,
-Roy-