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

From: Acee Lindem <[email-masked]>
Date: Fri, 01 Sep 2006 16:16:12 -0400

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

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

---

From: Paul Jakma <[email-masked]>
Date: Mon, 4 Sep 2006 15:26:39 +0100 (IST)

Hi Richard,

> It seems clear that Option 1 should remain in the document

Yes.

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

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

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

Also, note that even /partial/ ordering would have benefits. e.g. 
just ordering by (type) or (type,ID).

> sent in reply effectively acks the received one.

Yep.

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

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.

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

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
There are few people more often in the wrong than those who cannot endure
to be thought so.

---

From: Richard Ogier <[email-masked]>
Date: Tue, 05 Sep 2006 12:45:41 -0700

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:

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

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

>   Exchange, describing whatever LSAs it has left on its summary list

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

> 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

---

From: Erblichs <[email-masked]>
Date: Tue, 05 Sep 2006 14:10:53 -0700

Group,

	* I believe that this work-in-progress RFC is a architectural
	doc and implementations are out-of-scope of this RFC, thus IMO
	any difficulty of implementing a functionality should not be
	a considersation when looking at more efficient functionalities.

	If this is the case, then their should be some type of option
	or other support in the ARCHITECTURE doc for the implmentations 
	that see a benefit of that functionality.

	Thus, a reverse lex ordering scheme should be reviewed on
	whether it can repeatedly improve the efficency of LSDB
	exchange.

	As repeatedly stated 

> next DD packet in response.

However, the 2nd justification for option 2 is:
2) The second advantage of Option 2 is that the DR Other will
> priority.  Therefore, the less powerful router transmits fewer

---> Unless MANET has changed this. Their is no correlation of the
value of router-id and the chance of being a DR. This is a secondary
test ONLY when the priorities are equal.
*** Thus, it is unknown who has the greater capability or which one
   is the DR in a MBA env.

----> I also prefer Master-slave as this allows all env to achieve
this new functionality.

So,,,

IMO option 3, 

- Would benefit from both routers being in sync to
completely out-of-sync with respect to their LSDBs.
- Common sense allows both routers a lazy review 
of the recv'ed hdrs. This should remove a slow hdr review from possibly
being a bottleneck. A router could theorectically do other processing
at a higher priority and/or review after sending its next DD or other
pkt.
- While known hdrs are not present because of the ordering scheme, LS 
Update pkts could be sent.
- The jitter of the values of the LSAs becomes more important than
the number of LSAs: We are looking at holes within the LSDBs that
the other router has LSAs for.
- Example with a simple ordering of the total set of values from
1 to 100 with no holes. If the master increased and started with DD at 
a value of 49, the slave could send LS Updates containing 1-48 without
ever needing to sending any hdrs on those LSAs. ie:Flooding in parallel.
- The reverse gives us the ability to NOT have the Master list all of
its LSA hdrs in DD pkts. If the slave offers values that are not in its
LSDB or are newer, then normal REQ pkts could be sent or if they are
older, just send UPdates without the hdrs.
- The same is true for the other nbr where the slave may be decreasing
and send value 69, thus the master could theorectly identify what is
higher than 69 and just send updates for all of those items.
-- The last two results in a parallel dual flooding, that WOULD have
been done during loading after we exchanged hdrs.  If we had the slack 
time during DD exchange this would directly benefit us a faster
convergence.
-- So, in theory we could send just a tiny fraction of our LSAs
   hdrs during exchange.

Thus, best case is that as the LSDB diverge, the holes are at the
extremes 
of the LSA values and that updates would be done by the time that all
the 
hdrs are exchanged. Thus, this not ONLY decreases the number of hdr bits
exchanged (we don't need to send the hdrs of the LSAs that they don't
have),
we don't have to do nothing with a slow nbr, we also don't have to wait
until
all hdrs are exchanged to send updates for those holes. All of which
decreases 
the convergence time and the amount of bits sent to each other.

Please identify any non-implementation issues as I have a working
prototype
and see no negative issues other than the ability to periodicly flood
updates
based on holes in the LSDB. Thus, a DD with x LSA hdrs may generate a
flood of
say Y LSAs.

Mitchell Erblich
-----------------

---

From: Acee Lindem <[email-masked]>
Date: Tue, 05 Sep 2006 18:02:17 -0400

Hi Mitchell,

> 	whether it can repeatedly improve the efficency of LSDB
So, if one doesn't envision any implementation, what is the benefit of 
any ordering
of entries in the OSPF database exchange? The only time I could see that 
as being
of any advantage would be if the OSPF router taking part in the 
exchange, sends
the next OSPF database description packet prior to looking in the 
headers in the one
it just received. Given that the current specification (RFC 2328) uses 
the sending of
the next DD packet as acknowledgment of the previous, why would ordering
of LSA headers in the DD packets be of any advantage?

Thanks,
Acee

---

From: Paul Jakma <[email-masked]>
Date: Wed, 6 Sep 2006 00:05:09 +0100 (IST)

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

Sure.

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

Ah, I meant same order.

I.e. for some implementation, the index into the summary list may 
have some inherent order to it. Such that, when the same 
implementation talks to the other, with identical LSDBs, you get the 
benefits of:

A: Describes LSAs of order 0 to m to neighbour B
B: <scratches 0 to m from its summary list>
    Describes LSAs order n to p to A
A: <scratches as-recent LSAs m to p from its summary list>
    Describes LSAs order q to r to B
<etc>

Which was the optimisation I /thought/ was under discussion :). I 
must have lost the thread. :)

I don't think there's much point /mandating/ the order though, as 
Erblichs points out we're not here to dictate implementation (though, 
I'd disagree that we shouldn't pay any heed to glaring efficiency 
problems in implementation).

Suggesting an order might be useful though. E.g. for implementations 
using an index which can order things arbitrarily, why not at least 
suggest one?

> received list of LSA headers.

For option A, I think so, yes.

It seems harmless to suggest an order though. Implementations can 
follow it if they want/can, or not.. At least then implementations 
which /do/ want to avail of this optimisations will have a 
standardised order they can implement. If we don't suggest one, we 
deny interoperable use of this optimisation (other than by chance). 
Not hugely important though.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Madness takes its toll. Please have exact change.

---

From: Erblichs <[email-masked]>
Date: Tue, 05 Sep 2006 21:27:27 -0700

Acee Lindem,

	As you already know, an implementation and a arch spec
	are two different items. All RFCs are arch specs. All
	drafts are work-in-progress which are arch specs.

	All of this is about option 3, C, which was
	originally suggested by me.

	Definition: 

	"hole" : one or more lex contig LSAs 
	values that are present in one LSDB and not the
	other router's LSDB. 

	As stated multiple times, a MINOR side effect of the
	rev lex ordering is that it removes the need
	to immediately process the DD pkt when it arrives.

	** The major benefite is: remove the need to list
	all LSAs by one or the other router. The reverse
	actually allows us to remove more LSA hdrs from
	the DD pkt. If these extra LSAs were holes, then
	the nbr would send a req for each LSA that it
	didn't have, and then we respond with a
	Update pkt. All being unncessary with rev lex
	except the single Update.

	Why? The singly direction by both routers forces
	multiple chances of discontinuity.. This occurs
	at the ends of the DD pkt by both routers. If a
	hole occurs at the end or begining of the DD pkt
	and the hole is filled by DD hdrs of the other
	router, alot of efficicency is lost. Realize that
	the hole is first filled with DD hdrs, then reqs
	gen, req send, req rec, AND then the update.

	If the rev lex order is used, the two spaces only
	have one point where this occcurs, the middle.
	All of items (random placement of LSAs occuring
	in both routers that are newer for one router or
	the other) tend to cancel, still eqaully force 
	normal reqs.

	So, the greater the number and the size of holes
	that exist within the LSDB, the greater the number
	that the holes will fall at the ends and result in
	a unnecessary DD hdr, with a req gen and processing
	by both routers. With a LDDB in the 10s of thous, mult
	holes, each of hundreds of LSAs is possible that will
	need to be req, where they could have just been listed
	in a update pkt.

	Thus the amount of performance increases as the amount
	of LSDB differences occur between the two routers and
	how it is spread accross the LSDBs.

		Mitchell Erblich
		------------------

---

From: Acee Lindem <[email-masked]>
Date: Wed, 06 Sep 2006 16:49:20 -0400

Hi Mitchell,

See inline.

> 	to immediately process the DD pkt when it arrives.
If you read section 10.6 of RFC 2328, you'll see that the DD packet should
be processed prior to sending one in response. If fact, there are 
situations where
the contents of the DD packet dictates generation of a SeqNumMismatch
or ExchangeDone event. I don't think we want to change this...

Also, while were talking about protocol versus implementation, why should we
presume the time it takes to process the DD headers is significant 
relative to
the rest of the exchange process?

> 	gen, req send, req rec, AND then the update.
This is unequivocally FALSE as long as you process the current DD packet
before responding by building a new DD packet from your summary list.
Remember, that if both routers have the same instance of an LSA, it doesn't
matter which one of them includes it in a database exchange packet. If they
have different instances, there is absolutely nothing in the 
lexicographical
ordering that would effect the distribution of more recent LSAs.

Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Wed, 06 Sep 2006 14:16:01 -0700

>*** Thus, it is unknown who has the greater capability or which one
I'm not sure what your point is, but more powerful routers will likely be
assigned larger router priorities, and thus are more likely to be selected
as DR (or MDR for a MANET interface).
(This has nothing to do with the master-slave relationship.)

>----> I also prefer Master-slave as this allows all env to achieve
I would also prefer this *if* the master is more likely to be the DR/MDR,
but this is not the case.
That is why I said it is too bad that 2328 does not specify that the
router with larger value of (DR level, RtrPri, RID) is the master.
I was thinking of changing this when selecting MDRs in a MANET.

However, I think it is important that the DR is the router that 
initially lists
its LSAs, since it is more likely to have a more up-to-date database.
Also, this allows a possible future extension - multicast DD packets.
I.e., the DR can list all of its LSAs in DD packets that are multicast to
all neighbors.   The similarity of this to IS-IS leads one to understand
why it is important to use DR level instead of master-slave.

>at a higher priority and/or review after sending its next DD or other
A router could just process the headers for the purpose of updating the 
summary list,
which as stated can be done in time proportional to the number of 
headers if headers
are listed in lex order in both the summary list and in DD packets.
This processing is therefore essentially as fast as simply reading the 
DD packet,
which must be done anyway before the DD packet is acked.
Other processing, including processing for the purpose of creating the 
link state
request list, can be done after the next DD packet is sent in response.
Therefore, using reverse lex order does not help here, which is why some 
of us
are saying Option C is not needed.

>ever needing to sending any hdrs on those LSAs. ie:Flooding in parallel.
So you are saying the slave can send LSAs without receiving an LS request
from the master.  This is similar to IS-IS.
I am not sure we want to avoid the LS request mechanism of OSPF.
Here is one reason.  Suppose a new DR is establishing an adjacency with
100 neighbors at the same time.  Suppose the 100 neighbors all have
a particular LSA that the DR does not have.  Then the 100 neighbors
(or a subset of them depending on the timing) will send the same LSA
to the DR.  That is why we need the LS request, so that the DR only
needs to request the LSA from one neighbor.

Also, the idea of bypassing the LS request mechanism can be applied just as
easily to Option A,  by sending the LSA instead of the LSA header if the LSA
is newer than the neighbor's instance.

Also, it seems to me that both master and slave can list LSAs in the same
(forward) order.  For example, the master lists 1 to 30 in a DD packet, then
the slave reads the first LSA (1) and last LSA (30)  in the received DD 
packet
and then lists LSAs 31 to 60 in its next DD packet, etc.
I.e., there may be no need to list LSAs in reverse order, even if
a router does not fully process a received DD packet before sending the
next one in response (but only reads the first and last LSA headers).

However, as mentioned above, the router might as well update its
summary list before sending the next DD packet in response.
So, the only significant advantage of ordering LSA headers in DD packets is
to speed up the processing of updating the summary list.

>older, just send UPdates without the hdrs.
Again, you are saying to avoid the LS request mechanism of OSPF,
which I don't think is a good idea.

>higher than 69 and just send updates for all of those items.
Ditto here.  Also again, I think both master and slave can list LSAs in 
forward order,
since they can read the first and last LSAs listed in a received DD packet.

>-- So, in theory we could send just a tiny fraction of our LSAs

True.  But each LSA header *or* LSA must be sent by either the master or 
slave,
so on average at least half of the LSAs must be either sent or listed.
If the two routers are already synchronized, then at least half of the 
LSA headers
must still be sent.
I agree that this can reduce the number of LSA headers sent, but as 
mentioned
above there is a disadvantage of avoiding the LS request mechanism of OSPF.

If you want to propose avoiding (or bypassing) the LS request mechanism 
of OSPF,
that may be the topic of another RFC.    This idea can also be applied 
to Option A,
by sending the LSA instead of the LSA header if the LSA is newer than 
the neighbor's
instance.   Also, as mentioned above, the identification of missing LSA 
headers
(holes) might be just as easy if the LSAs are listed in forward order, so
reverse order might not be necessary.

Richard

---

From: Erblichs <[email-masked]>
Date: Wed, 06 Sep 2006 16:18:58 -0700

Acee Lindem,

	two inline sections..

	Mitchell Erblich
	----------------

> the rest of the exchange process?

	First.. The word MINOR is their, thus why would you think I think
	that it is significant????

	I should have said "removes" the need to FULLY process
	the pkt and all the LSAs within the pkt before our
	next local DD pkt is sent. Yes, some pre-processing of the
	pkt is needed. I just don't think you need to process all
	of it before you send your next local DD pkt.

	If something takes 1 microsec and I may have to process
	100 million DD hdrs for all the full nbr formations, iff
	I am able to process them while I am doing nothing, then
	why not. I would rather do a minimal amount of validation
	of the DD pkt, send my next local DD pkt, and then process
	the rest of it while I am waiting for the next DD pkt from
	my nbr..

	If I can shave 10 secs off of a full adj formation and
	I have a 10Gb interface, that allows me to send almost
	100Gb more information. Why not do this? Doesn't
	every implimentation prefer a faster "XYZ"?

> ordering that would effect the distribution of more recent LSAs.

	Acee, did you read the word "hole"? I left a description
	earlier in this email.

	A "hole" is that LSAs that don't exist within the
	LSDBs of BOTH the slave and the Master. In one but
	NOT the other. In the master, not in the slave.
	In the slave but not the master. I ALSO said that it
	doesn't make a difference if it is in both LSDBs. It
	cancels..

	Here is a simple example:
	Master Router sends a LSA hdr with a value of 22 at the
	end of the DD pkt. Its next value on its next DD pkt
	will be 55.

	Slave sends the headers between 22 and 55 in its DD pkt
	because it is also moving forwards.

	The Master says I don't have those LSA hdrs from the slave
	thus, I need to request them. The slave then processes
	the req and sends the update. 

	On the other hand if option 3, C was used.

	The next set of LSA hdrs from the Master would starts its
	next LSAs hdrs for the DD pkt with 55. The slave is listing
	the LSAs from the reverse direction. Since the slave
	was looking for holes, it says I have LSAs that fit between
	22 and 55, and sends them as LSAs within Updates.
	-- Thus the listing of the LSAs that fit into any hole
	is never listed as a DD hdr. It is never requested, and
	that non-request is never processed. Thus, you eliminate
	alot of overhead. 

	This also works between suceessive LSA hdrs within each DD
	pkt. Because of the greater time overhead in doing this additional
	lookup, a prototype implementation does in between the
	DD pkt.

	Bottom line, if the combined LSDB is equally split, maybe
	75% of all LSAs could be removed from the DD pkts. This
	is MAJOR. A major performance improvement.

	How else do I explain this???? And it only works FULLY
	when the two routers are approaching the LSDB space in 
	different directions.

	Mitchell Erblich
	-----------------

---

From: Acee Lindem <[email-masked]>
Date: Wed, 06 Sep 2006 20:44:10 -0400

Mitchell Erblichs,

See responses inline.

> 	Mitchell Erblich
I don't believe that in any stretch of the imagination that you are 
going to come up
10 seconds 1 second, or even 100 milliseconds quicker by doing this. Anyway,
not only did you jump from overlapping operations to savings of 
processing and bandwidth
but you completely glanced over the fact that it isn't compatible with 
section 10.6 of
RFC 2328. Since this would be protocol change, the onus is on you to 
garner support
from others who view this as useful .
 
> 	How else do I explain this???? 
Are you comparing option C with option A or the base OSPF exchange? Are 
you making
the assumption that the exchange partners are NOT processing DD packets 
before
sending a response? Are you inferring something about these holes that 
is not currently
in draft-ogier-ospf-dbex-opt-01.txt? Are you disagreeing with section 3 
in the draft?

Thanks,
Acee

> And it only works FULLY

---

From: Richard Ogier <[email-masked]>
Date: Fri, 08 Sep 2006 07:53:02 -0700

>	when the two routers are approaching the LSDB space in 

Mitchell,

The particular example you gave is biased in that it gives an
advantage to using reverse lex order.
In the first part of your example (using the forward direction),
the slave happened to send several LSA headers that the master
did not have.  The example could easily be changed so that
the slave would send a DD packet that either indicated
several missing LSAs (holes) or LSAs that are older than
what the master has (in both cases the master would send
these LSAs to the slave).

I studied this and have come to the conclusion that
your scheme works just as well if both master and slave
list LSAs in the same forward order.
By your scheme, I mean the idea of detecting holes and
sending the LSA instead of the LSA header when the router
has a newer instance than the neighbor (or the neighbor
has no instance).
(Note, however, that I am not saying I like the scheme,
only that using reverse lex order does not help.)

Let's consider a more symmetric, unbiased example.
Assume that for a given LSA:
The master has a newer instance than the slave
(or the slave has no instance) with probability 1/3,
the master has the same instance as the slave with probability 1/3,
and the slave has a newer instance than the master
(or the master has no instance) with probability 1/3.

Now suppose the master starts by listing LSAs 1 to 30
in a DD packet.  Both routers list LSAs in forward order.
The slave then lists LSAs 31 to 60 in its next DD packet.
The slave processes the received LSA headers 1 to 30
as follows, either before or after sending its next DD packet.
(In either case, it will not include any of these LSA
headers in the DD packet with the scheme we are considering.)
If the neighbor's LSA is older than the database copy,
or the neighbor's LSA does not exist (a hole is detected),
the slave sends the LSA to the neighbor.
If the neighbor LSA is the same as the database copy,
the slave does nothing (e.g., does not list the LSA).
If the neighbor LSA is newer than the database copy,
or the database copy does not exist,
the slave requests the LSA.

When the master receives the DD packet that lists
LSAs 31 to 60, it replies by sending a DD packet
starting with LSA header 61, and processes the received
DD packet as described above for the slave.

The main thing to notice is that the master and slave
send disjoint lists of LSA headers, even if they
both list LSAs in forward order, so it makes no difference
whether the master and slave list LSAs in the same order
or in reverse order.  This is because in the scheme we
are discussing, a router never lists an LSA if the neighbor
already listed it (or should have listed it but didn't have it).

On average, each router will be in charge of listing each
LSA with probability 1/2 (but will leave a "hole" if it
doesn't have the LSA).  Each LSA will be listed (in a DD packet)
by at most one router (master or slave).
So, for a given LSA, let's compute the probability that
a router (master or slave) will list the LSA header,
the probability that it will request the LSA,
and the probability that it will send the LSA itself
(and not the LSA header) without receiving a request.
These probabilities are the *same* whether the two routers
list LSAs in the same direction or in opposite directions.

The probability that a router lists a given LSA header
is 1/2 if the router has the LSA in its database.
(The probability that the router does not have the LSA
is not considered here.)
A router will request an LSA only if the neighbor lists
the LSA header and has a newer instance, which
has probability 1/2 * 1/3 = 1/6.
A router will send the LSA without receiving a request
only if the neighbor lists the LSA header and has an
older instance (or the neighbor should list the LSA but
doesn't have it), which has probability 1/2 * 1/3 = 1/6.

We could compare these probabilities to plain Option A (without
the scheme that sends LSAs without receiving a request).
However, the main point is that these probabilities are
the same whether or not the master and slave list LSAs
in the same direction or in opposite directions.

Sure, using Mitchell's scheme (with either Option A or
Option C) can reduce the number of LSA headers listed
in DD packets and in LS request packets.
But as I mentioned in a previous message, bypassing
the LS request mechanism of OSPF can cause other
problems.  Otherwise, OSPF could have been designed to
avoid requesting an LSA by having the router with the newer
instance send the LSA to the router with the older instance.
If one router does not have any instance of the LSA,
then an ordering is needed to detect holes, and this
is similar to IS-IS, which seems to be a major change
to OSPF.

Richard

---

From: Erblichs <[email-masked]>
Date: Thu, 14 Sep 2006 20:32:57 -0700

Richard Ogier,

	We have a number of discussion points.

	Summary:

	I contend that the rev listing with "hole" support
	can remove the standard excessive LSA overhead IFF
	we know that the other router does not contain it.
	And due to the fact that most LSAs are external LSAs,
	over 90% of LSAs exist only within one LSDB and can
	be simply Updated, significantly decreasing the
	exchange process.

	So, with that said..

	1) I must be blind, but I do not see an explicit section
	   in any OSPF RFC to require each LSA hdr to be listed
	   in a DD pkt.
	   Thus, if a nbr has never advertised a originated LSA,
	    I am curious why that LSA would not want to be advertised
	    in just a Update pkt versus a need for a DD hdr,
	    explicit request, and then the Update..

	  Isn't the explicit LSA within a hdr more efficient for 
	  advertising this group of LSAs versus the hdr, req, and
	  then the LSA within the update pkt?????

	2) The functionality of looking for address ranges exist
	in ALL CLIs, so the ability to do this already exists.

	3) Hole functionality simply combines the above two items
	   during the LSDB exchange process.

	4) The hole that is being refered to is at the "END" of one
	  DD pkt by a nbr and at the "Begining" of the next by SLAVE
	  and/or MASTER. My testing tends to show that some LSA holes
	  are normally filled in by same directions, but flip/flop
	  as who's address value is higher at the end of each DD pkt.
	  This is why its better than both forward direction. 3%
	  of hdr compares are lost with DD pkt swithovers when 30 hdrs/DD
	  pkt over the linear method. Additionally, LSA matching could
	  occur while we are awaiting for the next pkt from our nbr
	  (in parallel). We don't need to FULLY process the pkt before
	  before sending our pkt. We only need to check seq, etc.. We
	  don't need to check 10s or hundreds of LSAs before responding
	  depending on the MTU size.

	  5) Extemely important. With a BMA envir that only has a DR,
	     as the DR goes thru the exchange process, the number of
             LSAs that it will ONLY have will increase to over 95% on
	     avg. It is accumalating all the LSAs from all the previous
	     exchanges.

	     Most of them are external LSAs that sit at the DR...

	Rev listing...
	Bottom line is a min 3% bwdth savings in DD hdr over linear listing,
	(30 LSAs hdrs per DD pkt) and easily a 50% hdr reduction in where two 
	routers have equal sized LSDBs (that need to have DD hdrs) over random 
	LSA listing without hole support. This is dependent on LSA addr
bunching.

	EXAMPLE........
	TOTAL COMBINED LSDB is 250k LSAs. 125k on each side, no LSAs in both.
	If Master increasing and 100K of its LSAs are bunched at the high-end
	and Slave is decreaing and most of its LSAs are at the low end. It
	is possible that by the time that 25k LSAs hdrs are listed by each
side,
	the other 200k of LSAs have been resolved. they filled the holes of
	the others. Thus, the exchange process decreasesd the normal hdrs
	from 250K to 50K, limited to the exchange of necessary Updates.

	Realize depending on LSA bunching, the number of LSAs resolved
	without hdrs could allow the exchange process to be limited by
	the smaller LSDB.

	Now inline...

	Mitchell Erblich
	
> these LSAs to the slave).

 First, my example was limited to DD pkt ends. It was done because
 a range/hole needs two values. I was concentrating on the hole
 from the end of DD pkt X and the starting hdr of DD pkt X + 1.
 Only the rev scheme works with the DD pkt ends.

 I assume that any other hole (between ANY two consective values within
 the DD pkt) could be detected by the other nbr
 and added to a explicit update pkt.

 However, it seems that NORMAL address collisions would be occuring
 if both move in the same direction. I have to assume that the slave
 would fill a hole and then adv via hdrs addresses that are beyond
 the master's end hdr address. This is a flip flop from above.

> list LSAs in the same forward order.

  Does it work well in the same forward order? Yes. However, not
  the best. Because of flip flops and address discontinuity.
  Thus, yes even same forward order can staticly eliminate most
  un-necessay LSA hdrs. Howver, given a large enough LSDB, 
  flip/flops will occur and the end LSA hdr/begining LSA hdr
  will periodicly remove a large number of LSA hdrs. Moving
  forward forces each LSA to be listed though. Routers tend
  to have LSA values bunched around each other due to having
  common network addr portions and it is the change of of the
  network portion that gives us the best holes.

> only that using reverse lex order does not help.)

 If a LSA gets flooded IMMEDIATELY AFTER LSDB exchange,
 would it have been more efficient if it arrived a ms earlier?

 If we KNOW that the LSA has never been seen by the other
 router, do we really need the overhead?

> (or the slave has no instance) with probability 1/3,

Then how do we allow the Master to send the LSA to
the slave in the most efficient manner? If the slave
created a hole that this LSA fits into, it then can
be added to a Update pkt.

Else, it will be listed as a LSA hdr and then requested.

%50 / %50

> the master has the same instance as the slave with probability 1/3,

No changes.. Needs to be listed as a DD pkt hdr, by 1 and not
the other. Reviewed and not requsted.

> (or the master has no instance) with probability 1/3.

  Not sure I like the 1/3rds.. Why? First, you
  have a static LSDB exchange example. The number
  of LSAs accumalate with the DR as the number of
  exchanges take place.

  Lets assume that all routers have an equal number of LSAs
  to be advertised with your 1/3 split.

  As the DR goes thru the LSDB exchange the number of
   LSAs that are within ONLY one LSDB is going to increase.

  So, even as you may start with a 1/3 split, the number
  of LSAs within 1 LSDB is going to increase to over 7/8.
  In addition , if a router were a ABR or a ASBR the number
  percentage is going to increase.

  Lastly, most LSDBs that include external LSAs are going
  to be in one LSDB and since they are a signficant majority,
  I think the number of LSAs in one or the other is closer
  to 90%. Compensating for the DR/BDR and a 2nd adj with
  the BDR decreases to 80%. 

> the slave sends the LSA to the neighbor.

I am confused.. If Master has stopped at 172... and
slave does 174.x.x.x. Can the Master continue at 172. next host
addr??? This seems wierd to me...

 Ok, you are increasing from where the master stopped
ok. 1 of 30 LSAs are at the end which places 3.3% of LSAs
at the end. So, their is a 3.3% chance that each LSA after
number 30 was not needed. Basicly, if the next LSA was going
to be 40 but did not fit in the DD pkt, then 31 thru 39
were un-necessary listed as hdrs.

If the slave would have been working from the higher end,
the DD pkt by the Master would be continuous. This effectively
would remove the 3.3% holes and allow the Master to
list from 1 to 500 and the slave from 1000 to 501.

> already listed it (or should have listed it but didn't have it).

But you are missing the discontinous ends. The greater the number
of LSAs hdrs per DD pkt the smaller the discontinuity. Mine..

Think of Master 1   - 30
	 Master 31 - 60
         Master 61 - 90 

What we have here are LSA hdr counts. Between 30 and 31, between
60 and 61, between 90 and ... We have array ranges. The next
DD pkt is needed to identify whether the OTHER end of the addr
range.

With yours, the range from 30 to 31 is a hole. Their could be
100s of hdrs that could be theorectly advertised within a Update
without anything else.

This is a 3%+ hdr saving. Or really removing a hdr listing by
the slave, a hdr processing by the master, a req by the master,
a req processing from the slave, and now a Update.

This results in about a 10% performance increase if the holes
are equal in size over both increasing.

> by at most one router (master or slave).

The hole is a address range between 2 LSA address values. Thus,
a hole could consume the entire address space of the other
router. Thus, I could see a Master generating a DD pkt that
has two consective hdrs within 30 and 31 that would
remove the need for the slave to list most of its hdrs.

> list LSAs in the same direction or in opposite directions.

No... No. The rev is approx 3% less bandwith on a random set
of LSAs (Moys's simulator) and 10% better performance.

> (The probability that the router does not have the LSA

	I am only concerned with in one LSDB and not the other.

	Extreme example: compare the number of LSAs 
	that are only in the DR before the last exchange.
	And no BDR.

	Over 97% are in one LSDB and not the other.

> problems.  

	Then identify them and lets see if they are
	easily fixable.

>Otherwise, OSPF could have been designed to

---

From: Richard Ogier <[email-masked]>
Date: Tue, 26 Sep 2006 08:42:23 -0700

Mitchell,

My draft describes a simple, backward compatible change
to OSPF, which does not require any new option bits.

I do not want to propose a major change in the way two routers
becomes synchronized, as you propose.  I would rather keep the LSA
request mechanism of OSPF, i.e., send an LSA only if the neighbor
requested it.  Bypassing this mechanism might cause problems.
For example, suppose a router becomes a DR and forms adjacencies with
100 neighbors.  Also suppose that all neighbors have an LSA that the
new DR does not have.  In OSPF, the new DR could decide to request
the LSA from only one of its neighbors, but in your proposal it is
possible (depending on the timing) that all 100 neighbors will send
the LSA to the new DR without any request. In any case, I would not
want to include such a major change in my draft.  You could write
your own draft and try to garner support for this.

I don't agree that only the reverse order scheme detects holes
at the ends of DD packets.  For example, suppose the master
lists LSAs 1 to 30 in its first nonempty DD packet, and also
has LSA 31.  Suppose the slave does not have LSA 31 (a hole)
and thus lists LSAs 32 to 61 in a DD packet.
Then the master will detect the hole, i.e., will know that
the slave does not have LSA 31.
You might argue that this would not work if the master was
missing LSA 31 instead of the slave, and therefore this works
only half the time.  But similarly, the reverse order scheme
works only half the time since the master will list the lower
address LSAs while the slave lists the higher address LSAs,
so the master will only detect the slave's holes for the higher
address LSAs (and not for the lower address LSAs).

Another (perhaps cleaner) solution is to include the address
range in each DD packet, which is what IS-IS does.
This allows holes to be detected at the ends of DD packets even if
all LSA headers fit into one or two DD packets (unlike your method).
(The endpoints of the range can be included in an LLS TLV.)

BTW, I have decided to exclude Option B from my draft (in which
the router with larger DR level first lists all of its LSAs),
since it does not provide much advantage over Option A.
(Also, it has a potential problem if the DR level of one of
the routers changes during database exchange.  If Option B were
changed so that the *Master* always lists its LSAs first, as Erblich
suggested, then it would have even less advantage over Option A since
there is no reason to expect that the Master's database is more
current than the Slave's.) I plan to submit an updated draft soon.

Richard