How does a router choose a more appropriate path among many routing protocols, manual configurations, and routing policies?

Routers are important network devices that realize network interconnection and forward data units between different networks. Routers mainly work at the third layer (network layer) of the OSI reference model. The main task of a router is to find an optimal transmission path for each data frame passing through the router and effectively transmit the data to the destination site. In order to complete this task, the router stores the relevant data of various transmission paths - the routing table, which is used for route selection.

It can be seen that the strategy of selecting the best path, that is, the routing algorithm, is the key to the router. Therefore, when the router receives a data packet from a network interface, it first queries the routing table according to the destination address contained therein, determines the forwarding path (forwarding interface and next hop address), and then calls out the MAC address of the next hop address from the ARP cache, encapsulates the router's own MAC address as the source MAC, and the MAC of the next hop address as the destination MAC into the frame header, and at the same time, the TTL (Time To Live) of the IP data packet header also starts to decrease, and the data is sent to the forwarding port in sequence, waiting in order, and transmitted to the output link. In this process, the router is considered to perform two most important basic functions: routing function and switching function.

[[237986]]

• Routing function

Routing function refers to the router learning and maintaining the network topology by running dynamic routing protocols or other methods, and establishing, querying and maintaining routing tables.

The routing table stores the key information required by the router for routing selection, including the destination address, destination address mask, next hop address, forwarding port, routing information source, routing priority, metric, etc.

Routing information can be learned through a variety of protocols, and its sources can be divided into direct routing, static routing, default routing, and dynamic routing. Multiple different routing protocols can run on a router at the same time. Each routing protocol will calculate the best path to the destination network based on its own routing algorithm. However, due to different routing algorithms, different routing protocols may choose different best paths for a specific destination network. At this time, the router chooses to place the best path calculated by the routing protocol with the highest routing priority (the smallest value) in the routing table based on the routing priority (which determines the priority of routing information from different routing sources) as the forwarding path to this destination network (priority order: direct routing > static routing > dynamic routing (OSPF > RIP))

For a specific routing protocol, all paths to the destination network can be discovered, and a metric value is assigned to each path according to the routing algorithm. The metric values ​​are compared and the path with the smallest metric value is selected as the best path.

When searching for routes during the exchange process of the router, it may also find that multiple routing entries can be matched. At this time, the router will forward the data according to the longest match principle (the longest match principle has the highest priority, which is greater than the priority and metric). The router will choose the route with the deepest match, that is, the route with the longest matching mask length, for forwarding.

• Forwarding function

Generally speaking, the main task of a router is to store and forward data packets. The specific process is as follows:

Step 1: When a data frame arrives at a port, the port performs a CRC check on the frame and checks whether its destination data link layer address matches that of this port.

Step 2: If the check passes, remove the frame encapsulation and read the destination address information in the IP data packet, query the routing table, and determine the forwarding interface and next hop address.

Step 3: According to the next hop IP address found in the routing table, the MAC address of the next hop is retrieved from the ARP cache, and the MAC address of the forwarding interface is used as the source MAC, and the MAC of the next hop address is used as the destination MAC, and encapsulated into a frame header. At the same time, the TTL of the IP data packet header is reduced by one, and the checksum is recalculated.

Step 4: ***Encapsulate into a frame and send it to the output link through the forwarding interface.

So the question is: How does a router choose the best route under many routing protocols, manual configurations, and routing policies? Understanding this problem is very helpful for understanding the working principle of routers.

Routing involves three aspects:

1. Processing of various routing protocols, including rip, igrp, eigrp, ospf, is-is, bgp, etc. Each protocol transmits network routing information between routers through IP data packets to provide information for the establishment of routing tables.

2. Routing table, which receives information from routing protocols and provides the necessary information for forwarding data packets.

3. Forwarding process, which requests the required information from the routing table and makes decisions for correctly forwarding data packets.

This is discussed below from several aspects.

Create a routing table

When each routing protocol processes a routing update, it selects the best route to the destination address and attempts to install it into the routing table. If only multiple dynamic routing protocols are running, there is a problem of competing to install routes first. There must be a mechanism to manage the installation of routes. This mechanism determines the installation process based on the priority of each routing protocol. Each routing protocol has a default administrative distance value, and the smaller the value, the higher its priority. The default administrative distance values ​​of each routing protocol are as follows:

Assume that the router runs four routing protocols: EIGRP, OSPF, RIP, and IGRP. They all obtain the route to network 192.168.24.0/24, but only EIGRP (internal) can install its route into the routing table because its administrative distance value is the smallest and its priority is the highest.

Backup Routes

How do other protocols handle protocols that are not installed? What if the route installed by EIGRP fails? There are two solutions to this problem. One is that each routing protocol periodically tries to install its routes into the routing table. If the route installed by EIGRP fails, IGRP will install its corresponding route into the routing table. Another solution is to attach the uninstalled route to the routing table. If the previously installed route fails, the attached route will be officially installed into the routing table.

For routing protocols that do not have their own routing information table, such as IGRP, the first method will be adopted, and each time a routing update is received, it will try to install it into the routing table.

For routing protocols such as EIGRP, IS-IS, OSPF, BGP, and RIP that have their own routing information tables, the second method will be adopted. The routes that failed to be installed will be registered in the routing table. When the original route entry becomes invalid, the processing process of the routing protocol that registered it will be notified to install their routes. If there are multiple processes to install, the protocol with a smaller management distance will be given priority.

Adjusting the Administrative Distance Value

Changing the default distance value of a routing protocol is a relatively cautious action. It may cause routing loops or other strange problems. You must be very careful! The command is distance followed by a specific value. You can also change only the administrative distance value of routes distributed from a certain protocol. You can also add a value to the first line of a static route to change the original default value of 1.

Prefix length

Routes with different prefix lengths will be considered as different routes and will be installed into the routing table at the same time. For example, the following routes are obtained by the three routing protocols:

• EIGRP (internal): 192.168.32.0/26
• RIP: 192.168.32.0/24
• OSPF: 192.168.32.0/19

The prefix lengths (subnet masks) of the three routes are different, so routes to different destination networks are obtained and installed into the routing table at the same time.

Forwarding Decision

First, let’s take a look at the three routing entries that the router has just installed:

 router#show ip route 
 
 .... 
 
 D 192.168.32.0/26 [90/25789217] via 10.1.1.1 
 
 R 192.168.32.0/24 [120/4] via 10.1.1.2 
 
 O 192.168.32.0/19 [110/229840] via 10.1.1.3

If the destination address is 192.168.32.1, which route will be selected? This depends on the length of the prefix being matched, with the longest prefix length being given priority. The match is made by ANDing the mask in the route entry with the destination address and then comparing it with the network address. If they are the same, it means a match. This address matches all three routes, but the first matching route has the longest prefix (26), so the packet will be forwarded to 10.1.1.1.

If the destination address is 192.168.32.100, it does not match the first route, but matches the second and third routes, so it will be forwarded to 10.1.1.2.

The specific route search speed depends on the structure of the routing table and the hardware speed. For example, if a binary tree structure is used in the routing table, a 32-bit IP address can be searched at most 32 times to determine whether an appropriate routing entry is found.

The impact of IP CLASSLESS

This command only affects the forwarding process, not the creation of the routing table. See the following example:

 router#show ip route 
 
 .... 
 
 172.30.0.0/16 is variablysubnetted, 2 subnets, 2 masks 
 
 D 172.30.32.0/20 [90/4879540] via10.1.1.2 
 
 D 172.30.32.0/24[90/25789217] via 10.1.1.1 
 
 S* 0.0.0.0/0 [1/0] via 10.1.1.3

Assuming the ip classless command is not configured, then:

• Packets to 172.30.32.1 are forwarded to 10.1.1.1 because that route is the longest match.
• Packets to 172.30.33.1 are forwarded to 10.1.1.2 because that route is the longest match.
• The packet to 192.30.32.1 is forwarded to 10.1.1.3. Since there is no corresponding network route, it is forwarded using the default route.
• The packet to 172.30.100.1 cannot be forwarded and is discarded. Why not use the default route? Because the main network part of the destination address is known in the routing table and has a subnet route, the router searches for the corresponding subnet route, but no matching route is found, and the packet is eventually discarded. If the IP classless command is used for configuration, the default route will eventually be applied to forward the data packet to 10.1.1.3.

Summarize

The forwarding decision of a data packet depends on three parts of the process: routing protocol, routing table, and actual forwarding exchange. The relationship between these three is shown below:

The longest match principle is adopted when selecting a route, and the priority of the route installed by the routing protocol depends on the administrative distance value.