SPF in Operation

The ARPAnet used one of the first distance vector routing protocols. This protocol evolved into RIP, which is still in use today. Serious limitations were encountered with RIP as networks grew. This caused a demand for a new protocol that could run within an AS and had the capability to grow (scale) to a large-sized network comprised of many routers and network links.

Into this gap stepped OSPF version 1, published as Request for Comments (RFC) 1131 in October 1989 by the OSPF Working Group of the IETF. OSPF made use of the famous Dijkstra algorithm. This algorithm was not new and had not been created specifically to fill the demand of the networking community. This mathematical formula was initially created to demonstrate the ARMAC computer in 1956, over 30 years before OSPF was considered.

Edsger W. Dijkstra was born in 1930 in Rotterdam, the Netherlands. Born into a scientifically oriented family, he quickly excelled and achieved his Ph.D. in computer science in 1959 from the University of Amsterdam, Holland. By the time he was 32, Dijkstra achieved a full professorship in mathematics at Eindhoven University. His achievement remains extremely impressive to this day.

Dijkstra's most remembered contributions to the computer world are his algorithms, specifically the shortest path algorithm. Dijkstra did not consider his algorithm very remarkable at the time, and many years passed before he published it. Today, his algorithm is being applied to road building, communications routing, and the airline industry. His algorithm was even altered slightly to determine the most inexpensive way to wire a computer. The goal of Edsger Dijkstra's shortest path algorithm is to find the shortest route between two points through a series of nodes, as originally described in his paper outlining the algorithm. However, in routing, we translate the term node into router.

Consider the following example to describe the operation of the shortest path first algorithm in basic terms.

Suppose you are trying to find the shortest path in time between the cities of Raleigh and Boston. In between these cities are a number of other cities (routers) that might provide the best route to your final destination.

In this example, you want to determine the shortest path (cost) that is required to reach Boston while exploring every road (link) that each new city provides along the way. As you know, some roads (links) are better than others. These roads might be faster, bigger, or less traveled. To determine the shortest, (call it the fastest) path (route) from Raleigh to Boston, assign each road (link) a numerical value that reflects its speed.

Because computers only understand the importance of numbers and not opinions regarding path desirability, you need to manually assign these values to the paths to help the protocol do its job. A router can understand that a path with a value of 50 is more efficient than a path with a value of 100.

This example obviously refers to OSPF, so in the example, OSPF will collect all the link information on how to get from Raleigh to Boston. Then, the SPF algorithm will calculate the shortest path (see Figure 2-5). The sequence to find this minimum time value (shortest path) is as follows:

Figure 2-5 SPF in Action

Goal: Find the Shortest Path from Raleigh to Boston

Raleigh

Goal: Find the Shortest Path from Raleigh to Boston

Raleigh

Boston

1 Begin in the city of origin (Raleigh). The time (distance) needed to reach Raleigh is 0 (because you are there).

2 Raleigh knows (via OSPF) that one connection to another city heads toward Boston. This connection to City X has a cost of 100 because it is a nice two-lane road. Place this link information in a database for future reference:

66 Chapter 2: Introduction to OSPF

3 City X tells you that there are two paths leaving it. As OSPF examines these links, it learns the following:

Link B—Costs 100—Goes to City Y—Link is up Link C—Costs 100—Goes to City Z—Link is up Place both entries into the database, and continue to search for Boston.

4 City Y tells you that it has a connection to Boston via a brand new expressway; place that information in the database as well:

At this point though, you also learned that City Z has a link to Boston as well. Link E—Costs 100—Goes to Boston—Link is up

Faced with two links to Boston, the SPF algorithm must compute which is the shortest path.

5 OSPF turns to its database. (Don't you think you should give this database a name? Well because you're tracking data regarding the many links (cost and status such as up/down, call it the Link-state Database [Topological]) and reviews what it knows:

Path A—Costs 100—Goes to City X—Link is up Path B—Costs 100—Goes to City Y—Link is up Path C—Costs 100—Goes to City Z—Link is up Path D—Costs 50—Goes to Boston—Link is up Path E—Costs 100—Goes to Boston—Link is up

OSPF has discovered two paths to Boston, but which one should you use? You don't know which is the shortest. However, the SPF in OSPF can determine the shortest path for you.

6 OSPF now invokes the SPF algorithm and builds a map of all the links from Raleigh to Boston. This map can be visualized with Raleigh as the root (bottom) of a tree that has all these limbs (links) that go to many cities (destinations) (see Figure 2-6). Turn the book on its side so the figure looks like a tree.

Although this is a nice picture of a tree, computers prefer to treat this information mathematically:

Path 1: Link A (100) + Link B (100) + Link D (50) = Cost (250)

Path 2: Link A (100) + Link C (100) + Link E (100) = Cost (300)

Now the SPF algorithm compares these two paths and determines which is the shortest so that you can drive to Boston (transmit a packet). SPF chooses Path 1 because it has a lower cost than Path 2.

7 The shortest path is Path 1.

Figure 2-6 SPF Tree

Point of Origin

Raleigh, NC

Link A (100)

CityX

USA

Raleigh Is the root of the tree.

8 Path 1 is now inserted into the car's computer (route table), so it can tell you (the packet) how to get to Boston using the shortest possible path.

This example helps demonstrate the algorithm's name. Another important factor in its operation is how SPF converges. Using the preceding example, everything would change if the link between City X and Boston went down. The need to understand why this has happened and how traffic (packets) is redirected to the link through City Z is crucial. This concept is called convergence.

Reviewing the Link-State Database

The principle of link-state routing is that all the routers within a network maintain an identical copy of the network topology. From this map, each router performs a series of calculations that determine the best routes. This network topology is contained within a database, where each record represents the links to a particular node in the network. Each record contains several pieces of information: an interface identifier, a link number, and metric information regarding the state of the link. With that information, each router can quickly compute the shortest path from itself to all other routers.

Essentially, OSPF converges in 0(M.log M) iterations, where M is the number of links. This is far superior to the distance vector Bellman-Ford algorithm, which converges in 0(N.M) iterations, where N is the number of nodes.

68 Chapter 2: Introduction to OSPF

SPF Functions

Assume that you have the network shown in Figure 2-7 with the indicated interface costs. To build the shortest-path tree for RTA, you would have to make RTA the root of the tree and calculate the smallest cost for each destination.

Figure 2-7 SPF Functions

Physical Network Topology

RTA's cost to access 192.168.254.0 is 10. "

RTA 4

192.168.254.0

RTB t

RTC i

100.100.100.0

Figure 2-7 shows the view of the network as seen from RTA. Note the direction of the arrows in calculating the cost. For example, the cost of RTB's interface to network 192.168.254.0 is not relevant when calculating the cost to 10.10.10.0. RTA can reach 10.10.10.0 via RTB with a cost of 15 (10+5). RTA can also reach 100.100.100.0 via RTC with a cost of 20 (10+10) or via RTB with a cost of 20 (10+5+5). In case equal-cost paths exist to the same destination, Cisco's implementation of OSPF keeps track of up to six next hops to the same destination.

Figure 2-7 shows the view of the network as seen from RTA. Note the direction of the arrows in calculating the cost. For example, the cost of RTB's interface to network 192.168.254.0 is not relevant when calculating the cost to 10.10.10.0. RTA can reach 10.10.10.0 via RTB with a cost of 15 (10+5). RTA can also reach 100.100.100.0 via RTC with a cost of 20 (10+10) or via RTB with a cost of 20 (10+5+5). In case equal-cost paths exist to the same destination, Cisco's implementation of OSPF keeps track of up to six next hops to the same destination.

After the router builds the shortest-path tree, it starts building the routing table accordingly. Directly connected networks are reached via a metric (cost) of 0, and other networks are reached according to the cost calculated in the tree.

Before discussing the origins of the OSPF protocol, you should review its key characteristics. These characteristics and the protocol's many labels serve as a short review and as an introduction to future concepts.

The OSPF protocol is also known by the following definitions or labels:

• Link-state routing protocol

• Shortest path first (SPF) protocol

• Interior gateway protocol

• Distributed routing protocol

OSPF also has the following operational characteristics:

• Features open architecture

• Dynamically adjusts to changes in network topology

• Features adjustable distance metrics

• Features type of service (TOS) routing

• Supports hierarchical systems

• Features load balancing

• Provides security features

• Supports three kinds of connections or networks:

— Multiaccess networks with broadcasting

— Multiaccess networks without broadcasting

• Determines routing by computing a graph, abstracting the topology of the network by using the shortest-path algorithm

• Segments the network through the use of autonomous systems and areas for ease of management and traffic

• Features multicasts rather than broadcasts

• Allows the use of virtual links

• Supports VLSM and CIDR

70 Chapter 2: Introduction to OSPF

Full and Partial SPF Calculations

The Cisco Systems implementation of the SPF algorithm allows for quicker ways to calculate routes. This change has resulted in two types of SPF calculations: full and partial. The full SPF calculation operates as discussed so far this chapter.

The full SPF algorithm is run only when there is a topology change, as expressed in router linkstate advertisements (LSAs), not for summary LSAs. Summary LSAs cause a partial SPF to be run.

In OSPF, partial SPF relates to external and summary LSAs' change only. Basically, if a network flap occurs via an external or summary LSA, you run partial SPF. In other words, partial SPF is invoked when topology of the area did not change but some IP prefix flapped.

An IP prefix change inside the area invokes the full SPF recalculation.

Verifying SPF Operation

As previously discussed, it can be important to monitor flooding with OSPF. Whenever an LSA is received, SPF could recalculate. You can see how OSPF is operating by executing a show ip ospf process id command. This command can be used to determine the number of times the SPF algorithm has been executed. It also shows the link-state update interval, assuming no topological changes have occurred. Example 2-1 shows an example of the show ip ospf command, with the highlighted area representing the total number of SPF calculations.

Example 2-1 Displayed Output from the show ip ospf Command

HAL9000#show ip ospf 100

Routing Process "ospf 100" with ID 10.10.10.10

Supports only single TOS(TOS0) routes

SPF schedule delay 5 sees, Hold time between two SPFs 10

secs

Number of DCbitless external LSA 0

Number of DoNotAge external LSA 0

Number of areas in this router is 1. 1 normal 0 stub 0 nssa

Area BACKBONE(0) (Inactive)

Number of interfaces in this area is 1

Area has no authentication

SPF algorithm executed 13 times

Area ranges are

Link State Update Interval is 00:30:00 and due in

00:09:05

Link State Age Interval is 00:20:00 and due in 00

19:05

Number of DCbitless LSA 0

Number of indication LSA 0

Number of DoNotAge LSA 0

HAL9000#

Furthermore, for partial SPF, because only summary or external LSAs are affected, you can also execute either a debug ip ospf spf inter command or a debug ip ospf spf external command to monitor the partial SPF. You can specify an access list to filter calculations only for an LSA with specific LSA ID.

+1 0

Post a comment