Subject: Re: [OSPF] Database Exchange Summary List Optimization

From: Richard Ogier <[email-masked]>
Date: Thu, 10 Aug 2006 13:00:52 -0700

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
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf

---

From: Acee Lindem <[email-masked]>
Date: Thu, 24 Aug 2006 17:41:20 -0400

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 31 Aug 2006 11:05:00 -0700

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