The Open Shortest Path First (OSPF) routing protocol is the most common IGP routing protocol that is being used on routers in today’s enterprise IPv4 networks. Routing protocols basically exchange information so routers can learn routes dynamically.
The routers learn information about subnets, routes to those subnets, and metric information about how good each route is compared to others. This protocol uses link state mechanism called “cost” to find the shortest path to the destination.
This article begins by discussing how OSPF routers learn information and choose what routes to add to the routing table. The second part of this article looks at the fundamental part of the OSPF process. It shows how OSPF routers use neighbor relationships, and how routers must be neighbors before they ever exchange routing information to learn routes.
This article ends with some design discussions about how OSPF scales to larger enterprise designs, and the details of how link-state protocols work.
Building the LSDB and Creating IP Routes in OSPF
Link-state protocols build IP routes by going through a couple of major steps. First, the routers together build a lot of information about the network: routers, links, IP address, status information, and so on. Then the routers flood the information so the other routers learn the same information. At that point, each router can calculate routes to all subnets from its own perspective.
Routers using link-state routing protocols need to collectively advertise every detail about the inter-network to all the other routers. At the end of the process of flooding the information to all routers, every router in the inter-network will have the exact same information about the inter network.
OSPF is the most popular link-state IP routing protocol which organizes topology information using link-state advertisements (LSA) and the link-state database (LSDB). Each LSA is a data structure with some specific information about the network topology; the LSDB is simply the collection of all the LSAs known to a router. In Cisco routers the show ip ospf database command lists information about the LSDB.
Figure below shows the general idea of the flooding process, with R8 creating and flooding its
router LSA. The router LSA for Router R8 describes the router itself, including the existence
of subnet 172.16.3.0/24, as seen on the right side of the figure.
The figure above shows a rather basic flooding process, with R8 sending the original LSA for itself, and the other routers flooding the LSA by forwarding it until every router has a copy. The flooding process has a way to prevent loops so that the LSAs do not get flooded around in circles.
Basically, before sending an LSA to yet another neighbor, routers communicate, and ask “do you already have this LSA?” and then they avoid flooding the LSA to neighbors that already have it.
Once flooded, routers do occasionally re-flood a particular LSA. Routers re-flood an LSA when
some information changes, for example, when a link goes up or comes down. They also re-flood
each LSA based on each LSA’s separate aging timer (default is 30 minutes).
Applying Dijkstra SPF Math to Find the Best Routes in OSPF
The link-state flooding process results in every router having an identical copy of the LSDB in memory, but the flooding process alone does not cause a router to learn what routes to add to the IP routing table. Although incredibly detailed and useful, the information in the LSDB does not explicitly state each router’s best route to reach a destination.
To build routes, link-state routers have to do some math. Thankfully, we do not have to know the math! All link-state protocols use Dijkstra Shortest Path First (SPF) algorithm, to process the LSDB.
This algorithm analyzes the LSDB, and builds the routes that the local router should add to the IP routing table—routes that list a subnet number and mask, an outgoing interface, and a next-hop router IP address.
The Basics of OSPF Neighbors
OSPF neighbors are routers that both use same routing protocol and also the same data link protocol. That means two routers connected to the same VLAN become OSPF neighbors, or two routers on the ends of a serial link become OSPF neighbors.
Two routers need to do more than to simply exist on the same link to become OSPF neighbors;
they must send OSPF messages and agree to become neighbors. To do so, the routers send
Hello messages to introduce themselves to the neighbor. Assuming the two neighbors have compatible OSPF parameters, the two form a neighbor relationship, and would be displayed in the output of the show ip ospf neighbors command in Cisco routers.
Finally, the OSPF neighbor model allows new routers to be dynamically discovered. That means
new routers can be added to a network without requiring every router to be reconfigured. Instead, the configuration enables OSPF on a router’s interfaces, and then the router reacts to any Hello messages from new neighbors, whenever those neighbors happen to be installed.
Meeting Neighbors and Learning Their Router ID in OSPF
We know that OSPF process starts with messages called Hello messages. The Hellos in turn list each router’s Router ID (RID), which serves as each router’s unique name or identifier. Finally, OSPF does several checks of the information in the Hello messages to ensure if the two routers should become neighbors.
RIDs are 32-bit numbers. As a result, most command output lists these as dotted decimal numbers. Additionally, by default, routers chooses its OSPF RID based on an interface IPv4 address, because those are some nearby convenient 32-bit numbers as well. However, the RID can be directly configured.
As soon as a router has chosen its RID and the connected interface between two routers come up, the router is ready to become OSPF neighbors if following steps pass:
- The devices must be in the same area.
- The devices must have the same authentication configuration.
- The devices must be on the same subnet.
- The devices hello and dead intervals must match.
- The devices must have matching stub flag.
- MTU unit must be the same on both routers.
OSPF hello message
To discover other OSPF-speaking routers, a router sends multicast OSPF Hello packets to each interface and hopes to receive Hello packets from other routers connected to those interfaces. The front figure outlines the basic concept.
Routers A and B both send Hello messages onto the LAN. They continue to send Hellos at a
regular interval based on their Hello Timer settings. The Hello messages themselves have the following features:
- The Hello message follows the IP packet header, with IP protocol type 89.
- Hello packets are sent to multicast IP address 220.127.116.11, a multicast IP address intended for all OSPF-speaking routers.
- Routers listen for packets sent to IP multicast address 18.104.22.168, in part hoping to receive Hello packets and learn about new neighbors.
The Hello messages contain a variety of parameters. These details let each router know
something about their potential neighbor, including whether the two routers should or should
not become neighbors.
For example, two OSPF routers will not become neighbors if the IPv4 addresses of their interface are in different subnets. So, just because two routers happen to hear a Hello from a neighbor does not mean that they will become neighbors. However, if routers do become neighbors, they will begin to exchange their LSDBs and then calculate new IP routes.
Scaling OSPF Through Hierarchical Design
OSPF can be used in some networks with very little thought about design issues. However, in large networks, engineers need to think about and plan how to use several OSPF features that allow their network to scale well later on.
For instance, the OSPF design in the figure below uses a single area, because this small inter-network does not need the scalability benefits of OSPF areas.
Using a single OSPF area for smaller internetworks, as in the above figure, works well. The configuration is simple, and troubleshooting would be easy. But imagine a network with 900 routers instead of only 11, and several thousand subnets.
In a network that size, the sheer amount of processing required to run the complex SPF algorithm might cause convergence time to be slow just because of the time it takes each router to process all the math. Also, the routers might experience memory shortages.
The problems can be summarized as follows:
- A larger topology database requires more memory on each router.
- Processing the larger-topology database with the SPF algorithm requires processing power that grows exponentially with the size of the topology database.
- A single interface status change (up to down, or down to up) forces every router to run SPF again!
Breaking OSPF LSDB size with Area
OSPF breaks up the large and complex task of running SPF on a large LSDB by using areas. The
engineer places some links on one area, some in another, others in yet a third area, and so on.
OSPF then creates a smaller LSDB per-area, rather than one huge LSDB for all links and routers
in the internetwork. With smaller topology databases, routers consume less memory and take
less processing time to run SPF.
Multiarea design puts all of link – a serial link, and VLAN, and so on – inside an area. To
make that work, some routers (Area Border Routers, or ABRs) sit at the border between multiple areas. Routers D1 and D2 serve as ABRs in the area design shown in the figure below.
While the above figure shows a sample area design and some terminology related to areas, it does not show the power and benefit of the areas. By using areas, the OSPF SPF algorithm ignores the details of the topology in the other areas.
For example, when Router B1 (area 1) is processing a complex SPF math, it ignores the topology information about area 0 and area 2. This way, each router has far less SPF work to do and finishes its SPF work more quickly, finding the currently best OSPF routes.
OSPF network Command
The network command is used to identify which device interface will be included within the OSPF process and to what area the interface will be assigned to. OSPF sends hello packets from the interfaces which are in the range of network command by using wildcard mask.
The network command compares the first parameter in the command to each interface IP address on the local router, trying to find a match. However, rather than comparing the entire number in the network command to the entire IPv4 address on the interface, the router can compare a subset of the octets, based on the wildcard mask, as follows:
Wildcard 0.0.0.0: Compares all 4 octets. In other words, the numbers must exactly match.
Wildcard 0.0.0.255: Compares the first 3 octets only, ignoring the last octet.
Wildcard 0.0.255.255: Compares the first 2 octets only and ignors the last 2 octets.
Wildcard 0.255.255.255: Compares the first octet only and ignores the last 3 octets.
Wildcard 255.255.255.255: Compares nothing; this wildcard mask means that all addresses
will match the network command.
Basically, a wildcard mask value of 0 in an octet tells the router to compare to see if the numbers
match, and a value of 255 tells the router to ignore that octet when comparing the numbers.
OSPF Router ID
While OSPF has many other optional features, most enterprise networks that use OSPF choose to configure each router’s router ID. OSPF routers must have a Router ID (RID) for proper operation. By default, routers will choose an interface IP address to use as the RID. However, many network engineers prefer to choose each router’s ID, so command output from commands like show ip ospf neighbor lists more recognizable router IDs in Cisco devices.
To find its RID, a router uses the following process when the router reloads and brings up the OSPF process. Note that when one of these steps identifies the RID, the process stops.
- If the router-id is configured, this value is used as the RID.
- If any loopback interfaces have an IP address configured and the interface’s status is up, the router picks the highest numeric IP address among these loopback interfaces.
- The router picks the highest numeric IP address from all other interfaces that are physically up. In other words, an interface in up/down state will be included by OSPF when choosing its router ID.
Note that A loopback interface is a virtual interface that can be configured. Loopback interfaces are always in an “up and up” state unless administratively placed in a shutdown state.
OSPF Passive Interfaces
Once OSPF has been enabled on an interface with network command , the router tries to discover neighboring OSPF routers and form a neighbor relationship. The router also listens for incoming Hello messages from potential neighbors.
Sometimes, a router does not need to form neighbor relationships with neighbors on an interface. Often times, no other routers exist on a particular link, so the router has no need to keep sending those repetitive OSPF Hello messages.
When a router does not need to discover neighbors off some interface, the engineer has a couple of configuration options. First, by doing nothing, the router keeps sending the messages, wasting some small bit of CPU cycles and effort. Alternately, the engineer can configure the interface as an OSPF passive interface, telling the router to do the following:
- Quit sending OSPF Hello messages on that interface
- Ignore received Hellos on that interface
- Do not form neighbor relationships over that particular interface
Remember that by setting an interface on passive, OSPF does not form neighbor relationships over that interface, but it does still advertise the subnet that is connected to that interface.