Subject: [OSPF] question regarding DR/BDR in OSPFv2 graceful restart

From: "Sunil Patro" <[email-masked]>
Date: Fri, 7 Jul 2006 14:39:30 -0700

Quoting from rfc 3623-

"     3) If the restarting router determines that it was the Designated
         Router on a given segment prior to the restart, it elects
         itself as the Designated Router again.  The restarting router
         knows that it was the Designated Router if, while the
         associated interface is in Waiting state, a Hello packet is
         received from a neighbor listing the router as the Designated
         Router.

   Otherwise, the restarting router operates the same as any other OSPF
   router.  It discovers neighbors using OSPF's Hello protocol, elects
   Designated and Backup Designated Routers, performs the Database
   Exchange procedure to initially synchronize link-state databases with
   its neighbors, and maintains this synchronization through flooding."

What should be the procedure when the restarting router was the BDR
before the restart occurred? After it comes back, it is going to learn
that it was the BDR in the neighbor's hellos. Should it just accept that
fact and become the BDR again?

Thanks
Sunil

_______________________________________________
OSPF mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf

---

From: Acee Lindem <[email-masked]>
Date: Fri, 07 Jul 2006 18:08:19 -0400

Hi Sunil,

>fact and become the BDR again?
Since the intra-area topology isn't effected, it isn't necessary. This 
point was previously
argued on this list and you might want to check the archives for the 
complete discussion
(in the context of draft-holla-ospf-update-graceful-restart-00.txt). My 
take is that since
the BDR has to reestablish adjacencies anyway, thee is no advantage to 
retaining BDR
status. Also, the restarting router has quite a bit to do already.

Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Wed, 12 Jul 2006 11:10:08 -0700

I listened to Acee's presentation of my draft
http://www.ietf.org/internet-drafts/draft-ogier-ospf-dbex-opt-00.txt

Acee mentioned that it might help to list the LSAs in
lexicographical order, to achieve the maximum savings
in overhead.  One person commented that it may not be
reasonable to require this.

I want to point out that one can still achieve the 50% reduction
in the number of LSA headers exchanged even if LSAs are not
listed in lexicographical order, as long as the received DD packet
is processed completely (including updating the summary list
as specified in the draft) before the next DD packet is sent.
In this case, I don't think the order in which LSAs are listed
matters.

Comments?

Richard

---

From: Acee Lindem <[email-masked]>
Date: Wed, 12 Jul 2006 17:43:01 -0400

Hi Richard,

> In this case, I don't think the order in which LSAs are listed

I agree. I probably shouldn't have mentioned lexigraphically ordering
at all since it was with respect to how simple and low overhead this
optimization is when starting  with an implementation
following RFC 2328.

Given this fact,  I'd ask the question again as to whether anyone
is opposed to publishing this as an informational WG document?

Thanks,
Acee

---

From: Erblichs <[email-masked]>
Date: Wed, 12 Jul 2006 17:04:23 -0700

Group,

	I did not hear Acee's presentation, but have read the
	two page draft.

	You mention
	"This optimization reduces Database Description
         overhead by about 50% in large networks." I feel
	only in the last scenario, this statement may be
	true. However, In the simple, BMA
	environment, the DR will contain most of the LSAs
	(scenario 3), I doubt that any reduction would be
	significant.

	I am less aware of P2P,etc type environments, where this
	might be more signficant, thus I suggest a fine tuning
	to this idea below.

	Upon my first quick read, 4 scenarios came to mind:
	1) a minimal number of LSAs that need to be exchanged
	   on both sides.
	2) a large number of LSAs that need to be exchanged
	   on both sides and they are from two past DRs,
	   thus no LSA header will match...
	3) a new adj where the DR has already formed adjs
	   and a new router where only a few of its LSA
	   need to be exchanged.
	4) two routers have basicly the same LSA list.

	IF I read the draft correctly, one or both routers are
	creating a artifical delay before some LSAs are sent.
	One router might wait until it thinks it has recieved
	all of the other router's LSA headers.

	This delay introduces a longer period of time before
	the OSPF routers could be synchronized. This is
	expecially true if the waiting router is holds a number
	of new LSAs. Thus, you are optimizing for the last
	scenario.

	If (my theorectical two minute thought suggestion)
	implemented ordered LSAs, and both routers could
	agree on a order... stay with me..

	   Wouldn't it make more sense that the master say send
	increasing LSAs ids out and the slave send decreasing
	LSAs out?

	One could then theorectly compare LSAs and implement what
	you suggest without delay. In #1, Since the number of LSAs
	is small, the LSAs will still be exchanged. But where the
	number of LSAs is LARGE and almost identical between the 
	two routers, then half the number of headers would be sent.

	Thus, IMO, a new option should be specified that says that
	the two will exchange in the initial database sync, in reverse
	order. Again, this will help a DR/BDR full adj formation, only 
	if that is done last.

	Mitchell Erblich
	-------------------

---

From: Acee Lindem <[email-masked]>
Date: Thu, 13 Jul 2006 08:15:07 -0400

Hi Mitchell,

>	all of the other router's LSA headers.
Since the database exchange window size is 1 with the master pacing
the exchange, there is no additional delay. If you look at section 10.6 
of RFC 2328,
you'll note that the RFC specifies that the database exchange packet be 
processed
prior to response. One could envision trying to optimize this but I 
doubt you'd
get a lot of bang for your buck.

>	order. Again, this will help a DR/BDR full adj formation, only 
As I stated previously, the ordering has no impact other than
the processing of the database snapshot and that is an implementation
issue.

Thanks,
Acee

---

From: "Vishwas Manral" <[email-masked]>
Date: Thu, 13 Jul 2006 20:19:47 +0530

The draft looks good to me.

Thanks,
Vishwas

---

From: Richard Ogier <[email-masked]>
Date: Thu, 13 Jul 2006 09:34:12 -0700

Hello Mitchell,

Thanks for your comments.  I agree with Acee's response,
and I have a few more comments below.

>	4) two routers have basicly the same LSA list.

The optimization is mostly indended for the last scenario,
which is often the case in MANETs.  The following sentence from
Section 1 of my draft implies this:
  "The optimization reduces
   Database Description overhead by about 50% in large networks, since
   it reduces the total number of LSA headers exchanged by about one-
   half when the two routers are already nearly synchronized."

>	all of the other router's LSA headers.

There is no additional delay.  It is important that the received
DD packet be processed completely (including updating the summary list
as specified in my draft) before the next DD packet is sent in response,
and I will clarify this in the draft. As a result, the next sent
DD packet will not list any LSAs that were listed in the received
DD packet (with the same or newer instance).

>	increasing LSAs ids out and the slave send decreasing

As Acee mentioned, the ordering does not matter, as long as the received
DD packet is processed before the next DD packet is sent in response.

>	two routers, then half the number of headers would be sent.

Right. That was the main intention. This has been shown in simulations
of OSPF-MDR (for MANETs) using GTNetS.

I have one concern.  What if some future extension of OSPF assumes that
DD packets list all LSAs as specified in RFC 2328, e.g., so that some
action can be taken that depends on how "out of sync" the new neighbor
was.  If someone implements the optimization without any indication
(such as a new option bit), then a future extension
might incorrectly conclude that the new neighbor was out of sync
and take the wrong action.  This could be fixed either by including
a new option bit, or by changing the spec of OSPF to allow the
optimization.  Is this a valid concern?

Richard

---

From: Erblichs <[email-masked]>
Date: Thu, 13 Jul 2006 17:32:30 -0700

Richard,

	Their are two areas here: delay and ordering.

	First, inline you state:

> It is important that the received
	
  The act of processing before, is the delay that I speak of. This
action
sequentializes this processing. ie: recv DD pkt, process it, send our
DD resp, sleep: perchance to dream (ie:Shakespere), recv next, process
it, 
send our next DD  pkt. If all the LSA hdrs recv'd takes a total of 15
secs 
to process, this will add 15 secs before we can converge.

  To keep the parallelism of the current arch could do:

  * Upon all DD pkt recv'd, process it after our DD pkt
    is sent in response. While the resp DD pkt is being processed, clean
    the summary list based on the recvd pkt.

    We will send some percentage based on LSA ordering, relative size,
    but will decrease the number of LSA hdrs sent (cleaned ones), but
    will be able to do the cleaning during the time between successively
    recv'd DD pkts.

    Why should/could we order?
  * My older proposition. I don't care if 5% of hdrs are in common or
    95%, this in theory should work. If the master covers 1/2 of the DB
and 
    the slave covers the other half, best case the headers of 1x the
LSDB need
    be sent in DD pkts. The only assumption is that both LSDBs on the
two
    routers have approx the same number of LSAs. We will be filtering as
we
    recv the DD pkts, but should have no need to process the DD pkt from
the
    other router "before the next DD pkt is sent in response". We will
do this
    cleaning during the time between successively recv'd DD pkts.
Because of
    the ordering, their is NO NEED to wait, if the LSDB is of sufficient
size
    on both routers. We will not initially be sending LSAs that can
conflict.
    The complexity is what do we do as we approach the middle and start
with
    conflicts.

    Where this optmization does not help, if the number of hdrs is such
that
    only a few DD pkts need to be sent or where one router has a
significantly
    larger LSDB.

   * The third suggestion is inline for kbps environments...

	Mitchell Erblich
	---------------------------------

>    half when the two routers are already nearly synchronized."
	Shouldn't we find a implimentation that works also when they
	aren't nearly synchronized?

	That is where ordering stated earlier and above comes in, with
	a new option.
> DD packet (with the same or newer instance).
	Sorry, "BEFORE" implies a wait until... This is a additional delay..:^)
	If the Master contains enough LSAs such that it takes X secs to
	process, this adds to the convergence of these LSDBs. I see where
	a bandwidth is such that one wants to limit the number of LSA hdrs
	exchanged. 

	But this could also theorecticly be done if one would to
	segment the LSDB per LSA type, exchange LSDB type checksums, and
	if they then disagree exchange hdrs...

	You just need to come up with a checksum that only one set of
	LSAs will produce a unique checksum. I am not a mathematican
	to tell you how complex this might be..
> DD packet is processed before the next DD packet is sent in response.

	The ordering is based to remove the wait and LSA conflicts
	at the ends of the LSDB. ..
> optimization.  Is this a valid concern?

	I first want to sync with you on the above, but don't we do a
	checksum on our LSDB on most implementation. Why couldn't we
	exchange the result and if different, then.....

	Inline Mitchell Erblich

---

From: Richard Ogier <[email-masked]>
Date: Fri, 14 Jul 2006 07:36:30 -0700

Mitchell,

I assume this is why Acee suggested the lexicographic
ordering when he presented my draft.  (I had figured he
meant the slave would list LSAs in the reverse order as
the master, since otherwise there would be no benefit.)

Anyway, I will change the draft to allow this (but
not to require this).  In some cases, the additional delay
of processing the DD packet completely before sending
the responding DD packet is not significant.
One example is a MANET configured as a stub area.

Let's look at some rough numbers.  A MANET often uses
802.11 with 11 Mbps data rate and has an MTU of 1500.
A maximum size DD packet can be transmitted in roughly 1.2 msec
and contains less than 75 LSA headers (75 * 20 = 1500).
Normally, it would take much less than 1.2 msec to process
such a packet, let's say .1 msec as an upper bound.
Then the additional delay of not parallelizing is at
most .1 msec per DD packet, less than a 10% increase
compared to parallelizing (which would take 1.2 msec
per DD packet).  So, you can see that in the type of
networks I had in mind, there is no significant
advantage to sending the responding DD packet before
the received DD packet is completely processed.

Even if there are 10,000 LSA headers to exchange
in the MANET case (note that the number of summary-LSAs
flooded into a MANET stub area must be limited due to
limited bandwidth), this would require roughly
10,000 / 75 = 133 DD packets, making the additional
delay of not parallelizing at most .1 msec * 133 =
13.3 msec, still not significant.

I suppose there exist examples where it takes 15 seconds
to process all LSA headers and also takes at least 15 seconds
to send/receive all DD packets, so that parallelizing can
cut the delay in half (from 30 sec to 15 sec).
But the optimization also cuts the number of LSA headers
in half, which makes up for the additional delay of
not parallelizing.  However, it would be nice to also
reduce the delay required to synchronize, which I guess
is what you had in mind.

So, the draft can certainly suggest that the master
should list LSAs in forward order and the slave list them
in reverse order.
Also, the draft should mention that in some applications
where overhead savings is more important than delay
(such as MANETs) it may help to process the DD packet
completely before sending the responding DD packet,
in which case the ordering of LSAs is not important.

Even if the number of LSA headers fits into one DD packet,
I would like to have only one router send a full DD packet
instead of both routers (to save overhead).
Therefore, it might help to process the *last* DD packet,
(with M bit = 0), completely before sending the next DD packet.
This also avoids the problem you mentioned when the middle
of the summary list is reached.

Richard

stub area, the additional delay of processing the DD packet
completely before sending the responding DD packet is
not significant.

Is 15 seconds realistic?

I had MANETs in mind, so I don't think the number
of LSA headers will be that large.
If it were, and if the bandwidth is the typical 11 mbps...
I doubt that there will be so many LSAs in a MANET
that it would take 15 seconds, or even 1 second to process
all the LSA headers.

Actually, it might add 15 seconds if it also takes
at least 15 seconds to send and receive the DD packets.
By serializing, we cannot add more delay than the
minimum of the time to process the LSA list,
and the time to send and receive the DD packets
(since both must be done anyway either in parallel
or serially).

So this will at most double the time to converge.
(It is probably better to express the increased delay
percentagewise than in seconds.)
But since it also reduces the number of LSAs by 50%
when the two routers are nearly in sync, the time
to converge will be back to where it was originally.
Of course, it would be better to cut the time to converge in half,
which I guess is what you had in mind.

This is probably why Acee was talking about ordering
the LSA headers lexicographically at the meeting.

Sure, the draft can mention that this can be done and
may be beneficial in some cases.
But I still doubt that not doing this will add much delay
in MANETs, because the number of LSA headers probably will
not be that large, so they can probably be processed in a
few msec.

Let's say the MTU is 1500 bytes.
An LSA header is 20 bytes.
1500 / 20 = 75.
Time to transmit = 1500*8 / 10 Mbps = 1.2 msec.
So if we are talking about 15 seconds, then there
would have to be 15 / .0024 = 6250 DD packets each or
6250 * 75 = 468,000 LSAs.
More reasonably, there would be no more than about 1%
of this number in MANETs, or 4,680, which would
correspond to about 150 msec.
Given that the Hello interval is no less than 1 sec,
a 150 msec delay in synchronizing is not very significant.

But since this should be applicable to more than MANETs,
I see no problem recommending that the master list LSAs
in lex order and the slave list them in reverse lex order.
Also, the draft should mention that in some applications
where overhead savings is more important than delay
(such as MANETs) it may help to process the DD packet
completely before sending the responding DD packet.

Even if the number of LSA headers fits into one DD packet,
I would like to have only one router send a full DD packet
instead of both routers.
Therefore, it might help to process the *last* DD packet,
with the M bit zero, completely before sending the next DD packet.
This also avoids the complexity you mention when the middle
of the summary list is reached.

Richard