Day 19. Basic Routing Concepts
CCNA 200-301 Exam Topics
Explain the role and function of network components
Determine how a router makes a forwarding decision by default
Key Topics
Today we review basic routing concepts, including exactly how a packet is processed by intermediary devices (routers) on its way from source to destination. We then review the basic routing methods, including connected, static, and dynamic routes. We conclude the day’s review with a deep dive into the operation of dynamic routing protocols.
Packet Forwarding
Packet forwarding by routers is accomplished through path determination and switching functions. The path determination function is the process the router use to determine which path to use when forwarding a packet. To determine the best path, the router searches its routing table for a network address that matches the packet’s destination IP address.
This search results in one of three path determinations:
Directly connected network: If the destination IP address of the packet belongs to a device on a network that is directly connected to one of the router’s interfaces, that packet is forwarded directly to that device. This means the destination IP address of the packet is a host address on the same network as this router’s interface.
Remote network: If the destination IP address of the packet belongs to a remote network, the packet is forwarded to another router. Remote networks can be reached only by forwarding packets to another router.
No route determined: If the destination IP address of the packet does not belong to a connected or remote network and the router does not have a default route, the packet is discarded. The router sends an Internet Control Message Protocol (ICMP) Unreachable message to the source IP address of the packet.
In the first two results, the router completes the process by switching the packet out the correct interface. It does this by reencapsulating the IP packet into the appropriate Layer 2 data-link frame format for the exit interface. The type of interface determines the type of Layer 2 encapsulation. For example, if the exit interface is Fast Ethernet, the packet is encapsulated in an Ethernet frame. If the exit interface is a serial interface configured for PPP, the IP packet is encapsulated in a PPP frame.
Path Determination and Switching Function Example
Let’s review the process of path determination and switching functions that routers perform as a packet travels from source to destination. Consider the topology in Figure 19-1 and the following steps:
Figure 19-1 Packet Forwarding Sample Topology
Step 1. PC1 has a packet to send to PC2. Using the AND operation on the destination’s IP address and PC1’s subnet mask, PC1 has determined that the IP source and IP destination addresses are on different networks. Therefore, PC1 checks its Address Resolution Protocol (ARP) table for the IP address of the default gateway and its associated MAC address. It then encapsulates the packet in an Ethernet header and forwards it to R1.
Step 2. Router R1 receives the Ethernet frame. Router R1 examines the destination MAC address, which matches the MAC address of the receiving interface, G0/0. R1 therefore copies the frame into its buffer to be processed.
R1 decapsulates the Ethernet frame and reads the destination IP address. Because it does not match any of R1’s directly connected networks, the router consults its routing table to route this packet.
R1 searches the routing table for a network address and subnet mask that include this packet’s destination IP address as a host address on that network. It selects the entry with the longest match (longest prefix). R1 encapsulates the packet in the appropriate frame format for the exit interface and switches the frame to the interface (G0/1 in this example). The interface then forwards it to the next hop.
Step 3. The packet arrives at router R2. R2 performs the same functions as R1, but this time, the exit interface is a serial interface—not Ethernet. Therefore, R2 encapsulates the packet in the appropriate frame format for the serial interface and sends it to R3. For this example, assume that the interface is using High-Level Data Link Control (HDLC), which uses the data-link address 0x8F. Remember that serial interfaces do not use MAC addresses.
Step 4. The packet arrives at R3. R3 decapsulates the data-link HDLC frame. The search of the routing table results in a network that is one of R3’s directly connected networks. Because the exit interface is a directly connected Ethernet network, R3 needs to resolve the destination IP address of the packet with a destination MAC address.
R3 searches for the packet’s destination IP address, 192.168.4.10, in its ARP cache. If the entry is not in the ARP cache, R3 sends an ARP request out its G0/0 interface.
PC2 sends back an ARP reply with its MAC address. R3 updates its ARP cache with an entry for 192.168.4.10 and the MAC address returned in the ARP reply.
The IP packet is encapsulated into a new data-link Ethernet frame and sent out R3’s G0/0 interface.
Step 5. The Ethernet frame with the encapsulated IP packet arrives at PC2. PC2 examines the destination MAC address, which matches the MAC address of the receiving interface—that is, its own Ethernet NIC. PC2 therefore copies the rest of the frame. PC2 sees that the Ethernet Type field is 0x800, which means that the Ethernet frame contains an IP packet in the data portion of the frame. PC2 decapsulates the Ethernet frame and passes the IP packet to its operating system’s IP process.
Routing Methods
A router can learn routes from three basic sources:
Directly connected routes: Automatically entered in the routing table when an interface is activated with an IP address
Static routes: Manually configured by the network administrator and entered in the routing table if the exit interface for the static route is active
Dynamic routes: Learned by the routers through sharing routes with other routers that use the same routing protocol
In many cases, the complexity of the network topology, the number of networks, and the need for the network to automatically adjust to changes require the use of a dynamic routing protocol. Dynamic routing certainly has several advantages over static routing; however, networks still use static routing. In fact, networks typically use a combination of static and dynamic routing.
Table 19-1 compares dynamic and static routing features. From this comparison, you can list the advantages of each routing method. The advantages of one method are the disadvantages of the other.
Table 19-1 Dynamic Versus Static Routing
Feature |
Dynamic Routing |
Static Routing |
Configuration complexity |
Generally remains independent of the network size |
Increases with network size |
Required administrator knowledge |
Requires advanced knowledge |
Requires no extra knowledge |
Topology changes |
Automatically adapts to topology changes |
Requires administrator intervention |
Scaling |
Suitable for simple and complex topologies |
Suitable for simple topologies |
Security |
Less secure |
More secure |
Resource usage |
Uses CPU, memory, and link bandwidth |
Requires no extra resources |
Predictability |
Uses a route that depends on the current topology |
Always uses the same route to the destination |
Classifying Dynamic Routing Protocols
Figure 19-2 shows a timeline of IP routing protocols, along with a chart to help you memorize the various ways to classify routing protocols.
Figure 19-2 Evolution and Classification of Routing Protocols
Routing protocols are classified into different groups according to their characteristics:
IGP or EGP
Distance vector or link state
Classful or classless
IGP and EGP
An autonomous system (AS) is a collection of routers under a common administration that presents a common, clearly defined routing policy to the Internet. Typical examples are a large company’s internal network and an ISP’s network. Most company networks are not autonomous systems; in most cases, a company network is a network within its ISP’s autonomous system. Because the Internet is based on the autonomous system concept, two types of routing protocols are required:
Interior gateway protocols (IGP): Used for intra-AS routing—that is, routing inside an AS
Exterior gateway protocols (EGP): Used for inter-AS routing—that is, routing between autonomous systems
Distance Vector Routing Protocols
Distance vector means that routes are advertised as vectors of distance and direction. Distance is defined in terms of a metric such as hop count, and direction is the next-hop router or exit interface. Distance vector protocols typically use the Bellman-Ford algorithm for the best-path route determination.
Some distance vector protocols periodically send complete routing tables to all connected neighbors. In large networks, these routing updates can become enormous, causing significant traffic on the links.
Although the Bellman-Ford algorithm eventually accumulates enough knowledge to maintain a database of reachable networks, the algorithm does not allow a router to know the exact topology of an internetwork. The router knows only the routing information received from its neighbors.
Distance vector protocols use routers as signposts along the path to the final destination. The only information a router knows about a remote network is the distance or metric to reach that network and which path or interface to use to get there. A distance vector routing protocol does not have a map of the network topology.
Distance vector protocols work best in these situations:
When the network is simple and flat and does not require a hierarchical design
When the administrators do not have enough knowledge to configure and troubleshoot link-state protocols
When specific types of networks, such as hub-and-spoke networks, are being implemented
When worst-case convergence times in a network are not a concern
Link-State Routing Protocols
In contrast to distance vector routing protocol operation, a router configured with a link-state routing protocol can create a complete view, or topology, of the network by gathering information from all the other routers. Think of a link-state routing protocol as having a complete map of the network topology. The signposts along the way from source to destination are not necessary because all link-state routers are using an identical map of the network. A link-state router uses the link-state information to create a topology map and to select the best path to each destination network in the topology.
With some distance vector routing protocols, routers periodically send updates of their routing information to their neighbors. Link-state routing protocols do not use periodic updates. After the network has converged, a link-state update is sent only when the topology changes.
Link-state protocols work best in these situations:
When the network design is hierarchical, which is typically the case in large networks
When the administrators have good knowledge of the implemented link-state routing protocol
When fast convergence of the network is crucial
Classful Routing Protocols
Classful routing protocols do not send subnet mask information in routing updates. The first routing protocols, such as Routing Information Protocol (RIP), were classful. When those protocols were created, network addresses were allocated based on class: Class A, B, or C. A routing protocol did not need to include the subnet mask in the routing update because the network mask could be determined based on the first octet of the network address.
Classful routing protocols can still be used in some of today’s networks, but because they do not include the subnet mask, they cannot be used in all situations. Classful routing protocols cannot be used when a network is subnetted using more than one subnet mask. In other words, classful routing protocols do not support variable-length subnet masking (VLSM).
Other limitations come into play with classful routing protocols, including their inability to support discontiguous networks and supernets. Classful routing protocols include Routing Information Protocol version 1 (RIPv1) and Interior Gateway Routing Protocol (IGRP). CCNA exam topics do not include either RIPv1 or IGRP.
Classless Routing Protocols
Classless routing protocols include the subnet mask with the network address in routing updates. Today’s networks are no longer allocated based on class, and the subnet mask cannot be determined by the value of the first octet. Classless routing protocols are required in most networks today because of their support for VLSM and discontiguous networks and supernets. Classless routing protocols include Routing Information Protocol version 2 (RIPv2), Enhanced IGRP (EIGRP), Open Shortest Path First (OSPF), Intermediate System-to-Intermediate System (IS-IS), and Border Gateway Protocol (BGP).
Dynamic Routing Metrics
In some cases, a routing protocol learns of more than one route to the same destination from the same routing source. To select the best path, the routing protocol must be capable of evaluating and differentiating among the available paths. A metric is used for this purpose. Two different routing protocols might choose different paths to the same destination because they use different metrics. Metrics used in IP routing protocols include the following:
RIP—Hop count: The best path is chosen by the route with the lowest hop count.
IGRP and EIGRP—Bandwidth, delay, reliability, and load: The best path is chosen by the route with the smallest composite metric value calculated from these multiple parameters. By default, only bandwidth and delay are used.
IS-IS and OSPF—Cost: The best path is chosen by the route with the lowest cost. The Cisco implementation of OSPF uses bandwidth to determine the cost.
The metric associated with a certain route can best be viewed using the show ip route command. The metric value is the second value in the brackets for a routing table entry. In Example 19-1. R2 has a route to the 192.168.8.0/24 network that is two hops away.
Example 19-1 Routing Table for R2
R2# show ip route
<output omitted>
Gateway of last resort is not set
R 192.168.1.0/24 [120/1] via 192.168.2.1, 00:00:20, Serial0/0/0
192.168.2.0/24 is variably subnetted, 2 subnets, 2 masks
C 192.168.2.0/24 is directly connected, Serial0/0/0
L 192.168.2.2/32 is directly connected, Serial0/0/0
192.168.3.0/24 is variably subnetted, 2 subnets, 2 masks
C 192.168.3.0/24 is directly connected, GigabitEthernet0/0
L 192.168.3.1/32 is directly connected, GigabitEthernet0/0
192.168.4.0/24 is variably subnetted, 2 subnets, 2 masks
C 192.168.4.0/24 is directly connected, Serial0/0/1
L 192.168.4.2/32 is directly connected, Serial0/0/1
R 192.168.5.0/24 [120/1] via 192.168.4.1, 00:00:25, Serial0/0/1
R 192.168.6.0/24 [120/1] via 192.168.2.1, 00:00:20, Serial0/0/0
[120/1] via 192.168.4.1, 00:00:25, Serial0/0/1
R 192.168.7.0/24 [120/1] via 192.168.4.1, 00:00:25, Serial0/0/1
R 192.168.8.0/24 [120/2] via 192.168.4.1, 00:00:25, Serial0/0/1
Notice in the output that one network, 192.168.6.0/24, has two routes. RIP will load balance between these equal-cost routes. All the other routing protocols are capable of automatically load balancing traffic for up to four equal-cost routes, by default. EIGRP is also capable of load balancing across unequal-cost paths.
Administrative Distance
Sometimes a router learns a route to a remote network from more than one routing source. For example, a static route might have been configured for the same network/subnet mask that was learned dynamically by a dynamic routing protocol, such as RIP. The router must choose which route to install.
Although it is less common, more than one dynamic routing protocol can be deployed in the same network. In some situations, it might be necessary to route the same network address using multiple routing protocols, such as RIP and OSPF. Because different routing protocols use different metrics—for example, RIP uses hop count and OSPF uses bandwidth—it is not possible to compare metrics to determine the best path.
Administrative distance (AD) defines the preference of a routing source. Each routing source—including specific routing protocols, static routes, and even directly connected networks—is prioritized in order of most preferable to least preferable, using an AD value. Cisco routers use the AD feature to select the best path when they learn about the same destination network from two or more different routing sources.
The AD value is an integer value from 0 to 255. The lower the value, the more preferred the route source. An administrative distance of 0 is the most preferred. Only a directly connected network has an AD of 0, which cannot be changed. An AD of 255 means the router will not believe the source of that route, and it will not be installed in the routing table.
In the routing table in Example 19-1. the AD value is the first value listed in the brackets. You can see that the AD value for RIP routes is 120. You can also verify the AD value with the show ip protocols command, as Example 19-2 demonstrates.
Example 19-2 Verifying the AD Value with the show ip protocols Command
R2# show ip protocols
Routing Protocol is "rip"
Outgoing update filter list for all interfaces is not set
Incoming update filter list for all interfaces is not set
Sending updates every 30 seconds, next due in 21 seconds
Invalid after 180 seconds, hold down 180, flushed after 240
Redistributing: rip
Default version control: send version 1, receive any version
Interface Send Recv Triggered RIP Key-chain
GigabitEthernet0/0 1 1 2
Serial0/0/0 1 1 2
Serial0/0/1 1 1 2
Automatic network summarization is in effect
Maximum path: 4
Routing for Networks:
192.168.2.0
192.168.3.0
192.168.4.0
Routing Information Sources:
Gateway Distance Last Update
192.168.2.1 120 00:00:01
192.168.4.1 120 00:00:01
Distance: (default is 120)
R2#
Table 19-2 shows the different administrative distance values for various routing protocols.
Table 19-2 Default Administrative Distances
Route Source |
AD |
Connected |
0 |
Static |
1 |
EIGRP summary route |
5 |
External BGP |
20 |
Internal EIGRP |
90 |
IGRP |
100 |
OSPF |
110 |
IS-IS |
115 |
RIP |
120 |
External EIGRP |
170 |
Internal BGP |
200 |
IGP Comparison Summary
Table 19-3 compares several features of the IGPs that are currently most popular: RIPv2, OSPF, and EIGRP.
Table 19-3 Comparing Features of IGPs: RIPv2, OSPF, and EIGRP
Features |
RIPv2 |
OSPF |
EIGRP |
Metric |
Hop count |
Bandwidth |
Function of bandwidth, delay |
Sends periodic updates |
Yes (30 seconds) |
No |
No |
Full or partial routing updates |
Full |
Partial |
Partial |
Where updates are sent |
(224.0.0.9) |
(224.0.0.5, 224.0.0.6) |
(224.0.0.10) |
Route considered unreachable |
16 hops |
Depends on MaxAge of LSA, which is never incremented past 3600 seconds |
A delay of all 1s |
Supports unequal-cost load balancing |
No |
No |
Yes |
Routing Loop Prevention
Without preventive measures, distance vector routing protocols can cause severe routing loops in a network. A routing loop is a condition in which a packet is continuously transmitted within a series of routers without ever reaching its intended destination network. A routing loop can occur when two or more routers have inaccurate routing information to a destination network.
Several mechanisms are available to eliminate routing loops, primarily with distance vector routing protocols. These mechanisms include the following:
A maximum metric to prevent count to infinity: To eventually stop the incrementing of a metric during a routing loop, infinity is defined by setting a maximum metric value. For example, RIP defines infinity as 16 hops, an unreachable metric. When the routers “count to infinity,” they mark the route as unreachable.
Hold-down timers: Routers are instructed to hold any changes that might affect routes for a specified period of time. If a route is identified as down or possibly down, any other information for that route containing the same status, or worse, is ignored for a predetermined amount of time (the hold-down period) so that the network has time to converge.
Split horizon: A routing loop is prevented by not allowing advertisements to be sent back through the interface where they originated. The split horizon rule stops a router from incrementing a metric and then sending the route back to its source.
Route poisoning or poison reverse: The route is marked as unreachable in a routing update that is sent to other routers. Unreachable is interpreted as a metric that is set to the maximum.
Triggered updates: A routing table update is sent immediately in response to a routing change. Triggered updates do not wait for update timers to expire. The detecting router immediately sends an update message to adjacent routers.
TTL field in the IP header: The Time To Live (TTL) field avoids a situation in which an undeliverable packet circulates endlessly on the network. With TTL, the source device of the packet sets the 8-bit field with a value. This TTL value is decreased by 1 by every router in the path until the packet reaches its destination. If the TTL value reaches 0 before the packet arrives at its destination, the packet is discarded, and the router sends an ICMP error message back to the source of the IP packet.
Link-State Routing Protocol Features
Just as distance vector protocols send routing updates to their neighbors, link-state protocols send link-state updates to neighboring routers, which then forward that information to their neighbors, and so on. Also as with distance vector protocols, at the end of the process, routers that use link-state protocols add the best routes to their routing tables, based on metrics. However, beyond this level of explanation, these two types of routing protocol algorithms have little in common.
Building the LSDB
Link-state routers flood detailed information about the internetwork to all the other routers so that every router has the same information about the internetwork. Routers use this link-state database (LSDB) to calculate the current best routes to each subnet.
OSPF, the most popular link-state IP routing protocol, advertises information in routing update messages of various types. The updates contain information called link-state advertisements (LSA).
Figure 19-3 shows the general idea of the flooding process. R8 is creating and flooding its router LSA. Note that Figure 19-3 shows only a subset of the information in R8’s router LSA.
Figure 19-3 Flooding LSAs Using a Link-State Routing Protocol
Figure 19-3 shows the basic flooding process. R8 is sending the original LSA for itself, and the other routers are flooding the LSA by forwarding it until every router has a copy.
After the LSA has been flooded, even if the LSAs do not change, link-state protocols require periodic reflooding of the LSAs by default every 30 minutes. However, if an LSA changes, the router immediately floods the changed LSA. For example, if Router R8’s LAN interface failed, R8 would need to reflood the R8 LSA, stating that the interface is now down.
Calculating the Dijkstra Algorithm
The flooding process alone does not cause a router to learn what routes to add to the IP routing table. Link-state protocols must then find and add routes to the IP routing table by using the Dijkstra shortest path first (SPF) algorithm.
The SPF algorithm is run on the LSDB to create the SPF tree. The LSDB holds all the information about all the possible routers and links. Each router must view itself as the starting point and each subnet as the destination, and it must use the SPF algorithm to build its own SPF tree to pick the best route to each subnet.
Figure 19-4 shows a graphical view of route possibilities from the results of the SPF algorithm run by router R1 when trying to find the best route to reach subnet 172.16.3.0/24 (based on Figure 19-3).
Figure 19-4 SPF Tree to Find R1’s Route to 172.16.3.0/24
To pick the best route, a router’s SPF algorithm adds the cost associated with each link between itself and the destination subnet over each possible route. Figure 19-4 shows the costs associated with each route beside the links. The dashed lines show the three routes R1 finds between itself and subnet X (172.16.3.0/24).
Table 19-4 lists the three routes shown in Figure 19-2, with their cumulative costs. You can see that R1’s best route to 172.16.3.0/24 starts by going through R5.
Table 19-4 Comparing R1’s Three Alternatives for the Route to 172.16.3.0/24
Route |
Location in Figure 19-2 |
Cumulative Cost |
R1–R7–R8 |
Left |
10 + 180 + 10 = 200 |
R1–R5–R6–R8 |
Middle |
20 + 30 + 40 + 10 = 100 |
R1-R2–R3–R4–R8 |
Right |
30 + 60 + 20 + 5 + 10 = 125 |
As a result of the SPF algorithm’s analysis of the LSDB, R1 adds to its routing table a route to subnet 172.16.3.0/24, with R5 as the next-hop router.
Convergence with Link-State Protocols
Remember that when an LSA changes, link-state protocols react swiftly, converging the network and using the current best routes as quickly as possible. For example, imagine that the link between R5 and R6 fails in the internetwork in Figures 25-3 and 25-4. R1 then uses the following process to switch to a different route:
Step 1. R5 and R6 flood LSAs, stating that their interfaces are now in a down state.
Step 2. All routers run the SPF algorithm again to see if any routes have changed.
Step 3. All routers replace routes, as needed, based on the results of SPF. For example, R1 changes its route for subnet X (172.16.3.0/24) to use R2 as the next-hop router.
These steps allow the link-state routing protocol to converge quickly—much more quickly than distance vector routing protocols.
Study Resources
For today’s exam topics, refer to the following resources for more study.
Resource |
Module or Chapter |
Introduction to Networks v7.0 |
8 |
Switching, Routing, and Wireless Essentials |
14 |
Enterprise Networking, Security, and Automation |
1 |
CCNA 200-301 Official Cert Guide, Volume 1 |
3 |