Subject: Re: Comment on draft-ogier-manet-ospf-extension-00.txt

From: "Spagnolo, Phillip A" <[email-masked]>
Date: Mon, 23 Feb 2004 12:51:33 -0800

Richard,

Section 6.1 of your draft states:
   A router can decide to suppress ACKs for a given LSA if a new
   instance of the LSA (with a larger sequence number) is usually
   received every RxmtInterval seconds (e.g., 5-10 seconds).  An
   exponential moving average of the time between LSA updates, or of the
   number of LSA updates during the last RxmtInterval seconds, can be
   maintained for each LSA. Two thresholds can be defined to employ
   hysteresis in deciding whether to suppress ACKs for a given LSA.

We thought the above mechanism would effectively reduce the amount of
overhead due to useless acks.  It potentially allows for a hybrid
operation between reliable flooding during periods of low link change
and periodic flooding under high link change.  Therefore, we decided to
take a look at this technique in isolation, as applied to OSPF.
Specifically, we looked at a QualNet OSPFv2 simulation with
Point-to-Multipoint interfaces on 802.11b network, a random waypoint
mobility model, and only the above suggested modifications (no other
wireless-oriented changes such as flooding optimizations).

However, somewhat to our surprise, the simulation results suggest that
the performance gains may be elusive, at least in the mobility model we
tested.  Specifically, 

- the approach adapts to the link changes passively by predicting the
future based upon the history.  However, we found it difficult to
predict based on the past, looking at both fixed and exponentially
weighted windows with different window sizes and weights.  In fact, it
looked almost as if the interarrivals were exponentially distributed
(modulo the MinLSInterval).  Not only was there a degree of
unpredictability in the actual generation of the LSAs, the practice of
OSPF flooding further filters the interarrival process from the
perspective of a given node that may be multiple hops downstream of an
originator.  Due to inaccurate estimates, the overall overhead went up
in all simulations, and the delivery ratio went down.   The LSAcks are
reduced, but LSUs are increased (more retransmissions).  

- even if each node suppresses the ACKs, the LSAs are flooded through
out the network during rapid link changes around the originator.  These
LSAs generate much higher overhead than the ACKs (overhead due to LSA
transmissions dominates that of the ACKs).  

- the approach assumes senders use the same RxmtInterval as its own
value and requires sender uses same RxmtInterval for all neighbors. This
requirement may force the RxmtInterval to be interchanged between
neighbors like the hello and dead intervals, or make it into an area
parameter.

We are preparing a draft that will provide more details about this and
related topics, but just wanted to note that the early results were not
promising.

Phil

---

From: Richard Ogier <[email-masked]>
Date: Tue, 24 Feb 2004 08:29:37 -0800

Phil,

Thanks for summarizing the results of your simulation investigation.
Without knowing the parameters (e.g., smoothing constant, node speed,
graph density, threshold for suppressing ACKs, etc.) and details
such as whether retransmitted LSAs were unicast, I'm not sure
how to interpret your conclusions.

As I mentioned in my post of 2/17/04, I modified my suggested
technique so that the originator decides whether the LSA should be
marked as "non-ackable" depending on how frequently it changes.
(I did this so that all nodes agree on whether a given LSA
is ackable, and to distinguish between ackable LSAs which
are unicast when retransmitted, and non-ackable LSAs which
are never unicast on a MANET interface.)
A non-ackable LSA is never ACKed, but is effectively flooded
periodically, with a period slightly larger than MinLSInterval.

It seems pretty intuitive that if an LSA is updated (a new instance
originated) every MinLSInterval with probability 0.99 (for example),
then since it will be flooded every MinLSInterval anyway,
there is no need to ACK it, so you can save overhead by not ACKing
it (although as you say the overhead reduction could be small).
So the suggested technique seems useful at least in this case,
unless you have decided to avoid both ACKs and periodic flooding
(which is actually what I have decided).

Also, one of my main points had nothing to do with hybrid operation,
but only that your LSF message is not needed, since the LS sequence
number can be used for this purpose.  Do you agree with me on that
point now?

As I have discussed, I don't think LS ACKs is the best approach,
and my draft actually favors using what is essentially LS *NACKs*,
i.e., periodic DD packets similar to the periodic Complete Sequence
Numbers packets of IS-IS.  And from the new draft
(draft-clausen-manet-ospf-dbx-00.txt) it appears that INRIA
is also proposing to use a variation of the IS-IS technique.
The only reason I proposed the hybrid of ACKs and periodic flooding
is because it seemed to involve minimal changes to OSPF, which I
thought would make it more acceptable to the WG.  However, I am
seeing major changes to OSPF proposed by both the Cisco and
Boeing/INRIA teams which may be justified if they result in major
improvement in performance.

For example, I previously thought that incremental/differential
Hellos would be too much of a change, but am glad to see that Cisco
is proposing to use them. Since I used them in TBRPF (RFC 3684),
I also plan to use them in the OSPF extension that I am developing
(although with some differences).

This is a difficult problem, so it is good that there will be
multiple solutions to compare. But we need to have a plan for
comparing the different solutions via simulations!
Do you have a plan for compare your protocol to Cisco's?
I know you are using Qualnet and Cisco is using OPNET.

Regards,
Richard