Re: [OSPF] Database Exchange Summary List Optimization

[Acee Lindem <[e-mail]>]

Mitchell Erblichs,

See responses inline.

Erblichs wrote:
> Acee Lindem,
>
> 	two inline sections..
>
> 	Mitchell Erblich
> 	----------------
>
> Acee Lindem wrote:
>   
>> Hi Mitchell,
>>
>> See inline.
>>
>> Erblichs wrote:
>>     
>>> 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.
>>>
>>>       
>> 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?
>>
>>     
>
> 	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"?
>   
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 .
 
>
>   
>>>       ** 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.
>>>
>>>       
>> 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.
>>
>>     
>
> 	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???? 
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
> 	when the two routers are approaching the LSDB space in 
> 	different directions.
>
> 	Mitchell Erblich
> 	-----------------
> 	
>
> 	
>   
>> Thanks,
>> Acee
>>
>>     
>>>       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