After the release of the interesting routing series, Mr. Docs has received a lot of messages about OSPF.  In order to meet the requirements of all fans, no, Mr. Document has brought a lot of OSPF dry goods, here we come~

Why is PART.01 RIP "out of date"?

If you want to talk about OSPF, you have to start with one of the oldest routing protocols—RIP (Routing Information Protocol, Routing Information Protocol).

The most prominent feature of RIP is that it uses the hop count (the number of routers a packet passes through) as a measure of the quality of a route: the route with the smallest hop count is considered optimal.

With the development of the network, the types and characteristics of links (transmission channels between devices) are constantly upgrading and changing. Only considering the number of hops can no longer objectively reflect the pros and cons of routing.

For example, to reach the same destination, there are two paths: A→B, A→C→D→B.

Although the A→B path is the shortest, it is not suitable for practical applications. It is more reasonable to measure the network quality by network bandwidth and link status. For example, the A→C→D→B path with greater bandwidth is used in the above figure. better.

At the same time, RIP limits the maximum number of hops to 15, and the hop number of 16 becomes the "unreachable distance" of the RIP routing protocol~so RIP cannot be used to build large-scale networks.

RIP is "outdated" not only because of poor scalability, but also has the disadvantages of slow convergence and easy loops, but I won't introduce too much here~

How does PART.02OSPF calculate routes?

Next, we will introduce the popular fried chicken in the dynamic routing protocol—OSPF ​​(Open Shortest Path First, Open Shortest Path First)!

Different from RIP, OSPF is a link state routing protocol, which can collect topology changes around routers and form a reliable routing structure.

If RIP provides road signs, it only tells you how to go next, and it is easy to get lost when you go around (produce a loop). Then what OSPF provides is a map, and each router running the OSPF protocol has a complete network map. With the map in hand, you will never get lost again!

The cost of OSPF can be routing distance, link throughput, or link reliability. This routing metric is more flexible and accurate than the hop count of RIP, and is applicable to larger and more complex networks.

The network shown in the following figure is taken as an example to illustrate the process of calculating routes by OSPF.

The figure below is a network composed of four routers, and the cost (cost) required to go from one router to another router is marked next to the connection. To simplify the problem, we assume that the cost of sending packets to each other between two routers connected by the same link is the same.

First, each router generates an LSA (Link State Advertisement) according to its surrounding network topology, and sends this LSA to all other routers in the network by sending OSPF protocol packets to each other. In this way, each router has received the LSAs of other routers. Putting all LSAs together is called LSDB (Link State Database). Obviously, the LSDBs of these four routers are the same.

Secondly, since an LSA is a description of the network topology around a router, the LSDB is a description of the entire network topology. The router converts the LSDB into a vector weight map, which is a true reflection of the entire network topology. Then, what these four routers get is exactly the same picture.

The last and most important thing is that each router will take itself as the root node, use the shortest path first (SPF) algorithm to calculate a shortest path tree (select the path with the smallest cost value), and generate it to the network through the shortest path tree The shortest routes of other routers in the router form the routing table. The routing tables obtained by the four routers are different.

From the above analysis, it can be concluded that the OSPF protocol calculates the route mainly includes the following three main steps.

1. Describe the network topology around this router and generate LSA.
2. Spread the LSA generated by itself in the autonomous system, and collect the LSA generated by all other routers at the same time.
3. Routes are calculated based on all collected LSAs.

The method of OSPF calculation route is so simple~~

So why is OSPF more suitable for large networks?

PART.04 How does OSPF adapt to large-scale networks?

Let's take a look at how OSPF adapts to large-scale networks!

Think back to when we were in school, how did the teacher manage the students in a class?

Mr. Document will answer for you: Of course, it is divided into groups and the group leader is selected!

Subgroups: Divide network regions

When OSPF is applied to a large network, for example, there may be dozens or hundreds of routers in the network.

When these routers run the OSPF protocol and transmit and collect LSAs, the network will be flooded with these protocol packets. Such an LSDB will have a large capacity, and the running of the SPF algorithm will be very slow, which is not conducive to the normal calculation and forwarding of routes.

OSPF solves this problem by setting areas. As shown in the figure, a large network is divided into several small networks, and each small network is called an area (Area), and a number is used to number the area. Among them, area 0 is called the backbone area, and other areas with numbers other than 0 are called non-backbone areas, and it is stipulated that the non-backbone areas must be connected with the backbone area.

After such processing, OSPF has the following advantages.

• Only the LSDBs of routers in the same area will be kept synchronized, and routing changes will be updated in this area first.
• When routing update information is transmitted to other areas, route aggregation can be performed on the Area Border Router (ABR) to reduce the number of LSAs advertised to other areas and minimize the impact of network topology changes.

This can well solve the problem of slow routing calculation and forwarding speed. Of course, in actual networking applications, OSPF also defines many optimization methods for calculating routes according to different area characteristics, so we will not describe them one by one here.

We know that the OSPF protocol requires that each area must be directly connected to the backbone area (Area 0), but in actual networking, the network situation is very complicated, and sometimes it cannot be guaranteed that each area meets this requirement when dividing areas. At this time, virtual link technology is needed to solve this problem.

A virtual link refers to a logical connection channel established between two ABRs through a non-backbone area (also called a transition area, Transit Area) (configured on the ABRs at both ends).

As shown in the above figure, a virtual link is established between Router C and Router E, making a logical connection between Area3 and the backbone area Area0, and Area1 is the translation area.

"Logical channel" means that other routers running OSPF between two ABRs just forward packets, which is equivalent to forming a point-to-point connection between two ABRs. Therefore, on this connection, it can be used as a physical port Configure various parameters of the interface.

Election of group leader: OSPF election

On broadcast and NBMA (Non-Broadcast Multiple Access, Non-Broadcast Multiple Access) networks, any two routers need to transmit routing information. If there are N routers in the network, then "N×(N-1)/2" times of transmission should be established. This is unnecessary and a waste of valuable bandwidth resources.

To solve this problem, the OSPF protocol designates a router as the "group leader"——DR (Designated Router, Designated Router) to be responsible for transmitting information. All routers only send routing information to DR, and then DR sends routing information to other routers in the network segment.

The two routers that are not DRs (DR Other) no longer establish an adjacency relationship and do not exchange any routing information. In this way, only N-1 adjacencies need to be established between the same network segment, and only 2×(N-1) transfers are required for each route change.

Although the method of selecting a group leader is very effective, if the group leader is not around, who will be responsible for the management of the entire group?

Therefore, OSPF also defines a "deputy group leader" - BDR (Backup Designate Router, Backup Designated Router).

BDR is a backup of DR.  When the DR is elected, the BDR is also elected. The BDR also establishes adjacencies with all routers in the network segment and exchanges routing information.

Once the DR fails, the BDR will immediately become the DR.  Since re-election is not required and the adjacency relationship has been established in advance, the process of BDR replacing DR is very short.  After the BDR is successfully "assigned" as the DR, a new BDR needs to be re-elected, but this election process will not affect the routing calculation.

Through the previous introduction to OSPF, I wonder if fans have gained anything?