In computer
communication theory relating to packet-switched networks, a
distance-vector
routing protocol is
one of the two major classes of routing protocols, the other major
class
being the link-state protocol. Distance-vector routing protocols use
the Bellman–Ford algorithm, Ford–Fulkerson algorithm, or DUAL FSM
(in the case of Cisco Systems'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 protocols,
which require a router to inform all the nodes in a network of
topology changes, distance-vector routing protocols have less
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. The vector
distance algorithm was the original ARPANET routing algorithm and was
also used in the internet under the name of RIP (Routing Information
Protocol).
Examples of
distance-vector routing protocols include RIPv1 and RIPv2 and IGRP.
Method
Routers using
distance-vector protocol do not have knowledge of the entire path to
a destination. Instead they use two methods:
- Direction in which router or exit interface a packet should be forwarded.
- Distance from its destination
Distance-vector
protocols are based on calculating the direction and distance to any
link in a network. "Direction" usually means the next hop
address and the exit interface. "Distance" is a
measure of the cost
to reach a certain node. The least cost route between any two nodes
is the route with minimum distance. Each node maintains a vector
(table) of minimum distance to every node. The cost of reaching a
destination is calculated using various route metrics. RIP 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.
EGP and BGP 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.
Count-to-infinity
problem
The 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 the path
has B as a part of it. 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 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 relaxation property of
Bellman–Ford).
No comments:
Post a Comment