Distance-vector routing protocol - AbsoluteAstronomy.com

In computer communication theory relating to packet-switched networks, a distance-vector routing protocol is one of the two major classes of routing protocol

Routing protocol

A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...

s, the other major class being the link-state protocol. Distance-vector routing protocols use the Bellman-Ford algorithm

Bellman-Ford algorithm

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem....

, Ford–Fulkerson algorithm, or DUAL FSM (in the case of Cisco Systems

Cisco Systems

Cisco Systems, Inc. is an American multinational corporation headquartered in San Jose, California, United States, that designs and sells consumer electronics, networking, voice, and communications technology and services. Cisco has more than 70,000 employees and annual revenue of US$...

's protocols) to calculate paths.

A distance-vector routing protocol requires that a router informs its neighbors of topology changes periodically. Compared to link-state protocol

Link-state routing protocol

A link-state routing protocol is one of the two main classes of routing protocols used in packet switching networks for computer communications . Examples of link-state routing protocols include OSPF and IS-IS....

s, which require a router to inform all the nodes in a network of topology changes, distance-vector routing protocols have less computational complexity

Computational Complexity

Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...

and message overhead.

The term distance vector refers to the fact that the protocol manipulates vectors (arrays) of distances to other nodes in the network.

Routers using distance vector protocol do not have knowledge of the entire path to a destination. Instead DV uses two methods:

Direction in which or interface to which a packet should be forwarded.
Distance from its destination.

Examples of distance-vector routing protocols include RIPv1 and RIPv2

Routing Information Protocol

The Routing Information Protocol is a distance-vector routing protocol, which employs the hop count as a routing metric. RIP prevents routing loops by implementing a limit on the number of hops allowed in a path from the source to a destination. The maximum number of hops allowed for RIP is 15....

and IGRP

Interior Gateway Routing Protocol

Interior Gateway Routing Protocol is a distance vector interior routing protocol invented by Cisco. It is used by routers to exchange routing data within an autonomous system....

. EGP

Exterior Gateway Protocol

The Exterior Gateway Protocol is a now obsolete routing protocol for the Internet originally specified in 1982 by Eric C. Rosen of Bolt, Beranek and Newman, and David L. Mills. It was first described in RFC 827 and formally specified in RFC 904...

and BGP

Border Gateway Protocol

The Border Gateway Protocol is the protocol backing the core routing decisions on the Internet. It maintains a table of IP networks or 'prefixes' which designate network reachability among autonomous systems . It is described as a path vector protocol...

are not pure distance-vector routing protocols because a distance-vector protocol calculates routes based only on link costs whereas in BGP, for example, the local route preference value takes priority over the link cost.

Method

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

Distance Vector means that Routers are advertised as vector of distance and Direction.
Direction is simply next hop address and exit interface and Distance means hop count.

Routers using distance vector protocol do not have knowledge of the entire path to a destination. Instead DV uses two methods:

Direction in which router or exit interface a packet should be forwarded.
Distance from its destination.

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 calculated using various route metrics. RIP

Routing Information Protocol

uses the hop count of the destination whereas IGRP takes into account other information such as node delay and available bandwidth.

Updates are performed periodically in a distance-vector protocol where all or part of a router's routing table is sent to all its neighbors that are configured to use the same distance-vector routing protocol. RIP supports cross-platform distance vector routing whereas IGRP is a Cisco Systems proprietary distance vector 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 neighbors of the changes. This process has been described as ‘routing by rumor’ because routers are relying on the information they receive 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.

Count-to-infinity problem

The Bellman-Ford algorithm

Bellman-Ford algorithm

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem....

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 the path has B as a part of it. To see the problem clearly, imagine a subnet connected like as A-B-C-D-E-F, and let the metric between the routers be "number of jumps". Now suppose that A is taken offline. In the vector-update-process B notices that the route to A, which was distance 1, 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 C (C to B to A) , 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).

Workarounds and solutions

RIP

Routing Information Protocol

uses the Split Horizon

Split horizon

In computer networking, split-horizon route advertisement is a method of preventing routing loops in distance-vector routing protocols by prohibiting a router from advertising a route back onto the interface from which it was learned.-Example:...

with Poison Reverse

Route poisoning

Route poisoning is a method to prevent a router from sending packets through a route that has become invalid within computer networks. Distance-vector routing protocols in computer networks use route poisoning to indicate to other routers that a route is no longer reachable and should not be...

technique to reduce the chance of forming loops and uses a maximum number of hops to counter the 'count-to-infinity' problem. These measures avoid the formation of routing loops in some, but not all, cases. The addition of a hold time (refusing route updates for a few minutes after a route retraction) avoids loop formation in virtually all cases, but causes a significant increase in convergence times.

More recently, a number of loop-free distance vector protocols have been developed — notable examples are EIGRP, DSDV and Babel

Babel (protocol)

The Babel routing protocol is a distance-vector routing protocol for Internet Protocol packet-switched networks that is designed to be robust and efficient on both wireless mesh networks and wired networks....

. These avoid loop formation in all cases, but suffer from increased complexity, and their deployment has been slowed down by the success of link-state routing protocol

Link-state routing protocol

s such as OSPF.

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 broadcast 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 broadcast their DVs 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	25
to B
to C	26	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	33	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	31	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.

External links

A Java applet implementing Distance Vector algorithm for pedagogical purposes

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Method

Count-to-infinity problem

Workarounds and solutions

Example

Further reading

External links