09. Introduction to Routing - Distance Vector Algorithm

A dynamic, decentralized and asynchronous routing algorithm.

Both RIP and BGP use the Bellman-Ford (distance-vector) algorithm.

Bellman-Ford Equation

if $d_x(y)$ is the least-cost path from $x$ to $y$, then:

$d_x(y) = min_v{c(x, v) + d_v(y)}$ for all $v$ where $v$ is a neighbor of $x$.

Distance-Vector Algorithm

$D_x(y)$ is an estimation of the least-cost path from $x$ to $y$

The distance vector, $\vec{D_x}$, maintains a list of estimates for each node in the graph: $[ D_x(y): y \in N ]$, where $N$ is the set of all destinations.

Each node, $x$ knows the cost, $c(x, v)$ to each neighbor $v$, its distance vector, and its neighbors’ distance vectors.

In the algorithm, each node periodically sends its own distance vector estimates to its neighbors. When it receives a new estimate, it can update its own distance vector and if it changes, update its own neighbors. The distance estimates for any node will eventually converge to the actual least cost, $d_x(y)$.

The algorithm is iterative and asynchronous: each local iteration is called by either a local link cost change or a DV update message from its neighbor.

The algorithm is distributed: each node notifies its neighbors only when its DV changes, and each node only knows the next hop, not the entire path.

Hence, each node is in one of three state:

• Wait for change in local link cost, or message from a neighbor
• Recompute DV estimate
• Notify neighbors if required

Pseudo-code

distance_vector = []
neighbor_distance_vectors = {}

def init():
  for y in destinations:
    distance_vector[y] = cost(self, y) # Infinity if not a neighbor
  
  for w in neighbors:
    neighbor_distance_vectors[w] = [INFINITY for y in destinations]
    send(w, distance_vector)
  
  while True:
    get_update_or_link_cost_change()

    for y in destinations:
      distance_vector[y] = min([cost(self, v) + neighbor_distance_vectors[v][y] for v in neighbors])

    if change_occurred:
      for y in neighbors:
        send(y, distance_vector)

Count-to-infinity problem

Good news travels fast: if a link cost is lowered, this change propagates through the network quickly.

However, there is an issue when a link cost increases. For example, assume $x \rightarrow z > x \rightarrow y \rightarrow z$. If the link cost from $x \rightarrow y$ increases such that the new best path from $x$ to $y$ is $x \rightarrow z \rightarrow y$, an issue will occur as the algorithm is asynchronous: $z$ still thinks the best path from $z$ to $y$ is $z \rightarrow x \rightarrow y$. Hence, it will generate a routing loop: $x \rightarrow z \rightarrow x \rightarrow z\dots$.

Initial state: link costs of $c(x, y) = 1$, $c(y, z) = 2$, $c(z, x) = 20$.

At $t_0$, $y$ detects $c(x, y) = 40$. $y$ thinks the best route to $x$ is now through $z$:

$D_y(x) = min(cost(y, x) + D_x(x), cost(y, z) + D_z(x)) = min(40 + 0, 2 + 3) = 5$

At $t_1$, $z$ receives an update from $y$ and calculates $D_z(x)$:

$D_z(x) = min(cost(z, x) + D_x(x), cost(z, y) + D_y(x)) = min(20 + 0, 2 + 5) = 7$

Thus, at each iteration, $D_z(x)$ and $D_y(x)$ increases by 2 (link cost between $y$ and $z$) and eventually converge:

Poisoned reverse

If a node $x$ routes packets to $z$ through $y$, $x$ will lie to $y$, telling it that $D_x(z) = \infty$.

Before the link cost change in the example above, $z$ lies to $y$, saying $D_z(x) = \infty$ as long as it uses $y$ to route to $x$. In $y$’s DV table:

At $t_0$, $y$ detects $c(x, y) = 40$:

$D_y(x) = min(cost(y, x) + D_x(x), cost(y, z) + D_z(x)) = min(40 + 0, 2 + \infty) = 40$

At $t_1$, $z$, receives an update from $y$ and calculates $D_z(x)$:

$D_z(x) = min(cost(z, x) + D_x(x), cost(z, y) + D_y(x)) = min(20 + 0, 2 + 40) = 20$:

At $t_2$, $y$, updates $z$, now without lying. $y$ calculates $D_y(x)$:

$D_y(x) = min(cost(y, x) + D_x(x), cost(y, z) + D_z(x)) = min(40 + 0, 2 + 20) = 22$

Hence, the lie makes it converge faster.

However, poisoned reverse can make the situation worse and cause routing loops. Example:

Consider only entries only to $x$:

So $z$ tells $w$ that $D_z(x)=\infty$ and $w$ tells $y$ that $D_w(x)=\infty$; they lie to the node they rely on for routing, ensuring they do not send requests back to them.

At $t_0$, $y$ detects $cost(x, y) = 60$ and recalculates its vector table: $D_y(x)$ is the minimum of:

• $cost(y, z) + D_z(x) = 3 + 6 = 9$
• $cost(y, x) + D_x(x) = 60 + 0 = 60$
• $cost(y, w) + D_w(x) = 1 + \infty$

Hence, $D_y(x) = 9$ (through $z$). Now, $y$ notifies $w$ that $D_y(x) = 9$ and $z$ that $D_y(x) = \infty$.

Now $w$ recomputes $D_w(x)$:

• $cost(w, y) + D_y(x) = 1 + 9 = 10$
• $cost(w, z) + D_z(x) = 1 + \infty$

Hence, $D_w(x) = 10$ (through $y$). Now, $w$ notifies $z$ that $D_w(x) = 10$ and $y$ that $D_w(x) = \infty$.

Now, $z$ recomputes $D_z(x)$:

• $cost(z, w) + D_w(x) = 1 + 10 = 11$
• $cost(z, y) + D_y(x) = 3 + \infty$
• $cost(z, x) + D_x(x) = 50 + 0$

Hence, $D_z(x) = 11$ (through $w$). Now $z$ notifies $y$ that $D_z(x) = 11$ and $w$ that $D_z(x) = \infty$. Now, $y$ recomputes $D_y(x)$:

• $cost(y, z) + D_z(x) = 3 + 11 = 14$
• $cost(y, x) + D_x(x) = 60 + 0 = 60$
• $cost(y, w) + D_w(x) = 1 + \infty$

Hence, $D_y(x) = 14$ (through $z$). The process repeats.

The computed path from $y$ to $x$ is thus $y \rightarrow z \rightarrow w \rightarrow y \rightarrow \dots$; a routing loop occurs.

To fix this, RIP limits the maximum cost of a path is limited to 15.

Comparison of Link-State and Distance-Vector Algorithms

Message complexity:

• LS: $n$, nodes and $E$, links, $O(nE)$ messages
• DV: only exchanging information between neighbors
  • Convergence time varies

Speed of convergence:

• LS: $O(n^2)$ algorithm, $O(nE)$ messages
  • May have oscillations
• DV: convergence time varies
  • Routing loops
  • Count-to-infinity problem

Robustness - behavior when router malfunctions:

• LS: node advertises incorrect link cost
  • Each node computes only its own table
• DV: node advertises incorrect path cost
  • Each node’s table used by others; errors propagate through the network