Distance-vector routing protocol

In the distance-vector algorithm is " with parts of your neighbors, as you see the world " to a dynamic routing protocol that is based on the principle works and internally based on the Bellman - Ford algorithm. It is used by routers in packet-switched networks and the Internet is implemented eg as RIP and IGRP. Distance vector protocols are self-organizing, relatively easy to implement and operate virtually without any maintenance.

Principle

The basic procedure of a distance-vector protocol:

Example

There are four routers AD and between them the following links:

In the following the Kostenmatrizen the router are shown at the beginning and after each complete exchange of data packets. Here, the best path to another router is each green, a new best path - which is sent to the neighbor in the next step - yellow.

Explanation of the processes in the router A:

• T = 0: We generate the initial cost matrix. It contains only our immediate neighbors B and C with the costs known to us. We then send our new best paths ( B costs 3, C with cost 23) to our direct neighbors
• T = 1: We have received from routers B and C data packets and now know at what cost we D, and how we each can achieve C and B. In case the destination router C and D is even a new best path we are transferred to our neighbors in the next step
• T = 2: We have received from Router B a data packet and now know that B can reach the router D -effective. We will bear the cost to our Matrix and disseminate these new best path back to our neighbors.
• T = 3: We have received no new information more; our best paths have not changed and we do not send new information to our neighbors. Which are doing the same - the algorithm terminates.

Problems

A problem of the distance-vector algorithm is the counting to infinity, the so-called count- to- infinity effect. This can be illustrated by the following example.

If we assume that the link from C to D deteriorated drastically and look at the situation from the perspective of Router A:

• We received from C, the message that D is still very difficult to reach him. However, this does not alter our best path leading yes on B.
• Soon we will but also by B the message that D could be reached only very bad about him - the path costs are on 3 10 = 13 = 3 3 2 5 risen. The fact that the costs were determined not significantly higher is because B still knew an indirect route, which leads to D: the route BABCD. And A was yes, to the best knowledge that he could reach D to the cost of 10.
• Now, however, our path costs have changed to D. Because the B router D can still reach only at a cost of 13, we too can reach D only at a cost of 16.
• This changes but again our best path, we again tell B - The path cost is incremented slowly instead of suddenly to rise.

Counting to infinity is relatively easy to avoid with direct grinding between two routers. A path information may not be published on the same interface over which it was received. This procedure is called split horizon.

In the case of longer loops, a solution of the problem is no longer trivial. In distance vector protocols is generally that spread news about the increase in the cost slowly. In order to master this problem, the Poisoned reverse method and so-called Triggered Updates are used: Finds a router out that a neighbor today is difficult or impossible to reach, he shall publish this fact immediately active in the network.

In a variation of the distance-vector algorithm, called Distance- path algorithm to be implemented, for example BGP, could be the problem of loops easier to solve. This algorithm stores next to the next hop also all of the remaining path to the destination router. Thus, for in addition to the criterion of " best route " is also slightly different criteria, such as company policy provisos implement.

RIP versions

For IPv4, there are two versions of RIP before: RIPv1 and RIPv2. In RIPv1 no subnet masks are implemented.

For IPv6 RIP was adapted and published under the name of RIPng.