Re: [OSPF] Database Exchange Summary List Optimization

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

Erblichs wrote:

>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
>	
>Richard Ogier wrote:
>
>>Erblichs wrote:
>>
>>>      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
>>>      -----------------
>>>
>>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).
>>
>
> 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.
>
>>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.
>>
>
>  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.
>
>>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.)
>>
>
> 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?
>
> 
>
>>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,
>>
>
>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.
>
>
>>and the slave has a newer instance than the master
>>(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%. 
> 
>
>>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.
>>
>
>
>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.
>
>
>>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).
>>
>
>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.
>
>>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).
>>
>
>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.
>
>
>>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.
>>
>
>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 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.)
>>
>
>	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.
>
>>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.  
>>
>
>	Then identify them and lets see if they are
>	easily fixable.
>
>>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
>>
>>>
>>>
>>>
>>>
>
>

_______________________________________________
OSPF mailing list
OSPF@ietf.org
https://www1.ietf.org/mailman/listinfo/ospf