Overview

This chapter describes the Open Shortest Path First (OSPF) routing protocol support in RouterOS.

OSPF is Interior Gateway Protocol (IGP) and distributes routing information only 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;
• 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 SPF algorithm and maintenance of multiple copies of routing information;
• more complex protocol to implement compared to RIP;

MikroTik RouterOS implements OSPF version 2 (RFC 2328) and version 3 (RFC 5340, OSPF for IPv6) as well as Multi Instance Extension (RFC6547).

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 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. Interface is considered as 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. 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 neighbour 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, 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 neighbouring routers.
• Cost - Link-state protocols assign a value to each link called cost. the cost value is depend to speed of 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

Distinctive feature of OSPF is possibility to divide AS into multiple routing Areas which contains their own set of neighbours.
Imagine 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 quite heavy load on the network and even downtime since network convergence may take some time for such a large network. 

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

Each OSPF area has its own unique Area ID and the area with Area ID of 0.0.0.0 is the main one to which any other area should connect (it is called Backbone area).

OSPF Operation

OSPF is a link-state protocol. Interface of the router is considered an OSPF link and state of all the links are stored in link-state database.

Link-state routing protocols are distributing, replicating database that describes the routing topology. Each router in routing domain collects local routing topology and sends this information via link-state advertisements (LSAs). LSAs are flooded to all other routers in routing domain and each router generates link-state database from received LSAs. The link-state protocol's flooding algorithm ensures that each router has identical link-state database and routing table is calculated based on this database.

Looking at the link-state database each routing domain router knows 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.

There are several steps before OSPF network becomes fully functional:

• Neighbors discovery
• Database Synchronization
• Routing calculation

Communication Between OSPF Routers

OSPF runs directly over the IP network layer using protocol number 89.
Destination IP address is set to neighbour's IP address or to one of the OSPF multicast addresses AllSPFRouters (224.0.0.5) or AllDRRouters (224.0.0.6). Use of these addresses are described later in this article.
Every OSPF packet begins with 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 neighbours 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 neighbour's database. Out of date parts of routes 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

Neighbors are discovered by periodically sending OSPF Hello packets out of configured interfaces. By default Hello packets are sent out with 10 second interval. This interval can be changed by setting hello interval. Router learns the existence of a neighbouring router when it receives the neighbour's Hello in return.

The transmission and reception of Hello packets also allows router to detect failure of the neighbour. 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 neighbouring 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 different. It is clear that on point-to-point segments only one neighbour is possible and no additional actions are required. However if more than one neighbour can be on the segment additional actions are taken to make OSPF functionality even more efficient.

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

• Two way communication between routers is possible. Determined by flooding Hello packets.
• Interface should belong to the same area;
• 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 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

Attached node to the broadcast subnet can send 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 to send single packet which will be received by nodes configured to receive multicast packet. OSPF is using this capability to find OSPF neighbours and detect bidirectional connectivity.

Consider Ethernet network illustrated in image below.

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

This approach has several advantages:

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

Discovery on NBMA Subnets

Nonbroadcast multiaccess (NBMA) segments similar to broadcast supports more than two routers, only difference is that NBMA do not support data-link broadcast capability. Due to this limitation OSPF neighbours must be discovered initially through configuration. On RouterOS NBMA configuration is possible in/routing ospf nbma-neighbor menu. To reduce the amount of Hello traffic, most routers attached to 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 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.

On PTMP subnets Hello protocol is used only to detect active OSPF neighbours and to detect bidirectional communication between neighbours. Routers on PTMP subnets send Hello packets to all other routers that are directly connected to them. Designated Routers and Backup Designated routers are not elected on Point-to-multipoint subnets.

Database Synchronization

Link-state Database synchronization between OSPF routers are very important.

There are two types of database synchronizations:

initial database synchronization reliable flooding.

When the connection between two neighbours first come up, initial database synchronization will happen. Unsynchronized databases may lead to calculation of incorrect routing table, resulting in routing loops or black holes.
OSPF is using explicit database download when neighbour connections first come up. This procedure is called Database exchange. Instead of sending the entire database, OSPF router sends only its LSA headers in a sequence of OSPF Database Description (DD) packets. Router will send next DD packet only when previous packet is acknowledged. When entire sequence of DD packets has been received, 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 neighbour responds by flooding LSAs in Link-State Update (LSU) packets. After all updates are received neighbours are said to be fully adjacent.

Reliable flooding is another database synchronization method. It is used when adjacencies are already established and OSPF router wants to inform other routers about LSA changes. When OSPF router receives such Link State Update, it installs new LSA in link-state database, sends an acknowledgement packet back to 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. Sequence number is incremented each time the record is flooded and neighbour receiving update resets Maximum age timer. LSAs are refreshed every 30 minutes, but without a refresh LSA remains in the database for maximum age of 60 minutes.

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

Synchronization on Broadcast Subnets

On broadcast segment there are n*(n-1)/2 neighbor relations, it will be huge amount of Link State Updates and Acknowledgements sent over the subnet if 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 amount of adjacencies from n*(n-1)/2 to only 2n-3.

Image on the right illustrates adjacency formations on broadcast subnets. Routers R1 and R2 are Designated Router and Backup Designated router respectively. For example, R3 wants to flood Link State Update (LSU) to both R1 and R2, 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 Hello packet. The first OSPF router on a subnet is always elected as Designated Router, when second router is added it becomes Backup Designated Router. When existing DR or BDR fails new DR or BDR is elected taking into account configured router priority. 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 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 are similar as 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 it´s address instead of it´s routing table.
• type 5 - (External LSA) Announces the Routes learned through the ASBR, is flooded to all areas except Stub areas. This LSA divides in 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 in 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 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 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 shortest path to 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 travels over one path, but response travels different path). Asymmetric paths are not very popular, because it makes 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 configuration menu, for example to add ether2 interface with cost of 100:

/routing ospf interface add interface=ether2 cost=100

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

Cost = 100000000/bw in bps.

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

SPT Calculation

Assume we have the following network. Network consists of 4(four) routers. OSPF costs for outgoing interfaces are shown near the line that represents the link. In order to build 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 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, 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.