The Distance-Vector (DV) Routing Algorithm

The Distance-Vector (DV) Routing Algorithm

The LS algorithm is an algorithm using global information, the distance-vector (DV) algorithm is iterative, asynchronous, and distributed. It is distributed in that each node receives some information from one or more of its directly attached neighbors, performs a calculation, and then distributes the results of its calculation back to its neighbors. It is iterative in that this process continues on until no more information is exchanged between neighbors. (Interestingly, the algorithm is also self-terminating - there is no signal that the computation should stop; it just stops.) The algorithm is asynchronous in that it does not require all of the nodes to operate in lockstep with each other. We'll see that an asynchronous, iterative, self-terminating, distributed algorithm is much more interesting and fun than a centralized algorithm!

Before we present the DV algorithm, it will prove useful to discuss an important relationship that exists among the costs of the least-cost paths. Let dx(y) be the cost of the least-cost path from node x to node y. Then the least costs are related by the celebrated Bellman-Ford equation, namely,

Bellman-Ford equation

where the minv in the equation is taken over all of x's neighbors. The Bellman-Ford equation is rather intuitive. In fact, after traveling from x to v, if we then take the least-cost path from v to y, the path cost will be c(x,v) + dv(y). Since we must begin by traveling to some neighbor v, the least cost from x to y is the minimum of c(x,v) + dv(y) taken over all neighbors v.

But for those who might be skeptical about the validity of the equation, let's check it for source node u and destination node z in "Routing Algorithms" Figure 1. The source node u has three neighbors: nodes v, x, and w. By walking along several paths in the graph, it is easy to see that dv(z) = 5, dx(z) = 3, and dw(z) = 3. Plugging these values into the Bellman-Ford equation, along with the costs c(u,v) = 2, c(u,x) = 1, and  c(u,w) = 5, gives du(z) = min {2 + 5, 5 + 3, 1 + 3} = 4, which is obviously true and which is exactly what the Dijskstra algorithm gave us for the same network. This quick verification should help relieve any skepticism you may have.

The Bellman-Ford equation is not just an intellectual curiosity. It actually has significant practical importance. Particularly, the solution to the Bellman-Ford equation provides the entries in node x's forwarding table. To see this, let v* be any neighboring node that achieves the minimum in the Bellman-Ford equation. Then, if node x wants to send a packet to node y along a least-cost path, it should first forward the packet to node v*. Therefore, node x's forwarding table would specify node v* as the next-hop router for the ultimate destination y. Another important practical contribution of the Bellman-Ford equation is that it suggests the form of the neighbor-to-neighbor communication that will take place in the DV algorithm.

The main idea is as follows. Each node x begins with Dx(y), an estimate of the cost of the least-cost path from itself to node y, for all nodes in N. Let Dx = [Dx(y): y in N] be node x's distance vector, which is the vector of cost estimates from x to all other nodes, y, in N. With the DV algorithm, each node x maintains the following routing information:

●  For each neighbor v, the cost c(x,v) from x to directly attached neighbor, v
●  Node x's distance vector, that is, Dx = [Dx(y): y in N], containing x's estimate of its cost to all destinations, y, in N
●  The distance vectors of each of its neighbors, that is, Dv = [Dv(y): y in N] for each neighbor v of x

In the distributed, asynchronous algorithm, from time to time, each node sends a copy of its distance vector to each of its neighbors. When a node x receives a new distance vector from any of its neighbors v, it saves v's distance vector, and then uses the Bellman-Ford equation to update its own distance vector as follows:

Eq12315a

If node x's distance vector has changed as a result of this update step, node x will then send its updated distance vector to each of its neighbors, which can in turn update their own distance vectors. Amazingly enough, as long as all the nodes continue to exchange their distance vectors in an asynchronous fashion, each cost estimate DX(y) converges to dx(y), the actual cost of the least-cost path from node x to node y [Bertsekas 1991]!

Distance-Vector (DV) Algorithm


At each node, x:

Distance Vector

In the DV algorithm, a node x updates its distance-vector estimate when it either sees a cost change in one of its directly attached links or receives a distance-vector update from some neighbor. But to update its own forwarding table for a given destination y, what node x really needs to know is not the shortest-path distance to y but instead the neighboring node v*(y) that is the next-hop router along the shortest path to y. As you might expect, the next-hop router v*(y) is the neighbor v that achieves the minimum in Line 14 of the DV algorithm. (If there are multiple neighbors v that achieve the minimum, then v*(y) can be any of the minimizing neighbors.) Therefore, in Lines 13-14, for each destination y, node x also determines v*(y) and updates its forwarding table for destination y.

Remember that the LS algorithm is a global algorithm in the sense that it requires each node to first get a complete map of the network before running the Dijkstra algorithm. The DV algorithm is decentralized and does not use such global information. In fact, the only information a node will have is the costs of the links to its directly attached neighbors and information it receives from these neighbors. Each node waits for an update from any neighbor (Lines 10-11), calculates its new distance vector when receiving an update (Line 14), and distributes its new distance vector to its neighbors (Lines 16-17). DV-like algorithms are used in many routing protocols in reality, including the Internet's RIP and BGP, ISO IDRP, Novell IPX and the original ARPAnet.

Figure 1 shows the operation of the DV algorithm for the simple three-node network shown at the top of the figure. The operation of the algorithm is shown in a synchronous manner, where all nodes at the same time receive distance vectors from their neighbors, compute their new distance vectors, and inform their neighbors if their distance vectors have changed. After studying this example, you should convince yourself that the algorithm operates correctly in an asynchronous manner as well, with node computations and update generation/reception occurring at any time.

The leftmost column of the figure displays three initial routing tables for each of the three nodes. For instance, the table in the upper-left corner is node x's initial routing table. Within a particular routing table, each row is a distance vector - particularly, each node's routing table contains its own distance vector and that of each of its neighbors. In this way, the first row in node x's initial routing table is Dx = [Dx(x), Dx(y), Dx(z)] = [0, 2, 7]. The second and third rows in this table are the most recently received distance vectors from nodes y and z, respectively. Because at initialization node x has not received anything from node y or z, the entries in the second and third rows are initialized to infinity.

After initialization, each node sends its distance vector to each of its two neighbors. This is shown in Figure 1 by the arrows from the first column of tables to the second column of tables. For instance, node x sends its distance vector Dx = [0, 2, 7] to both nodes y and z. After receiving the updates, each node recomputes its own distance vector. For instance, node x computes

Eq12315

Distance-vector algorithm

The second column therefore displays, for each node, the node's new distance vector along with distance vectors just received from its neighbors. Note, for instance, the node x's estimate for the least cost to node z, Dx(z), has changed from 7 to 3. Also note that for node x, neighboring node y achieves the minimum in line 14 of the DV algorithm; thus at this stage of the algorithm, we have at node x that v*(y) = y and V*(Z) = y.

After the nodes recompute their distance vectors, they again send their updated distance vectors to their neighbors (if there has been a change). This is shown in Figure 1 by the arrows from the second column of tables to the third column of tables. Note that only nodes x and z send updates: node y's distance vector didn't change so node y doesn't send an update. After receiving the updates, the nodes then recompute their distance vectors and update their routing tables, which are shown in the third column.

The process of receiving updated distance vectors from neighbors, recomputing routing table entries, and informing neighbors of changed costs of the least-cost path to a destination continues until no update messages are sent. At this point, since no update messages are sent, no further routing table calculations will occur and the algorithm will enter a quiescent state; that is, all nodes will be performing the wait in Lines 10-11 of the DV algorithm. The algorithm remains in the quiescent state until a link cost changes, as discussed next.


Tags

ls algorithm, nodes, dijskstra algorithm, asynchronous algorithm, routing tables

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.