OSPF Database

[rohit_s]

I am bit confused of the fact: -

How multiple OSPF areas reduces the Size of the LSA database of an Internal Router. I am considering the fact that no Stub area and Route Summarization is happening.

Though Multiple OSPF areas reduces the Type 1 and 2 LSA on the Internal Router but correspondingly Type 3 Summary LSA are flooded by the ABR into the Internal Routers. So Overall the size of database is actually the same.

I mean reduction in Type 1 and 2 LSA is overwriden by the Type 3 Summary LSA of other Areas.

[mheusinger]

Hi,

there are two resources to consider: memory and CPU.

Consider the OSPF database being like a puzzle. LSA1 and LSA2 allow for the reconstruction of the topology of an area. The advantage of multiple areas is for an internal router, that the known topology is reduced to less routers and therefore less possible pathes.

Consider a network with 100 routers partially meshed.

The SPF calculation needs to find the best path to every destination, which gives lots of possibilities in my example.

Now consider this network split into area 0 and area 1 consisting of one ABR and one internal router R1 with one link to the ABR. For R1 this means a lot less calculation as the topology is not 100 routers partially meshed, but only two.

So even without reducing the size of the IP routing table or OSPF database, the SPF calculation is simplified for an internal router.

In other words: memory consumption might not be dramatically reduced, but CPU utilization is.

And you have tools available to reduce memory consumption as well with multiple areas (stub, area range ...)

Hope this helps

Martin

[rohit_s]

Hi Martin....Thanks for the Update

But in your example though there is only one link to ABR and so only two Type 1 LSA, so SPF calculation is less.

But what about Type 3 LSA for the rest of the networks which would be flooded by the ABR into the Internal Router R1. These would then also be the part of R1 database and would be involved in the SPF calculation. So again the SPF calulation time is drastically increased as he needs to look all the LSA (Type 1 and 3) while SPF calculation

Hope I am right above...

Rohit

[mheusinger]

Hi,

yes the number of SPF calculations might not be reduced, but the length of each one. In my multi area example SPF stops after one hop (ABR) each time - so to say.

With one area maybe 99 hops need to be considered - a lot more to calculate in each step!

Hope this helps

Martin

[rohit_s]

Hi,

I Got some Idea here from your explanation.

Correct me if I am wrong below in understanding you...

SPF depends on both LSA numbers and also the number of hops for each LSA calculation. So in your example of multiple areas, though SPF will have to calculate all the LSA (Type 1/3) but it will calulate them upto the ABR. So CPU Util. for SPF calaculation has overall reduced. Means SPF Tree structure has reduced because of ABR...

kindly also clarify me that...

Does having a single area with Only Type 1 and 2 LSA will have small database size than having the Multiple areas with both Type 1/2 and Type 3 LSA. Or in both case LSA size will alsmost be same????

Rohit

[rohit_s]

Hi,

I Got some Idea here from your explanation.

Correct me if I am wrong below in understanding you...

SPF depends on both LSA numbers and also the number of hops for each LSA calculation. So in your example of multiple areas, though SPF will have to calculate all the LSA (Type 1/3) but it will calulate them upto the ABR. So CPU Util. for SPF calaculation has overall reduced. Means SPF Tree structure has reduced because of ABR...

kindly also clarify me that...

Does having a single area with Only Type 1 and 2 LSA will have small database size than having the Multiple areas with both Type 1/2 and Type 3 LSA. Or in both case LSA size will alsmost be same???

Rohit

[mheusinger]

Well the size of the database really depends on the network topology at hand.

But generally I assume that multiple areas will reduce even memory consumption for an internal router because the topology information is hidden in LSA3 compared to LSA1/2.

Hope this helps

Martin

[Richard Burts]

It seems to me that Rohit asked one question about the size of the OSPF database and that Martin answered a slightly different question about impact on calculation of the SPF algorithm. Rohit makes an interesting point about the memory consumed by the LSA type 1 and LSA type 2 vs the memory consumed by the LSA type 3 that replaces them. And I have never actually measured the memory consupmtion to compare this.

But Martin is on the right track in discussing the impact on the calculation of the SPF. There are performance advantages in creating more areas/smaller areas. Part of the advantage is that the complete SPF to create the network topology is only run on LSA type 1 and LSA type 2 changes. The router does not use the LSA type 3 in calculating the topology. For the LSA type 3 the router only needs to know the route to the ABR and does not need to know the topology of the remote area.

Another factor that imporves performance of OSPF with more and smaller areas is the number of events that cause recalculation of the SPF. If there is a link state change all of the routers in the area must calculate the SPF but routers outside of the area who receive type 3 LSA may have to change the table but do not have to calculate the complete SPF.

HTH

Rick

[ruwhite]

The other answers you've received are good--but I'll try and give, perhaps, a "more technical" response, that might help, as well (?). :-)

The easiest way to understand how flooding domain borders help scale a link state protocol (area borders in ospf, and l1/l2 borders in is-is), is to mentally conceive of the tree SPF builds based on the database, and then consider how flooding domain borders impact the shape of the tree. So, consider a tree, with a set of roots, a trunk, and then branches. Now, suppose you had to climb up the tree (it's a big one), and you had to walk around up there, going to the end of every branch, and check for some small piece of fruit that only grows at the very tip of each branch.

Obviously, there are two factors that are going to determine the amount of time it takes to do this:

-- The hieght of the tree. How far do you have to climb to reach all the branches?

-- The breadth of the tree. How many branches are there off of each branch, so how many times do you have to climb to the end of a branch, then climb back to the intersection point with other branches, and then move down another branch from that intersection point?

SPF does the same thing, in stark terms. It "walks" to the end of every branch, following through every possible intersection, and all the way to the top of the tree. Now, as the network grows, you get more branches further away from any given edge router (the depth, or height, of the tree), and you get more branching points at every place on the tree (the breadth of the tree).

Suppose the tree gets very large, and it starts taking you a long time to get to all the branches. It would help if someone took all the fruit out at the end of some large multibranch mess sitting off some "large" branch, and relocated all the fruit to the intersection point. Then, you wouldn't have to walk all the way out to the ends of that branch, saving you a tremendous amount of time. This is exactly what area borders do--they relocate the information "closer to the root," so SPF can take a shorter time to walk all the way out to where the fruit is.

So, that illustrates the SPF and processor run time issues, but what about the database size. Now, consider that if the person who went out there and moved the fruit from the edges to branch intersections closer to the trunk also cut off all the branches that don't have fruit on them any longer?? The tree would suddlenly become much smaller--you could stuff the tree into a much smaller truck, etc. Thus, although the fruit (destinations) is still there, the branches (topology) is not, and the tree is much smaller. This is where you get the impact of the database being smaller.

HTH.

:-)

Russ.W