An overview of the content of the article

RIP of the internal gateway routing protocol

Distance vector (DV) algorithm

Before introducing RIP, learn about the DV algorithm, because the PROTOCOL is implemented using the DV algorithm

The algorithm is running on a graph

  • Each node uses two vectors Di and Si
  • Di describes the distance between the current node and other nodes.
  • Si describes the “next node” from the current node to another node.

“How does this algorithm work?“

  1. Each node exchanges information about the vectors Di and Si with its neighbors
  2. Each node updates its own node information according to the exchanged information
  • Di1 represents the distance from node “I” to node “1”
  • Si1 represents the “next node” from node “I” to node “1”
  • N indicates the number of nodes

“For DV, he’s essentially minimizing the distance to D“. For example, the minimum value of Dij is min (Dix+Dxj). Let’s take an example to understand the DV algorithm

There are six vertices A, B, C, D, E, F and several edges in the graph. For these six nodes, there is distance vector information of Di and Si on the right. For Di, it has six elements, Dia, Dib… By Dif, he means the distance between the node I and the six nodes A, B, C, D, E, and F. For Si, it also has six elements, Sia, Sib… To Sif, he’s saying, what’s the next node from I to A, B, C, D, E, and F

Now, I’m going to use this node A as an example to show how the DV algorithm works, which is to find Da and Sa. Suppose the distance vector information (Da) of A is as follows

It represents the distance between A and each of the other nodes as the value of the column on the right. When I introduced the DV algorithm, it’s going to be the same“adjacent“To exchange Da and Sa information. Suppose A receives the information from B, C, D and F, and knows the straight-line distance between A and each neighboring node when receiving the distance vector information

In order to understand the process of DV more conveniently, the distance vector information of A is combined with the vector information of A to the other four adjacent nodes

What is the distance between A node and nodes A, B, C, D, E, and F

You might wonder why the distance from A to B is 11, but the distance from B to A is 9. This is because the distance vector information inside is not up to date. For example, the distance from A to B could be obtained by A->C->B, so here the distance from A to B could be 11. The distance from B to A may be obtained by B->C->D->A, so the distance vector information from A to B can be different from the distance vector information from B to A

List the S vector of A, initialized by default to“empty“The S vector represents A to several other nodes and what’s the next node

“So let’s say that A is exchanging information with this node B, and A is getting information about this node B, which is the distance from B to each of these nodes“

So when A gets that information, he’s going to perform the first operation. Since A and B communicate directly, A knows what the distance from A to B is. And then it calculates the distance from A to the other nodes by taking the distance from B to the other nodes

A->B = 6
A->B->C = 6+11 = 17
A->B->D = 6+7 = 13
A->B->E = 6+17 = 23
A->B->F = 6+11 = 17
Copy the code

The above is“The operation that A performs after obtaining B’s data“And then he would compare that data to his own distance vector,“If the distance is smaller than itself to some other node, then it will fill it into its distance vector“. So I got the data of B, and after calculation, I found that the distance from A to B was 6, which was smaller than my original 11, so I replaced my original 11 with 6. And then you realize that the distance from A to F is 17, which is the same as the distance from A to F, so A will also make the substitution. I’m going to replace that with,“A will set the corresponding next node to B“. The above is the whole process after A obtains B’s information, as shown in the figure below

Then A receives the information of node C, including the distance from C to A, B, C, D, E and F. When A receives the message from C, it will perform the same operation as before

A->B->C = 9+9 = 18
A->C = 9
A->C->D = 9+8 =17
A->C->E = 9+11 = 20
A->C->F = 9+10 = 19
Copy the code

After calculation, it will also be compared with its existing distance vector. For example, the distance between A->C is 9, which is smaller than the distance between A and C before 12, so the original 12 will be replaced by 9, and the corresponding S will be filled with C, and the following is the same, as shown in the figure:

The process of exchanging information between A, D and F is exactly the same as above. When A exchanges information with each adjacent node, the following results are obtained

So that’s the whole process of the DV algorithm, going back to the DV algorithm introduced earlier, and then understanding its definition will be a lot easier to understand

  • Each node uses two vectors Di and Si
  • Di describes the distance between the current node and other nodes.
  • Si describes the “next node” from the current node to another node.
  • Each node exchanges information about the vectors Di and Si with its neighbors
  • “Each node updates its own node information according to the exchanged information“

RIP process

  • Routing Information ProtoCol (RIP)
  • RIP is a routing protocol that uses the DV algorithm
  • RIP takes the hop count of the network as the distance of the DV algorithm.
  • RIP exchanges routing information (including Di and Si) every 30 seconds.
  • RIP considers the route whose hop count is greater than 15 as unreachable

“Router that uses RIP“

  • The router initializes the routing information (two vectors Di and Si)
  • Modify the information based on the information sent by neighboring router X (Set the next-hop address to X, and increase all distances by 1). That is, through X, it can reach each node of the message sent by X, just by increasing the distance by one.
  • After the modification, first retrieve the local route and insert the new route in the information into the routing table (because some destinations may not be in the local routing table).
  • Retrieves the local route with the modified information for the next hop of X
  • Retrieves local routes, compares distances to the same destination, and updates the local routing table if the new information is smaller
  • If no adjacent routes are received within 3 minutes, the adjacent routes are set to unreachable (16 hops).

Use examples to understand the above description. Suppose the route initializes the leftmost part of the information as follows:

“Step 1: Retrieve the local route and insert the new route from the information into the routing table“

Initialize the information in the routing table, indicating that the distance from the route to D is 2 and its next hop address is A. Suppose you receive a message from Router X. The message has A distance of 4 to A and the next hop address is C. The distance to B is 2, and the next-hop address is C. After receiving the information, the router modifies its own information by increasing all distances by one and setting the next hop address to X. The local route is searched and information about A and B is inserted into the routing table because A and B do not exist in the original route. You get the updated routing table

“Step 2: Retrieve the local route and update the updated information for the route whose next hop is X“

Assume the leftmost part of the initialized routing information is as follows:

When the initial router receives the intermediate route information, it first modifies the route information. After the modification, it modifies itself based on the received route information, overwriting the original route information because it is the latest one

“Step 3: Retrieve the local route, compare the distance of the same destination, and update the local routing table if the distance of the new information is smaller“

This step is actually the DV algorithm described earlier. When the initial route receives the information of another route, the information of the other route is updated and compared with that of the initial route. If the distance of the new information is smaller, the local routing table is updated

The above is the complete RIP process

Disadvantages of RIP

This section describes the disadvantages of RIP as an example. Suppose there are nodes A, B, and C, and they are linearly connected. The distance between B and C to A is 1 and 2, respectively. B reaches A directly, and C reaches A through B

Suppose at some point router A goes down, that is, router A is unreachable. At this point, after B finds that A is unreachable, it will ask C. After asking C, it finds that A can be reached through C. Therefore, B sets the next hop to C and increases the distance by one (i.e., 3). C at A certain moment also found A inaccessible, C will ask B, found by 3 after the jump to A, B so it will update its routing information, will reach A distance is set to 4, and set up for the next dance, B will die cycle at this time, all the way to the distance of 16 (has introduced above to jump up to 16, will think target inaccessible), Only to discover that it is unreachable

Therefore, the most fatal disadvantage of RIP is that fault information is transmitted slowly.

“Why does RIP have this feature?“

  • Trust the neighbor (no matter B or C. If B gets C’s routing information, it will trust C unconditionally. Similarly, if it is C, he will also unconditionally trust B, thus causing a loop until the hop count is 16 and it is not reachable.)
  • (For RIP, each router only sees information about adjacent routes, not information about farther routes.)

Network faults occur frequently. If a fault is detected by multiple hops, the entire network cannot be controlled. This is the fatal shortcoming of RIP

It is the core competitiveness of a technician to seek invariance in the rapidly changing technology. Unity of knowledge and practice, theory and practice