Routing Protocol Design – Routing Protocol Concepts

Before analyzing the details of each individual routing protocol, general information about IP routing will be presented first. Network designers should know the key characteristics of different routing protocols because they will be in a position to recommend specific routing protocols for different projects.

The first decision to make is whether you should use static or dynamic routing. Static routing involves manually defining routes on devices and dynamic routing involves the use of 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), useful in situations in which 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 routes can also be used in the form of floating static routes, meaning setting the AD (Administrative Distance) 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

Another important decision to make when choosing the routing protocol is whether you need an Interior Gateway Protocol (IGP) or an Exterior Gateway Protocol (EGP). When you are routing between the devices within the organization (i.e., Autonomous System), you can choose one of the many IPv4-based IGPs, such as the following:

• Routing Information Protocol version 1 (RIPv1)
• Routing Information Protocol version 2 (RIPv2)
• Open Shortest Path First (OSPF)
• Intermediate System to Intermediate System (IS-IS)
• Interior Gateway Routing Protocol (IGRP)
• Enhanced Interior Gateway Routing Protocol (EIGRP)
• On Demand Routing (ODR)

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 the following specially developed versions of these routing protocols:

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

Routing between autonomous systems (i.e., from large corporations to the Internet or between service providers) is accomplished using EGP, which is a special routing protocol. The most common EGP for both IPv4 and IPv6 is the Border Gateway Protocol (BGP). Some companies are very big and they span the entire globe, so they use BGP inside their network as their IGP.

Large networks, including the Internet, are based on the Autonomous System (AS) concept. An AS defines a group of network devices under a common administration, and most often, this defines a large company or a service provider. 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 classified further as distance vector protocols or link-state protocols, based on their behavior regarding the router update exchange process. Each routing protocol type will be covered in detail in subsequent sections, along with their respective design considerations.

Interior Routing Protocols

Interior routing protocols (i.e., IGP) are configured on groups of routers from the same AS; thus, the IGP routing activity never leaves the enterprise premises, as illustrated in Figure 7.1 below:

Figure 7.1 – Interior Routing Protocols 

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 protocols were developed after distance vector protocols, and they are much more sophisticated than distance vector protocols. A special category involves the hybrid routing protocols that feature the best elements of distance vector and link-state technologies. The only hybrid routing protocol used in modern networks is EIGRP.

Distance vector protocols include the following:

• RIPv1
• RIPv2
• IGRP
• RIPng

Link-state protocols include the following:

• 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 neighbor devices. The main difference between distance vector routing protocols and link-state routing protocols is the way they exchange routing updates. Distance vector protocols function using the “routing by rumor” technique, where every router relies on its neighbors to maintain correct routing information. This means the entire routing table is sent periodically to all neighbors, as illustrated in Figure 7.2 below:

Figure 7.2 – Distance Vector Routing Protocol Behavior

The most important advantage of distance vector routing protocols is they are easy to implement and maintain. The downside is mainly convergence times. A converged network is one 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. Considering this is done on a hop-by-hop basis (i.e., every router passes its fully updated routing information to each neighbor), network convergence will not be established until a significant amount of time has passed.

In addition to slow convergence times, distance vector protocols are also bandwidth-intensive, especially in large networks, where routing tables can be of considerable size. Considering these aspects, distance vector protocols are recommended only in small enterprise network implementations.

An example of a distance vector routing protocol still used in modern networks is RIPv2 (Routing Information Protocol described in RFC 2453). RIPv2 uses a metric – hop count – 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 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, as it wastes bandwidth.

Note:    Although it is generally believed that all routing table information is exchanged between neighbors during routing updates, only the best routes are actually exchanged, and alternate routes are not included in the routing update packets.

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

Link-State Routing Protocols

Link-state routing protocols do not “route by rumor”. Instead, the routing devices exchange information about their link-states between them. Devices build a map of the network independently and loop-free (i.e., they do not rely on a map of a particular node) 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 the routers in the network. This means that every router in the topology has detailed knowledge of the entire network, 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. This calculation results in the shortest path to each destination in the network, as illustrated in Figure 7.3 below:

Figure 7.3 – Link-State Routing Protocol Behavior

This is a much more efficient approach to building routing databases, and there is no fixed update timer such as with distance vector technologies. Link-state protocols re-flood their entire routing information every 30 minutes to ensure the network is properly converged.

Link-state protocols offer a series of important advantages compared to distance vector 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 the routers learn about the specific change, thus decreasing the need for bandwidth, unlike distance vector protocols, which 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 in use, this can mean a link going up/down or changing some of its parameters (e.g., bandwidth).

Examples of link-state routing protocols are OSPF, described in RFC 2328, and IS-IS, described in RFC 1142.

Note:    An interesting and special routing protocol is EIGRP, a Cisco proprietary protocol, which possesses both distance vector and link-state characteristics. EIGRP is also called a hybrid or an advanced distance vector routing protocol.

Exterior Routing Protocols

Exterior routing protocols operate as inter-ASs, and the most common example is BGPv4. The main reason for using different types of routing protocols to carry routes outside the AS boundaries is the need 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 IGP, for example, because of the crucial need for fast convergence and choosing the best possible path.

While IGP is used within enterprise-level networks, BGP is typically used in ISP-to-ISP or ISP-to-enterprise connections. Unlike intra-AS protocols that make routing decisions exclusively based on the metric value, inter-AS protocol policies can also include other factors, such as business decisions or possible AS vulnerabilities. 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 enterprise connecting to multiple ISPs (i.e., multihoming). 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 7.4 below:

Figure 7.4 – Enterprise Multihoming Scenario

Other Routing Protocol Considerations

Another key parameter of routing protocols and a measure of their sophistication is whether they have a hierarchical or flat behavior. IS-IS, OSPF, and EIGRP can be configured in a hierarchical manner, which offers 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 of the actions a router performs is deciding on the best way to get to a destination. If a router learns different paths to a destination from different protocols, the router must decide to which prefix it should listen. In order to make this decision, the router uses 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:

Using the AD is a way in which a router selects routing based on a particular protocol, but what also 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 came 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 metric that considers both bandwidth and delay values when creating 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. Among the different routing protocols, the more sophisticated the metric calculation is, the lower the AD value assigned.

Routing Problems and Avoidance Mechanisms

As mentioned before, distance vector routing protocols are prone to major problems due to their simplistic “routing by rumor” approach. Distance vector and link-state protocols use different techniques to prevent routing problems. The most important mechanisms include the following:

• Invalidation 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. Hop count limit prevents updates from looping in the network, as with 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 throughout the network.
• Hold down timers: If a metric for a particular route keeps getting worse, updates for that route are not accepted for a delayed period.
• Asynchronous updates: These represent another safety mechanism that prevents the routers from flooding the entire routing information at the same time by generating a small delay for every device. This improves bandwidth utilization and processing capabilities. As mentioned before, OSPF does this every 30 minutes.
• Route poisoning: This mechanism prevents routers from sending packets through a route that has become invalid. Distance vector protocols use this to indicate 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.