Networking / Beginners

Distance Vector Routing Protocol

In a distance vector routing algorithm, routes are selected based on the distance between networks. The distance metric is something simple enough to allow consistent values across the domain (for instance, number of hops, the time delay in getting messages to the destination, or the cost of sending messages to it). Routers maintain a database with distance values to all known networks. They periodically send this database to each of their neighbors (or peers if connected over virtual links). These neighbors update their own tables by computing distances to known networks, which typically involves adding their own contribution to the distance received from neighbors. Then they send the information to their own neighbors and so on. This mechanism propagates the distance information across the entire network.

To compute the shortest path (from a distance perspective) and next hop to each destination prefix, the Bellman-Ford algorithm is used, named after its inventors. RIP, IGRP, and EIGRP are IPv4 examples of RPs using this technology. For IPv6, this translates into RIPng and EIGRP for IPv6.

Distance vector RPs provide suitable performance on small or medium-sized networks. On large networks, route computation may become slow and impact the convergence time, because it must occur at each router prior to propagating the routing updates. Problems can also appear because routers are not aware of the topology of the entire network. They know their connected neighbors and the routes known by these neighbors (sometimes referred to as routing by rumor). In large networks, this can lead to routing loops, so additional anti-loop mechanisms are required. RIP implements the split-horizon and poison-reverse mechanisms to prevent incorrect routing information from being propagated. The basic split-horizon algorithm omits routes learned from one neighbor in updates sent to that neighbor. Poison reverse does include such routes in updates, but sets their metrics to infinity. (A metric of 16 means route is unreachable.) BGP relies on the full-path analysis carried in advertisements.

[Contents] [Next]