Lesson 38 - OSPF Fundamentals Part1 - Terminology

Open Shortest Path First is the dynamic routing protocol based a link-state algorithm. In the upcoming few posts I will attempt to explain the basics of OSPF operation. Cisco CCNA level of expertise assumes that the candidates know how to implement it in a single area. In my OSPF related posts I will go a bit beyond CCNA requirements but not too much, just enough to help you appreciate this fascinating solution and put OSPF into practice.

Link-state algorithm is faster and more accurate in selecting the best path compared to distance vector approach. The latter algorithm allows routers to know how far the destinations are (distance) and the next-hop router(s) the packets should be sent to (vector). Thus, the routers do not know the topology of the network.

Routers using link-state algorithm create "a map" of the network which allows them to choose paths more accurately. Even though they are more demanding hardware-wise (CPU and RAM memory) they supersede distance vector based solutions.

OSPF Basic Operation

OSPF is a very complex routing protocol but its fundamental operation is quite simple. The steps of operation might be pictured as follows:

1. Each router sends so called hello packets out of all OSPF-enabled interfaces. This way, the OSPF-enabled router discovers directly connected routers which also run OSPF. If certain parameters in the hello packets match between the neighboring routers, they form the relationship called the adjacency. It is a sort of virtual communication between them. 
2. Then, each router exchanges special packets called Link State Advertisements (LSAs) with its neighbors (adjacent routers). In OSPF terminology the word link is the same as the interface. LSAs contain details such as: addresses/network masks configured on the links (interfaces running OSPF of course), the metric, the state of the link (which is its relation to the rest of the network), list of neighbors connected to the link.
3. Each router stores the LSAs in its Link State Database (LSDB). These LSAs are then flooded (advertised) to all OSPF neighbors. As a result of the LSA flooding, all routers in the area have identical LSDBs. An analogy would be having the same road map of a given country which all drivers use. Their journey's starting point is different but the map is still the same.
4. Each router runs Dijkstra's algorithm to select the best path from this topological database (LSDB). This way, each router creates loop free graph indicating the shortest (best) path to each network/subnet advertised. The best paths end up in the routing table.

OSPF Network Types

OSPF distinguishes between two major types of networks:

• Transit Networks - Networks which have two or more attached routers. The packets might be originated or passing through this type of network.
• Stub Networks - Networks which have only one router attached (one exit point). Packets are either originated or destined to these types of networks. A loopback interface is a type of stub network as well. The loopbacks are by default advertised as /32 prefixes (255.255.255.255). If you want to advertise loopbacks with their real network mask length, you must change the OSPF mode of operation to point-to-point (presented in the upcoming posts).

More specifically OSPF defines five different types of networks it can operate on. These are:

• Broadcast - such as Ethernet, Token-Ring
• Non Broadcast Multiple Access (NBMA) - such as Frame-Relay, ATM, X.25 (they may but do not have to be fully meshed)
• Point-To-Multipoint - such as Frame-Relay but treated as point-to-point links (Hub and Spoke)
• Point-to-Point - such as using PPP, HDLC protocols
• Virtual Links - used in special situations if the OSPF area 0 (backbone area) is partitioned or if an OSPF area cannot be connected to the area 0 directly

There are some differences in OSPF operation, depending on what type of network it runs on. I will explain the relevant details in the upcoming posts. 

OSPF routers will go through multiple states with their neighbors before they are ready to route the packets. Some of them will be used on all type of the networks but others only on specific types of networks listed above. 

OSPF Neighbor State Machine

All possible states between the neighbors are shown in pic. 1. They are also referred to as Neighbor State Machine.

Pic. 1 - OSPF Neighbor States.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

Down

In this state, a router has not heard a hello packet from any OSPF neighbor yet.

Attempt

This state is applied only on NBMA networks in which the neighbors are not discovered dynamically but must be configured manually ('neighbor' statement in the config-router context).

Init

A router has heard a hello packet from its neighbor(s), which among other parameters the Router IDs of all the neighbors are listed  (look at hello packet structure in the next post).

2-Way

A router has seen its own Router ID in the hello packet from the neighbor(s). This means that bidirectional communication has been established between the routers.

ExStart

In this state the master/slave relationship is established necessary to exchange Database Description Packets. Since all the packets have their sequence number allowing routers to detect more recent information, initial numbers are negotiated in this state. The router with the highest Router ID becomes the master.

Exchange

The routers will send Database Description packets (description of the LDSB). Link State Request packets to request more recent LSAs are also sent in this state.

Loading

The Link State Request packets are sent to neighbors in the loading state. They request more recent LSAs discovered in the Exchange state. Link State Updates are sent in response to LSRs.

Full

OSPF neighbors are fully adjacent. All information about networks/subnets have been exchanged and acknowledged. 

OSPF Packet Types

In the Neighbor State Machine description, a few types of OSPF packets were mentioned. OSPF uses five types of packets for communication. Take a look at them (pic. 2):

Pic. 2 - OSPF Packet Types.

Icons designed by: Andrzej Szoblik - http://www.newo.pl

Type 1 - Hello

This packet type is used to discover neighbors and maintain the adjacencies between them. More details regarding a hello packet will be presented in the next post.

Type 2 - Database Description

It is used to describe the LSAs so that the receiving router (neighbor) can determine if all LSAs have been synchronized between them (all routers in the area must have the same LSDB). It is accomplished by exchanging the headers of LSAs (Database Description packets aka DD packets) with the neighbor(s). The receiving router will check if it has a match for all LSAs in its local database. If not, LSR packets are sent to retrieve the missing LSAs.

Type 3 - Link State Request

During the exchange state the router creates a list of all missing or older LSAs in the so called Link State Request List. Then, it sends one or more LSR packets asking the neighbor for the copy of all these LSAs.

Type 4 - Link State Update

It is the response to LSR packets. Contains one or more LSAs which are sent to the neighbor which sent LSR. Upon receiving them the router is flooding them to all its neighbors in order to maintain the same LSDB within the OSPF area.

Type 5 - Link State Acknowledgment

Each LSA the router receives must be acknowledged in order to synchronize the LSDB with neighbors reliably. This packet is used to acknowledge the reception of all LSAs.

This lesson's terminology should make it easier for you to understand some details of OSPF operation presented in the upcoming lessons.

In my next post, I will focus in on the process of building adjacency between OSPF routers.