Concepts of Routing Protocols

Before analyzing details about each individual routing protocol, some general information about IP routing will be presented first. Network designers should know the key characteristics that different routing protocols have because they will be in a position to recommend specific routing protocols for different projects. The first key decision criteria is figuring out whether static or dynamic routing should be used. Static routing implies manually defining routes on devices and dynamic routing implies using a dedicated routing protocol that will build the routing table.

Static Routing

Even though static routes may not seem necessary in modern networks, there are situations in which they can offer granular control and optimization of the information learned by the routing protocols. Static routes can be used in conjunction with dynamic routing protocols to reach specific networks or to provide the default gateway (e.g., pointing to the ISP), which is useful in situations where the destination network is not part of the routing protocol database.

Another scenario in which static routes are used is to override some dynamically learned routing information. Static routing can also be used in the form of floating static routes, for example, setting the Administrative Distance (AD) of a particular static route to a higher (worse) value than the AD value of the same route learned via a routing protocol for failover reasons.

Dynamic Routing

An important decision to be made when choosing the routing protocol is whether an Interior Gateway Routing Protocol (IGRP) or an Exterior Gateway Routing Protocol (EGRP) will be needed. When routing between devices within an organization (Autonomous System – AS), there are many IPv4-based IGRPs to choose from, such as the following:

• RIPv1
• RIPv2
• OSPF
• IS-IS
• IGRP
• EIGRP
• ODR

 

Note:    RIPv1 and IGRP are considered legacy protocols and some modern network devices do not support them.

On Demand Routing (ODR) is a Cisco proprietary protocol designed for hub-and-spoke topologies. It offers basic routing functionality and works over Cisco Discovery Protocol (CDP). The most common interior protocols used in non-hub-and-spoke environments are RIPv2, OSPF, IS-IS, and EIGRP. IPv6 uses specially developed versions of routing protocols, such as the following:

• IS-IS
• RIPng
• OSPFv3
• EIGRP for IPv6

Routing between ASs (from large corporations to the Internet, or between ISPs) is accomplished using special routing protocols called EGRPs. The most common EGRP for both IPv4 and IPv6 is the Border Gateway Protocol (BGP). Some companies have a very complex and large network infrastructure that spans worldwide, so they use BGP inside their network as their IGRP.

Large networks, including the Internet, are based on the AS concept. An AS defines a group of network devices under a common administration, and most often this defines a large organization or an ISP. Routing protocols can be classified based on different criteria. Depending on the zone in which they operate, they can be considered interior (inter-AS) routing protocols or exterior (intra-AS) routing protocols. Interior routing protocols can be further classified as distance vector routing protocols and link-state routing protocols, based on their behavior regarding the router update exchange process. Each routing protocol type will be covered in detail in the following sections, along with their respective design considerations.

Interior Routing Protocols

Interior routing protocols are configured on groups of routers from the same AS; thus, the routing activity never leaves the organization’s premises.

 

Figure 5.1 – Routing Protocols

Figure 5.1 above illustrates the different routing protocols available. An important aspect that must be considered when selecting the routing protocol is the difference between distance vector and link-state routing protocols. Link-state routing protocols were developed after distance vector routing protocols and they are much more sophisticated. A special category involves the hybrid routing protocols that feature the best attributes of distance vector and link-state technologies. The only hybrid routing protocol used in modern networks is EIGRP.

Distance vector routing protocols include:

• RIPv1
• RIPv2
• IGRP
• RIPng

Link-state routing protocols include:

• OSPF
• IS-IS
• OSPFv3

Distance Vector Routing Protocols

Distance vector routing is a property of certain routing protocols that build an internal picture of the topology by periodically exchanging full routing tables between the neighbor devices. The main difference between distance vector routing protocols and link-state routing protocols is the way they exchange routing updates. Distance vector routing protocols function using the “routing by rumor” technique, as every router relies on its neighbors to maintain correct routing information. This means the entire routing table is sent periodically to the neighbors, as illustrated in Figure 5.2 below:

 

Figure 5.2 – Distance Vector Routing Protocol Behavior

The most important advantage of distance vector routing protocols is that they are easy to implement and maintain. The downside is the convergence time. A converged network is a network in which every router has the same perspective of the topology. When a topology change occurs, the routers in the respective area propagate the new information to the rest of the network. Because this is done on a hop-by-hop basis (i.e., every router passes its fully updated routing information to each neighbor), network convergence is finally established after a significant amount of time has passed.

In addition to the downside of slow convergence, because full routing table exchanges occur between the routers, distance vector routing protocols are more bandwidth intensive than link-state routing protocols are. This happens especially in large networks, where routing tables can be of considerable size. Based on these aspects, distance vector routing protocols are recommended only in small Enterprise Network implementations.

An example of a distance vector routing protocol still used in modern networks is RIPv2 (described in RFC 2453). RIPv2 uses a hop count as the metric for path selection, with a maximum hop count of 15. RIPv2 updates are sent using multicast by default, although they can be configured as unicast or broadcast, and, unlike its predecessor (RIPv1), RIPv2 permits Variable Length Subnet Masking (VLSM) on the network.

Devices receive routing information from their neighbors and pass it on to other neighbors. RIP repeats this process every 30 seconds. The downside in this scenario is that when the network is stable and there are no changes in the topology, RIP still sends its routing table every 30 seconds, which is not very effective because it wastes bandwidth.

 

Note:    Although it is widely believed that all of the routing table information is exchanged between neighbors, actually only the best routes are exchanged through the routing updates. Alternate routes are not included in the routing update packets.

 

If a router that uses a distance vector routing protocol has inaccurate information, that information will propagate through the entire network. Distance vector routing protocols are prone to major problems, including routing loops.

Link-State Routing Protocols

Link-state routing protocols do not generally “route by rumor.” The routing devices exchange information about their link-states between them. Devices build a map of the network (i.e., they do not rely on a map of a particular node) independently and loop-free based on the link-state information each router generates and propagates to the other routers.

Unlike distance vector routing protocols, link-state routing protocols flood information about its links to a specific area or to all of the routers in a specific area. This way, every router in the topology has detailed knowledge of a specific area, unlike the routers using distance vector routing protocols, where only the best routes are exchanged between neighbors. The routing decisions are made by applying the Shortest Path First (SPF) or Dijkstra’s algorithm to the information received from various sources. The result of this calculation consists of the shortest path to each destination in the network.

 

Figure 5.3 – Link-State Routing Protocol Behavior

Figure 5.3 above illustrates link-state routing protocol behavior. This is a much more efficient approach to building routing databases, and there is no fixed updated timer like in the distance vector technologies case. Link-state protocols re-flood their entire routing information periodically to ensure that the network is properly converged.

Link-state routing protocols offer a series of important advantages compared to distance vector routing protocols. The most important advantage relates to the convergence factor. Convergence occurs much faster because as soon as a network topology changes, only that specific information is sent to the routers in a given area. The routing updates stop after all of the routers learn about the specific change, thus decreasing the need for bandwidth, unlike with distance vector routing protocols that periodically exchange routing tables, even if no topology change occurs. In link-state routing, updates are triggered only when a link-state changes somewhere in the network. Depending on the routing protocol used, this can mean a link going up or down or changing some of its parameters (e.g., bandwidth).

Examples of link-state routing protocols are OSPF (Open Shortest Path First), described in RFC 2328, and IS-IS (Intermediate System-to-Intermediate System), described in RFC 1142.

 

Note:    An interesting and special routing protocol is EIGRP (Enhanced Interior Gateway Routing Protocol), a Cisco proprietary protocol. It has both distance vector and link-state characteristics. It is also called a hybrid or an advanced distance vector routing protocol.

 

Exterior Routing Protocols

Exterior routing protocols run between ASs and the most common example is BGPv4. The main reason to use different types of routing protocols to carry routes outside of the AS boundaries is to exchange a large amount of route entries. In this regard, exterior routing protocols support special options and features that are used to implement various policies. The routing metrics for these kinds of protocols include more parameters than for interior routing protocols because of the need for flexible routing policies and choosing the best possible path.

While interior routing protocols are used within Enterprise Networks, BGP is typically used in ISP-to-ISP or ISP-to-Enterprise connections. Unlike intra-AS protocols that make routing decisions based exclusively on the metric value, the policies for inter-AS protocols can also include other factors, such as business decisions or possible AS vulnerabilities (e.g., monetary costs, preferred provider, non-secure provider, geographical traffic path, and others). These are technically implemented by configuring different BGP parameters.

 

A typical scenario in which the use of BGP is beneficial because of its flexible policy implementation is an organization that is connected to multiple ISPs (multi-homing). BGP can interconnect with any interior routing protocol used inside the Enterprise Network, so administrators have maximum flexibility when it comes to choosing a suitable interior routing protocol. A simple example of this scenario is presented in Figure 5.4 below:

 

 

Figure 5.4 – Enterprise Multi-Homing Scenario

 

Other Considerations for Routing Protocols

Another key parameter of routing protocols and a measure of their sophistication is whether they have a hierarchical or a flat behavior. IS-IS and OSPF and can be configured in a hierarchical manner and they offer improved scalability. For example, OSPF splits the topology into multiple areas and uses the Area 0 (backbone) concept, which connects to every other area in the topology. Routes can be summarized as they enter or leave the backbone, which leads to increased efficiency and bandwidth optimization. IGRP and RIP are examples of routing protocols that are based on a flat behavior because they are not optimized and they use a single structure, no matter how large the network is.

 

One task for the router is choosing the best way to get to a destination. If a router learns different paths to a destination from different protocols, the router must decide which prefix it should listen to. To make this decision it uses Administrative Distance (AD). Lower AD values are preferred over higher AD values, so, for example, OSPF routes (AD=110) will be preferred over RIP routes (AD=120). The AD value represents how trustworthy a particular routing protocol is. The most common AD values are summarized below:

 

 

The AD is the way a router selects a route based on one protocol over another, but something else that must be decided is the way in which the device will select a routing table entry over another entry from the same protocol. Routing protocol metrics are used to make this decision.

 

Different routing protocols use different metrics. RIP uses the hop count as a metric, selecting the best route based on the lowest number of routers it passed through. This is not very efficient because the shortest path can have a lower bandwidth than other paths. OSPF is more evolved and takes bandwidth into consideration, creating a metric called cost. Cost is directly generated from the bandwidth value, so a low bandwidth has a high cost and a high bandwidth has a low cost.

 

EIGRP is even more sophisticated and uses a composite metric, considering both bandwidth and delay values to create the metric value. BGP, the most sophisticated of all, uses many different attributes grouped in path vectors that can be used to calculate the best path.

 

Note:    One of the reasons RIP has a high AD value is that it uses the hop count metric, which is not very efficient in complex environments. The more sophisticated the metric calculation is, the lower the AD value assigned to different routing protocols.

Routing Problems and Avoidance Mechanisms

As mentioned, distance vector routing protocols are prone to major problems as a result of their simplistic “routing by rumor” approach. Distance vector and link-state routing protocols use different techniques to prevent routing problems. The most important mechanisms are as follows:

 

• Invalid timers: These are used to mark routes as unreachable when updates for those routes are not received for a long time.
• Hop-count limit: This parameter marks routes as unreachable when they are more than a predefined number of hops away. The hop-count limit for RIP is 15, as it is not usually used in large networks. Unreachable routes are not installed in the routing table as best routes. The hop-count limit prevents updates from looping in the network, just like the TTL field in the IP header.
• Triggered updates: This feature allows the update timer to be bypassed in the case of important updates. For example, the RIP 30-second timer can be ignored if a critical routing update must be propagated through the network.
• Hold down timers: If a metric for a particular route keeps getting worse, updates for that route will not be accepted for a delayed period.
• Asynchronous updates: These offer another safety mechanism that prevents the routers from flooding the entire routing information at the same time. As mentioned, OSPF does this every 30 minutes. The asynchronous updates mechanism generates a small delay for every device so they do not flood the information exactly at the same time. This improves bandwidth utilization and processing capabilities.
• Route poisoning: This prevents routers from sending packets through a route that has become invalid. Distance vector routing protocols use this to indicate that a route is no longer reachable. This is accomplished by setting the route metric to a maximum value.
• Split horizon: Split horizon prevents updates from being sent out of the same interface they came from because routers in that area should already know about that specific update.
• Poison reverse: This is an exception to the split horizon rule for the poisoned routes.