Subject: [OSPF] Preliminary idea: OSPF Database Exchange : Pre-Step

From: Mitchell Erblich <[email-masked]>
Date: Mon, 20 Apr 2009 19:10:12 -0700

Group,

		General thoughts...

		After a conversation about OSPF's standard database exchange and how  
inefficient it
		is when two routers have large LSDBs and them almost being the same,  
we concluded
		that the use of Checksums might significantly decrease the amount of  
overhead and
		achieve faster convergence.

			Moy first (I think) suggested the LSDB checksum support to identify  
identical
			LSDBs.  Sometime later the MIB supported the ospfExternLsaChksumSum,
			ospfAreaLsaChksumSum, and ospfLsdbChecksum fields.

			Thus, why not support the ability to have OSPF routers first exchange
			checksums with LSA counts. If the LSDBs have more than XYZ entries
			in their LSDBs, then the counts which are above specific thresholds  
then
			support the checksum on each X count of LSA type. Only the groups
			with non-matching Checksums would then go thru database exchange.

			Thus, before database exchange, support some form of triple that
			as routers have almost the same LSDBs,   the checksum exchange
			 would remove unnecessary LSA header exchange.

			This, IMO, would also be a big win if say a DRother was adjacent,  
lost
			adjacency, and re-exstablished it a short time later while keeping a
			past snapshot. It could remove its own originated LSAs and compare
			checksums..

			In this scenario, within BMA areas, I think only DR / DRother and  
BDR/ DRother
			need to be making this Checksum exchange..

			Wouldn't the exchange of this data benefit each router receiving the
			information and allow both routers to know the number of LSAs to
			be possibly exchanged?
			
			Yes, a new capability would probably have to be added.

			So, the first question is whether the checksums are unique enough  
with a
			count and type to determine whether that section of the LSDB matches
			between two routers?

			And then what savings would normally exist in this hybrid database  
exchange
			and is it worth the effort?

		Mitchell Erblich

---

From: Anton Smirnov <[email-masked]>
Date: Tue, 21 Apr 2009 19:29:42 +0200

Mitchell,
   LSDBs may be very close but they are seldom EXACTLY the same. The
thing is that change in adjacency triggers LSA [re]build, so depending
on timing router and/or network LSAs may change by the time adjacency
restores.
   Also, in moderately sized modern OSPF network there is constant
background noise of LSAs being refreshed. So again, chances that
refreshed LSA arrived to one side but not another while adjacency is
down are relatively high.
   These considerations make precomputed checksums over large number of
LSAs rather bad for the purpose.
   If you want to explore venue of checksumming database exchange then I
recommend to look for more flexible approach giving routers possibility
to choose range of LSAs to compute checksum over. For example, if both
routers support the checksum exchange then router sending DBD could
specify the first, the last LSA and value of some kind of hash of LSA
headers between them (LSAs in LSDB can be viewed as ordered sequence as
per RFC 5243). In this way router preparing DBD packet may place start
and end points of checksumming to avoid including into the range LSAs
with ages around 0 and MAXAGE (because these are LSAs which are less
likely to match between routers). So database exchange will consist of
series of single LSA headers (the 'old' way) and large LSA sequences.

Anton

Mitchell Erblich wrote:
> Group,
> 
>         General thoughts...
> 
>         After a conversation about OSPF's standard database exchange and
> how inefficient it
>         is when two routers have large LSDBs and them almost being the
> same, we concluded
>         that the use of Checksums might significantly decrease the
> amount of overhead and
>             Moy first (I think) suggested the LSDB checksum support to
> identify identical
>             in their LSDBs, then the counts which are above specific
> thresholds then
>             This, IMO, would also be a big win if say a DRother was
> adjacent, lost
>             In this scenario, within BMA areas, I think only DR /
> DRother and BDR/ DRother
>             So, the first question is whether the checksums are unique
> enough with a
>             And then what savings would normally exist in this hybrid
> database exchange
> _______________________________________________
> OSPF mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ospf

---

From: Richard Ogier <[email-masked]>
Date: Sun, 26 Apr 2009 17:22:17 -0700

Anton,

I like your idea of sending a checksum for a range of LSAs, to
increase the probability that the LSAs in a given range are in
sync between the two neighbors.  (This helps even if the
age field is ignored when selecting the ranges.)

For example, suppose there are 100 LSAs and each LSA has a 2%
chance of not being in sync.  Then the probability that all
LSAs are in sync is .98^100 = .1326, too low to result in
a significant overhead reduction.
Now suppose the LSAs are divided into 10 ranges, each with 10 LSAs.
The probability that all LSAs in a given range are in sync is then
.98^10 = .8171, resulting in a big overhead reduction on average.

The selected range for each LSA type can depend on how frequently
new LSAs are originated for that type, with a larger range chosen
if LSAs are originated less frequently (so that the probability
of being out of sync is lower).

This idea can be combined with the database exchange optimization
of RFC 5243 to further reduce overhead.  I.e., if the checksums
do not match, then RFC 5243 can be used to reduce the number of
LSA headers exchanged in DD packets by up to 50%.
Also, if the checksums do match for a given range of LSAs, then the
router receiving the checksum need not send the same checksum for
the same range of LSAs.

Richard

---

From: Emmanuel Baccelli <[email-masked]>
Date: Mon, 27 Apr 2009 09:57:27 +0200

Hi Anton,
yes, a similar scheme was studied a few years back, in this paper:
OSPF Database Exchange and Reliable Synchronization in Mobile Ad Hoc
Networks <http://www.emmanuelbaccelli.org/publications/WNET_2004.pdf>

Such a mechanism could indeed lead to interesting performance enhancements,
I agree with Richard.

cheers,

Emmanuel

---

From: Mitchell Erblich <[email-masked]>
Date: Mon, 27 Apr 2009 07:47:35 -0700

Group,

	First my thoughts are currently in the inception phase
	and COULD apply to both wired and wireless
	environments and I applogize for my verboseness.

	My initial assumptions are that a OSPF area will be
	majority built using the common Ethernet (BMA) environment
	and once a OSPF area is formed major LSA changes are rare.

	Second is that the LSDB is comprised of say 50k LSAs
	which are mostly/90% ExternalLSAs. Thus, Anton, I do not think
	your numbers are correct. If we had routers forming adjs
	via standard LSDB exchange each 100k LSAs sum exchange with
	DR/BDR and using checksums. Then no ExternalLSA hdrs would
	need to be exchanged with the BDR, thus removing almost
	 50% from database exchange. FYI: We got them from the DR.

	My below inquiry stated a checksum per LSA type and
	the ability to generate subgroups of checksums per
	LSA type. Yes, it also stated a full LSDB checksum.

	Since the flooding of LSAs is mostly the same, even a few
	LSAs changing within the ExternalLSa type COULD be covered
	by specifying that the A-Y range did not change and the
	Z range has new hdrs/LSAs and updated normally.

	If the later/changes was false, during convergence, routing anomalies
	would be a major concern and data would be routed improperly
	or just lost. With OLD standardized TCP congestion avoidance
	algorithms, a single lost packet assumes congestion and
	assuming 100% bandwidth usage drops TCP to 50% with
	multiplicative decrease. Then a huge number of round trips
	before additive increase gets back to approx 100% bandwidth.
	Even changes in routing paths can generate out-of-orderness with
	the same result. Different hosts/end systems can have different
	Congestion Avoidance algorithms.

	Thus, if convergences are frequent then the utilization
	of each of the TCP connection paths would have frequently
	poor bandwidth usage. So the assumption is that once a
	OSPF area is formed, it tends to be UNCHANGING.

	I mentally prefer a predefined range such that routers
	can pre-compute the checksums before even the
	initial LSDB exchange. To predetermine where the
	breaks should exist is currently unknown.

	I see three possible major wins where checksums COULD
	be used.
	     The first is flooding from the DR to DRothers
	       to update the LSDB so the amount of flooding could
	       be minimized, with the same same effect of DNA LSAs.
		Effectively a group LSA refresh.
	  The second is when a DRother initially forms an adjacency
	      with the BDR and accepting that the ExternalLSAs would
	      be the majority of LSAs and the belief that the DRother
	      would already have the ExternalLSAs in its LSDB.
	   The third is when the DRother wants to just verify that
		no LSAs were lost due to either congestion, temp
		drop of the adj, etc and verfify that no-one has either
		given up rexmits or is still doing xmits. And to pick up
		a single dropped LSA without a full Database Exch.

	Getting back to the pre-computation would prevent a
	OSPF speaking router from doing the calcs at adj
	formation time. Even doing the calc at adj formation
	should remove say 90+% of LSAs from needing to
	be recomputed on each LSDB verify sync.

	However, to decrease the need to do the calcs at
	overhead, first checking whether LSA type counts
	match could be done and only if they match, then
	do the necessary computation. The type, count,
	and checksum, should generate some form of
	uniqueness. Some field within the begining and
	ending LSAs might add some more verifcation.

	So, what am I missing here? and why hasn't anybody
	done this?

	Mitchell Erblich
	===================

On Apr 27, 2009, at 12:57 AM, Emmanuel Baccelli wrote:

> Networks
> Such a mechanism could indeed lead to interesting performance  
> enhancements, I agree with Richard.
>
> cheers,
>
> Emmanuel
>
>
>

---

From: Anton Smirnov <[email-masked]>
Date: Mon, 27 Apr 2009 21:31:58 +0200

Richard,
   indeed, interaction with RFC 5243 can have multiple aspects.
   It is easy for routers to learn that neighbor supports checksumming
(via, say, some new option bit). But this is not enough to start sending
checksums, routers should first get an idea that their databases are
close enough (i.e. chance of being not in sync is closer to 2% than to
98%). This can come from knowledge external to the algorithm (say,
neighbor was recently fully adjacent but lost neighborship for a short
time). Or it can be part of the algorithm itself - routers start DBD
exchange the 'old' way and if during the exchange they get very good
hits for RFC 5243 optimization then they can measure how close are their
databases and if it makes sense to switch to batched exchange.

   Thanks,

Anton

---

From: Dave Katz <[email-masked]>
Date: Mon, 27 Apr 2009 18:20:56 -0500

On first principles, it seems as though the only reason to do  
something like this is to reduce the amount of time it takes to bring  
up a new link, and even that is probably only interesting if the  
network is at least slightly partitioned without it.  Keep in mind  
that such a scheme is only useful if the database is already close to  
synchronized, so it doesn't help when a router first comes up.  Given  
all that, it's not entirely clear that doing this is *that*  
interesting, but no matter.

The problem with any of these checksum schemes is that the benefits  
are compromised by the LSA refresh mechanism, as has been noted.  With  
50,000 LSAs, my back-of-the-laptop calculations are that an LSA is  
refreshed on the average of once every 36 msec, or roughly 30 per  
second.  Scalable implementations go out of their way to smooth  
refreshes when they are originating a large number of LSAs, and if  
there are a large number of machines originating a small number of  
LSAs, these will (hopefully) tend to be smoothed out as well, in a way  
that does not correlate with the ordering mechanism proposed.

The efficiency of such schemes improves as the number of LSAs per  
checksum block goes up, but so does the probability of a checksum  
failure, in which case you're actually worse off than if you'd just  
send the darned things (since you have to anyhow, unless you start  
doing scary bifurcations of the space, all of which takes more time,  
and all of which causes even more LSAs to be stale.)

If that 50K LSA network was represented as 30 checksum blocks, and it  
takes a second for the basic handshaking to take place with a  
neighbor, the odds are decent that *all* of them will fail, in which  
case it's a waste of time.  Keep in mind that if you want to avoid bad  
checksums, you need to make the block size small, and thus the number  
of blocks large, and then you end up back where you started from  
unless the checksum-exchange protocol is reasonably windowed as well.

If you want to improve adjacency bringup in a non-compatible way, it  
seems like a more effective mechanism would be simply to fix the brain- 
dead DBD protocol so that it is not stop-and-wait;  if you can pump a  
few hundred PPS of DBDs across the wire without stopping, you can sync  
up very quickly in terms of wall-clock time without getting into the  
inevitable problems caused by trying to glom LSAs together and  
expecting them to sit still in the process.  It seems a lot cheaper  
and more straightforward.

Bandwidth and CPU are practically free (particularly for something  
done relatively rarely) so trying to do heroic things to optimize such  
situations seems like a waste of effort.

Maybe I'm missing something fundamental here?

--Dave

On Apr 27, 2009, at 9:47 AM, Mitchell Erblich wrote:

>> OSPF Database Exchange and Reliable Synchronization in Mobile Ad  
>> Hoc Networks
>>
>>           Thus, why not support the ability to have OSPF routers  
>> first
>> exchange
>>           count and type to determine whether that section of the  
>> LSDB
>> matches
>>           between two routers?
>>

---

From: Anton Smirnov <[email-masked]>
Date: Tue, 28 Apr 2009 12:50:05 +0200

Hi Dave,
   I agree with you in most (but not all) statements.

> Bandwidth and CPU are practically free

   Unless you consider MANETs where bandwidth is not free and CPU
resources may also be relatively limited.
   Originally idea of checksumming was born in context of MANETs. And in
that environment exchange of database checksums may actually work  well.
   The first Mitchell's post was about network scenario NOT related to
MANETs but questioned how well that idea will work. So my post was more
to point out that no, idea conceived with MANET in mind will not work in
non-MANET environment. At least not until the idea is properly generalized.

> seems like a more effective mechanism would be simply to fix the
> brain-dead DBD protocol so that it is not stop-and-wait

   Agree.

>  if you can
> pump a few hundred PPS of DBDs across the wire without stopping, you can
> sync up very quickly in terms of wall-clock time without getting into
> the inevitable problems caused by trying to glom LSAs together and
> expecting them to sit still in the process.  It seems a lot cheaper and
> more straightforward.

   That's good only in case of homogeneous network of powerful routers
connected by high-bandwidth links.
   It is likely to give a lot of troubles in star topologies where one
router has many neighbors. Fast DBD flooding from spokes will just swamp
the hub router.
   And I have mentioned it is not going to work in case of MANETs.

   Of course, transport protocols have solved all these issues long time
ago. But we don't want to turn DBD into window-based protocol with slow
start, congestion avoidance and all the stuff :-)

   Thanks,

Anton

Dave Katz wrote:
> On first principles, it seems as though the only reason to do something
> like this is to reduce the amount of time it takes to bring up a new
> link, and even that is probably only interesting if the network is at
> least slightly partitioned without it.  Keep in mind that such a scheme
> is only useful if the database is already close to synchronized, so it
> doesn't help when a router first comes up.  Given all that, it's not
> entirely clear that doing this is *that* interesting, but no matter.
> 
> The problem with any of these checksum schemes is that the benefits are
> compromised by the LSA refresh mechanism, as has been noted.  With
> refreshes when they are originating a large number of LSAs, and if there
> are a large number of machines originating a small number of LSAs, these
> will (hopefully) tend to be smoothed out as well, in a way that does not
> correlate with the ordering mechanism proposed.
> 
> failure, in which case you're actually worse off than if you'd just send
> the darned things (since you have to anyhow, unless you start doing
> scary bifurcations of the space, all of which takes more time, and all
> of which causes even more LSAs to be stale.)
> 
> takes a second for the basic handshaking to take place with a neighbor,
> the odds are decent that *all* of them will fail, in which case it's a
> waste of time.  Keep in mind that if you want to avoid bad checksums,
> you need to make the block size small, and thus the number of blocks
> large, and then you end up back where you started from unless the
> checksum-exchange protocol is reasonably windowed as well.
> 
> seems like a more effective mechanism would be simply to fix the
> brain-dead DBD protocol so that it is not stop-and-wait;  if you can
> pump a few hundred PPS of DBDs across the wire without stopping, you can
> sync up very quickly in terms of wall-clock time without getting into
> the inevitable problems caused by trying to glom LSAs together and
> expecting them to sit still in the process.  It seems a lot cheaper and
> more straightforward.
> 
> Bandwidth and CPU are practically free (particularly for something done
> relatively rarely) so trying to do heroic things to optimize such
>>> On Mon, Apr 27, 2009 at 2:22 AM, Richard Ogier <[email-masked]
>>> <mailto:[email-masked]>> wrote:
>>>
>>>     Anton,
>>>
>>>                       Thus, why not support the ability to have OSPF
>>>             routers first
>>>             exchange
>>>                       checksums with LSA counts. If the LSDBs have
>>>             more than XYZ
>>>             entries
>>>                       support the checksum on each X count of LSA
>>>             type. Only the
>>>             groups
>>>                       with non-matching Checksums would then go thru
>>>             database
>>>             exchange.
>>>
>>>                       Thus, before database exchange, support some
>>>             form of triple
>>>             that
>>>                       adjacency, and re-exstablished it a short time
>>>             later while
>>>             keeping a
>>>                       past snapshot. It could remove its own
>>>             originated LSAs and
>>>             compare
>>>                       checksums..
>>>
>>>                       Wouldn't the exchange of this data benefit each
>>>             router
>>>             receiving the
>>>                       information and allow both routers to know the
>>>             number of
>>>             LSAs to
>>>                       be possibly exchanged?
>>>                       count and type to determine whether that
>>>             section of the LSDB
>>>             matches
>>>                       between two routers?
>>>
>>>             [email-masked] <mailto:[email-masked]>
>>>         [email-masked] <mailto:[email-masked]>
>>>     [email-masked] <mailto:[email-masked]>
>>> [email-masked] <mailto:[email-masked]>
>> [email-masked] <mailto:[email-masked]>
> ------------------------------------------------------------------------
>

---

From: Dave Katz <[email-masked]>
Date: Tue, 28 Apr 2009 18:50:34 -0500

> non-MANET environment. At least not until the idea is properly  

I guess I'd be impressed with a network that had 50,000 LSAs but very  
limited bandwidth and CPU.  I have a feeling that such a network would  
have bigger problems than the time it takes to bring up an additional  
link.

>> and

But this is no different than the situation with LSUpd packets today,  
and needs to be solved in the same way (hack.)  We used to deal with a  
much worse situation ten or fifteen years ago, which were sizable full  
meshes.  If it were easy, we wouldn't make any money doing it.  ;-)

--Dave

>> something
>> are
>> there
>> send
>> neighbor,
>> and
>> done
>>>> Hoc
>>>> Networks <http://www.emmanuelbaccelli.org/publications/WNET_2004.pdf 
>>>> >
>>>>
>>>>        routers support the checksum exchange then router sending  
>>>> DBD
>>>>        could
>>>>                  After a conversation about OSPF's standard  
>>>> database
>>>>            exchange and
>>>>            how inefficient it
>>>>                      Moy first (I think) suggested the LSDB  
>>>> checksum
>>>>            support to
>>>>            identify identical
>>>>                      in their LSDBs, then the counts which are  
>>>> above
>>>>            specific
>>>>            thresholds then
>>>>                      So, the first question is whether the  
>>>> checksums
>>>>            are unique
>>>>            enough with a

---

From: Mitchell Erblich <[email-masked]>
Date: Wed, 29 Apr 2009 04:24:34 -0700

Group,

	Sorry, verbose..

	Inline..

	Mitchell Erblich
	===============
On Apr 27, 2009, at 4:20 PM, Dave Katz wrote:

> something like this is to reduce the amount of time it takes to  
> bring up a new link, and even that is probably only interesting if  
> the network is at least slightly partitioned without it.  Keep in  
> mind that such a scheme is only useful if the database is already  
> close to synchronized, so it doesn't help when a router first comes  
> up.  Given all that, it's not entirely clear that doing this is  
> *that* interesting, but no matter.

Actually, the first thought was how to verify that two LSDBs are  
identical at ANY time after Database Exchange.
And if not first what are the differences wrt LSA type and count. And  
have the router periodicly report / summarize
any seen diffs.

Then how to resynch without waiting for the LSA update or renewing  
(tear down and reforming the adj) the adj

However, if you can then resync, you should be able to do refreshes  
from the DR and BDR (common Eth).

However, the first interaction between two OSPF speakers is with  
Database Exchange and decreasing the
workload on the 2nd adj due to common LSAs should allow the formation  
of 2x simulateneous adj formations
than standard.

> are compromised by the LSA refresh mechanism, as has been noted.   
> With 50,000 LSAs, my back-of-the-laptop calculations are that an LSA  
> is refreshed on the average of once every 36 msec, or roughly 30 per  
> LSAs, these will (hopefully) tend to be smoothed out as well, in a  
> way that does not correlate with the ordering mechanism proposed.

First, 50k was just a number picked that would identify a common large  
number of LSAs of a specific type(Externals)
  (also the major of LSAs in the LSDB) that should all match and not  
have any new DRother add to this LSA type pool.

The simplified assumption is that the updates are just age refreshes.

I am not sure that this/checksums would be a better approach then say  
DNA LSAs. The chksum approach fits better
IMO in this case when a router stops rexmits of the LSA and has taken  
down the adj. The DRother either would
have to renew the adj or implement a search for the lost LSA.

In the common case of Eth, with your flooding example, in my limited  
experience, the OSPF routers tend to
initially come up within the area at the same time and thus iniitally  
the LSAs are mostly flooded within the
same quarter hour, if not within the first 5 minutes. Thus, peaks of  
LSAs per second would be on the order
of 200 LSAs per sec.

Since the chksum is even simpler than a LSA hdr, I would expect more  
than a 100 to 10kx LSA processing of
just LSA age refreshes should be able to be accomplished with the same  
level of work.

Somewhere in these numbers is a meltdown by a router with standardized  
OSPF, where I question whether
the chksum approach would have the same failure behaviour.

> and all of which causes even more LSAs to be stale.)

The assumption is that a checksum is specified for the entire LSDB,  
then a chksum for all the LSAs of a specified
type, then a breakdown of each type. If we have Eth, we have a  
1500byte packet. We have no LSA lookups if
we can can match each table line. If we add additional values like LSA  
count, LSA type, etc, to each group
checksum, then the same chksums that map to different sets of LSAs  
should be minimized. Remember, we
need a double failure/mapping because not just the group must map  
identically but the chksum over the
entire LSA type.

FYI, yes, I know about the 64k byte offset of IP, but I don't want  
reassembly overhead so a limit of 1.5k.

What the additional groups get us, is the ability to locate request  
entire LSA groups without needing
all of the LSAs. The smaller the group, then  the smaller number of  
extra LSAs that we really don't
need but with more table lookups.

YES, the complication is the CORRECT number of LSAs needed in a block  
to minimize a duplicate mapping,
where all items in the table line match, but the set of LSAs don't  
match within the group.

>
> If that 50K LSA network was represented as 30 checksum blocks, and  
> it takes a second for the basic handshaking to take place with a  
> case it's a waste of time.  Keep in mind that if you want to avoid  
> bad checksums, you need to make the block size small, and thus the  
> number of blocks large, and then you end up back where you started  
> from unless the checksum-exchange protocol is reasonably windowed as  
> well.

Actually, how long does it take to process 1 1500 byte packet and do  
say 100 table lookups. The key here is that not
the entire LSDB summary needs to be exchanged per packet. We could say  
that every 15 secs the next set of groups
is xmit'ed and every x minutes you cover all the LSAs via the  
groupings. So, I would expect less than 10ms to processs
each packet.

> pump a few hundred PPS of DBDs across the wire without stopping, you  
> can sync up very quickly in terms of wall-clock time without getting  
> into the inevitable problems caused by trying to glom LSAs together  
> and expecting them to sit still in the process.  It seems a lot  
> cheaper and more straightforward.

The wireless win is the minimum number of bytes that COULD then be  
sent over the connection and the ability
to have dropouts and verifications that the LSDB is in sync and if  
not, why not.

With a protocol like OSPF that has aged, I would think that simpler  
approaches to
scale them in a transparent way would make more sense.

With chksums, I would think that a DRother forming an adj with a BDR  
after the DR, should be able to
do this within just a few 100 packets. If the fastpath allows a common  
read-mostly table lookup and can
remove 90% of LSA hdr exchanges, then the ability for the BDR to  
support 100+ simultaneous adj formations
should sum to your 100s of packets per sec rate.

With the ability to not send say 100s packets before a response to a  
DRother
during database exchange prevents the DR and/or BDR to FLOOD/overload
  the DRother with LSAs. TCP's slow start is a multiplicative increase  
to identify
not just un-used capacity but also buffer capacity. If a flood of 100  
packets is
jjust sent, and they are fragmented, they really need to be  
reasembled, etc.
This is assuming no tail drop or RED, where a dropped fragment requires
the sending of the entire packet/segment. The problem is not all  
routers would
have the same pps capacity and if they did and say 5 DRothers  
implement your
flooding to a single DR, wouldn't that be a problem? With a ACK based  
protocol,
the two communicating end points can add small latencies as needed and
prevent one end point to overwhelm the other end point. Lastly, the  
amount of
CPU cycles needed to process 100 pps tends to be greater than xmiting  
the
100 pps rate.

Within an area, the assumption is
that the link/media connection is probably at 1ms or less and thus the  
round-trip-time should not
be a concern. If the DRother and DR/or/BDR processes the packet within  
say 1ms each, then
the sum of packets per connection should easily reach your 100s of  
packets per sec.

Yes, with a ACK like protocol, having the the ability to poll or  
generate just 1 interrupt
for x number of packets can not be done with only 1 set of concurrent  
connections. If
you had say 100 simultaneous adj formations, yes you can then  
implement the above.

> done relatively rarely) so trying to do heroic things to optimize  
> such situations seems like a waste of effort.

The above SHOULD use a fraction of the bandwidth and CPU. The gains of  
doing so is the ability
to verify that all the LSDBs are in synch within the area every sec.  
The decrease of bandwidth
is a decrease in latency when differences exist and the ability to  
correct them quickly. IF flooding
uses 1% of a CPU, we then have 99% to recompute routing changes. With  
1Gb and faster Eth
media, having short convergent cycles is imperative. With this  
additional CPU cycles and low cost
memory, we have the abiltiy to compute backup routes. And to be able  
to separate the LSA
updates into age updates versus content updates. The later need to be  
processed as a high
priority and moving the former into Chksum verification, should be  
able to take LSA content
changes and reconverge the area within a subsec timeframe.

However, alot of end systems (and routers) are or becoming mobile and  
their bandwidth is in the
kilobytes/sec capabilities, have expected dropouts, and we still need  
to route to them. Thus adding
downward scalability shouldn't be a negative.

>>>           Thus, before database exchange, support some form of  
>>> triple
>>> that

---

From: Dave Katz <[email-masked]>
Date: Wed, 29 Apr 2009 10:34:22 -0500

On Apr 29, 2009, at 6:24 AM, Mitchell Erblich wrote:

> And if not first what are the differences wrt LSA type and count.  
> And have the router periodicly report / summarize
> any seen diffs.

This already happens by magic over a 60 minute period, and is  
unnecessary in any case unless the implementation is broken (in which  
case, adding additional complexity is not likely to improve it.)

> (tear down and reforming the adj) the adj

A generalized refresh mechanism would make things like hot standby  
much easier (it's very tricky to do without it) but seems to be  
orthogonal to what is being presented here, as you could easily use  
the existing mechanisms to leverage a refresh-without-teardown scheme.

> from the DR and BDR (common Eth).

I don't understand what you think is special about the DR or BDR as  
opposed to any other adjacent router.  DR-ness is just an adjacency  
pruning hack, nothing more.

> workload on the 2nd adj due to common LSAs should allow the  
> formation of 2x simulateneous adj formations
> than standard.

>> With 50,000 LSAs, my back-of-the-laptop calculations are that an  
>> LSA is refreshed on the average of once every 36 msec, or roughly  
>> 30 per second.  Scalable implementations go out of their way to  
>> smooth refreshes when they are originating a large number of LSAs,  
>> and if there are a large number of machines originating a small  
>> number of LSAs, these will (hopefully) tend to be smoothed out as  
>> well, in a way that does not correlate with the ordering mechanism  
>> proposed.
>
> First, 50k was just a number picked that would identify a common  
> large number of LSAs of a specific type(Externals)

Refreshed LSAs are no different than LSAs with significant changes,  
from the standpoint of flooding--even if the contents haven't changed,  
they still need to be flooded and the identities of those to be  
flooded need to be ascertained.  The fact of the matter is that the  
LSDB entropy grows with the size, and very large databases are very  
entropic, and thus resistant to any sort of blocky verification.

>
> I am not sure that this/checksums would be a better approach then  
> say DNA LSAs. The chksum approach fits better
> IMO in this case when a router stops rexmits of the LSA and has  
> taken down the adj. The DRother either would

I'm lost here.  What "lost LSA" are we searching for?  Why would a  
DROther not learn it in any case (from any other box with which it is  
adjacent)?

> initially come up within the area at the same time and thus  
> iniitally the LSAs are mostly flooded within the

That's not my experience, but even if it were, our implementation  
rapidly covers this up so that there are no LSA peaks.  Refreshes are  
smeared smoothly across the refresh period precisely to avoid peaks,  
but of course this causes worst-case LSDB entropy.

Keep in mind that this flooding load is per-adjacency as well.

> just LSA age refreshes should be able to be accomplished with the  
> same level of work.

But LSA processing is simply not that costly.

>
> Somewhere in these numbers is a meltdown by a router with  
> standardized OSPF, where I question whether

OSPF meltdowns in my experience are not caused by a lack of CPU;  they  
are caused by poor queueing and memory management behavior and stupid  
implementations that forget to send Hellos when they are busy.

>> doing scary bifurcations of the space, all of which takes more  
>> time, and all of which causes even more LSAs to be stale.)
>
> we can can match each table line. If we add additional values like  
> LSA count, LSA type, etc, to each group
> YES, the complication is the CORRECT number of LSAs needed in a  
> block to minimize a duplicate mapping,

I don't really follow all this, but I'll point out once again that  
because of refresh smoothing, the probability that *any* blocking  
scheme will work is very low when there are large numbers of LSAs.

>> neighbor, the odds are decent that *all* of them will fail, in  
>> which case it's a waste of time.  Keep in mind that if you want to  
>> avoid bad checksums, you need to make the block size small, and  
>> thus the number of blocks large, and then you end up back where you  
>> started from unless the checksum-exchange protocol is reasonably  
>> windowed as well.
>
> the entire LSDB summary needs to be exchanged per packet. We could  
> say that every 15 secs the next set of groups

You're completely missing the point, I think.  Or maybe I am.  In 15  
seconds in a 50K LSA network (at least with our routers) there will be  
400 changed LSAs, randomized across however you divide things into  
blocks.  If there are less than O(400) blocks, the probability of any  
of them being unchanged is poor.

>
>>
>> If you want to improve adjacency bringup in a non-compatible way,  
>> it seems like a more effective mechanism would be simply to fix the  
>> brain-dead DBD protocol so that it is not stop-and-wait;  if you  
>> can pump a few hundred PPS of DBDs across the wire without  
>> stopping, you can sync up very quickly in terms of wall-clock time  
>> without getting into the inevitable problems caused by trying to  
>> glom LSAs together and expecting them to sit still in the process.   
>> It seems a lot cheaper and more straightforward.
>
> do this within just a few 100 packets. If the fastpath allows a  
> common read-mostly table lookup and can
>  the DRother with LSAs. TCP's slow start is a multiplicative  
> increase to identify
> not just un-used capacity but also buffer capacity. If a flood of  
> 100 packets is
> flooding to a single DR, wouldn't that be a problem? With a ACK  
> based protocol,
> CPU cycles needed to process 100 pps tends to be greater than  
> xmiting the
> 100 pps rate.
>
> that the link/media connection is probably at 1ms or less and thus  
> the round-trip-time should not
> be a concern.

The RTT on most networks I've seen are 10s or 100s of msec (they are  
geographically diverse.)  If you're using slow media (which I thought  
was one of the points of the exercise) the latency is also very high.   
A 1500 byte packet on a 56K link has over 200 msec of latency even  
before the speed of light comes into play.

> If the DRother and DR/or/BDR processes the packet within say 1ms  
> each, then
> for x number of packets can not be done with only 1 set of  
> concurrent connections. If
> The above SHOULD use a fraction of the bandwidth and CPU. The gains  
> of doing so is the ability
> uses 1% of a CPU, we then have 99% to recompute routing changes.  
> With 1Gb and faster Eth
> updates into age updates versus content updates. The later need to  
> be processed as a high
> However, alot of end systems (and routers) are or becoming mobile  
> and their bandwidth is in the
> kilobytes/sec capabilities, have expected dropouts, and we still  
> need to route to them. Thus adding

IMHO, you have a solution looking for a problem here, and the solution  
seems to be uninteresting.

There's lots of talk about CPU optimization, and while it may be true  
that something could take 50% less CPU, if that thing is only taking a  
nominal amount of CPU to begin with (and is not the long pole in the  
tent) that optimization may be uninteresting.

OSPF as a whole doesn't scale well for large networks with small,  
unreliable bandwidth, and any scheme to improve initial database  
synchronization is only a patch on a much larger problem.

Rather than coming up with a one-off fix for part of the protocol  
(which may not even be viable), it seems like the right thing to do is  
to start on first principles.  What problem are you trying to solve,  
on the large scale?  Is OSPF (or link-state routing in general) a good  
match for solving this problem?  What other kinds of things need to be  
fixed in that problem space?

But that's just my opinion...

--Dave

---

From: Anton Smirnov <[email-masked]>
Date: Fri, 01 May 2009 00:12:05 +0200

Hi Dave,

link.

   In the context of this discussion example with 50000 LSAs does not
interest me at all, MANET or not. Not because it is a difficult case.
Vice versa, it is unrealistically too optimal case.

>>> checksum-exchange protocol is reasonably windowed as well.

   Not at all. Refreshed LSAs are easy to exclude from checksumming on
both sides exactly because they are known to be young. Let me do MY math :-)
   Suppose LSDB of routers were in sync N seconds ago. In this case LSA
ages for older LSAs should be within N +- InfTransDelay. Lets take a
value k with sufficiently big margin, say 15.
   Router sending DBD places start and end points of checksumming range
so that the range does not cover any LSAs with age of N +- k  (but may
cover LSAs with age less than N-k; those are 'new' refreshed LSAs).
After that checksum is calculated over the range but LSAs with age less
than N-k are not included into the checksum.
   Router receiving DBD will have N and start/end points. It too
calculates the checksum over the range excluding from it LSAs with age
less than N.
   Value of 2k is << MaxAge (1-2%), hence it is very easy to choose
range with good chances of eligible LSAs in the range being in sync.

   As for the value of N - it can be known from prior events or it can
even be estimated dynamically.
   If a router receives DBD describing LSA with age n and finds this LSA
in its LSDB then it is not unreasonable to expect that n seconds ago
LSDBs were in sync. Hence N can be set to n. There are some scenarios
where this assumption fails, for example if adjacency was terminated
while LOADING. But estimation is good enough to try using this for
sending older LSAs as checksum ranges.

   You may wonder what's my point :-)
   My point is that technically idea of checksumming can be made
working. And it will work the better the more LSAs are in LSDB.
   The downside of it is that it is not backward compatible. So the
question is if this scenario needs to be solved even if it can be
solved. Or if it needs to be solved by checksumming, by complicating DBD
packet serialization or by some other means.

   Thanks,

Anton

Dave Katz wrote:
> have bigger problems than the time it takes to bring up an additional link.
> 
>>
>>