OSPF protocol state machine and establishment of neighbor adjacency

OSPF protocol basics

OSPF (Open Shortest Path Firs) shortest path first routing protocol is an IGP (Interior Gateway Protocol) routing protocol based on the SPF (shortest path tree) algorithm. It is used in Ethernet networking for routing and loop prevention.
In the early days, RIP (Routing Information Protocol) was used. Both RIP and OSPF are dynamic routing protocols of IGB. The main difference is that RIP selects routes based on the number of hops, while OSPF selects routes based on link state information. At the same time, RIP has been replaced by OSPF due to its huge limitations.

Features of OSPF:

No loopBased on the SPF shortest path tree algorithm, there is no loop in design. For example, our STP protocol also uses an SPF tree structure, which is also used to prevent loops. OSPF also uses inter-area connection rules to ensure that there are no routing loops between areas
Fast convergenceOSPF supports triggered updates and can quickly detect and notify topology changes in autonomous systems. RIP uses hop-by-hop convergence in convergence. Only after the previous device has converged will it send information to the next device for convergence. Therefore, the convergence speed is completely weaker than OSPF
Good scalabilityA large Ethernet environment can be divided into multiple small areas to solve the negative effects caused by network expansion, and it is easy to manage and maintain after the area is divided, and it also reduces the traffic used to synchronize data (LSA)
Support certificationIt supports area authentication and interface authentication. A device configured with authentication can only establish an OSPF relationship with a device that is also configured with authentication and has passed the authentication.

Principle of OPSF

OSPF working process

First, the devices running the OSPF protocol establish neighbors and adjacency relationships with each other, and then send their own link state information (LSA) to each other. Each device builds and maintains its own link state database (LSDB), which contains a single Network link status information in the OSPF area, and SPF algorithm to build a shortest path tree based on LSDB, and fill effective and optimal routing entries into the final IP routing table.
The information contained in an LSA includes:

Type of link
Interface IP address and mask
The router connected on the link
Link bandwidth (overhead)

OSPF packet types

Before explaining the working process of OSPF, first understand the types of OSPF packets:

OSPF packet

OSPF is encapsulated in IP packets, and the protocol number is 89
according to the types:

Hello messageUsed to discover neighbors and maintain neighbor relationships, and also used to select DR and BDR in broadcast and NBMA network environments
DD (Database Description) messageThe data description packet is used to describe its own LSDB. Each entry in the DD packet contains only the header information of the LSA, which can reduce the data size.
Link State Request (LSR) packetsAfter exchanging DD packets, the devices know the missing LSA entries, and then use the LSA request packet LSR to request the missing LSA entries.
LSU (Link State Update) packetsAfter receiving the LSR request, the device puts the LSA entry in the LSA update message LSU and sends it to the peer.
LSACK (Link State Acknowledgment) messageAfter receiving the LSU message, the device must send a confirmation message to the opposite end to tell the opposite end that I did receive the message.

The field format of the HELLO message:

Insert picture description here
Network MaskThe netmask of the interface that sends the Hello message.
Hello IntervalThe interval for sending Hello packets, in seconds. Default 10s
OptionsIdentifies the optional functions supported by the OSPF router that sends this message.
Router PriorityThe Router Priority of the interface that sends the Hello message is used to elect DR and BDR.
Router Dead IntervalExpiration time. If the Hello message from the neighbor is not received within this time, the neighbor is considered invalid; the unit is seconds, usually four times the Hello Interval, which is 40s
Designated RouterThe IP address of the DR elected by the router that sends the Hello message. If it is set to, it means that the DR router is not elected.
Backup Designated RouterThe IP address of the BDR elected by the router that sends the Hello message. If it is set to, it means that no BDR is elected.
NeighborIndicates the router ID of the known neighbor

Router ID is used to identify the identity of the device in the network. It can be configured manually. If it is not configured, the IP address with the largest IP address from the interface will be selected as its Router ID.

Neighbor establishment process

Then look at the process of establishing the neighbor relationship with the adjacency.

Insert picture description here

This is the state of the device after running OSPF.

DOWNIndicates that the device has just run OSPF in its initial state and has not received any HELLO packets. But I will start to send HELLO messages according to the Hello Interval 10s interval
ATTEMPTThis message is only used in the broadcast and NBMA network environment, indicating that the device has sent HELLO but has not received a response.
InitIndicates that the device has received the HELLO packet, but it does not have itself in the neighbor field. At this time, it will enter the init state and send
2-WayAfter receiving the HELLO message, the device finds its own Route ID in the neighbor field and enters the 2-Way state. This state indicates that the neighbor relationship is successfully established.
Insert picture description here

The neighbor relationship establishment process can refer to the figure above:
RTA enters the Down state after configuring OSPF and sends HELLO messages at the Hello Interval interval, and the neighbor field in the HELLO message is empty. After RTB receives it, it enters the Init state, and RTB also A HELLO message will be sent, and RTA will also enter the Init state after receiving it. When the device receives a HELLO message with an empty neighbor, it will fill in the router ID of the peer into its neighbor field in the next HELLO message and send it After going out, the opposite end will confirm the neighbor field after receiving it, and it will enter the 2-Way state when it finds that it is its own Route ID. After both parties enter the 2-Way state, the neighbor establishment is completed.

LSDB synchronization process

ExStartAfter the neighbor relationship is established, the synchronization of the database will start. The ExStart phase will send DD messages to each other to confirm the master/slave relationship of the device. In this state, the device does not send DD description information.
ExchangeDevices will send DD packets to each other to describe their LSDB database information
LoadingIn this state, the devices will request each other for LSA entries and send LSR, LSU, and LSACK packets
FullThe LSDB synchronization is completed, and an adjacency relationship is formed between the devices
Insert picture description here

The database synchronization process is shown in the figure above: After
entering the ExStart state, RTA and RTB will send DD messages to each other to confirm the master-slave relationship between the devices. At the beginning, everyone thinks they are the master device, and then they will compare the Router ID with each other. The larger one is the master device, and the smaller one is the slave. At this time, RTB's RouterID is larger, so RTB is called the master device, and then RTA sends DD description information packets to describe its own LSDB database information, and enters the Exchange state, RTB It will also send DD packets to describe its own LSDB. Later, since RTB is the master and RTA is the slave, subsequent RTA will no longer send description DD packets, but will confirm the DD packets sent by RTB.

After the LSDB is synchronized, it will initiate a request for its missing LSA, and the opposite end will send an update message LSU. After receiving it, the local end will respond with an LSACK message. At this point, the adjacency relationship is also established.

Network types supported by OSPF:

OSPF supports the following network types: P2P, P2MP, NBMA and broadcast. By default, OSPF considers the network type of Ethernet to be broadcast, and the network type of WAN is P2P.

P2P networkIt is mostly used for the interconnection of equipment between WANs, and the network that uses PPP or HDLC data link layer protocol for interconnection
Broadcast networkMostly used for the interconnection of local area network equipment, the network interconnected through the Ethernet protocol
NBMA networkNon-broadcast multiple access network, router network connected by fully interconnected frame relay links, rarely seen in existing networks
P2MPCollection of multiple P2P networks

DR/BDR election

Designated Router (DR) designates a router to elect a DR in an OSPF area, which is used to establish adjacency with other non-DR devices to establish synchronization with the database.
BDR (Backup Designated Router) The backup DR is used to become a new DR when the DR fails. , Other devices have to establish adjacency relationship with DR and BDR respectively.
After the neighbor discovery is complete, the router will conduct DR elections according to the network segment type. On broadcast and NBMA networks, routers will perform DR elections based on the priority of each interface participating in the election. The priority value range is 0-255, the higher the value, the more priority. By default, the interface priority is 1. If the priority of an interface is 0, the interface will not participate in the election of DR or BDR. If the priorities are the same, compare the Router IDs. The larger the value, the more preferred it is to be elected as the DR.