Re: [OSPF] Database Exchange Summary List Optimization

[Erblichs <erblichs at earthlink.net>]

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 at ietf.org
https://www1.ietf.org/mailman/listinfo/ospf