22 pictures to explain OSPF: the most commonly used dynamic routing protocol

Hello everyone, I am Xiao Fu.

RIP Defects

When talking about OSFP, we have to start with RIP.

RIP uses the number of hops to calculate the optimal path to the destination network, which is not suitable in practical applications. It is more reasonable to measure network quality by network bandwidth and link delay.

The maximum number of hops supported by RIP is 16, which cannot be used to build large-scale networks.

RIP converges slowly. RIP will suppress the information update of unreachable routes, and the original routes will become invalid. New routes can only be updated after the suppression time ends.

The update cycle of RIP is long. If a router suddenly goes offline, it will take a long time for other routers to detect it.

RIP uses broadcast to send all routing information. The larger the network scale, the more network resources the routing information occupies.

Therefore, RIP routing is not suitable for large-scale networks, while the OSPF protocol solves these problems and is widely used.

OSPF Principles

OSPF is the abbreviation of Open Shortest Path First. OSPF is an autonomous system internal routing protocol based on link state, used to replace RIP protocol. The most common one is OSPFv2.

Unlike distance vector protocols, link state protocols use the Shortest Path First (SPF) algorithm to calculate and select routes. This type of routing protocol is related to the status of network links or interfaces, such as up, down, IP address, mask, bandwidth, utilization, and latency. Each router announces the known link status to other routers, so that each router on the network has the same understanding of the network structure. Then, the router uses the SPF algorithm to calculate and select routes based on this.

The OSPF protocol uses multicast to send protocol packets, saving resources and reducing interference with other network devices.

OSPF encapsulates protocol packets in IP packets, with protocol number 89. Since the IP protocol is connectionless, OSPF defines some mechanisms to ensure secure and reliable transmission of protocol packets.

In short, OSPF protocol has greater scalability, faster convergence, and greater security and reliability than RIP. It uses incremental route updates to ensure route synchronization and reduce the waste of network resources.

OSPF Protocol Introduction

The OSPF protocol has four main processes:

• Find Neighbors

After the OSPF protocol is started, it first searches for neighbors in the network, that is, confirms that two-way communication is possible through Hello messages.

• Establishing Adjacency

After some routers form neighbor relationships, they begin to establish adjacency relationships. Only routers that have established neighbor relationships can transmit link state information to each other.

• Link state information synchronization

OSPF routers that establish adjacency relationships exchange LSAs (Link State Advertisements) in the network, and finally form an LSDB (Link State Database) containing complete link state information of the network.

• Calculate Routing

After LSDB synchronization is completed, each router in the OSPF area has the same understanding of the network structure, and a complete adjacency relationship is formed between neighboring routers. Then, each router independently calculates the route based on the information in the LSDB using the SPF (Shortest Path First) algorithm.

OSPF Protocol Process

The four processes of OSPF are described in detail as the switching of neighbor states. Different neighbor states have different behaviors.

Down

The initial state of an OSPF neighbor, indicating that the interface has not received any Hello messages from the neighbor.

Init

When a neighbor receives a Hello message, but the message does not contain its own Router-ID, the neighbor state is Init. This state indicates that there is an OSPF router on the direct link, but two-way communication has not been confirmed. Next, the router will add the other party's Router-ID to the Hello message it sends.

What is Router-ID?

Router-ID is used to identify OSPF routers. It is a 32-bit value with the same format as IPv4 address. A network composed of continuous OSPF routers is called an OSPF domain. The Router-ID in the domain must be unique, that is, two routers with the same Router-ID are not allowed in the same domain. Router-ID can be set manually or automatically generated. The common practice is to specify the device's Router-ID as the IP address of the device's loopback interface.

Attempt

Appears only in NBMA networks. When the NBMA interface of the router is started, the neighbor state switches from Down to Attempt. In this state, the router periodically sends Hello messages to the neighbor, but does not receive valid Hello messages from the neighbor. When the router receives a Hello message from the neighbor without its own Router-ID, it switches the neighbor state to Init.

What is NBMA?

NBMA type networks are no longer seen. They allow multiple routers to access, but they do not have broadcast capabilities and cannot use multicast or broadcast. They can only be configured to send OSPF packets in unicast. Frame relay and X.25 are both such networks.

2-Way (two-way communication)

When a router receives a Hello message from its neighbor that contains its own Router-ID, the state switches to 2-Way, indicating that the two routers have formed a neighbor relationship that allows two-way communication.

Electing DR and BDR

If the router is in an MA network, after the neighbor status is 2-Way, DR and BDR elections will be performed.

What is MA Network?

MA network, or multi-access network, is a network that connects multiple devices in the same shared medium. Any two devices in the network can directly communicate at Layer 2. There are two types of MA networks. One is BMA network, which is a broadcast multi-access network, such as Ethernet. The typical scenario is that an Ethernet switch is connected to multiple routers. If a broadcast data is sent out, all routers in the network can receive it. The other is NBMA network, which is a non-broadcast multi-access network, such as frame relay, but frame relay does not support broadcast.

In an MA network, n routers establish adjacency relationships with each other, so there are n(n-1)/2 adjacency relationships, which will consume a lot of router resources and increase the number of LSA flooding in the network. In order to optimize the number of adjacency relationships and reduce unnecessary protocol traffic, OSPF will elect a DR (designated router) and a BDR (backup designated router) in each MA network.

A router that is neither a DR nor a BDR is called a DROther. All DROthers in an MA network only establish OSPF adjacencies with the DR and BDR. The BDR also establishes adjacencies with the DR. The DROthers only stay in the 2-Way state. In this way, there are 2(n-2)+1 adjacencies, and the number is optimized.

The DR will listen to the topology change information in the network and notify other routers of the change information. The BDR will monitor the DR status and take over its work when the DR fails.

The election of DR and BDR is realized through Hello messages, which occurs after the 2-Way state. The Hello message contains the DR priority of the router interface, ranging from 0 to 255, with a default value of 1. Interfaces with a DR priority of 0 are not eligible for DR and BDR election.

When OSPF is activated on an interface, it will check whether there is a DR in the network. If there is, the existing DR will be used, that is, the DR cannot be preempted. Otherwise, the router with the highest priority will be selected as the DR. When the priorities are equal, the router with the largest Router-ID will be selected as the DR. After that, the BDR election will be carried out, and the election process is similar to that of the DR.

It should be noted that DR and BDR are concepts at the interface level. It is not accurate to say that a certain router is a DR. The more precise statement is that a certain interface of a certain router is a DR in this MA network.

In an MA network, the DR must ensure that all routers in the network have the same LSDB, that is, to ensure LSDB synchronization. The DR uses the multicast address 224.0.0.5 to send LSU messages to the network. All OSPF routers will listen to this multicast address and synchronize their own LSDBs. When the DROther senses a topology change, it sends an LSU message to 224.0.0.6 to notify the change. The DR and BDR will listen to this multicast address.

ExSart (Exchange Start)

Next, the router will enter the ExStart state and send an empty DD message for Master/Slave negotiation. The router with the largest Router-ID becomes the Master router, and the sequence number of the DD message is determined by the Master router. The message for Master/Slave negotiation is an empty DD message without an LSA header, and the I bit of the message is set to 1.

Exchange

Next, the router enters the Exchange state and sends a DD message describing its own LSDB to its neighbor. The DD message contains the LSA header. DD messages are sent one by one, and each message has a DD sequence number. The DD sequence number is determined by the Master router and increases during the interaction of DD messages to ensure the orderliness and reliability of the interaction process.

What is a DD message?

DD messages are used to describe LSDB and carry the header data of LSA in LSDB, rather than the complete LSA content. In the process of establishing router adjacency, empty DD messages are used to negotiate Master/Slave first, and then DD messages are used to describe their respective LSDBs. Such DD messages contain the LSA header in LSDB. A router can use multiple DD messages to describe LSDB. In order to ensure the order and reliability of DD message transmission, the Master router uses the incrementing sequence number field to dominate the entire LSDB description process.

Loading

Next, the router enters the Loading state and sends LSR to the neighbor to request the complete information of LSA. The neighbor responds with LSU, which contains the complete information of LSA. After receiving the LSU message, the router needs to send LSAck to confirm the LSA.

Full

When the list of LSAs to be requested on the interface is empty, it means that the router has completed LSDB synchronization with the neighbor and no more LSAs need to be requested. At this time, the neighbor status is Full.

Route calculation

Next, the router starts calculating the route. First, the metric required from one router to another is evaluated. The OSPF protocol determines the shortest path based on the metric of each router interface. The cost of a route refers to the sum of the metrics of all router interfaces on the path to the destination network.

The metric is related to the interface bandwidth. The interface metric of a router is calculated based on the formula 100/bandwidth (Mbps). It is used as a reference value for evaluating network resources between routers. You can also manually specify the metric of a router through commands.

What is a metric?

Each routing protocol has a different definition of metric. OSPF uses Cost as the routing metric. The smaller the Cost value, the better the path (route). Each OSPF-activated interface has an interface Cost value, which is equal to 100/interface bandwidth Mbit/s. The calculation result takes the integer part. When the result is less than 1, the value is 1. This value can also be modified manually. The modified value will directly affect the calculation of the Cost value, thereby affecting the selection of OSPF routes in the network.

Synchronize the LSDB of each router in the OSPF area. Routers achieve LSDB synchronization by exchanging LSAs. LSAs carry not only network connection status information, but also cost information of each interface.

Since an LSA describes the topology of a router or a network segment, the entire LSDB forms a description of the topology of the entire network. All routers obtain exactly the same map.

Use SPF (Shortest Path First) to calculate the route. The OSPF router uses the SPF algorithm to calculate a shortest path tree with itself as the root node. On this tree, the cumulative cost from the root to each node is the smallest, that is, the path from the root to each node is the best, so the route from the root to each node is obtained. After the calculation is completed, the router adds the route to the OSPF routing table. When the SPF algorithm finds that there are two routes to the destination network with the same cost value, both routes will be added to the OSPF routing table to form equal-cost routes.

Conclusion

This article only describes part of the OSPF protocol process in order to give us a preliminary understanding of OSPF.