Routing protocols and architectures/The Distance Vector algorithm

The Distance Vector (DV) algorithm is based on distribution of information about the whole network within the neighborhood of the router.

Every router periodically generates a DV, that is a set of destination-cost pairs:

• destination: all the destinations known by the generating router (in real IP networks they are network addresses with netmask);
• cost: the cost of the path from the generating router to the destination.

The receiving router learns from each DV:

• reachable destinations: they are added to the ones already known locally;
• direction: those destinations are reachable through the generating router;
• cost: the one reported by the generating router plus the cost of the link between the receiving router and the generating router.

Each node stores all the DVs coming from its neighbors, and integrates them by selecting the best costs for every destination in order to build its routing table and its DV:

Process generating the routing table and the new DV for node A.

Basic algorithm

• main process:
  1. the DV is announced to adjacent routers;
  2. it waits for timeout;
  3. it comes back to step 1;
• upon receiving a new DV:
  1. the DV is saved into memory;
  2. the DV is merged with stored DVs;
• upon failure of a link (detected at the physical layer):
  1. all the DVs coming from that link are deleted;
  2. remaining DVs are merged;
• when a DV has not been received within timeout:
  1. the missing DV is deleted;
  2. remaining DVs are merged.

Remarks

• reliability: timeouts avoid the use of link-up signals that may not be always available (e.g. if the failure occurs beyond a hub);
• efficiency: on a link failure, the router gets its new routing table without exchanging any DVs with its adjacent nodes;
• convergence speed: when a router changes its DV, it does not announce it until the next timeout of the main process (no triggered updates).

Triggered updates

A router can send its updated DV as soon as it updates its routing table, without waiting for the default timeout, to improve convergence time. It can announce either the entire DV or, like it is more frequent in real implementations, just the changed routes.

The triggered update does not reset the timeout of the main process, to avoid that routers start generating DVs at the same time (synchronization).

Count to infinity

Example of count to infinity.

A count to infinity is triggered when the cost to reach a destination, which is no longer reachable, is progressively increased to the infinity.

Example

In the side figure, a failure on the link between A and B triggers a count to infinity:

1. B detects the failure at the physical layer and deletes the DV from A, but C is not able to detect the failure at the physical layer;
2. C announces to B it can reach A through a path of cost 2, which really was the old one crossing B;
3. B updates the DV from C, appearing that A became reachable through an alternative path at cost 3 crossing C;
4. B in turn sends its DV to C, which updates it and increase the cost to 4, and so on.

Effect

B thinks it can reach A through C, while C thinks it can reach A through B → a packet which is directed to A starts bouncing between B and C (bouncing effect) saturating the link between B and C until its TTL goes down to 0.

Cause

Unlike black hole and routing loop, count to infinity is a specific problem of the DV algorithm, due to the fact that the information included in the DV does not consider the network topology.

Possible solutions

• threshold for infinity: upper bound to count to infinity;
• additional algorithms: they prevent count to infinity, but they make the protocol heavier and tend to reduce its reliability because they can not foresee all the possible failures:
  • route poisoning: bad news is better than no news;
  • split horizon: if C reaches destination A through B, it does not make sense for B to try to reach A through C;
  • path hold down: let the rumors calm down waiting for the truth.

Threshold for infinity

A threshold value can be defined: when the cost reaches the threshold value, the destination is considered no longer reachable.

For example RIP has a threshold value equal to 16: more than 15 routers in a cascade can not be connected.

Protocols with complex metrics (e.g. IGRP) require a very high threshold value to consider differentiated costs: for example a metric based on bandwidth may result in a wide range of cost values.

If the bouncing effect takes place on a low-cost link, it is required too much time to increase costs up to the threshold value → two metrics at the same time can be used:

• a metric for path costs (e.g. based on link bandwidth);
• a metric for count to infinity (e.g. based on hop count).

When the metric used for count to infinity returns 'infinity', the destination is considered unreachable whatever the path cost is.

Route poisoning

The router which detected the failure propagates the destinations no longer reachable with cost equal to infinity → the other routers hear about the failure and in turn propagate the 'poisoned' information.

Split horizon

Every router differentiates DVs sent to its neighbors: in each DV it omits the destinations which are reachable through a path crossing the neighbor to which it is sending it → it does not trigger 'ghost' paths to appear toward a destination no longer reachable after sending obsolete information in the DV.

Characteristics

• it avoids count to infinity between two nodes (except in case of particular loops);
• it improves convergence time of the DV algorithm;
• routers have to compute a different DV for each link.

Split horizon with poisoned reverse

In real implementations, the DV may be fragmented into multiple packets → if some entries in the DV are omitted, the receiving node does not know whether those entries were intentionally omitted by the split horizon mechanism or the packets where they were included went lost.

In split horizon with poisoned reverse, destinations instead of being omitted are transmitted anyway but 'poisoned' with infinite cost, so the receiving node is sure it has received all the packets composing the DV → this increases convergence time.

Path hold down

If the path toward a destination increases its cost, it is likely to trigger a count to infinity → that entry is 'frozen' for a specific period of time waiting for the rest of the network to find a possible alternative path, whereupon if no one is still announcing that destination it will be considered unreachable and its entry will be deleted.

DUAL

Diffusing Update Algorithm (DUAL) is an additional algorithm that aims at improving the scalability of the DV algorithm by guaranteeing the absence of routing loops even during the transient:

• positive status change: if any neighbor node announces an alternative path with a lower cost, it is immediately accepted because definitely it will not cause a routing loop;
• negative status change: if
  • either the current next hop announces the increase of the current route (worsening announces by other neighbor nodes are ignored),
  • or the router detects at the physical layer a fault on the link belonging to the current route

  then the DUAL algorithm must be activated:

  1. selection of a feasible successor: another neighbor is selected only if it guarantees that the alternative path across it will not cause routing loops;
  2. diffusing process: if no feasible successors can be found, the node enters a sort of 'panic mode' and asks its neighbors for help, waiting for someone to report a feasible path toward that destination.

Selection of a feasible successor

If the current route is no longer available due to a negative status change, an alternative path is selected only if it can be proved that the new path does not create loops, that is if it is certain that the new next hop does not use the node itself to reach the destination.

A neighbor node $K$ is a feasible successor for router $R$ if and only if its distance toward destination $D$ is smaller than the distance that router $R$ had before the status change:

$d\left(K,D\right)<d\left(R,D\right)$

This guarantees that neighbor $K$ can reach destination $D$ by using a path that does not go through router $R$: if path $K\rightarrow D$ passed across $R$, its cost could not be lower than the one of sub-path $R\rightarrow D$.

In case more than one feasible successor exists, neighbor $X$ is selected offering the least-cost path toward destination $D$:

$\min {\{L\left(R,X\right)+d\left(X,D\right)\}}$

where:

• $L\left(R,X\right)$ is the cost of the link between router $R$ and its neighbor $X$;
• $d\left(X,D\right)$ is the distance between neighbor $X$ and destination $D$.

The selected feasible successor is not guaranteed to be the neighbor which the best possible path toward the destination goes across. If the mechanism does not select the best neighbor, the latter will keep announcing the path which is really the best one without changing its cost → the router will recognize the existence of a new, better path which was not selected and adopt the new path (positive status change).

Diffusing process

If router $R$ can not find any feasible successor for the destination:

1. it temporarily freezes the entry in its routing table related to the destination → packets keep taking the old path, which definitely is free of loops and at most is no longer able to lead to the destination;
2. it enters an active state:
   1. it sends to each of its neighbors, but the next hop of the old path, a query message asking if it is able to find a path which is better than its old path and which is definitely free of loops;
   2. it waits for a reply message to be received from each of its neighbor;
   3. it chooses the best path exiting from the active state.

Each neighbor router $X$ receiving the query message from router $R$ sends back a reply message containing its DV related to a path across it:

• if router $R$ is not its next hop toward the destination, and therefore the cost of its path toward the destination has not been changed, then router $X$ reports that router $R$ can use that path;
• if router $R$ is its next hop toward the destination, then router $X$ should in turn set out to search for a new path, by either selecting a feasible successor or entering the active state too.

Advantages and disadvantages

Advantages

• very easy to implement, and protocols based on the DV algorithm are simple to configure;
• it requires limited processing resources → cheap hardware in routers;
• suitable for small and stable networks with not too frequent negative status changes;
• the DUAL algorithm guarantees loop-free networks: no routing loops can occur, even in the transient (even though black holes are still tolerated).

Disadvantages

• the algorithm has an exponential worst case and it has a normal behavior between $O\left(n^{2}\right)$ and $O\left(n^{3}\right)$;
• convergence may be rather slow, proportional to the slowest link and the slowest router in the network;
• difficult to understand and predict its behavior in big and complex networks: no node has a map of the network → it is difficult to detect possible routing loops;
• it may trigger routing loops due to particular changes in topology;
• additional techniques for improving its behavior make the protocol more complex, and they do not solve completely the problem of the missing topology knowledge anyway;
• the threshold 'infinity' limits the usage of this algorithm only to small networks (e.g. with few hops).

The Path Vector algorithm

The Path Vector (PV) algorithm adds information about the announced routes: also the path, that is the list of crossed nodes along it, is announced:

Process generating the routing table and the new PV for node A.

The list of crossed nodes allows to avoid the appearance of routing loops: the receiving node is able to detect that the announced route crosses it by observing the presence of its identifier in the list, discarding it instead of propagating it → paths crossing twice the same node can not form.

Path Vector is an intermediate algorithm between Distance Vector and Link State: it adds the strictly needed information about announced paths without having the complexity related to Link State where the whole network topology needs to be known.

Application

The PV algorithm is used in inter-domain routing by the BGP protocol: B5. Border Gateway Protocol#Path Vector algorithm.