Re: [OSPF] Database Exchange Summary List Optimization

[Acee Lindem <[e-mail]>]

Hi Richard,

Richard Ogier wrote:
> 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.
This is ok with me. I think it is also fully backward compatible and
I can see situations where the total number of LSA headers exchanged
will be reduced. However, this is at the expense of some serialization
in the exchange process (the extreme example would be two routers
with completely disjoint Link State Databases forming an adjacency
for the first time).

>
> 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.
I'd be in favor of removing this option. When a DD packet
is sent, it essentially acknowledges the previous one received.
Hence, I really think the DD packet should be processed
prior to sending one in response. Also, when I first brought
up lexicographical ordering I was envisioning a linear
representation of the database summary list - clearly, it is
a mistake to assume this or specify it 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.
I could go either way here. Since we're talking about an informational
track anyway and there are some benefits, I'd say we can retain it.

Thanks,
Acee

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