Shulou(Shulou.com)06/02 Report--

The following content is extracted from the newly listed, has been incorporated into the national university teaching material system, and in the national best-selling, well-received new book "in-depth understanding of computer Network".

7.5.3 distance vector routing algorithm

Modern computer networks usually use dynamic routing algorithms, because these algorithms can adapt to the changes of network topology and traffic. The two most popular dynamic routing algorithms are distance vector routing algorithm and link-state routing algorithm.

Distance vector routing algorithm (Distance Vector Routing,DV) is the earliest routing algorithm used in ARPANET networks, also known as Bellman-Ford routing algorithm and Ford-Fulkerson algorithm, which is mainly used in RIP (Route Information Protocol) protocol. Cisco's IGRP and EIGRP routing protocols also use the DV routing algorithm.

The basic idea of "distance vector routing algorithm" is as follows: each router maintains a table of distance vectors (usually with delay as a variable), and then updates the distance vector table through distance vector advertisements between neighboring routers. Each distance vector table item consists of two parts: the best output line to reach the destination node and the time or distance required to reach the destination node. Each other router in the communication subnet occupies a table item in the table and serves as the index of the table item. Every once in a while, the router sends its distance table to each destination node to all neighbor nodes, and it also receives the distance table from each neighbor node. In this way, after a period of time, the distance vector information obtained by each router in the network can be unified on each router, so that each router only needs to look at the distance vector table to find the best route for packets from different sources.

Now assume that delay is used as a measure of distance, and give a simple example, as shown in figure 7-37. Suppose that at some point router Y receives the distance vector of its neighbor router X, where m is the estimated delay for Y to reach router X. If the Y router knows that its delay to neighbor Z is n, then it can know that it takes time for Z to reach X through Y. If the Z router has other neighboring routers, the router performs the same calculation for the distance vector received from each other neighbor, and finally selects the least time-consuming route as the best route from Z to X. then update its routing table and advertise it to its neighbor router.

Figure 7-37 simple example of distance vector routing algorithm

The determination process of the route in the distance vector algorithm is introduced with an example shown in figure 7-38, and the delay of each link has been marked in the figure. A, B, C, D, and E represent five routers, assuming that the routing table is passed in the direction of A → B → C → D → E (this is related to the order in which the router starts). The following is the specific process.

The main results are as follows: (1) in the initial state, each router only collects the delay information of directly connected links, and each router node obtains its own initial vector table as shown in figure 7-39. Because routing information has not been exchanged between nodes, the routing tables of their initial states are also like their vector tables.

Figure 7-38 example of route determination by distance vector algorithm

Fig. 7-39 Vector table of each node in the initial state

(2) now router A sends its routing table to router B. At this point, it combines the routing table sent from router A with its own initial routing table and updates it to a new vector table, as shown in the left side of figure 7-40 (the final vector table is shown in the dark part of the figure). It can be seen from the figure that there are two paths from node B to node E, one is direct, the other is through node A. Moreover, the overhead of the two lines is different, and the cost of reaching the E node through the A node (7) is lower than that of the direct line (8), so finally, in the formed routing table, the route to the E node is changed to the line via the A node, as shown in figure 7-40 on the right.

Figure 7-40 new vector table and routing table of node B

(3) B then sends the routing table to router C. Similarly, router C combines its original initial routing table with the routing table sent from router B to form a new vector table, as shown on the left side of figure 7-41 (the final vector table is shown in the dark part of the figure). In the new vector scale, in addition to the vectors between the original directly connected B and D nodes, the new vector information reaching An and E nodes is also collected. Because there is no direct connection between C node and An and E nodes, and there is no routing information to reach these two nodes in the initial routing table, we can only use the routing table sent from B router to get to An and E nodes through B node.

It should be noted here, because it has been identified in the B node routing table that the cost of directly reaching the E node through the B node (8) is also higher than that of reaching the E node through the B node and A node (7). Therefore, the path of reaching E node through B node and A node in turn is adopted in the routing table of C node. The resulting routing table is shown on the right of figure 7-41.

Figure 7-41C node new vector table and routing table

(4) Router C then sends its final routing table to router D. Similarly, router D combines its original initial routing table with the routing table sent from router C to form a new vector table, as shown on the left side of figure 7-42 (the final vector table is shown in the dark part of the figure). In the new vector scale, in addition to the vector information between the original directly connected C and E nodes, the vector information reaching An and B nodes is also collected. Because D node is not directly connected to An and B nodes, there is no vector information to reach these two nodes in its initial routing table, and the path to An and B nodes through C node is still adopted.

It should also be noted here that there are two paths from D node to E node: one is to arrive directly, and the other is to arrive through C, B and A nodes in turn. After comparison, it is found that the cost of direct connection (2) is less than that of the E node through C, B and A nodes (10), so in the D node, the E node is directly connected to this line. The resulting routing table is shown on the right of figure 7-42.

(5) Router D then sends its final routing table to router E. Similarly, router E combines its original initial routing table with the routing table sent from router D to form a new vector table, as shown on the left side of figure 7-43 (the final vector table is shown in the dark part of the figure). In the new vector scale, in addition to the vectors between the original directly connected A, B and D nodes, the vector information reaching the C node is also collected, because the E node is not directly connected to the C node. At this time, the path to the C node through the D node is still adopted.

Figure 7-42 D node new vector table and routing table

There are two points to pay attention to here: one is the problem of the path from the E node to the A node, because the E node is directly connected to the A node, and its cost (1) is smaller than the path cost (11) provided in the routing table sent from the D routing port to the A node, so in the final E node routing table, the A node is directly connected to this line. Second, although the E node is also directly connected with the B node, its cost (8) is larger than that provided in the routing table sent from the D router to the B node (5). Therefore, in the final E node routing table, the path to the B node is through the D and C nodes in turn. The resulting routing table is shown on the right of figure 7-43.

Figure 7-43 E node new vector table and routing table

Through the above steps, each router in the network completes the determination of the entire routing table. of course, when the topology changes, the routing table of each router will be changed and updated again.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.