Routing is the process of determining where to send data packets that are destined for addresses outside the local network. Routers gather and maintain routing information to enable the transmission and receipt of these data packets. Routing information takes the form of entries in a routing table, with one entry for each identified route. The router can use a routing protocol to create and maintain the routing table dynamically so that network changes can be accommodated whenever they occur.
It is important to understand dynamic routing and how the various types of routing protocols, such as distance vector and link-state, determine IP routes. It is equally important to understand scalability and convergence constraints with routing protocols.
Classless routing protocols, such as Routing Information Protocol version 2 (RIPv2), Enhanced Interior Gateway Routing Protocol (EIGRP), and Open Shortest Path First (OSPF) scale better than classful routing protocols because they support variable-length subnet masks (VLSM) and route summarization.
To effectively manage an IP network, you must understand the operation of dynamic routing protocols and the impact that they have on an IP network. This chapter describes the operation and limitations of distance vector and link-state routing protocols.
Chapter Objectives
Upon completing this chapter, you will be able to describe the application and limitations of dynamic routing for a medium-sized routed network. This ability includes being able to meet these objectives:
Describe the purpose and types of dynamic routing protocols
Describe the operation and implementation of distance vector routing protocols
Describe the operation and implementation of link-state routing protocols
Reviewing Dynamic Routing
Routers can forward packets over static routes or dynamic routes, based on the router configuration. There are two ways to tell the router how to forward packets to networks that are not directly connected:
Static: The router learns routes when an administrator manually configures the static route. The administrator must manually update this static route entry whenever an internetwork topology change requires an update. Static routes are user-defined routes that specify the path that packets take when moving between a source and a destination. These administrator-defined routes enable precise control over the routing behavior of the IP internetwork.
Dynamic: The router dynamically learns routes after an administrator configures a routing protocol that helps determine routes. Unlike the situation with static routes, after the network administrator enables dynamic routing, the routing process automatically updates route knowledge whenever new topology information is received. The router learns and maintains routes to the remote destinations by exchanging routing updates with other routers in the internetwork.
Dynamic routing relies on a routing protocol to disseminate knowledge. A routing protocol defines the rules that a router uses when it communicates with neighboring routers to determine paths to remote networks and maintains those networks in the routing tables. Figure 3-1 illustrates that a router in the network can have knowledge of networks that are not directly connected to an interface on that device. These routes must be configured statically or learned via routing protocols.
Routing Protocols
The following are the differences between a routed protocol and a routing protocol:
Routed protocol: Any network protocol that provides enough information in its network layer address to enable a packet to be forwarded from one host to another host based on the addressing scheme, without knowing the entire path from source to destination. Packets generally are conveyed from end system to end system. IP is an example of a routed protocol.
Routing protocol: Facilitates the exchange of routing information between networks, enabling routers to build routing tables dynamically. Traditional IP routing stays simple because it uses next-hop (next-router) routing, in which the router needs to consider only where it sends the packet and does not need to consider the subsequent path of the packet on the remaining hops (routers). Routing Information Protocol (RIP) is an example of a routing protocol.
Routing protocols describe the following information:
How updates are conveyed
What knowledge is conveyed
When to convey the knowledge
How to locate recipients of the updates
You can classify dynamic routing protocols using many different methods. One method to classify a routing protocol is to determine if it is used to route in an autonomous system or between autonomous systems. An autonomous system is a collection of networks under a common administration that share a common routing strategy.
There are two types of routing protocols:
Interior Gateway Protocols (IGP): These routing protocols exchange routing information within an autonomous system. Routing Information Protocol version 2 (RIPv2), Enhanced Interior Gateway Routing (EIGRP), and Open Shortest Path First (OSPF) are examples of IGPs.
Exterior Gateway Protocols (EGP): These routing protocols are used to route between autonomous systems. Border Gateway Protocol (BGP) is the EGP of choice in networks today.
Figure 3-2 shows the logical separation of where an IGP operates and where an EGP operates.
IGP Versus EGP
Note - The Internet Assigned Numbers Authority (IANA) assigns autonomous system numbers for many jurisdictions. Use of IANA numbering is required if your organization plans to use BGP. However, it is good practice to be aware of private versus public autonomous system numbering schema.
Within an autonomous system, most IGP routing can be further classified as conforming to one of the following algorithms:
Distance vector: The distance vector routing approach determines the direction (vector) and distance (such as hops) to any link in the internetwork.
Link-state: The link-state approach, which utilizes the shortest path first (SPF) algorithm, creates an abstraction of the exact topology of the entire internetwork, or at least of the partition in which the router is situated.
Advanced distance vector: The advanced distance vector approach combines aspects of the link-state and distance vector algorithms. This is also sometimes referred to as a hybrid routing protocol.
There is no single best routing algorithm for all internetworks. All routing protocols provide the information differently.
Multiple routes to a destination can exist. When a routing protocol algorithm updates the routing table, the primary objective of the algorithm is to determine the best route to include in the table. Each distance vector routing protocol uses a different routing metric to determine the best route. The algorithm generates a number called the metric value for each path through the network. With the exception of BGP, the smaller the metric, the better the path.
Metrics can be calculated based on a single characteristic of a path. More complex metrics can be calculated by combining several path characteristics. The metrics that routing protocols most commonly use are as follows:
Hop count: The number of times that a packet passes through the output port of one router
Bandwidth: The data capacity of a link; for instance, normally, a 10-Mbps Ethernet link is preferable to a 64-kbps leased line
Delay: The length of time that is required to move a packet from source to destination
Load: The amount of activity on a network resource, such as a router or link
Reliability: Usually refers to the bit error rate of each network link
Cost: A configurable value that on Cisco routers is based by default on the bandwidth of the interface
Figure 3-3 shows an example of multiple routes between two hosts and the way different routing protocols compute metrics.
Multiple routing protocols and static routes can be used at the same time. If there are several sources for routing information, an administrative distance value is used to rate the trustworthiness of each routing information source. By specifying administrative distance values, Cisco IOS Software can discriminate between sources of routing information.
An administrative distance is an integer from 0 to 255. A routing protocol with a lower administrative distance is more trustworthy than one with a higher administrative distance. As shown in Figure 3-4, if Router A receives a route to network 172.16.0.0 advertised by EIGRP and by OSPF at the same time, Router A would use the administrative distance to determine that EIGRP is more trustworthy.
Routing Protocol Metrics
Administrative Distance
Router A would then add the EIGRP route to the routing table because EIGRP is a more trusted routing source than OSPF. The administrative distance is an arbitrary value that Cisco IOS sets to handle cases when multiple routing protocols send information about the same routes. Table 3-1 shows the default administrative distance for selected routing information sources.
Table 3-1 Default Administrative Distance Values
Route Source | Default Distance |
Connected network | 0 |
Static route | 1 |
EIGRP | 90 |
OSPF | 110 |
RIPv2 | 120 |
External EIGRP | 170 |
Unknown or unbelievable | 255 (will not be added to the routing table to pass traffic) |
If nondefault values are necessary, you can use Cisco IOS Software to configure administrative distance values on a per-router, per-protocol, and per-route basis.
Understanding Distance Vector Routing Protocols
Distance vector–based routing algorithms (also known as Bellman-Ford-Moore algorithms) pass periodic copies of a routing table from router to router and accumulate distance vectors. (Distance means how far, and vector means in which direction.) Regular updates between routers communicate topology changes.
Each router receives a routing table from its direct neighbor. For example, in Figure 3-5, Router B receives information from Router A. Router B adds a distance vector metric (such as the number of hops), increasing the distance vector. It then passes the routing table to its other neighbor, Router C. This same step-by-step process occurs in all directions between direct-neighbor routers. (This is also known as routing by rumor.)
Distance Vector Protocols
In this way, the algorithm accumulates network distances so that it can maintain a database of internetwork topology information. Distance vector algorithms do not allow a router to know the exact topology of an internetwork.
Route Discovery, Selection, and Maintenance
In Figure 3-6, the interface to each directly connected network is shown as having a distance of 0.
Routing Information Sources
As the distance vector network discovery process proceeds, routers discover the best path to nondirectly connected destination networks based on accumulated metrics from each neighbor.
For example, Router A learns about other networks based on information it receives from Router B. Each of these other network entries in the routing table has an accumulated distance vector to show how far away that network is in the given direction.
When the topology in a distance vector protocol internetwork changes, routing table updates must occur. As with the network discovery process, topology change updates proceed step by step from router to router.
Distance vector algorithms call for each router to send its entire routing table to each of its adjacent or directly connected neighbors. Distance vector routing tables include information about the total path cost (defined by its metric) and the logical address of the first router on the path to each network it knows about.
When a router receives an update from a neighboring router, it compares the update to its own routing table. The router adds the cost of reaching the neighboring router to the path cost reported by the neighbor to establish the new metric. If the router learns about a better route (smaller total metric) to a network from its neighbor, the router updates its own routing table.
For example, if Router B in Figure 3-7 is one unit of cost from Router A, Router B would add 1 to all costs reported by Router A when Router B runs the distance vector processes to update its routing table. This would be maintained by the routers exchanging routing information in a timely manner through some update mechanism.
Maintaining Routes
Routing Loops
When you are maintaining the routing information, routing loops can occur if the slow convergence of the internetwork after a topology change causes inconsistent routing entries. The example presented in the next few pages uses a simple network design to convey the concepts. Later in this chapter, you look at how routing loops occur and are corrected in more complex network designs. Figure 3-8 illustrates how each node maintains the distance from itself to each possible destination network.
Maintaining Distance
Just before the failure of network 10.4.0.0, shown in Figure 3-9, all routers had consistent knowledge and correct routing tables. The network is said to have converged. For this example, the cost function is hop count, so the cost of each link is 1. Router C is directly connected to network 10.4.0.0, with a distance of 0. The path of Router A to network 10.4.0.0 is through Router B, with a hop count of 2.
Slow Convergence Produces Inconsistent Routing