OSPF SPF Scheduling and Throttling

Lessons Discussion
1

This topic is to discuss the following lesson:

2

Hello Rene,
I have a question. I see that after the 2xspfhold and then second spf start there is a gap of 5 seconds(35 to 40). Could you please explain as to why is that so?

3

Hi Ravi,

There is no particular reason, the time from 35 to 40 seconds ( 5 seconds in total) is a period of inactivity, I made up that time.

Rene

4

i could not understand the SPF hold and spf-max-wait timer …??

Can u please help me with it ??

5

Hello Narad

The OSPF SPF scheduling and throttling feature is used to keep an OSPF topology stable in the event that there is a continuous inflow of LSAs, causing continuous recalculation of the SPF algorithm.

The spf-hold value is the initial amount of time to wait between one SPF calculation and the next. Every time a new LSA is received before sfp-hold has elapsed, this value doubles, so it waits longer before running the SPF calculation again. You can see this clearly in the diagrams in the lesson.

Now imagine that you keep getting LSAs all the time. This spf-hold value will continue to double. It could potentially continue to double forever, reaching values of several minutes or hours!! This doubling must have a limit, and that’s where the spf-max-wait value comes in. The spf-hold value, as it doubles, will hit a maximum of spf-max-wait, and will not double further, but will remain at that maximum. The original spf-hold value is reset only if spf-max-wait has elapsed without any new incoming LSAs.

I hope this has been helpful!

Laz

6

Hi, I have one question in this instance.
Even if we don’t receive any LSAs in (2x spf-hold) it still have to run SPF?

7

“Since we didn’t receive any LSAs during the last wait interval, the router resets the wait interval to spf-start. A few seconds later, we receive another LSA:”

According to previous mentioned by Rene wait = 5sec, although i believe between 40-45 sec lsa recieved should be = hold time and not start time. Is is right?

10

Hello TE-EN LIN

Yes, that is correct. If no LSAs are received, the SPF will always run after the current hold time expires. That hold time may be spf-hold, 2 x spf-hold, or more, depending on how many times the spf-hold value was doubled.

I hope this has been helpful!

Laz

11

Hello Konstantinos

The value of spf-start is the value that the spf-hold will be set to whenever it is reset. So when spf-hold is initially reset, it will be equal to spf-start. This is why at that point in time, spf-hold = spf-start = 5 seconds.

So yes you are correct, that:

…but at that particular time, spf-hold is the same as spf-start.

I hope this has been helpful!

Laz

12 
*Dec 20 01:24:37.637: OSPF-1 INTRA:   Processing link 1, id 192.168.12.1, link data 192.168.12.1, type 2
*Dec 20 01:24:37.637: OSPF-1 SPF  :    Add better path to LSA ID 192.168.12.1, gateway 192.168.12.1, dist 1
*Dec 20 01:24:37.638: OSPF-1 INTRA:    Putting LSA on the clist LSID 192.168.12.1, Type 2, Adv Rtr. 1.1.1.1
*Dec 20 01:24:37.638: OSPF-1 SPF  :    Add path: next-hop 192.168.12.1, interface GigabitEthernet0/0
*Dec 20 01:24:37.638: OSPF-1 INTRA:      Downheap LSA ID 192.168.12.1, Type 2, Adv 1.1.1.1 on clist from index 1 to 1

same topology as instructor, getting this when spf calculation, is it anyway to explain me downheap lsa id line wht is the meaning, previous messages just gives ls-id to the link and assigns it theip address. Downheap means it verifies the link-id?

13

Hello Konstantinos

The term downheap needs a bit of explaining. The term comes from heap data structure theory, a theory that involves how binary trees are manipulated. Because OSPF uses the Shortest Path First (SPF) methodology using Dijkstra’s algorithm, it uses heap data structure theory.

When the topology changes, the nodes that comprise the tree structure are modified. This modification must be reflected in the tree construct that OSPF has created. The terms “upheap” and “downheap” are used to refer to how nodes are kept in order when changes occur to the tree.

Upheap refers to the process by which the order of the nodes in the tree (heap order) is restored after a new node has been added.

Downheap refers to the process by which the order of the nodes in the tree (heap order) is restored after a node is removed.

For more info on heaps and their operations, take a look at this quick summary on heaps as constructs.

To be honest, I’m surprised that such a specific term like “downheap” has made its way into the output of a syslog entry. Usually, such algorithm-specific terminology doesn’t make its way into networking jargon and is typically kept as a black box, but not in this case.

To answer your question then, in your topology, since a better path was found, a node was removed (the old path) and thus a downheap operation had to take place.

I hope this has been helpful!

Laz

1 Like