Open Shortest Path First
Open Shortest Path First (OSPF) is a link-state routing protocol that was developed for IP networks and is based on the Shortest Path First (SPF) algorithm. OSPF is an Interior Gateway Protocol (IGP).
In an OSPF network, routers or systems within the same area maintain an identical link-state database that describes the topology of the area. Each router or system in the area generates its link-state database from the link-state advertisements (LSAs) that it receives from all the other routers or systems in the same area and the LSAs that itself generates. An LSA is a packet that contains information about neighbors and path costs. Based on the link-state database, each router or system calculates a shortest-path spanning tree, with itself as the root, using the SPF algorithm.
- Compared with distance-vector routing protocols such as the Routing Information Protocol (RIP), OSPF is more suitable for serving large, heterogeneous internetworks. OSPF can recalculate the routes in a short amount of time when the network topology changes.
- With OSPF, you can divide an Autonomous System (AS) into areas and keep area topologies separate to decrease the OSPF routing traffic and the size of the link-state database of each area.
- OSPF provides equal-cost multipath routing. You can add duplicate routes to the TCP stack using different next hops.
OSPF Hello protocol and link-state database exchange
After routers or systems in an OSPF network ensure that their interfaces are functional, they first send out Hello packets, using the Hello protocol over their OSPF interfaces, to discover neighbors. Neighbors are routers or systems that have interfaces to the common network. After that, neighboring routers or systems exchange their link-state databases to establish adjacencies.
The following figure illustrates the process of discovering neighbors and establishing adjacencies for two systems in the 188.8.131.52 subnet. Each system has an OSPF interface to the common subnet 184.108.40.206 (interface 220.127.116.11 for system A and interface 18.104.22.168 for system B). Subnet 22.214.171.124 belongs to area 126.96.36.199.
- EXSTART phase
- This is the first step of the link-state database exchange. The two systems negotiate who is the master and who is the subordinate.
- EXCHANGE phase
- The two systems exchange Database Description packets to find out the LSAs that the link-state database of each system does not include. Each system stores the LSAs that are not included in its link-state database in the retransmission list.
- LOADING phase
- Each system sends Link State Request packets to request the neighbor (the other system in this example) to send to it the entire LSAs that were stored in the retransmission list during the EXCHANGE phase. The neighbor responds to the request with the LSAs in Link State Update packets.
- FULL phase
- When the two systems finish exchanging LSAs and their link-state databases are synchronized, adjacency is established between the two systems.
After adjacencies are established between all the routers or systems in an area, each router or system in the area periodically sends an LSA to share its adjacencies or to report its state change. By comparing the established adjacencies with the LSAs, routers or systems in the area can discover the area topology changes and update their link-state databases accordingly.
Designated router and backup designated router
In a multiaccess OSPF network that has at least two attached routers, the routers elect a designated router and a backup designated router using the Hello protocol. (A multiaccess network is a network in which multiple devices can connect and communicate simultaneously.)
The designated router generates LSAs for the entire multiaccess network, floods the LSAs to the other routers in the network, and determines which routers should become adjacent. All the other routers in the network are adjacent to the designated router. The designated router decreases the network traffic and the size of the link-state database for this network.
The backup designated router does not have any differences from the other routers except that it needs to establish adjacencies with all the routers in the network (including the designated router). The backup designated router is promoted to the designated router when the current designated router fails.
In Figure 1, the 188.8.131.52 subnet is a broadcast network. Therefore, the routers in the 184.108.40.206 subnet elect a designated router and a backup designated router using the Hello protocol. In this example, system A is elected as the designated router and system B is elected as the backup designated router.
Splitting an OSPF AS into areas
Unlike RIP, OSPF can operate within a hierarchy. The largest entity within the hierarchy is the AS. An AS is a group of networks under a common administration that share a common routing strategy. An AS can be divided into areas, which are connected to each other by routers. An area consists of groups of contiguous networks and attached hosts. The topology of an area is invisible to entities outside the area. Routers within the same area have an identical link-state database. Separate area topologies allow for less routing traffic and smaller link-state database for each area.
A router that is located on the border of OSPF areas and connects these areas to the backbone network is called area border router. An area border router has multiple interfaces to multiple areas and maintains separate link-state databases for each area.
In the following figure, two areas (area 220.127.116.11 and area 18.104.22.168) are configured. System B is an area border router, with interface 22.214.171.124 attached to area 126.96.36.199 and with interface 188.8.131.52 attached to area 184.108.40.206. System B has two link-state databases, one for each area. System B establishes adjacencies with system A and router C in area 220.127.116.11 through interface 18.104.22.168, and establishes adjacency with system D in area 22.214.171.124 through interface 126.96.36.199.