Distance-vector routing protocol

From Wikipedia, the free encyclopedia

This article or section does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
Any unsourced material that has been or is likely to be challenged may be removed at any time. This article has been tagged since February 2007.

A distance-vector routing protocol is one of the two major routing protocols used in routing of packet-switched networks in computer communications. The other major type of routing protocol is the link state protocol. A distance-vector routing protocol uses the Bellman-Ford algorithm to calculate paths.

Examples of distance-vector routing protocols include RIPv1 or 2 and IGRP. EGP and BGP are not pure distance-vector routing protocols but their concepts are the same. In many cases, EGP and BGP are considered DV (distance-vector) routing protocols.

A distance vector routing protocol requires that a router informs its neighbours of topology changes periodically and in some cases when a change is detected in the topology of a network. Compared to link state protocols, which requires a router to inform all the nodes in a network of topology changes, distance vector routing protocols have less computational complexity and message overhead.

1 Method
2 Limitations
- 2.1 Partial solutions
3 Example
4 External links

[edit] Method

The actual figures which are used to calculate the best path for a network differ between different routing protocols but the fundamental features of distance vector algorithms are the same across all DV based protocols.

As the name suggests the DV protocol is based on calculating the direction and distance to any link in a network. The cost of reaching a destination is performed by using mathematical calculations such as the metrics of the route. RIP uses the hop count of the destination whereas IGRP has other information such as delay and bandwidth which it can use to calculate the desirability of a particular route.

Updates are performed periodically in a distance vector protocol where all or part of a routers routing table is sent to all its neighbours that are configured to use the same routing protocol. Once a router has this information it is able to amend its own routing table to reflect the changes and then inform its neighbours of the changes. This process has been described as ‘routing by rumour’ because routers are relying on the information it receives from other routers and cannot determine if the information is actually valid and true. There are a number of features which can be used to help with instability and inaccurate routing information

[edit] Limitations

Bellman-Ford algorithm does not prevent routing loops from happening and suffers from the count-to-infinity problem. The core of the count-to-infinity problem is that if A tells B that it has a path somewhere, there is no way for B to know if it's on the path. To see the problem clearly, imagine a subnet connected like A-B-C-D-E-F, and let the metric between the routers be "number of jumps". Now suppose that A goes down. In the vector-update-process B notices that it's once very short route of 1 to A is down - B does not receive the vector update from A. The problem is, B also gets an update from C, and C is still not aware of the fact that A is down - so it tells B that A is only two jumps from it, which is false. This slowly propagates through the network until it reaches infinity (in which case the algorithm corrects itself, due to the "Relax property" of Bellman Ford.

[edit] Partial solutions

RIP uses Split Horizon with Poison Reverse technique to reduce the chance of forming loops and use a maximum number of hops to counter the count-to-infinity problem. However, these measures can only mitigate the problems but not solve them, and has turned out to be of mere theoretical value. In practice this has led to the development of more complex but more scalable distance vector routing protocols.

[edit] Example

In this network we have 4 routers A, B, C, and D:

We shall mark the current time (or iteration) in the algorithm with T, and shall begin (at time 0, or T=0) by creating distance matrices for each router to its immediate neighbors. As we build the routing tables below, the shortest path is highlighted with the color green, a new shortest path is highlighted with the color yellow.

T=0

from A	via B	via C
to A
to B	3
to C		23
to D

from B	via A	via C
to A	3
to B
to C		2
to D

from C	via A	via B	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

At this point, all the routers (A,B,C,D) have new "shortest-paths" for their DV (the list of distances that are from them to another router via a neighbor). They each broacast this new DV to all their neighbors: A to B and C, B to C and A, C to A, B, and D, and D to C. As each of these neighbors receives this information, they now recalculate the shortest path using it.

For example: A receives a DV from C that tells A there is a path via C to D, with a distance (or cost) of 5. Since the current "shortest-path" to C is 23, then A knows it has a path to D that costs 23+5=28. As there are no other shorter paths that A knows about, it puts this as its current estimate for the shortest-path from itself (A) to D, via C.

T=1

from A	via B	via C
to A
to B	3	25
to C	5	23
to D		28

from B	via A	via C
to A	3	25
to B
to C	26	2
to D		7

from C	via A	via B	via D
to A	23	5
to B	26	2
to C
to D			5

from D	via A	via B	via C	via D
to A			28
to B			7
to C			5
to D

Again, all the routers have gained in the last iteration (at T=1) new "shortest-paths", so they all their DVs broadcast to their neighbors; This prompts each neighbor to re-calculate their shortest distances again.

For instance: A receives a DV from B that tells A there is a path via B to D, with a distance (or cost) of 7. Since the current "shortest-path" to B is 3, then A knows it has a path to D that costs 7+3=10. This path to D of length 10 (via B) is shorter than the existing "shortest-path" to D of length 28 (via C), so it becomes the new "shortest-path" to D.

T=2

from A	via B	via C
to A
to B	3	25
to C	5	23
to D	10	28

from B	via A	via C
to A	3	7
to B
to C	8	2
to D	31	7

from C	via A	via B	via D
to A	23	5	33
to B	26	2	12
to C
to D	51	9	5

from D	via A	via B	via C	via D
to A			10
to B			7
to C			5
to D

This time, only routers A and D have new shortest-paths for their DVs. So they broadcast their new DVs to their neighbors: A broadcasts to B and C, and D broadcasts to C. This causes each of the neighbors receiving the new DVs to re-calculate their shortest paths. However, since the information from the DVs doesn't yield any shorter paths than they already have in their routing tables, then there are no changes to the routing tables.

T=3

from A	via B	via C
to A
to B	3	25
to C	5	23
to D	10	28

from B	via A	via C
to A	3	7
to B
to C	8	2
to D	13	7

from C	via A	via B	via D
to A	23	5	15
to B	26	2	12
to C
to D	33	9	5

from D	via A	via B	via C	via D
to A			10
to B			7
to C			5
to D

None of the routers have any new shortest-paths to broadcast. Therefore, none of the routers receive any new information that might change their routing tables. So the algorithm comes to a stop.