Re: [OSPF] Database Exchange Summary List Optimization

[Richard Ogier <[e-mail]>]

Erblichs wrote:

>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 
>
>>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.
>>
>
>However, the 2nd justification for option 2 is:
>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.
>>
>
>---> 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'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
>this new functionality.
>
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.

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

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

>
>- 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.
>
Again, you are saying to avoid the LS request mechanism of OSPF,
which I don't think is a good idea.

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

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

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

>
>
>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
>-----------------
>	
>
>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.
>>
>>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."
>>
>>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      [e-mail]   [e-mail]  Key ID: 64A2FF6A
>>Fortune:
>>There are few people more often in the wrong than those who cannot endure
>>to be thought so.
>>
>>_______________________________________________
>>OSPF mailing list
>>[e-mail]
>>https://www1.ietf.org/mailman/listinfo/ospf
>>
>
>



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