Re: [OSPF] Database Exchange Summary List Optimization

[Erblichs <[e-mail]>]

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

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