Introduction to Routing Protocols

The purpose of routing is to enable end-to-end network layer connectivity between endpoints. There is always a forward and reverse path selected between endpoints. The routing table is comprised of routes with next hop address to a destination network learned from different route sources. Cisco will refer to a network address as a subnet or prefix as well. Routes can be classified as connected, static, default, or dynamic. The distinction is in how a route is learned. For example, dynamic routes are advertised and automatically learned, while static and default routes are manually configured. Connected routes are automatically added to a routing table when a network interface is configured.

Figure 1 Network Layer Forwarding Path

Static vs Dynamic

Static, default and connected routes are the most common route types since they are found on most routers. Static and default routes are explicitly configured and automatically added to the routing table upon configuration. They have an administrative distance of 1 and path metric of zero (0). Static routes have an administrative distance lower than any dynamically learned route and preferred over dynamic routes to the same destination.

Static routes are NOT advertised to neighbors unless they are advertised through a dynamic routing protocol. Connected routes are automatically generated and added to the routing table when a network interface with an IP address is enabled. They have an administrative distance of zero and are preferred over all other route types.

There are various dynamic routing protocols that are designed to exchange route information with neighbors. The network administrator does not configure dynamic routes. Instead, they are learned from a connected neighbor so that each router installs and selects routes for best path selection.

The routes advertised are based on the routing protocol configuration. Common routing protocols such as OSPF, EIGRP, RIP, IS-IS, BGP, along with static and default routes support IPv4 and IPv6 address space. Network devices such as routers and Layer 3 switches support multiple dynamic routing protocols. Cisco ASA firewalls also support routing services with routed mode operation. The distinction between each routing protocol is how they learn, update, and advertise routes between neighbors.

Dynamic routing protocols are classified as link state or distance vector based on routing operation. The distinction between them is based on how neighbors communicate, send routing updates and converge. Originally, before internet connectivity, network domains were smaller and distance vector protocols such as RIP were adequate. There has been a paradigm shift to an IP-only internet connection model, with larger network domains and complex traffic routing. Distance vector routing protocols are being replaced with link state protocols for scalability and performance.

Distance vector routing protocols advertise their routing table to all connected neighbors at regular intervals. That occurs whether or not a topology change occurs or neighbor sends a request. Flooding of full routing tables occurs throughout the network domain when there is a link failure. That causes slower convergence that gets exponentially worse as the network domains become larger. There is also routing instability and flapping since routers do not have accurate updated route information.

Link state routing protocols are more sophisticated, since only event-triggered routing updates are sent to neighbors. That occurs when an interface goes down and a topology changes results. There is faster link failure detection, and only partial updates are sent for any missing route/s. The result is faster convergence and performance compared with distance vector protocols. Flooding occurs throughout the routing domain, however it is limited between areas to a single advertisement. SPF algorithm calculates shortest path based on an updated topology table.

OSPF and IS-IS are considered link state protocols. RIP is really the only pure distance vector protocol left, and has been updated with RIPv2 enhancements. EIGRP is classified as an advanced distance vector protocol with characteristics of both distance vector and link state protocols. EIGRP only has a neighbor topology table instead of a complete network topology database. Similar to link state protocols, EIGRP does form neighbor adjacencies and sends event-triggered updates instead of periodic full routing table updates.

BGP is a path vector protocol that advertises the destination path comprised of single of multiple autonomous system numbers (ASN) with each route. There are some other path attributes that are advertised with each route as well. The routes advertised from BGP neighbors include vector (direction) information for each forwarding path with AS path attribute.

Route Selection Algorithm

There are rules for route selection between different routing protocols and within the same routing protocol. The router first installs routes, and then selects the best path or route based on a route selection algorithm. Route sources include dynamic protocols (OSPF, EIGRP, IS-IS, BGP), static, default, and directly connected routes.

Refer to the Cisco routing table output comprised of multiple route entries from different route sources. Each route entry is comprised of a prefix, prefix length, next hop address, and local exit interface. Static interfaces only have a local exit interface when it is fully specified with the configuration. There is a recursive lookup to identify the local exit interface for a static route when not specified.

Sometimes there are multiple routes advertised from multiple route sources to the same destination. Each dynamic routing protocol maintains a separate routing table with best routes. The route with lowest administrative distance is installed in the global routing table when multiple routes exist to the same destination. For example, EIGRP has a lower administrative distance than OSPF or IS-IS. Conversely, static routes are preferred over all dynamic routes.

The route with lowest metric is installed when multiple routes exist from the same routing protocol to the same destination. In addition, when multiple routes with equal metric exist from the same routing protocol to the same destination, they are all installed and load balancing is enabled. The number of routes installed in the routing table for load balancing purposes, is based on routing protocol support.

The destination IP address field of each inbound packet is examined and a routing table lookup occurs for the best route. Once a route is selected, that creates a next hop forwarding path. There is frame rewrite of next hop MAC address that is obtained from an ARP table lookup, and data message is sent.

Figure 2 Inbound Routing Lookup

For the purpose of installing routes in the routing table, the router considers different prefix lengths as different destinations. That is why multiple routes from the same and/or different routing protocols are installed in the routing table. Tie breaker is longest match rule, that selects the route with the longest subnet mask (prefix length) from among routes already in the routing table.

1. Install route = lowest administrative distance (multiple route sources)
2. Install route/s = lowest metric (same routing protocol only)
3. Select route = longest match rule (multiple routes and route sources)
4. Select default route when no other route exists
5. Discard packet when no default route exists -> send ICMP unreachable message

Single Routing Protocol Only

Anytime you have only a single routing protocol implemented on a router, then administrative distance applies only if static routes are configured. For example, you could have a static route and an OSPF route to the same destination. The static route would then be installed in the routing table for that destination subnet. The exception is if both routes have different subnet mask lengths. At that point, longest match rule is in effect and router would select the route with longest subnet mask (prefix length) for packet forwarding.