Sunday, January 8, 2012

When OSPF Becomes a Distance Vector Routing Protocol

In this final section of OSPF main text we revisit some basic and important concepts of OSPF. We were always being told that OSPF is a fast converging loop-free link-state routing protocol. However, to be precise, OSPF is a link-state routing protocol only within an area (intra-area); but almost a distance-vector routing protocol between areas (inter-area).

OSPF requires all traffic between non-backbone areas to pass through the backbone area. The reason behind this leads us back to the fundamental concepts of OSPF.

Every OSPF router floods information about its links, and its neighbors to other OSPF routers. Each router then builds an identical link-state database based on the flooded information, and then independently runs the SPF calculation upon its LSDB to derive the SPF tree, which is sort of a map of shortest paths to other routers (local calculation using distributed information).

One of the advantages of LS protocols is that the LSDB provides a “view” of the entire network, which in turn able to prevent most routing loops. This is in contrast to DV protocols, in which routing information is being propagated on a hop-by-hop basis throughout the network, and a calculation is performed at each hop (distributed calculation using local information). Each router along a path is dependent on the router before it to perform its calculations correctly and then pass along the results. When a router advertises the routing information it learnt to its neighbors, it is basically saying “I know how to reach these destinations.”. Since every DV router knows only what its neighbors tell it, and has no “view” of the network beyond their neighbors, the protocol is vulnerable to loops.

Those were the days when memory resources and CPU processing power were limited; it became a scaling problem when a link-state routing domain grew larger with a large number of routers, and large size of the LSDBs. The problem is solved by partitioning the routing domain into areas. The flooding occurs within the boundary of an area, and the LSDBs contain only information from other routers within the area. This means that the SPF tree on each router only describes only the paths to other routers within an area; and there are separate LSDBs for different areas.

OSPF areas are connected by one or more area border routers (ABRs) which maintain separate LSDBs and calculate separate SPF trees for each area that they reside in. An ABR is a member of multiple areas. It advertises the prefixes it learnt in an area to other areas by flooding Type-3 LSAs into those areas which basically saying “I know how to reach these destinations.”.
Note: Another main LS protocol – IS-IS, connects areas somewhat differently.

The last concept described earlier is not link-state, it is distance-vector! The routers in an area have no “view” beyond the ABR, and rely upon the ABR to tell them the prefixes it can reach. The SPF calculation on the routers within an area derives a SPF tree that depicts all prefixes beyond the ABR as leaf subnets connected to the ABR with some specified costs.

This leads us to the answer to the question why OSPF requires all traffic between non-backbone areas to pass through the backbone area in a hub-and-spoke topology. Because inter-area OSPF is distance-vector, it is vulnerable to routing loops. Hence OSPF specifies that traffic from one area can only reach another area through the backbone area in order to maintain a loop-free inter-area routing topology, in which no loops will be formed between the areas.

Jeff Doyle, the author of the Routing TCP/IP series, had involved in many discussions regarding the scalability of OSPF. He came across a single-area OSPF network with over 1000 routers, yet still operates without any performance or memory problem. Always design OSPF networks with the single-area mindset and add non-backbone areas only when they are really necessary. Defending a single-area design is a matter of convincing that multiple areas are not necessary.
A cardinal rule of network design is to start as simple as possible and then add complexities only when they are the simplest solution to an identified problem. – Jeff Doyle.

Suboptimal routing can occurs in OSPF area routing due to the fact that an internal router not in the destination area will use the routing path via the first segment (ABR) to the destination area.

Suboptimal OSPF Inter-Area Routing

The figure above shows a sample OSPF network with high-speed high-capacity links (OSPF cost 1), in the backbone area, and low-speed low-capacity links (OSPF cost 4) in Area 1. When all routers and links reside in a single area, plain shortest path routing will follow the backbone as much as possible; therefore the traffic from RT1 to behinds RT7 will follow the route: RT1 – RT2 – RT3 – RT7.

However, due to inter-area routing and RT1 does not reside in the destination area (Area 1), RT2 will route traffic via RT6 when the traffic arrives at RT2, as it resides in the destination area. The routing path will be changed to RT1 – RT2 – RT6 – RT7; even it has higher accumulated OSPF path cost than the optimal path (13 against 10)!

No comments:

Post a Comment