Re: [OSPF] Database Exchange Summary List Optimization

Richard Ogier <ogier@earthlink.net> Tue, 05 September 2006 19:45 UTC

Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1GKgro-000598-Ap; Tue, 05 Sep 2006 15:45:52 -0400
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1GKgrn-00058t-9E for ospf@ietf.org; Tue, 05 Sep 2006 15:45:51 -0400
Received: from pop-borzoi.atl.sa.earthlink.net ([207.69.195.70]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1GKgrk-0003og-Ss for ospf@ietf.org; Tue, 05 Sep 2006 15:45:51 -0400
Received: from dialup-4.243.128.70.dial1.sanfrancisco1.level3.net ([4.243.128.70] helo=earthlink.net) by pop-borzoi.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1GKgrf-0001Gw-00; Tue, 05 Sep 2006 15:45:44 -0400
Message-ID: <44FDD3E5.7080900@earthlink.net>
Date: Tue, 05 Sep 2006 12:45:41 -0700
From: Richard Ogier <ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: Paul Jakma <paul@clubi.ie>
Subject: Re: [OSPF] Database Exchange Summary List Optimization
References: <44B7E563.3000706@cisco.com> <44B7E6D0.6030304@cisco.com> <44BD1FE6.2030202@earthlink.net> <44CAAB32.4B2A546D@earthlink.net> <44DB9074.8000700@earthlink.net> <44EE1D00.50502@cisco.com> <44F724CB.50100@earthlink.net> <Pine.LNX.4.64.0609041353380.1936@sheen.jakma.org>
Content-Type: text/plain; charset="us-ascii"; format="flowed"
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Scan-Signature: 202a3ece0492a8c7e7c8672d5214398f
Cc: OSPF List <ospf@ietf.org>, paul.jakma@sun.com
X-BeenThere: ospf@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: The Official IETF OSPG WG Mailing List <ospf.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf>, <mailto:ospf-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/ospf>
List-Post: <mailto:ospf@ietf.org>
List-Help: <mailto:ospf-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf>, <mailto:ospf-request@ietf.org?subject=subscribe>
Errors-To: ospf-bounces@ietf.org

Hi Paul,

I agree with you and Acee that Option C (also called 3) should be removed.
The reason for Option C was so that the next DD packet could be sent
before processing the one received.  But such processing, at least for
updating the summary list, can be done very quickly, especially if the
LSAs are listed in lexicographic order (by both master and slave)
in the summary list and in DD packets.

However, we don't need to require that the LSA headers be processed
for the purpose of creating the link state request list (as in RFC 2328)
before sending the next DD packet.
In particular, it is not necessary for the LSA to be looked up in the
link state database (which may require more time than looking up
the LSA in a lexicographically ordered summary list) before the
next DD packet is sent.
Therefore, Option A should probably be changed to require that the LSA
headers be processed for the purpose of updating the summary list before
sending the next DD packet (but the LSA headers can be processed
later for the purpose of creating the link state request list).

I will plan to keep Option B in the document, since the document is
informational, and Option B is useful in some cases.

More comments below.

Paul Jakma wrote:

> Hi Richard,
>
> On Thu, 31 Aug 2006, Richard Ogier wrote:
>
>> It seems clear that Option 1 should remain in the document
>
>
> Yes.
>
>> (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.
>
>
> It may need refinement in language though. E.g. Acee's point about DD 
> being a strictly master-driven process and sequence numbers..
>
>> The main question I have is whether Option 3 is useful enough
>> to remain in the document.
>
>
> No.
>
> There are two possibilities for 3/C:
>
> a) It occurs naturally as a result of the index the implementation
>    uses for the summary list
>
> b) The implementation must go through contortions to try meet this
>    requirement
>
> I would suggest perhaps instead only mentioning the benefits of 
> implementations ordering their index in that manner, and encourage 
> implementations to try do so if possible.


I assume you mean that the master should list its LSAs in increasing
lex order, and the slave should list its LSAs decreasing lex order.
But there is also an advantage to having the master and slave list
their LSAs in the *same* order, to allow faster processing of the
received list of LSA headers.  Actually, having the slave list its
LSAs in the reverse order can also help speed up this processing
(if the routers know about this ordering in advance).
But since I plan to omit Option C, each router will be required to update
the summary list before sending the next (nonempty) DD packet, so there will
be no advantage to having the slave list its LSAs in the reverse order.
 I tend to agree with Acee that such an ordering should not be
specified in the document.

>
>
> Also, note that even /partial/ ordering would have benefits. e.g. just 
> ordering by (type) or (type,ID).
>
> <option 2/B discussion>:
>
>> 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.
>
>
> Yep.
>
>> 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.
>
>
> Yes, just ACK it. As long as slave keeps ACKing or master keeps 
> polling, with More set, Exchange should continue (modulo 
> implementation bugs :), and 2328 isn't quite as clear on this as it 
> perhaps it could be due to redundancy in description of Exchange, so 
> there is some appreciable real-world risk here.).
>
> I think the text for 2/B perhaps(?) would be better as, if I 
> understood the intention correctly:
>
>  "The router with the lower DR level should continue to acknowledge
>   DD packets or poll for further DD packets, in accordance with which
>   role of Slave or Master it is in, but should do so with empty DD
>   packets with the More bit set.
>
>   LSA headers received may be set aside, their processing deferred
>   until a DD packet is received from the neighbour with the More
>   bit clear.

>
>
>   After which the implementation should proceed normally with
>   Exchange, describing whatever LSAs it has left on its summary list
>   to the neighbour." 


OK.  I will rewrite the desciption of Option B to make it clearer.

>
>
> That ought to get you the 'one side describes first, then the other' 
> behaviour, and is in spec (Exchange does not end until both sides have 
> sent DD with More clear, according to 2328), I think.
>
> Another option, more disruptive, is to observe that the language could 
> be made more simple if it could be guaranteed that Master/Slave always 
> corresponded with the DR level (reduces a combination). It's 
> unfortunate it's a tri-state, otherwise it could be achieved with just 
> one extra DD-flag, but with 2 flags one could arrange that, between 
> neighbours implementing the draft, the roles would be aligned. 
> Wouldn't be as transparent though, compatibility wise.


Right.  Too bad 2328 doesn't specify that the master is the router with the
larger value of (DR level, RtrPri, Router ID).

>
>
> FWIW: Quagga 'ospfd' has an implementation of option A, in CVS HEAD. 


Yes, I wrote the code for the summary list optimization last year
(delimited by OSPF6_MANET_MDR_FLOOD_DD) in Boeing's
GTNetS code.

Richard

>
>
> regards,




_______________________________________________
OSPF mailing list
OSPF@ietf.org
https://www1.ietf.org/mailman/listinfo/ospf