Overview

OSPF is Interior Gateway Protocol (IGP) designed to distribute routing information between routers belonging to the same Autonomous System (AS).

OSPF is based on link-state technology that has several advantages over distance-vector protocols such as RIP:

• no hop count limitations;
• multicast addressing is used to send routing information updates;
• updates are sent only when network topology changes occur;
• the logical definition of networks where routers are divided into areas
• transfers and tags external routes injected into AS.

However, there are few disadvantages:

• OSPF is quite CPU and memory intensive due to the SPF algorithm and maintenance of multiple copies of routing information;
• more complex protocol to implement compared to RIP;

OSPF Terminology

Term definitions related to OSPF operations.

• Neighbor - connected (adjacent) router that is running OSPF with the adjacent interface assigned to the same area. Neighbors are found by Hello packets (unless manually configured).
• Adjacency - logical connection between a router and its corresponding DR and BDR. No routing information is exchanged unless adjacencies are formed.
• Link - link refers to a network or router interface assigned to any given network.
• Interface - physical interface on the router. The interface is considered as a link when it is added to OSPF. Used to build link database.
• LSA - Link State Advertisement, data packet contains link-state and routing information, that is shared among OSPF Neighbors.
• DR - Designated Router, chosen router to minimize the number of adjacencies formed. The option is used in broadcast networks.
• BDR -Backup Designated Router, hot standby for the DR. BDR receives all routing updates from adjacent routers, but it does not flood LSA updates.
• Area - areas are used to establish a hierarchical network.
• ABR - Area Border Router, router connected to multiple areas. ABRs are responsible for summarization and update suppression between connected areas.
• ASBR - Autonomous System Boundary Router, router connected to an external network (in a different AS). If you import other protocol routes into OSPF from the router it is now considered ASBR.
• NBMA - Non-broadcast multi-access, networks allow multi-access but have no broadcast capability. Additional OSPF neighbor configuration is required for those networks.
• Broadcast - Network that allows broadcasting, for example, Ethernet.
• Point-to-point - Network type eliminates the need for DRs and BDRs
• Router-ID - IP address used to identify OSPF router. If the OSPF Router-ID is not configured manually, a router uses one of the IP addresses assigned to the router as its Router-ID.
• Link State - The term link-state refers to the status of a link between two routers. It defines the relationship between a router's interface and its neighboring routers.
• Cost - Link-state protocols assign a value to each link called cost. the cost value depends on the speed of the media. A cost is associated with the outside of each router interface. This is referred to as interface output cost.
• Autonomous System - An autonomous system is a group of routers that use a common routing protocol to exchange routing information.

All of these terms are important for understanding the operation of the OSPF and they are used throughout the article.

Understanding OSPF Areas

A distinctive feature of OSPF is the possibility to divide AS into multiple routing Areas which contain their own set of neighbors.
Imagine a large network with 300+ routers and multiple links between them. Whenever link flaps or some other topology change happens in the network, this change will be flooded to all OSPF devices in the network resulting in a quite heavy load on the network and even downtime since network convergence may take some time for such a large network. 

The introduction of areas allows for better resource management since topology change inside one area is not flooded to other areas in the network. The concept of areas enables simplicity in network administration as well as routing summarization between areas significantly reducing the database size that needs to be stored on each OSPF neighbor.

Each OSPF area has its own unique Area ID and the area with an Area ID of 0.0.0.0 is the main one to which any other area should connect (it is called the Backbone area). Routers that connect to more than one area are called ABR (Area Border Routers), their main responsibility is summarization and update suppression between connected areas. The router connecting to another routing domain is called ASBR (Autonomous System Boundary Router).

Neighbour Relationship and Adjacency

OSPF is a link-state protocol that assumes that the interface of the router is considered an OSPF link. Whenever OSPF is started, it adds the state of all the links in the local link-state database.

There are several steps before the OSPF network becomes fully functional:

• Neighbors discovery
• Database Synchronization
• Routing calculation

Link-state routing protocols are distributing, replicating database that describes the routing topology. The link-state protocol's flooding algorithm ensures that each router has an identical link-state database and the routing table is calculated based on this database.

After all the steps above are completed link-state database on each neighbor contains full routing domain topology (how many other routers are in the network, how many interfaces routers have, what networks link between router connects, cost of each link, and so on).

Communication Between OSPF Routers

OSPF operates over the IP network layer using protocol number 89.
A destination IP address is set to the neighbor's IP address or to one of the OSPF multicast addresses AllSPFRouters (224.0.0.5) or AllDRRouters (224.0.0.6). The use of these addresses is described later in this article.
Every OSPF packet begins with a standard 24-byte header.

There are five different OSPF packet types used to ensure proper LSA flooding over the OSPF network.

• Hello packet - used to discover OSPF neighbors and build adjacencies.
• Database Description (DD) - check for Database synchronization between routers. Exchanged after adjacencies are built.
• Link-State Request (LSR) - used to request up-to-date pieces of the neighbor's database. Out of date parts of routing database are determined after DD exchange.
• Link-State Update (LSU) - carries a collection of specifically requested link-state records.
• Link-State Acknowledgment (LSack) - is used to acknowledge other packet types that way introducing reliable communication.

Neighbors Discovery

OSPF discovers potential neighbors by periodically sending Hello packets out of configured interfaces. By default Hello packets are sent out with 10 second interval which can be changed by setting hello interval in OSPF interface settings. The router learns the existence of a neighboring router when it receives the neighbor's Hello in return with matching parameters.

The transmission and reception of Hello packets also allow a router to detect the failure of the neighbor. If Hello packets are not received within Dead interval (which by default is 40s) router starts to route packets around the failure. Hello protocol ensures that the neighboring routers agree on the Hello interval and Dead interval parameters, preventing situations when not in time received Hello packets mistakenly bring the link down.

On each type of network segment Hello protocol works a little differently. It is clear that on point-to-point segments only one neighbor is possible and no additional actions are required. However, if more than one neighbor can be on the segment additional actions are taken to make OSPF functionality even more efficient.

Two routers do not become neighbors unless the following conditions are met.

• Two-way communication between routers is possible. Determined by flooding Hello packets.
• The interface should belong to the same area;
• The interface should belong to the same subnet and have the same network mask unless it has network-type configured as point-to-point;
• Routers should have the same authentication options, and have to exchange the same password (if any);
• Hello and Dead intervals should be the same in Hello packets;
• External routing and NSSA flags should be the same in Hello packets.

Discovery on Broadcast Subnets

The attached node to the broadcast subnet can send a single packet and that packet is received by all other attached nodes. This is very useful for auto-configuration and information replication. Another useful capability in broadcast subnets is multicast. This capability allows sending a single packet which will be received by nodes configured to receive multicast packets. OSPF is using this capability to find OSPF neighbors and detect bidirectional connectivity.

Consider the Ethernet network illustrated in the image below.

!!!!!!bilde!!!!!! OSPF Broadcast network

Each OSPF router joins the IP multicast group AllSPFRouters (224.0.0.5), then the router periodically multicasts its Hello packets to the IP address 224.0.0.5. All other routers that joined the same group will receive a multicasted Hello packet. In that way, OSPF routers maintain relationships with all other OSPF routers by sending a single packet instead of sending a separate packet to each neighbor on the segment.

This approach has several advantages:

Automatic neighbor discovery by multicasting or broadcasting Hello packets. Less bandwidth usage compared to other subnet types. On the broadcast segment, there are n*(n-1)/2 neighbor relations, but those relations are maintained by sending only n Hellos. If broadcast has the multicast capability, then OSPF operates without disturbing non-OSPF nodes on the broadcast segment. If the multicast capability is not supported all routers will receive broadcasted Hello packet even if the node is not an OSPF router.

Discovery on NBMA Subnets

Non-broadcast multiaccess (NBMA) segments similar to broadcast supports more than two routers, the only difference is that NBMA does not support a data-link broadcast capability. Due to this limitation, OSPF neighbours must be discovered initially through configuration. On RouterOS static neighbour configuration is set in /routing ospf static-neighbor menu. To reduce the amount of Hello traffic, most routers attached to the NBMA subnet should be assigned Router Priority of 0 (set by default in RouterOS). Routers that are eligible to become Designated Routers should have priority values other than 0. It ensures that during the election of DR and BDR Hellos are sent only to eligible routers.

Discovery on PTMP Subnets

Point-to-MultiPoint treats the network as a collection of point-to-point links.

By design PTMP networks should not have broadcast capabilities, which means that OSPF neighbours (the same way as for NBMA networks) must be discovered initially through configuration and all communication happens by sending unicast packets directly between neighbours. On RouterOS static neighbour configuration is set in /routing ospf static-neighbor menu. Designated Routers and Backup Designated Routers are not elected on Point-to-multipoint subnets.

For PTMP networks that do support broadcast, hybrid type named "ptmp-broadcast" can be used. This network type uses multicast Hellos to discover neighbours automatically and detect bidirectional communication between neighbours. After neighbour detection "ptmp-broacast" sends unicast packets directly to the discovered neighbours. This mode is compatible with RouterOS v6 "ptmp" type.

Master-Slave Relation

Before database synchronization can begin, a hierarchy order of exchanging information must be established, which determines which router sends Database Descriptor (DD) packets first (Master). Master router is elected based on highest priority and if priority is not set then router ID will be used. Note that it is a router priority-based relation to arranging the exchanging data between neighbors which does not affect DR/BDR election (meaning that DR does not always have to be Master).

Database Synchronization

Link-state Database synchronization between OSPF routers is very important. Unsynchronized databases may lead to incorrectly calculated routing tables which could cause routing loops or black holes.

There are two types of database synchronizations:

• initial database synchronization
• reliable flooding.

When the connection between two neighbors first comes up, initial database synchronization will happen. OSPF is using explicit database download when neighbor connections first come up. This procedure is called Database exchange. Instead of sending the entire database, the OSPF router sends only its LSA headers in a sequence of OSPF Database Description (DD) packets. The router will send the next DD packet only when the previous packet is acknowledged. When an entire sequence of DD packets has been received, the router knows which LSAs it does not have and which LSAs are more recent. The router then sends Link-State Request (LSR) packets requesting desired LSAs, and the neighbor responds by flooding LSAs in Link-State Update (LSU) packets. After all the updates are received neighbors are said to be fully adjacent.

Reliable flooding is another database synchronization method. It is used when adjacencies are already established and the OSPF router wants to inform other routers about LSA changes. When the OSPF router receives such Link State Update, it installs new LSA in the link-state database, sends an acknowledgment packet back to the sender, repackages LSA in new LSU, and sends it out all interfaces except the one that received the LSA in the first place.

OSPF determines if LSAs are up to date by comparing sequence numbers. Sequence numbers start with 0×80000001, the larger the number, the more recent the LSA is. A sequence number is incremented each time the record is flooded and the neighbor receiving the update resets the Maximum age timer. LSAs are refreshed every 30 minutes, but without a refresh, LSA remains in the database for the maximum age of 60 minutes.

Databases are not always synchronized between all OSPF neighbors, OSPF decides whether databases need to be synchronized depending on the network segment, for example, on point-to-point links databases are always synchronized between routers, but on Ethernet networks databases are synchronized between certain neighbor pairs.

Synchronization on Broadcast Subnets

On the broadcast segment there are n*(n-1)/2 neighbor relations, it will be a huge amount of Link State Updates and Acknowledgements sent over the subnet if the OSPF router will try to synchronize with each OSPF router on the subnet.

This problem is solved by electing one Designated Router and one Backup Designated Router for each broadcast subnet. All other routers are synchronizing and forming adjacencies only with those two elected routers. This approach reduces the number of adjacencies from n*(n-1)/2 to only 2n-3.

The image on the right illustrates adjacency formations on broadcast subnets. Routers R1 and R2 are Designated Router and Backup Designated routers respectively. For example, R3 wants to flood Link State Update (LSU) to both R1 and R2, a router sends LSU to IP multicast address AllDRouters (224.0.0.6) and only DR and BDR listens to this multicast address. Then Designated Router sends LSU addressed to AllSPFRouters, updating the rest of the routers.

DR Election

DR and BDR routers are elected from data received in the Hello packet. The first OSPF router on a subnet is always elected as Designated Router, when a second router is added it becomes Backup Designated Router. When existing DR or BDR fails new DR or BDR is elected to take into account configured router priority. The router with the highest priority becomes the new DR or BDR.

Being Designated Router or Backup Designated Router consumes additional resources. If Router Priority is set to 0, then the router is not participating in the election process. This is very useful if certain slower routers are not capable of being DR or BDR.

Synchronization on NBMA Subnets

Database synchronization on NBMA networks is similar to on broadcast networks. DR and BDR are elected, databases initially are exchanged only with DR and BDR routers and flooding always goes through the DR. The only difference is that Link State Updates must be replicated and sent to each adjacent router separately.

Synchronization on PTMP Subnets

On PTMP subnets OSPF router becomes adjacent to all other routes with which it can communicate directly.

LSA Types

OSPF defines several LSA types:

• type 1 - (Router LSA) Sent by routers within the Area, including the list of directly attached links. Does not cross the ABR or ASBR.
• type 2 - (Network LSA) Generated for every "transit network" within an area. A transit network has at least two directly attached OSPF routers. Ethernet is an example of a Transit Network. A Type 2 LSA lists each of the attached routers that make up the transit network and is generated by the DR.
• type 3 - (Summary LSA) The ABR sends Type 3 Summary LSAs. A Type 3 LSA advertises any networks owned by an area to the rest of the areas in the OSPF AS. By default, OSPF advertises Type 3 LSAs for every subnet defined in the originating area, which can cause flooding problems, so it´s a good idea to use a manual summarization at the ABR.
• type 4 - (ASBR-Summary LSA) It announces the ASBR address, it shows “where” the ASBR is located, announcing its address instead of its routing table.
• type 5 - (External LSA) Announces the Routes learned through the ASBR, is flooded to all areas except Stub areas. This LSA divides into two sub-types: external type 1 and external type 2.
• type 6 - (Group Membership LSA) This was defined for Multicast extensions to OSPF and is not used by RouterOS.
• type 7 - type 7 LSAs are used to tell the ABRs about these external routes imported into the NSSA area. Area Border Router then translates these LSAs to type 5 external LSAs and floods as normal to the rest of the OSPF network
• type 8 - External Attributes LSA (OSPFv2) / link-local LSA (OSPFv3)
• type 9 - Link-Local Scope Opaque (OSPFv2) / Intra Area Prefix LSA (OSPFv3). LSA of this type is not flooded beyond the local (sub)network.
• type 10 - Area Local Scope Opaque. LSA of this type is not flooded beyond the scope of its associated area.
• type 11 - Opaque LSA which is flooded throughout the AS (scope is the same as type 5). It is not flooded in stub areas and NSSAs.

Routing Table Calculation

When link-state databases are synchronized OSPF routers are able to calculate the routing table.
Link state database describes the routers and links that interconnect them and are appropriate for forwarding. It also contains the cost (metric) of each link. This metric is used to calculate the shortest path to the destination network.
Each router can advertise a different cost for the router's own link direction, making it possible to have asymmetric links (packets to destination travel over one path, but response travels a different path). Asymmetric paths are not very popular, because it makes it harder to find routing problems.
The Cost in RouterOS is set to 10 on all interfaces by default. Value can be changed in OSPF interface template configuration menu, for example, to add ether2 interface with a cost of 100:

/routing ospf interface-template add interfaces=ether2 cost=100

The cost of an interface on Cisco routers is inversely proportional to the bandwidth of that interface. A higher bandwidth indicates a lower cost. If similar costs are necessary on RouterOS, then use the following formula:

Cost = 100000000/bw in bps.

OSPF router is using Dijkstra's Shortest Path First (SPF) algorithm to calculate the shortest path. The algorithm places router at the root of a tree and calculates the shortest path to each destination based on the cumulative cost required to reach the destination. Each router calculates its own tree even though all routers are using the same link-state database.

SPT Calculation

Assume we have the following network. The network consists of 4(four) routers. OSPF costs for outgoing interfaces are shown near the line that represents the link. In order to build the shortest-path tree for router R1, we need to make R1 the root and calculate the smallest cost for each destination.

As you can see from the image above multiple shortest paths have been found to 172.16.1.0 network, allowing load balancing of the traffic to that destination called equal-cost multipath (ECMP). After the shortest-path tree is built, a router starts to build the routing table accordingly. Networks are reached consequently to the cost calculated in the tree.

Routing table calculation looks quite simple, however, when some of the OSPF extensions are used or OSPF areas are calculated, routing calculation gets more complicated.