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

From: Richard Ogier <[email-masked]>
Date: Thu, 01 Dec 2005 16:13:22 -0800

Abhay Roy wrote:

> Richard Ogier wrote:
>
>>
>> 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.)
>
>
> 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.

I have no problem with these choices.  Even 1.0 does not ensure the
network is fully connected (one corner of a unit square is distance
1.414 from the opposite corner), but it is close enough to fully connected.
But even 0.75 is quite dense, so I could accept either 0.75 or 1.0 as
the maximum range to consider.

>
>
>> 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.
>
>
> 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.

I have several comments about this. As you know, Boeing has already run 
simulations
with 110 nodes with partial-topology LSAs. I don't know how long these 
simulations took,
but the simulations run faster with partial-topology LSAs.  (Your 
experience may
have been only for full-topology LSAs.)  If not 100 nodes, than maybe 80 
nodes with
partial-topology LSAs, whichever takes a reasonable amount of time.
Also, if you design your protocol to be scalable and efficient (even if 
you only
simulate with 50 nodes), then your protocol should also perform well for 
100 nodes.
Scalability (to as many nodes as possible) is an important objective, so
I think people want to know how scalable the solutions are.
Also, it is really the number of edges (neighbor pairs) that affects running
time.  So a sparse 100 node network will take less time to simulate than
a dense 100 node network.
In summary, I don't think it is necessary or desirable to limit simulations
to 50 nodes.

Richard

>
>
>> 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
>
>
> I like the 5,15,25 m/s data points..
>
>>   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.)
>
>
> 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.
>
>> 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.
>
>
> 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-
>
>> 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
>>
>>
>>
>> Henderson, Thomas R wrote:
>>
>>> 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
>>>
>>>
>>>
>>
>>
>> _______________________________________________
>> Ospf-manet mailing list
>> [email-masked]
>> https://www1.ietf.org/mailman/listinfo/ospf-manet
>>
>
>

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

---

From: Russ White <[email-masked]>
Date: Thu, 15 Dec 2005 16:02:30 -0500

>> 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.
> 
> 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.

If there are three solutions available, one of them changes 1/2 of the 
code in all examined implementations, the second changes 1/4, and the 
third changes 1/12, then there should be a clear preference for the one 
that changes 1/12. Remind me why we chose to modify OSPF, rather than 
creating a new protocol? :-)

> 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.

And I don't agree, at all. IS-IS is very similar to OSPF in most 
concepts (including SPF, DR election, flooding, adjacency bringup, etc), 
but the code is _completely_ different. You're not addressing the issue 
at hand--leaving OSPF, as much as possible, alone, so well tested and 
understood implementations remain as they are, taking advantage of the 
well tested and understood parts.

> 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.

They are not better than spending time analysing corner cases, and 
understanding the operation of the protocol. Simulations do _not_ test 
corner cases or pathological cases. This is _not_ an "educated guess."

BTW, can you point to the simulations undertaken for various OSPF 
designs during the original design work? Or was there mostly analysis so 
that people understood various possible situations, and design to make 
certain there were no holes?

:-)

Russ

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