Subject: Question about routing table update

From: Sushma Venkatesh <[email-masked]>
Date: Thu, 23 Feb 2006 18:42:25 -0500

As per section 13.2 in RFC 2328, receipt of a router or network LSA with 
changed
contents leads to recalculation of entire routing table.

As per section 16 in RFC 2328, the routing table calculation involves:

(1)Dijkstra calculation for each attached area considering only the links

between routers and transit networks.
(2)Stub networks are incorporated into the area trees by going through th
e
router LSA of each reachable router again.
(3)All the summary LSAs are examined to calculate inter-area routes.
(4) All AS-external LSAs are examined to calculate routes to external
destinations.

Questions for the group:
(1)Clearly, depending on the number of summary and ASE LSAs, the routing 
table
update may take much longer than simple dijkstra calculations of all atta
ched
areas. There exist some studies (Shaikh 2001, Basu 2001) that attribute t
imes
of the order of tens of milliseconds to dijkstra calculations based on th
e
number of routers in the area.  Are you aware of any studies that
experimentally measure or model the time spent in doing routing table upd
ates?
Are their any studies or rules of thumb to estimate the time spent examin
ing
the summary and ASE LSAs? Is it reasonable to assume that the time spent
examining the summary/ASE LSAs is linear in terms of the number of such L
SAs?
(2)Is it reasonable to assume that modern routers perform the complete ro
uting
table update following the receipt of a changed router/network LSA as ONE

activity WITHOUT PREEMPTION? Or are they likely to split the complete rou
ting
table update process in multiple parts and perform them as time permits?

---

From: Santosh Esale <[email-masked]>
Date: Mon, 27 Feb 2006 16:21:30 +0530

Hi Sushma,
                 see inline.
Thanks
Santosh

> examining the summary/ASE LSAs is linear in terms of the number of such L

San>>
a) The time spent examining the summary LSAs depends upon the type of OSPF
router. OSPF ABR calculates routes for backbone summary LSAs as well
generates summary LSA for these routes to be flooded into other non backbone
areas. OSPF router internal to any area will only calculate the routes for
these LSAs.So it takes linear time in terms of number of LSAs on a
particular type of OSPF router.
b) External LSA will take linear time in terms of number of LSAs.
Thuogh i never measured in terms of time this calculation.

> table update process in multiple parts and perform them as time permits?
San>>
i know atleast one implementation where its splits the routing table
calculations into three parts:
1. Intra-area calculations(Dijkstra calculation ) for all areas and starts a
timer for inter-area calculation.
<< preemption can occur here >>
2. Inter-area calculations and it will start a timer of external-route
calculations
<< preemption can occur here>>
3. External route calculations

---

From: Dave Katz <[email-masked]>
Date: Mon, 27 Feb 2006 08:00:30 -0800

> examining the summary/ASE LSAs is linear in terms of the number of  

The reality in many networks is much larger than this.  In transit  
networks, OSPF is basically calculating next hops for hundreds of  
thousands of BGP routes.  The actual OSPF part of the process is in  
the noise;  a single route change can result in a next hop change for  
a gazillion routes.  This is where the real work happens.

In practice, SPF calculations take inconsequential time for practical  
networks, even very large ones, and all of the work in partial  
Dijkstras and such is pretty much just academic.  Networks large  
enough for the SPF calculation to take a significant amount of time  
(more than milliseconds) tend to be impractical for other reasons.

> table update process in multiple parts and perform them as time  

There are many ways of going about it.  Obviously a completely  
nonpreemptive environment can cause trouble if Hellos aren't being  
sent while the box is off calculating routes (as many implementors  
found out as networks started to grow.)  The only architectural  
requirement is that the LSDB remains consistent while the SPF is  
being calculated, which means some fancy footwork if you're going to  
continue to send and receive anything other than Hello packets.  (And  
Hellos have to go out as scheduled.)

--Dave

---

From: Erblichs <[email-masked]>
Date: Mon, 27 Feb 2006 13:00:34 -0800

Sushma Venkatesh,

	Alot of questions..

	Let me give you some common sense answers.

	If a changed network LSA is larger than the previous
	instance then we should be also expecting new router
	LSAs. Would it make sense to process the network or
	the router LSA separately wrt the SPF calc?

	Also if most LSAs recieved are just refreshes,
	then pre-empting the SPF calc should not be an
	issue. The reason for doing this COULD be to process
	incoming refresh LSAs so you can simply prevent tail 
	drops wrt the in buffer for OSPF control pkts.

	The amount of time for the SPF calc that also includes
	routing table updates is dependent on too many factors
	to estimate.

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

Sushma Venkatesh wrote:
> 
> As per section 13.2 in RFC 2328, receipt of a router or network LSA with changed
> (2)Stub networks are incorporated into the area trees by going through the
> (1)Clearly, depending on the number of summary and ASE LSAs, the routing table
> update may take much longer than simple dijkstra calculations of all attached
> areas. There exist some studies (Shaikh 2001, Basu 2001) that attribute times
> of the order of tens of milliseconds to dijkstra calculations based on the
> experimentally measure or model the time spent in doing routing table updates?
> Are their any studies or rules of thumb to estimate the time spent examining
> examining the summary/ASE LSAs is linear in terms of the number of such LSAs?
> (2)Is it reasonable to assume that modern routers perform the complete routing
> activity WITHOUT PREEMPTION? Or are they likely to split the complete routing