Re: [OSPF] Database Exchange Summary List Optimization

[Erblichs <[e-mail]>]

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

Acee Lindem wrote:
> 
> Hi Mitchell,
> 
> 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.
> >
> 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
> 
> >       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
> >
> >

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