In packet switching networks, routing directs packet forwarding, the transit of logically addressed packets from their source toward their ultimate destination through intermediate nodes. These nodes are typically hardware devices called routers, bridges, gateways, firewalls, or switches. General-purpose computers with multiple network cards can also forward packets and perform routing, though they are not specialized hardware and may suffer from limited performance.
The routing process usually directs forwarding on the basis of routing tables that maintain a record of the routes to various network destinations. Thus, constructing routing tables, which are held in the routers’ memory, is very important for efficient routing. Most routing algorithms use only one network path at a time, but multipath routing techniques enable the use of multiple alternative paths.
The decision of which routing protocol to configure and use must consider many different factors. One of those factors is which branch or family of routing protocols to implement. There are three main branches or families of routing protocol algorithms; Distance Vector, Link-State, and Balanced Hybrid. Each family has distinct functions and features that can provide a desired functionality. Each family also presents certain deficiencies that may preclude its use in modern networks.
Historically speaking, distance vector protocols were developed first, primarily in the early 1980s. A distance-vector routing protocol requires that a router inform its neighbors of topology changes periodically and, in some cases, when a change is detected in the topology of a network. Compared to link-state protocols, which require a router to inform all the nodes in a network of topology changes, distance-vector routing protocols require less router overhead and bandwidth utilization.
The phrase “distance vector” means that routes are advertised as a vector representing distance and direction. Direction is simply the next hop address or exit interface. In the case of the only currently used distance vector routing protocol, RIP, distance means hop count between the initiating router and the destination network.
Routers using a distance vector protocol do not have a record of the entire path from source to destination. Instead, distance vector protocols use two options:
- Direction in which a packet should be forwarded.
- Distance from its destination in hop count
As the name suggests, the distance vector protocol is based on calculating the direction and distance to any link in a network. The cost of reaching a destination is calculated using various route metrics. RIP uses the hop count of the destination as its metric for optimal route calculation. Updates are performed periodically in a distance-vector protocol network, where all or part of a router’s routing table is sent to all its neighbors that are configured to use the same distance-vector routing protocol. The updates are sent every 30 seconds whether or not there is a topological change.
By the early 1990s, distance vector protocol’s somewhat slow convergence and potential for routing loops drove the development of new, alternative routing protocols that used new algorithms. Link-State protocols, in particular OSPF and Integrated IS-IS, solved the main issues with distance vector protocols. However, these new link-state protocols required more planning in medium-to larger-sized networks.
First, each node needs to determine what ports it is connected to over fully-working links. It does this using a simple reachability protocol that it runs separately with each of its directly-connected neighbors. Next, each node periodically, and in case of connectivity changes, makes up a short message called the Link State Advertisement LSA), which is flooded throughout the network.
The basic concept of link-state routing is that every node constructs a map of the connectivity to the network in the form of a topology table showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical hop from it to every possible destination in the network. The collection of best next hops will then form the node’s routing table.
Link-state routing protocols use path cost to the destination as its metric for optimal route calculation and do not rely on periodic route updates in order to maintain its topology table. Routing information is exchanged only upon the establishment of new neighbor adjacencies and construction of the adjacency table, after which only changes are sent through an event generated Link State Update (LSU.
Around the same time as the introduction of OSPF, Cisco created a proprietary routing protocol called Enhanced Interior Gateway Routing Protocol (EIGRP) which used some features of the earlier IGRP protocol. EIGRP solved the same problems as did link-state routing protocols, but less planning is required when implementing the network. As time went on, EIGRP was classified as a unique type of routing protocol. It was considered to be neither distance vector nor link state, so EIGRP is called either a balanced hybrid protocol or an advanced distance vector protocol.
EIGRP was designed to minimize both the routing instability incurred after topology changes, as well as the use of bandwidth and processing power in the router. Most of the routing optimizations are based on the Diffusing Update Algorithm (DUAL) that guarantees loop-free operation and provides a mechanism for fast convergence.
The data EIGRP collects is stored in three tables:
- Neighbor Table – Stores data about the neighboring routers, i.e. those directly accessible through directly connected interfaces.
- Topology Table – Contains the aggregation of the routing tables gathered from all directly connected neighbors.
- Routing Table – Stores the actual routes to all destinations
EIGRP does not rely on periodic route updates in order to maintain its topology table. EIGRP uses the bandwidth and delay to the destination as its metrics for optimal route calculation and does not rely on periodic route updates in order to maintain its topology table. Routing information is exchanged only upon the establishment of new neighbor adjacencies, after which only changes are sent through triggered updates.
In my next post, I will discuss the three most commonly implemented routing protocols, RIP, OSPF, and EIGRP, in detail.
Author: David Stahl