Re: [OSPF] Database Exchange Summary List Optimization

[Richard Ogier <[e-mail]>]

I have a few comments and questions regarding the document.
It seems clear that Option 1 should remain in the document
(as Acee indicated).  My comments below suggest that Option 2
is also useful and should also remain in the document.
Finally, I discuss the question of whether Option 3 is useful
enough to be included in the document.

First, I want to mention two advantages of Option 2 (which might
not be clear in the draft).
Option 2 applies only to broadcast (or MANET) interfaces, and
depends on the DR levels of the two routers (DR, BDR, or DR Other).
(In a MANET, if both routers have the same DR level, then the
tie is broken using Router ID.)
For simplicity, let's say the router with larger DR level is a DR,
and the router with smaller DR level is a DR Other.

(1) With Option 2, the DR always lists all LSAs in its database,
while the DR Other lists only LSAs for which it has a more
recent instance than the DR.
Therefore, even if the two routers are completely out of sync,
and assuming the DR has more recent instances (which is more
likely), the DR Other will not list any LSAs.
In this case, if Option 1 were used, the DR Other would
list roughly half of its LSAs on average (i.e., the LSAs
that are not first listed by the DR), and the DR would still
list all of its LSAs (assuming they are more recent), so
Option 2 has an advantage over Option 1 in this case.

(2) The second advantage of Option 2 is that the DR Other will
list far fewer LSAs (and thus transmit fewer bits) than the DR
on average.  This may be useful in a MANET, since the DR Other
may be less powerful than the DR, and thus have a lower router
priority.  Therefore, the less powerful router transmits fewer
bits, which makes sense.

For the above two reasons, I think Option 2 is useful and
should remain in the document.

The main question I have is whether Option 3 is useful enough
to remain in the document. In Option 3, the master lists LSAs
in forward lexicographical order, while the slave lists LSAs
in reverse order.  This reduces the number of LSAs that are
listed by both the master and slave, without requiring a router
to completely process a received DD packet before sending the
next DD packet in response.

Acee told me he does not see a great advantage to sending the
next DD packet prior to processing the received one,
and that this may be a protocol violation since the DD packet
sent in reply effectively acks the received one.
So one question is whether it is possible to effectively
ack a received DD packet without first processing the
list of LSA headers in the packet, or at least reading
the LSA headers to make sure they are valid.  Processing
the LSA headers for the purpose of updating the summary list
will not take significantly more time than simply reading all
the LSA headers, assuming the summary list is ordered
lexicographically or is organized as a binary tree.

Note also that Option 3 has a disadvantage.  For example,
if all LSA headers fit into a single DD packet, then both
routers will still list all LSAs.

So my main question is whether Option 3 is sufficiently
useful and advantageous to be included in the document.
Also, the same question can be applied to Option 2, considering
the advantages I discussed above.
One possibility is to include only Option 1 in the document.

Richard


Acee Lindem wrote:

> We had a  majority of the attendees in favor of making this a WG
> document in Montreal. Is there anyone not in favor of adopting it as
> an informational WG document?
>
> I know there are those who feel we shouldn't publish any document
> that is fully compatible. However, in this case, IMHO, it is 
> worthwhile for
> the WG to do so since:
>
>    1. WG discussion and review will verify with a high probability
>         that this change is, in fact, fully backward compatible.
>    2. We'd be accepting a document that most people agree is a
>         good thing to do - there is less disagreement on the details
>         then some other proposals.
>    3. The relatively simple optimization can result in a significant
>        decrease in DB exchange overhead. In fact, I predict option A
>        will some day be in most implementations.
>
> Thanks,
> Acee
>     
> Richard Ogier wrote:
>
>> I have submitted the following updated draft:
>> http://www.ietf.org/internet-drafts/draft-ogier-ospf-dbex-opt-01.txt
>>
>> The update incorporates comments of others and some ideas I presented
>> in my post on 7/18/2006.  In particular, it describes three options
>> that differ in whether the LSAs must be listed in lexicographical order
>> and whether a router must fully process a received DD packet before
>> sending its next DD packet.  To summarize:
>>
>> In Option A, the router is required to fully process a received DD
>> packet before sending the next DD packet in reply.
>> (LSAs are not listed in lexicographical order.)
>>
>> In Option B, the router with the larger DR level performs database
>> exchange as in RFC 2328 without change.  The router with the smaller
>> DR level sends only empty DD packets (with no LSA headers) until it
>> has received the entire summary list from its neighbor (indicated
>> by M = 0), and then lists only LSAs that are more recent than those
>> received.  I forgot to mention in the draft that Option B applies
>> only to broadcast (or MANET) interfaces.
>>
>> In Option C, the master lists LSAs in lexicographical order
>> and the slave lists LSAs in reverse lexicographical order,
>> as suggested by Mitchell Erblich.
>>
>> Regarding recent comments by Mitchell, I am not yet convinced that
>> there is any benefit to detecting whether a neighbor is nearly in sync
>> and using the optimization (with one of the three options) only if
>> the neighbor is nearly in sync, versus simply employing the
>> optimization.  For example, in MANETs, it appears best to simply
>> employ the optimization with Option A.
>> Maybe you can provide a concrete, realistic example.
>>
>> Even if it does help to detect whether a neighbor is nearly in sync,
>> I am not sure that the (informational) document I am working on
>> needs to specify such a detection mechanism.  Such a mechanism
>> could be specified in a separate document.  Instead, the document I
>> am working on can just state that such a mechanism can be employed
>> if desired.  If two routers are performing database exchange, the
>> protocol does not fail if only one of the routers decides to use
>> the optimization, or if one router decides to use Option A while the
>> other decides to use Option B or C.
>>
>> Of course, this optimization was motivated because we wanted
>> to reduce overhead in MANETs, and I would prefer to keep
>> the document as simple as possible.
>>
>> Richard
>>
>>
>>
>> _______________________________________________
>> OSPF mailing list
>> [e-mail]
>> https://www1.ietf.org/mailman/listinfo/ospf
>>
>
> _______________________________________________
> OSPF mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/ospf
>
>



_______________________________________________
OSPF mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/ospf