The distance vector algorithm (also known as distance vector routing or Distance Vector Routing) is a dynamic routing protocol that works on the principle of “ tell your neighbors how you see the world” and works internally on the Bellman-Ford algorithm based. It is used by routers in packet-switched networks and is used in IP networks e.g. B. implemented as RIP and IGRP . Distance vector protocols are self-organizing, relatively easy to implement, and function with almost no maintenance. Link-state protocols are another type of routing protocol.
The basic procedure of a distance vector protocol:
Generate a cost matrix showing which routers can be reached via which neighbors and at what cost and initially only contains the (known) costs to direct neighbors.
Create a list with information about which routers we can best reach at what cost and send it to all neighbors.
Wait for statements of this type from other routers, then include them in your own cost matrix.
If this changes the minimum costs at which we can reach a router: continue with step 2, otherwise with step 3.
Costs can be equated with metrics . Each routing protocol uses a different consideration for the cost of a route. With RIP, for example, the number of routers to the destination ("hop count") is used as the only cost value, ie the bandwidth is not taken into account here.
example
There are four routers AD and the following point-to-point connections (links) between them:
The following shows the router cost matrices at the beginning and after each complete exchange of data packets. The best path to another router is always green, a new best path - which is sent to the neighbors in the next step - has a yellow background. Gray fields mark values that are not considered and therefore not maintained. These values would either represent the distance between a router and itself (concerns rows and columns) or the router x under consideration is not a direct neighbor to another listed router e.g. The distance from router x to router y via ("via") router z is not considered (concerns columns).
T = 0
by A
via A
via B
via C
via D
to A
to B
3
to C
23
to D
by B
via A
via B
via C
via D
to A
3
to B
to C
2
to D
by C
via A
via B
via C
via D
to A
23
to B
2
to C
to D
5
from D
via A
via B
via C
via D
to A
to B
to C
5
to D
T = 1
by A
via A
via B
via C
via D
to A
to B
3
25th
to C
5
23
to D
28
by B
via A
via B
via C
via D
to A
3
25th
to B
to C
26th
2
to D
7th
by C
via A
via B
via C
via D
to A
23
5
to B
26th
2
to C
to D
5
from D
via A
via B
via C
via D
to A
28
to B
7th
to C
5
to D
T = 2
by A
via A
via B
via C
via D
to A
to B
3
25th
to C
5
23
to D
10
28
by B
via A
via B
via C
via D
to A
3
25th
to B
to C
8th
2
to D
31
7th
by C
via A
via B
via C
via D
to A
23
5
33
to B
26th
2
12
to C
to D
51
9
5
from D
via A
via B
via C
via D
to A
10
to B
7th
to C
5
to D
T = 3
by A
via A
via B
via C
via D
to A
to B
3
25th
to C
5
23
to D
10
28
by B
via A
via B
via C
via D
to A
3
25th
to B
to C
8th
2
to D
13
7th
by C
via A
via B
via C
via D
to A
23
5
15th
to B
26th
2
12
to C
to D
33
9
5
from D
via A
via B
via C
via D
to A
10
to B
7th
to C
5
to D
Explanation of the processes in router A:
T = 0 : We generate the initial cost matrix. It only contains our direct neighbors B and C with the costs known to us. We then send our new best paths (B with cost 3, C with cost 23) to our direct neighbors
T = 1 : We have received data packets from routers B and C and now we know at what cost we can reach D and how we can reach C and B. In the case of destination routers C and D, this is even a new best path that we will transmit to our neighbors in the next step
T = 2 : We have received a data packet from router B and now we know that B can reach router D more cheaply. We'll put the cost in our matrix and we'll redistribute this new best path to our neighbors.
T = 3 : We have not received any more new information; our best paths haven't changed and we don't send new information to our neighbors. They feel the same way, the algorithm terminates.
Problems
Network ABCD
One problem with the distance vector algorithm is counting to infinity, the so-called count-to-infinity effect. This can be shown in the following example.
Let's assume that the link from C to D deteriorates drastically and consider the situation from the perspective of router A:
We receive the message from C that it is very difficult to reach D via him. However, that does not change our best path, which leads via B.
But soon we also get the message from B that D can only be reached very poorly via him - the path costs have risen to 13 = 3 + 10 = 3 + 3 + 2 + 5. The reason that the costs were not set significantly higher is that B knew an indirect route that leads to D: the route B – A – B – C – D. And A stated to the best of his knowledge that he could reach D at cost 10.
But now our path costs to D have changed. Because B can only reach router D at a cost of 13, we can only reach D at a cost of 16.
However, this changes our best path again, which we immediately tell B again - the path costs are slowly counted up instead of rising abruptly.
Counting to infinity is relatively easy to avoid with direct loops between two routers. Path information may not be published via the same interface over which it was received. This process is called split horizon .
In the case of longer loops, a solution to the problem is no longer trivial. As a general rule, in distance vector protocols, messages of increases in costs are slow to spread. The poisoned reverse method and so-called triggered updates are used to deal with this problem as well: If a router finds out that a neighbor is difficult or impossible to reach, it immediately publishes this fact actively on the network.
In a modification of the distance vector algorithm, the so-called distance-path algorithm, the z. For example, if BGP was implemented, the problem of loops would be easier to solve. In addition to the next hop, this algorithm also saves the entire remaining path to the destination router. In addition to the “cheapest route” criterion, other criteria, e.g. B. implement corporate policy requirements.
RIP versions
There are two versions of RIP for IPv4 : RIPv1 and RIPv2. No subnet masks are implemented in RIPv1 .
RIP was adapted for IPv6 and published under the name RIPng .
James F. Kurose , Keith W. Ross: Computer Networks: The Top-Down Approach , Pearson Studium, 4th updated edition (September 1, 2008), ISBN 978-3827373304 , p. 425.
Individual evidence
^ Andrew S. Tanenbaum: Computer Networks , Pearson Studies, 4th revised edition (July 15, 2003), ISBN 978-3827370464 , p. 397.
