The routing process can be outlined to find a path to each possible destination for a node. The route appears in each layer from the first to the seventh layer. The routes that people are familiar with appear in the third layer (network layer), so we only discuss the IP routes of the third layer.
Protocols that exchange routing information connect many routers in the world. Although these routers are of different classes, they can provide their common network view through routing tables. The routing table stores all necessary information for the router to reach any destination on the network.
Routing protocol
Various routing protocols are used to fill in routing tables in the network. Protocols such as BGP, OSPF, RIP and ISIS can be transmitted to all routers with a correct and consistent network view.
The routing protocol wants to achieve the goal
You can imagine that if each router stores the information needed from each target point that its node can reach, it is likely that the router will accumulate a huge routing table. Due to physical limitations (cpu, memory) limitations, it is difficult for routers to sometimes simply impossible to handle a huge routing table. Therefore, without affecting the ability to reach each destination, we want to minimize the routing table. For example, if a router connects to the Internet by connecting to another router a DS1 link, the router can store information for all nodes on the Internet, or it can store non-local information outside the DS1 serial link. That is to say, the router does not store any information about the non-local network destination that the data "packet" is looking for in its routing table, but instead sends these "packets" to the router on the other end of the serial link, which provides the necessary information. We often call the router on the other end of the serial DS1 link like we mentioned in this example "Gateway of Last Resort". This simple trick can save 30 orders of magnitude entries on the routing table. There is no need for routing information to be exchanged between routers too often. Usually the agitators in the routing table put a lot of unnecessary pressure on the poor memory and CPU that any router can provide. The replication of information should not affect the forwarding operation of the router. Although there is no need to refresh the routing table every millisecond, of course, it cannot be refreshed every other week. An important goal of routing is to provide the host with a routing table that can accurately reflect the current network status.
The most important operation of a router is to send the received packet to the correct path. Unrouted packets may result in data loss. Inconsistency in the routing table will cause the routing loop and cause a packet to be sent looped between two adjacent interfaces.
People really hope that all routers can converge quickly. Convergence can be informally defined as a unit of measurement of the speed at which all routers obtain a consistent network view. One would like to have a very small convergence time, because in this way every router on the network can accurately reflect the current network topology even if the network topology (i.e., network view) is severely changed. When the network topology is changed, each router must transmit data to help other routers converge out the correct network view. However, there is also a problem with rapid convergence when refreshing the routing table. If a link is vibrating rapidly (once breaking, on a while), it will generate a large number of installation and revocation requests. This link will eventually exhaust the resources of every router on the network, as other routers are forced to quickly install or undo the route. Therefore, even if fast convergence is the goal of routing protocols, it is not a panacea for all network puzzles.
Distance vector routing
The distance vector routing protocol distributes a list of records in the form of <Target, Overhead> to all neighbors of the router. These records assign overhead value to each other node in the network that is not the present node. It is worth noting that this information is only distributed to the neighboring routers of the source router. The neighbor routers here are often physical, but they also apply logically in eBGP. Overhead means the sum of link overhead from the source router to the target node. The source router periodically refreshes its distance vector record and distributes the record to its neighbor router. The neighbor router compares the records received in the past with the present, and if the past is less overhead, the router will send the output along the path indicated by the distance vector record of the past received.
Many distance vectors will encounter infinity problems when actually used. For example, we assume that all links have an overhead unit and that each link between adjacent nodes corresponds to one unit. If router X is connected to router Y and router Y is connected to router Z as shown in Figure 1, we will find infinity problems. Y knows that there is an overhead of 1 unit to Z and X knows that there is an overhead of 2 units to Z. Assuming that link YZ is closed, the overhead of this link becomes infinite (as shown in Figure 2). Now Y knows that the overhead of reaching Z is infinite, it routes this distance vector to X. Suppose X is sent to Y at this time a distance vector route claims that it needs to reach Z for 2 units overhead. Now Y will think that it can reach Z through X, and it will send X a refreshed distance vector route. It claims that the overhead of reaching Z is 3 units (as shown in Figure 3). Please note that X did not expect that the distance vector route sent to it by Y was calculated by the distance vector route sent to Y. This is a serious flaw in distance vector routing, which does not contain information about routing barriers in their unimproved structures. As shown in the legend, the router will constantly change the path information to Z. The two routers X and Y will always exchange this path information about the Z router or until the value of the overhead unit reaches a certain previously agreed infinite value (for example, 15 in RIP).
X--------------------Y--------------------Z
Y:1 X:1 X:2
Z:2 Z:1 Y:1
[Picture 1]
X--------------------Y--------* *---------Z
Y:1 <------------- Z:Infinity
Z:2 -------------> X:1
[Figure 2]
X--------------------Y--------* *---------Z
Z: Infinity (from Y) -> X:1
Y:1 <------------- Z:3
[Figure 3]
Using path vector routing can solve the problem of infinity. Each distance vector also includes the path through which it passes (as shown in Figure 4). If the router receives a path vector containing its own refresh record, the router will not refresh the record (as shown in Figure 5). The Border Gateway Protocol uses the above method to solve the infinity problem. Obviously if you want the routing table to contain the AS (Autonomous Systems on the internet) path information transmitted by the router, you will have to add more information to the routing table. Therefore, the designers of BGP decided to sacrifice a little storage space and processing power that the router can afford.
X--------------------Y--------------------Z
Y:1 (Y) X:1 (X) X:2 (YX)
Z:2 (YZ) Z:1 (Z) Y:1 (Y)
[Figure 4]
X--------------------Y--------* *---------Z
Y:1 (Y) X:1 (X)
Z:2 (Y Z) Z:infinity
[Figure 5]
Another solution to the infinity problem is to separate the scope. The main idea is that if the neighbor router is at the second node on the path to the destination, the router does not broadcast the path to the neighbor router. This solution can be explained by the example just now. Because the path to Z passes from X to Z, and because Y is the neighbor router of X, Y is not broadcast when the path is broadcast from X.
Link status routing
When a router uses link state routing, it will distribute its distance to its neighbor router to all other routers on the network. This allows each router to generate a routing table without knowing the overhead from a certain source node to the destination node. The loop problem does not occur because each router has the topology of the entire network. The main idea is that a router generates overheads that contain the source router (its own), the neighbor router and to the neighbor router. Therefore, if router A connects to router B through a link with overhead of 3 and router A connects to router C through a link with overhead of 5, the router will broadcast link status packets (LSPs) and to all routers on the network. Each router will be able to calculate a shortest path to the destination node from the received LSPs.
Obviously, LSP is an integral part of the convergence process. If the wrong LSP is added to the network. This will lead to incorrect routing information (which will cause packets to be transmitted along longer paths than the original one) and even generate routing black holes. If router C broadcasts a path information to his neighbor router to other routers, but when the link is disconnected, router C withdraws the previous broadcast. Unfortunately, the second LSP arrives first and the first LSP arrives first. At this time, the routing tables of other routers cannot correctly reflect the network topology, but can only wait until another correct LSP arrives.
To solve this problem, LSP introduced sequence codes. Therefore, all routers on the network will initialize their sequence code with some values as the starting value, and then broadcast their LSP. This solved the problem just now.
When using sequence code, you will encounter the problem that the sequence code space is limited. All sequence codes that can be used in LSPs are set to finite values. Therefore, when the sequence code reaches the maximum value, it is necessary to start over from the minimum value. This brings difficulties to the router when comparing the current record of the link state and refreshing the record, because the sequence code has priority. To solve this problem, a maximum aging time can be defined for the LSP. That is, if the router does not receive a refresh record within X period of time, it will discard the existing record and wait for the updated record. Be careful that the path information to the destination must be invalid. For example, when router Y disconnects the link to a certain local network, router Y broadcasts the information of this link to router Z. At this time, routers in the local network still think that they can still reach Z. If they do not receive refresh records within the maximum aging time, they assume that the link to Y is already unreachable. In this way, the routing tables of all routers will be consistent, and routers Y and Z can also use limited sequence codes.
Initialization of sequence code is also another important aspect of this problem. Suppose router Y restarts, and the network starts to recalculate the path. When the router's link state protocol starts working, it must know why the value of the reinitialization of its sequence code to keep it consistent with other routers. Therefore, it broadcasts a path information with a special initialization set. This record will tell other routers that sequence code it needs, and other routers will tell it.
[1]
Article entry: csh Editor in charge: csh