Re: [OSPF] Database Exchange Summary List Optimization

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

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

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,
the master has the same instance as the slave with probability 1/3,
and the slave has a newer instance than the master
(or the master has no instance) with probability 1/3.

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

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

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