The distance-vector routing is a type of algorithm used by routing protocols to discover routes on an interconnected network. A distance-vector routing protocol uses the Bellman-Ford algorithm to calculate paths.
A distance-vector routing protocol requires that a router informs its neighbors 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.
Distance vector routing protocols include the following:
Routing Information Protocol (RIP) for IP
Xerox Networking System's XNS RIP
Novell's IPX RIP
Cisco's Internet Gateway Routing Protocol (IGRP)
DEC's DNA Phase IV
AppleTalk's Routing Table Maintenance Protocol (RTMP)
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 it is 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 its 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).
Distance Vector and LinkState protocols
Distance Vector protocols judge best path on how far it is. Distance can be hops or a combination of metrics calculated to represent a distance value. The IP Distance Vector routing protocols still in use today are: Routing Information Protocol (RIP v1 and v2) and Interior Gateway Routing Protocol (IGRP – developed by Cisco).
A Link-state routing is a concept used in routing of packet-switched networks in computer communications. Link-state routing works by having the routers tell every router on the network about its closest neighbors. The entire routing table is not distributed from any router, only the part of the table containing its neighbors.
Some of the link-state routing protocols are the OSPF, IS-IS and EIGRP. Novell's NLSP (NetWare Link State Protocol) is also a link-state routing protocol, which only supports IPX. This type of routing protocol requires each router to maintain at least a partial map of the network. When a network link changes state (up to down, or vice versa), a notification, called a link state advertisement (LSA) is flooded throughout the network. All the routers note the change, and re-compute their routes accordingly.
Distance-vector routing protocols are simple and efficient in small networks, and require little, if any management. However, they do not scale well, and have poor convergence properties, which has led to the development of more complex but more scalable link-state routing protocols for use in large networks.