A routing protocol specifies how routers communicate with each other, distributing information that enables them to select routes between any two nodes on a computer network.[1] There are 4 main categories of routing protocols:

  • Distance Vector (RIP)
  • Link-state (OSPF, ISIS)
  • Path Vector (BGP)
  • Hybrid (EIGRP)

image1-1
Figure 1: Routing protocol category summary.

Distance Vector

The distance vector (DV) protocol is the oldest routing protocol in practice. With distance vector routes are advertised based upon the following characteristics:

  • Distance - How far the destination network is based upon a metric such as hop count.
  • Vector - The direction (next-hop router or egress interface) required to get to the destination.

This routing information is exchanged between directly connected neighbours.[2] Therefore when a node receives a routing update, it has no knowledge of where the neighbour learned it from. In other words, the node has no visibility of the network past its own neighbour. This part of distance vector is also known as "routing by rumour".

Furthermore, routing updates are sent in full (rather than delta-based updates) and at regular intervals, resulting in extremely slow convergence times - one of the key downfalls to distance vector protocols. In addition due to the slow convergence times and "routing by rumour", distance vector protocols are prone to routing loops.

However, on the flipside, the resource consumption is low compared to link-state, due to not having to hold the full state of the entire topology.

Link-state

In contrast to distance vector routing, link state routing (OSPF, ISIS) relies on each node advertising/flooding the state (i.e. delay, bandwidth etc) of their links to every node within the link state domain. This results in each node building a complete map of the network (shortest path tree), with itself as the root using the shortest path first algorithm, also known as the Dijkstra algorithm.

Unlike distance vector link-state neighbours only sends incremental routing updates (LSAs) rather than a full routing update. Also, these updates are only sent at the point a change in the network topology occurs, rather than at regular intervals.

Link-state protocols provide extremely low convergence times and, due to each router having a complete view of the network, aren't prone to the same routing loops seen with DV-based protocols.

However, due to the computation required for the algorithms to run across the shortest path trees upon each node, greater resources are consumed compared to that of distance vector, however, this really isn't a concern with the systems of today.

Path Vector

Path vector (PV) protocols, such as BGP, are used across domains aka autonomous systems. In a path vector protocol, a router does not just receive the distance vector for a particular destination from its neighbor; instead, a node receives the distance as well as path information (aka BGP path attributes), that the node can use to calculate (via the BGP path selection process) how traffic is routed to the destination AS.

Hybrid

A hybrid routing protocol consists of characteristics from both, link state and distance vector routing protocols.

For example, EIGRP can be considered a hybrid routing protocol, as it displays characters of both. As shown below:

Distance Vector Link-state
EIGRP routers only advertise the best route , not every route that is aware of. An EIGRP router forms neighbour relationships.
EIGRP routers do not have a complete network map of the topology, but only what it has been told by its neighbour aka "routing by rumour". Triggered updates are sent only when a topology change occurs.

References


  1. "Routing protocol - Wikipedia." https://en.wikipedia.org/wiki/Routing_protocol. Accessed 8 Nov. 2018. ↩︎

  2. "Distance vector versus link-state - PacketLife.net." http://packetlife.net/blog/2008/oct/2/distance-vector-versus-link-state/. Accessed 7 Nov. 2018. ↩︎