Distance-Vector Routing

Each node constructs a one-dimensional array containing the "distances"(costs) to all other nodes and distributes that vector to its immediate neighbors.

1. The starting assumption for distance-vector routing is that each node knows the cost of the link to each of its directly connected neighbors.
2. A link that is down is assigned an infinite cost.

To see how a distance-vector routing algorithm works, it is easiest to consider an example 

 

Distance-vector routing: an example network.

In this example, the cost of each link is set to 1, so that a least-cost path is simply the one with the fewest hops. We can represent each node’s knowledge about the distances to all other nodes as a table like the one given in Table. Note that each node only knows the information in one row of the table. The global view that is presented here is not available at any single point in the network.

Table 1: Initial distances stored at each node (global view).

We may consider each row in Table 1 as a list of distances from one node to all other nodes, representing the current beliefs of that node. Initially, each node sets a cost of 1 to its directly connected neighbors and ∞ to all other nodes. Thus, A initially believes that it can reach B in one hop and that D is unreachable. The routing table stored at A reflects this set of beliefs and includes the name of the next hop that A would use to reach any reachable node. 

Table2: Initial routing table at node A.

Initially, then, A’s routing table would look like Table 2.The next step in distance-vector routing is that every node sends a message to its directly connected neighbors containing its personal list of distances.

Table 3: Final routing table at node A.

For example, node F tells node A that it can reach node G at a cost of 1; A also knows it can reach F at a cost of 1, so it adds these costs to get the cost of reaching G by means of F. This total cost of 2 is less than the current cost of infinity, so A records that it can reach G at a cost of 2 by going through F. Similarly, A learns from C that D can be reached from C at a cost of 1; it adds this to the cost of reaching C (1) and decides that D can be reached via C at a cost of 2, which is better than the old cost of infinity. At the same time, A learns from C that B can be reached from C at a cost of 1, so it concludes that the cost of reaching B via C is 2. Since this is worse than the current cost of reaching B (1), this new information is ignored.

Node A can update its routing table with costs and next hops for all nodes in the network and  The result is shown in Table 3

If there is any topology changes, it only takes a few exchanges of information between neighbors before each node has a complete routing table. The process of getting consistent routing information to all the nodes is called convergence.

There are two different circumstances under which a given node decides to send a routing update to its neighbors.

One of these circumstances is the periodic update. each node automatically sends an update message every time interval, even nothing has changed.The frequency of these periodic updates varies from protocol to protocol.

The second mechanism, sometimes called a triggered update, happens whenever a node receives an update from one of its neighbors that causes it to change one of the routes in its routing table. That is, whenever a node’s routing table changes, it sends an update to its neighbors, which may lead to a change in their tables, causing them to send an update to their neighbors.

Final distances stored at each node (global view).

When a node detects a link failure

• F detects that link to G has failed
• F sets distance to G to infinity and sends update to A
• A sets distance to G to infinity since it uses F to reach G
• A receives periodic update from C with 2-hop path to G
• A sets distance to G to 3 and sends update to F
• F decides it can reach G in 4 hops via A

Slightly different circumstances can prevent the network from stabilizing.Suppose the link from A to E goes down. In the next round of updates, A advertises a distance of infinity to E, but B and C advertise a distance of 2 to E. Depending on the exact timing of events, the following might happen.

• Node B, upon hearing that E can be reached in 2 hops from C, concludes that it can reach E in 3 hops and advertises this to A
• Node A concludes that it can reach E in 4 hops and advertises this to C
• Node C concludes that it can reach E in 5 hops; and so on.
• This cycle stops only when the distances reach some number that is large enough to be considered infinite
• This problem is called as Count-to-infinity problem

 There are several partial solutions to this problem. The first one is to use some relatively small number as an approximation of infinity. For example, we might decide that the maximum number of hops to get across a certain network is never going to be more than 16, and so we could pick 16 as the value that represents infinity. This at least bounds the amount of time that it takes to count to infinity.

One technique to improve the time to stabilize routing is called split horizon. The idea is that when a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor.For example, if B has the route (E, 2, A) in its table, then it knows it must have learned this route from A, and so whenever B sends a routing update to A, it does not include the route (E, 2) in that update.In a stronger variation of split horizon, called split horizon with poison reverse, B actually sends that route back to A, but it puts negative information in the route to ensure that A will not eventually use B to get to E.

Routing Information Protocol (RIP)

One of the most widely used routing protocols in IP networks is the Routing Information Protocol (RIP). RIP is the canonical example of a routing protocol built on the distance-vector algorithm.

RIP Packet Format

RIP is in fact a fairly straightforward implementation of distance-vector routing. Routers running RIP send their advertisements every 30 seconds; a router also sends an update message whenever an update from another router causes it to change its routing table. One point of interest is that it supports multiple address families, not just IP. The network-address part of the advertisements is actually represented as a family, address pair. RIP version 2 (RIPv2) also has some features related to scalability