Subject: [Ospf-wireless-design] comment resolution, and next steps

From: "Henderson, Thomas R" <[email-masked]>
Date: Tue, 31 May 2005 08:41:23 -0700

Responding to comments on our simulation, and next steps
--------------------------------------------------------

We've received some on-list and off-list comments on our simulation
results (and previous simulations).  Let me try to summarize these
now, and discuss how we would like to handle them.

If I have overlooked an issue that was previously raised and you 
think the omission is important, please chime in.

First, Padma suggested a number of steps for evaluation in her message 
on 4/5:

"IMHO, evaluation should be done thru a number of clearly defined
criteria. A first attempt could look like the following
- Comparison of base algorithm without any optimization.
- Evaluation of the changes required to the OSPFv3 protocol , bearing in
mind extensive changes usually spell instability and newly discovered 
corner cases.
- Leverage of existing proven mechanisms of the OSPFv3 protocol.
- Clearly define in which circumstances the optimizations that really
make sense. For instance, limiting adjacencies is an interesting concept
only if there is a high number of nodes potentially going out of range.
However, it adds unnecessary complexity if the nodes have a wide range
and less likely to drop out. In other words, do these scenarios really
matter or are they unlikely in the particular nework we are addressing. 
Also, optimizations should retain their optional character.
- Last but not the least, identify the sector most likely to deployment
of this technology and tackle their specific problems and perks first. "

Let me handle these in turn:

1.  "Comparison of base algorithm without any optimization."

We have tried to do so, although Richard has pointed out some things
that he disagreed with in our approach, and subsequent discussion also 
highlighted that certain metrics (how to compute average relay node 
set size) can be biased (or not wholly appropriate) for one or the other

algorithms.

To try to isolate these, we did the following:
- turned off incremental hellos (which are in both proposals but which
work differently)
- enabled a full topology mode for Richard's proposal, even though he
has not focused on that mode of operation
- disable the capability to use ACKs as surrogate Hellos in the Cisco
proposal

Richard pointed out some things he did not like with how we did
the evaluations:
- our default for BackupWaitInterval (turns out this doesn't matter
much)
- running his algorithm in "persistent CDS" mode against an overlapping
  relays algorithm that is non-persistent biases against his approach
  when computing the relay node set size
- our approach for computing size of relay set 
- our metric for route quality (agreed, although this does not change
  the absolute results-- only the relative differences)
- two more changes:  i) MDR/BMDR sends multicast ACK when it receives 
  duplicate LSA, ii) reset of retransmit time when Backup MDR floods 
  an LSA  (added to our code) 

These can be remedied in our next release. (Note:  Richard proposed some

database description optimizations but we haven't implemented those.)

2.  "Evaluation of the changes required to the OSPFv3 protocol"

What we have done for the Overlapping Relays code (if anyone
would like to see the full documentation) is go through the draft
and cross-reference all of our code to the draft, so that people
can see what it took to instrument.  We need to do the same for
Richard's-- we plan to do so soon.

Of course, such an evaluation is somewhat subjective.  Phil might
be able to comment on his impression of the relative impact of the
core algorithms on the quagga OSPF implementation.  Richard's
implementation is presently larger but there are many more knobs
to experiment with configuration.

3.  "Leverage of existing proven mechanisms of the OSPFv3 protocol"

I think that both drafts claim to do this.

4.  "Clearly define in which circumstances the optimizations that really
make sense. For instance, limiting adjacencies is an interesting concept
... however, it adds unnecessary complexity..."

Our design team has agreed that networks on the order of 50-100 nodes
are the target size, but has not really scoped the density and mobility
requirements.  Our most recent simulations were for a fixed density
and mobility; previous results looked at varying also the density
and mobility.  We plan to return to that methodology next.

As for limiting adjacencies, I will just say that the results indicate
that it is potentially a very substantial savings in overhead for
dense networks.  My opinion is that while determining the exact strategy

for pruning adjacencies may be considered a later design objective,
whether 
or not an algorithm is suitable to such a later optimization should be 
considered.  So far, only Richard's proposal has explained how this
might work, and has suggested some initial algorithms to evaluate.

5.  "Last but not the least, identify the sector most likely to
deployment
of this technology and tackle their specific problems and perks first. "

I perceive that there are two primary customers of this work:
- military RF systems that want to become Internet-enabled
- people deploying OSPF for wireless mesh networks

What do others think?  What are the requirements for the above two?
I think they are all over the map for the first bullet.

How does this specifically affect how we do our evaluations?  
(Comments suggested)

Some other comments we've received:
- "it is important to consider the robustness of the relay set
  (how well it responds to errors in neighborhood information)"

Response: Agreed.

- "separate overhead between flooding and other elements like
  exchange"

Response:  We provide such a detailed breakdown in our .stat
  files.  We probably need to provide a bit more data to address
  the relay node set size issue.

- "separate packet loss in packet delivery statistics into two
   cases-- i) packets lost due to partitioned networks and 
   ii) packets lost due to routing not converged"

Response:  This is pretty hard to do in wireless simulations
  when packet delivery is probabilistic.  We have decided not
  to try to isolate these components, but instead feel that 
  since the node mobility and radios are the same for different
  simulation runs, the delivery ratios should compare fairly
  between simulation runs with different routing protocols 
  running.

- "extend the set of Overlapping Relays validation tests to
   handle more complicated scenarios (multiple LSAs)"

Response:  This has been done and is in our full documentation. 

- "look at the routing protocol under more fully loaded data
   traffic rather than the light loading we subject our
   scenarios to"

Response:  This is difficult to do in simulation and probably
  best for implementation testing (since all of the packet
  events slow things down significantly).  However, I would
  mention that it is probably reasonable to prioritize
  routing traffic over data traffic when internal contention
  for the link is being resolved, and that if such prioritization
  takes place, the main effect of data traffic is the possible
  capture of the channel by other nodes, if 802.11 MAC is
  being used.  So I agree that it is something worth looking at.

- "efficiency is not the only thing-- robustness is important"
  (similarly, "robustness to imperfect two-hop information" is a
  concern expressed, although Joe Macker has verbally made the
  more general point many times in meetings)

Response:  Agreed.  In fact, there are multiple competing 
  metrics in play, and it is hard to optimize some of these
  without compromising other metrics.
  i) efficiency of the initial optimized floods
  ii) efficiency of the backup flooding mechanisms
  iii) robustness of the algorithm to imperfect information
  (could be inappropriately tuned to the wrong size network,
  or some two-hop neighbor information might be outdated, etc.)    
  iv) latency in converging to workable routing
  v) quality of routes (stretch)

Our simulation data captures some of these metrics but not all;
it is IMO the area for which further progress would benefit our
current design team discussions the most.

Next steps
----------
With the above in mind, we plan to work on the following items
and will release them as they become available.
-  address Richard's comments on our previous results and
   rerun those simulations
-  look at performance under a wider range of mobility and density
   scenarios (also, larger number of nodes where possible)
-  cross-reference the code representing the core and optional
   parts of Richard's algorithms with his draft
-  look at providing more data regarding the core performance
   of the two alternative flooding optimizations

Again, your comments or suggestions on this process are welcome.

Tom

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