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

["Spagnolo, Phillip A" <[e-mail]>]

Richard,

A general comment on our current approach to designing a wireless
interface.  We see that the OSPF community would like to see as few
changes as necessary in a new interface.  Therefore, our current
approach is to start from the standard point-to-multipoint interface
(could change)and to make small changes until we reach a interface that
will be considered efficient enough.  We are testing many of the ideas
by Cisco and yourself.  For example, our first step is to find the best
flooding algorithm because we see that as the top generator of overhead.
If after making small changes, the interface is still not efficient more
drastic changes must be made.  For example we are not giving up on acks,
yet.  We will distribute a draft that gives some insights we have gained
in this approach.

Comments below. 

> -----Original Message-----
> From: Richard Ogier [mailto:[e-mail]] 
> Sent: Tuesday, February 24, 2004 8:30 AM
> To: [e-mail]
> Subject: Re: Comment on draft-ogier-manet-ospf-extension-00.txt
> 
> 
> 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.

Of course, different scenarios and assumptions may yield different
results, but the point is that we were more discouraged than we expected
in getting it to improve performance, and in looking at it more closely,
it seemed like there might be fundamental difficulties in at least some
scenarios.

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

I saw your post, but we wanted to address the current draft before
moving on.  We also have come to the opinion that the decision to ACK or
even send an LSA must be from the originators perspective.  The
originator has a better view of how its links are changing.  Instead of
not acking, it may be best to just delay the LSA that will change
shortly anyway.

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

In the case you present there is no need to use ack suppression.  If you
delay the receiver from acking by MinLSInterval+delta<RxmtInterval then
the ack will never be sent because in the case you present a new LSA
will be received from the sender and the ack will be eliminated.

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

Yes, it is not strictly necessary, but may be convenient, as discussed 
in a previous post:
http://peach.ease.lsoft.com/scripts/wa.exe?A2=ind0401&L=ospf&T=0&F=&S=&P
=5579
> 
> 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

We can provide patches and scripts to QualNet if you want to repeat them
(don't know if you use QualNet).  It would be nice if we could get a
common framework using an open-source discrete 
event simulator with wireless models (such as ns-2).  We looked at
porting John Moy's simulator to ns but it didn't seem straightforward.

Phil

> 
> 
> Spagnolo, Phillip A wrote:
> 
> >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
> >
>