OSPF protocol

Table of contents

Terminology

• ABR - router located at OSPF areas borders.
• ASBR - a router located at the autonomous system border and connected to the external networks.
• DR - designated router.
• BDR - backup designated router.
• LSA - link state advertisement.
• LSDB - link state data base.
• DBD - LSDB short description.
• LSR - link state advertisement request.
• LSU - link state update, reply on LSR.
• LSAck - acknowledgment upon receiving an LSU.

OSPF protocol

OSPF (Open Shortest Path First) - a dynamic routing protocol based on an algorithm that constructs a shortest path tree. The OSPF protocol has the following features:

• OSPF was developed by the IETF community in 1988. Since it is an open protocol, it can be used in heterogeneous networks built using equipment from different manufacturers.
• Today, two versions of the OSPF protocol are relevant: version 2 for IPv4 networks, described in RFC 2328, and version 3 for IPv6 networks, described in RFC 2740. InfiNet devices support the operation of the IPv4 protocol, therefore, in this article only OSPF version 2 will be described.
• OSPF is a link state dynamic routing protocol.
• OSPF is an internal routing protocol, i.e. used to exchange routing information within an autonomous system (AS).
• The OSPF service messages are encapsulated in IP packets. The upper layer protocol field is set to 89.
  Two multicast addresses are reserved for OSPF: 224.0.0.5 and 224.0.0.6. These addresses are described below (see setting up neighborhood relations and  DR and BDR selection algorithm).
• The distance value for the OSPF protocol is 110.

OSPF area

The number of autonomous system routers that use OSPF to exchange routing information can be large. This leads to a high load of the communication channels because of the large number of OSPF service messages. To reduce the amount of transmitted service information, the OSPF protocol divides the autonomous system into areas.

Each area has a 32-bit identifier, which is usually written in two formats:

• four octet format: used in the device's configuration. For example, areas 0 and 2 (Figure 1a) will be written as 0.0.0.0 and 0.0.0.2 when configuring the devices;
• number format: used in schemes (Figure 1a-b) in order to make it easier to understand and easier to remember.

It is not necessary to use sequential identifiers for areas. For example, the network can include areas with identifiers 0, 2 and 7 (Figure 1a).

An interface belongs to an area, not the device itself. Thus, one router can be connected to multiple areas through its interfaces (Figure 1a).

The area with the identifier 0.0.0.0 has a special role - this area is called the backbone area. The backbone area is a requirement for the OSPF operation. Each area must be directly connected to the backbone area, i.e. a scheme in which some area is connected to another one without having a direct connection to the backbone is prohibited (Figure 1b).

Routers types

Depending on the router's place in the network, the following types of devices are distinguished (Figure 2):

• Internal router (IR): a router which has all its interfaces associated with the same area. Routers R2 and R4 are internal.
• Backbone router (BR): a router with an interface connected to the backbone area. Routers R1, R2 and R3 are backbone routers.
• Area border router (ABR): a router having interfaces associated with different OSPF areas. Router R3 is ABR because it is located at the border of areas 0 and 2.
• Autonomous system border router (ASBR): a router connected to an external network. Router R1 is ASBR because it is connected to a third party LAN.

OSPF's operation

The OSPF's operation follows the below steps. Some steps will require a detailed explanation which is provided in the sections below.

• Step 1: OSPF protocol launching. The configuration of the devices includes a list of interfaces that will participate in the OSPF's protocol operation associated with the area identifiers to which these interfaces are connected. Upon this configuration, OSPF is launched.
• Step 2: Setting up neighboring relations. The device makes an attempt to find other routers and establish neighboring relations using the list of interfaces defined in step 1.
• Step 3: Role distribution. To reduce the service traffic volume in the broadcast network segments, a designated router (DR) is elected, which will be the central point for routing information exchange inside the broadcast segment.
• Step 4: Link state database (LSDB) synchronization. OSPF requires that each router has the same set of routing information, which implies the synchronization of the link state databases.
• Step 5: Building the shortest paths tree (SPT). Dijkstra's algorithm is applied to the routing information obtained in step 4 in order to build the shortest path tree. The root of the tree is the device on which the algorithm is running and the branches are the known destination networks, obtained from the other routers. Thus, each device has a set of paths to each network, optimized using the metric.
• Step 6: Export of the routes to the FIB. The set of routes obtained in step 5 is stored in the RIB, so that the device can perform additional optimizations by comparing the Distance values for the routing information obtained from different sources. The best routes obtained during the comparison are placed in the FIB and used to transfer the user and the service data.
• Step 7: Continuous monitoring of the network's state. Dynamic routing protocols perform constant link state monitoring, because the routing table of all the devices must be kept up to date.

OSPF protocol launching

Two processes are performed when the OSPF service is launching: the selection of a router identifier  and the definition of a list of interfaces that will participate in OSPF.

The router has a 32-bit identifier, which is usually written in the IP address format. Usually, the identifier is not connected with the device's IP address and can be set manually. If the identifier is not set manually, it will be automatically selected as the highest IP address of the device. In case of manual ID selection, it is recommended to set it in the IP address of the loopback0 interface. This will help to identify the devices easier and to speed up the diagnostic of the network problems.

During the automatic router ID selection, the Infinet device generates a special address from the 224. *. *. * multicast subnet, associated with the router's serial number. This helps to avoid the redefinition of the ID when the IP address or the network interface are removed.

The set of interfaces that will take part into the OSPF's protocol operation is determined according to the following rules:

• the range of IP addresses (or subnet) and their association with a specific area are specified in the configuration of the device (router);
• the network interfaces having IP addresses included in the specified range will take part into the OSPF process and become associated with the specified area. Note: not only the IP address of the interface is checked to see if it included in the specified range, but the whole network associated with the interface (see the example below).

If OSPF has not been started on a network interface, this does not mean that the network associated with this interface will not be advertised to the other routers. Launching OSPF on an interface only impacts the discovery of the neighbors.

Let's take a look at some examples of how to start the OSPF service on router R1 (Figure 3). The table below contains the configuration commands and their correspondence with the router's interfaces; if a match is found, a neighbor discovery process will be performed on the interface.

Passive interfaces

After the router has determined the list of interfaces where OSPF is running, it starts looking for neighbors connected to these interfaces. Besides that, all the networks assigned to these interfaces will be advertised to the other routers. This behavior can be exploited by an attacker: the router will establish neighboring relations with the attacker's device and will transmit all the routing information about the network.

This type of attack can be prevented by using passive interfaces. Any interface participating in OSPF can be configured as passive. In this case, the search for neighbors via such an interface will not be performed, however, the network assigned to this interface will be advertised to the other routers.

External routes

The list of networks that are assigned to the interfaces is defined when OSPF starts. in addition, OSPF can advertise routes to other networks, that were added to the device's routing table. The announcement of such routes is called redistribution. These routes are external to OSPF.

The routing sources for redistribution can be other dynamic routing protocols, static entries or directly attached networks not added to OSPF.

Setting up neighboring relations

Routing information exchange is possible only after the establishment of neighbor relations between the routers. Two routers having a common link will establish a neighborhood relationship if the following parameters match:

• address and netmask at the interface towards a potential neighbor;
• MTU value on interfaces towards a potential neighbor;
• area ID and area type;
• authentication parameters;
• Hello messages interval and Router dead interval (see step 1 of setting up neighboring relations).

Neighborhood relations are established in several steps. Let's look at the network example (Figure 4a): the network consists of three routers R1, R2 and R3 connected to the switch, neighbor relations are established between the routers, R2 router is selected as the designated router (DR), R3 as the backup designated router (BDR) ). Router R4 will be added to the network scheme, and let's assume that the conditions for establishing neighborhood relations are met.

• Step 1: R4 router sends Hello messages to the multicast address 224.0.0.5 (Figure 4b). This address is supported by all devices running OSPF. Hello messages are sent from all interfaces defined during OSPF launch with a specified periodicity. The default Hello message broadcast interval is 10 seconds. Hello messages are an indicator of the connection with the neighbor, therefore, if no Hello messages are received from the neighbor during the Router dead interval, the device is marked as unavailable. By default, the Router dead interval is equal to four Hello message intervals.
• Step 2: R1, R2 and R3 routers receive Hello from R4 and add it to the list of neighbors with the Init status (Figure 4b).
• Step 3: in accordance with internal timers, R1, R2, R3 routers send Hello messages to router R4 (Figure 4c). Since Hello messages contain a list of neighbors, messages sent to R4 contain its ID. This means that router R4 can add all routers to the list of neighbors with 2-Way statuses, skipping the Init status. Then R4 will generate Hello messages for routers, where it will indicate routers R1 and R3 as neighbors, which will allow R1, R2 and R3 to change the status for R4 from Init to 2-Way (Figure 4d).
• Step 4: in broadcast segments (Ethernet, MINT, etc.), routers designated as primary (DR) and backup (BDR) must be selected. The rest routers will be set as the DROther roles. This mechanism is intended to reduce the overhead traffic amount: each DROthers will exchange routing information only with DR and BDR. The DR and BDR selection algorithm is describer below. Note, roles are not assigned to a device, but to an interface, so a router that has multiple interfaces in different broadcast segments may be DR in one and DROther in the other.
  • Step 4a: let R2 be DR and R3 - BDR as it was before R4 has been connected to the network. To routers R1 and R4 are set the DROther roles, so the relationship status between them will remain 2-Way.
• Step 5: routers pairs R2-R4 and R3-R4 distribute the roles of master and slave among themselves, the status of their relationship becomes ExStart.
• Step 6: master device first starts the exchange of service messages with a brief DBD route database description. During the exchange of such messages, the relationship status is set to Exchange.
• Step 7: devices receive a route database short description from a neighbor and generate requests for detailed information about unknown networks. These messages are called LSRs.
  • Step 7a: LSU is the answer to the LSR. LSUs contain detailed information about the requested routes.
  • Step 7b: the device receives LSU and generates an acknowledgment of information receipt. This message is called LSAck, and it has been appeared due to refuse of using guaranteed delivery protocols such as TCP.
  • Step 7c: all routing information base is called LSDB, and the exchange of LSDB service messages changes the relationship status to Loading.
• Step 8: after LSDB synchronization on devices, the relationship between routers R4-R2 and R4-R3 is set to the Full status (Figure 4e). Note that DR and BDR establish Full relationships with all routers at the segment.

Roles distribution

In each broadcast segment where OSPF is running, DR and BDR elections are performed. Elections are carried out in accordance with the following rules:

• Interface priority value: DR is the router with the highest priority value, BDR is the router following DR in priority value, DROther - other routers. Priority - the parameter of the router interface, connected to the broadcast segment. The priority is set manually by the network administrator, can be in the range from 0 to 255. By default, the priority is 1, if the router interface priority value is set to 0, then that router does not participate in the DR and BDR elections.
• Router-id value: DR is the router with the highest Router-id value, BDR is the router following DR in Router-id value, DROther - other routers. The Router-id is unique, so the router IDs comparison is used when the priorities are equal, which ensures the roles distribution.

The group address 224.0.0.6 is associated with DR and BDR devices, which is used for LSDB synchronization. Devices with DR and BDR roles establish a Full relationship with each router in broadcast segment, it leads to higher demands on device performance compared to DROther. If the devices hardware performance can become a bottleneck, it should be taken into account during network planning, interface prioritization should be set to ensure predictable selection of the highest performing devices as DR and BDR.

The main function of DR is the routing information exchange in the broadcast segment. The main function of the BDR is to monitor DR the state and, if it fails, change the role to DR. Since each DROther establishes a Full relationship with both DR and BDR, the LSDB on the BDR is synchronous with the DR, so the BDR can start performing DR functions without timing database synchronization delays. If BDR becomes DR, then BDR is selected among DROther according to the algorithm described above.

LSDB synchronization

Routing information in OSPF is represented as different types of LSA. The LSDB is a set of LSAs. Note, LSA is not an OSPF service message, therefore, DBD, LSR, LSU, LSAck messages are used to transmit it in accordance with the steps 6-8 of the neighbor relationship establishment algorithm.

Supported by WANFleX OS OSPF version 2 defines 7 LSA types shown in the table below. To explain the purpose of different LSAtypes the network sheme at Figue 5a will be used: the network consists of 6 routers, forming three OSPF areas. This scheme describes the LSA types generated by devices regardless of the establishing neighborhood relations stages.

Building the shortest paths tree

After LSDB synchronization, each router performs a shortest paths tree calculation using Dijkstra's algorithm.

In networks with channel redundancy, LSDB contains announcements about the same network received from different sources. Such routes are transmitted to the RIB in the following order:

• Intra-area routes: routes distributed within the same area using LSA types 1 and 2.
• Inter-area routes: routes received from neighboring areas using LSA type 3.
• External routes type 1: routes to external networks received from ASBR. The routes metric for this type is counted as the metrics sum set by the ASBR during announcement plus the metric of a path to the ASBR.
• External routes type 2: are similar to External routes type 1, with a different method of the metric calculation. The metric is equal to the value set by the ASBR during announcement and does not include the path to the ASBR.
• Route metric value: for two routes to the same network received from sources of the same type, the metric values are compared. The route with the lower metric value will be added to the RIB.

Areas types

The way to reduce the OSPF service traffic volume is to use different types of areas. The protocol provides for the following types of areas:

• Normal;
• Stub;
• Totally Stub;
• NSSA;
• Totally NSSA.

Let's look the main features of different areas types at the example via the following scheme (Figure 6): routers R1, R2, R3 and R4 are connected in sequence with each other, forming three OSPF areas. Routers R3 and R4 have external links. In each example, we will change the type of area 4 and analyze the LSA types associated with that area. In these examples, the details of LSA not connected with area 4 and LSA of types 1 and 2 will be omitted because they are distributed within areas of any type.

Normal

Normal areas do not change the LSA propagation and processing logic described above (Figure 7a). This area type is used by default. The backbone area is a special case of the Normal area.

Stub

The Stub area is characterized by the following features (Figure 7b):

• The Stub area cannot have external links. Thus LSA types 5 and 4 are prohibited in the Stub area.
• Stub area routing information is distributed to neighboring areas using LSA type 3.
• LSA Type 3 about networks in third areas are distributed in the Stub area, similarly to the Normal areas.
• LSA type 5 from third areas, when it enters the Stub area, is converted to LSA type 3 with default route information.

Stub areas are used in LAN segments that have no connection to external links, but routers in this area must receive routing information from neighboring areas in full. The Stub areas using allows to obtain a small performance increasment by reducing the LSA number and to protect the network from attacks that involve connecting the router to the external network segment.

Totally Stub

The Totally Stub area behaves similarly to the Stub area with one exception: LSA of types 3 and 5 from neighboring areas are replaced with one LSA type 3 with a default route (Figure 7c).

Totally Stub areas applications are similar to Stub, but the area routers will not have all the routing information about neighboring areas. This will give significant performance increase as Totally Stub area routers will use a single default route to transmit data to neighboring areas.

NSSA

The NSSA has the characteristics of the Stub area with one exception: the NSSA can have an external link (Figure 7d). Since LSA type 5 which are used to distribute routing information about external links, are prohibited in Stub areas, NSSA use LSA type 7 for this purpose. This LSA type has the same structure as LSA type 5, but is permitted for distribution in NSSA areas. At the area border the ABR converts LSA type 7 to LSA type 5, setting itself as the source. Since ABR performing the LSA conversion become the source, there is no need to create an additional type 4 LSA.

Usually, the NSSA area using is a result of the network development: connecting an external communication channel to the Stub area requires changing its type to NSSA.

Totally NSSA

Totally NSSA behave similarly to NSSA with the exception: only one type 3 LSA with a default route is exported to the Totally NSSA (Figure 7e).

Totally NSSA areas is a result of the network development: connecting an external link to a Totally Stub area requires changing the area type to Totally NSSA.

Virtual link

One of the OSPF principles is possibility to connect two non-backbone areas only through the backbone area. Despite that, as a result of the historical development, the structure of some networks does not match to this principle. Bringing such networks up to OSPF requirements can be costly, so OSPF has been extended with the virtual link concept.

The virtual link has the following features (Figure 8):

• A virtual link is a logical connection configured on two ABRs, one of which is connected to the backbone area. Routers R1 and R2 are ABRs on which a virtual network interface is created, R2 is connected to the backbone area via eth1interface.
• The virtual link is the interface used by R2 to connect area 4. All LSA types are distributed over the virtual link, like through a normal interface.
• The area that is common for two ABRs organizing a virtual link is called a transit area. In the example below, area 7 is the transit.
• Transit area should have Normal type. It is not possible to establish a virtual link through Stub or NSSA areas.

OSPF protocol features

OSPF protocol features can be represented in following way:

• Open implementation: OSPF is an open protocol, so it can be used on equipment from different manufacturers.
• Easy configuration: in small networks, the protocol can be started with two commands.
• Flexible configuration: wide protocol tools set allows to implement many network schemes.
• Scalability, fault tolerance, balancing, efficiency: similar to the ODR, OSPF has advantages of dynamic routing protocols.
• High entry threshold: understanding the OSPF terminology and logic is time consuming.

Additional materials

Webinars

1. Typical scenario of routing setting using Infinet Wireless devices. Part II

Other

1. Ifconfig command (interfaces configuration)
2. ARDA (Aqua Router Daemon)
3. OSPF command
4. arip command
5. rip command
6. RFC 2328