Introduction

14.0.1

Why should I take this module?

Welcome to Routing Concepts!

No matter how effectively you set up your network, something will always stop working correctly, or even stop working completely. This is a simple truth about networking. So, even though you already know quite a bit about routing, you still need to know how your routers actually work. This knowledge is critical if you want to be able to troubleshoot your network. This module goes into detail about the workings of a router. Jump in!

14.0.2

What will I learn to do in this module?

Module Title: Routing Concepts

Module Objective: Explain how routers use information in packets to make forwarding decisions.

Table caption
Topic Title Topic Objective
Path Determination Explain how routers determine the best path.
Packet Forwarding Explain how routers forward packets to the destination.
Basic Router Configuration Review Configure basic settings on a router.
IP Routing Table Describe the structure of a routing table.
Static and Dynamic Routing Compare static and dynamic routing concepts.

Path Determination

14.1.1

Two Functions of Router

Before a router forwards a packet anywhere, it has to determine the best path for the packet to take. This topic explains how routers make this determination.

Ethernet switches are used to connect end devices and other intermediary devices, such as other Ethernet switches, to the same network. A router connects multiple networks, which means that it has multiple interfaces that each belong to a different IP network.

When a router receives an IP packet on one interface, it determines which interface to use to forward the packet to the destination. This is known as routing. The interface that the router uses to forward the packet may be the final destination, or it may be a network connected to another router that is used to reach the destination network. Each network that a router connects to typically requires a separate interface, but this may not always be the case.

The primary functions of a router are to determine the best path to forward packets based on the information in its routing table, and to forward packets toward their destination.

14.1.3

Best Path Equals Longest Match

What is meant by the router must determine the best path in the routing table? The best path in the routing table is also known as the longest match. The longest match is a process the router uses to find a match between the destination IP address of the packet and a routing entry in the routing table.

The routing table contains route entries consisting of a prefix (network address) and prefix length. For there to be a match between the destination IP address of a packet and a route in the routing table, a minimum number of far-left bits must match between the IP address of the packet and the route in the routing table. The prefix length of the route in the routing table is used to determine the minimum number of far-left bits that must match. Remember that an IP packet only contains the destination IP address and not the prefix length.

The longest match is the route in the routing table that has the greatest number of far-left matching bits with the destination IP address of the packet. The route with the greatest number of equivalent far-left bits, or the longest match, is always the preferred route.

Note: The term prefix length will be used to refer to the network portion of both IPv4 and IPv6 addresses.

14.1.4

IPv4 Address Longest Match Example

In the table, an IPv4 packet has the destination IPv4 address 172.16.0.10. The router has three route entries in its IPv4 routing table that match this packet: 172.16.0.0/12, 172.16.0.0/18, and 172.16.0.0/26. Of the three routes, 172.16.0.0/26 has the longest match and would be chosen to forward the packet. Remember, for any of these routes to be considered a match there must be at least the number of matching bits indicated by the subnet mask of the route.

Destination IPv4 AddressAddress in Binary172.16.0.1010101100.00010000.00000000.00001010
Destination IPv4 Address Address in Binary
172.16.0.10 10101100.00010000.00000000.00001010
Route EntryPrefix/Prefix LengthAddress in Binary1172.16.0.0/1210101100.00010000.00000000.000010102172.16.0.0/1810101100.00010000.00000000.000010103172.16.0.0/2610101100.00010000.00000000.00001010
Route Entry Prefix/Prefix Length Address in Binary
1 172.16.0.0/12 10101100.00010000.00000000.00001010
2 172.16.0.0/18 10101100.00010000.00000000.00001010
3 172.16.0.0/26 10101100.00010000.00000000.00001010
14.1.5

IPv6 Address Longest Match Example

In the table, an IPv6 packet has the destination IPv6 address 2001:db8:c000::99. This example shows three route entries, but only two of them are a valid match, with one of those being the longest match. The first two route entries have prefix lengths that have the required number of matching bits as indicated by the prefix length. The first route entry with a prefix length of /40 matches the 40 far-left bits in the IPv6 address. The second route entry has a prefix length of /48 and with all 48 bits matching the destination IPv6 address, and is the longest match. The third route entry is not a match because its /64 prefix requires 64 matching bits. For the prefix 2001:db8:c000:5555::/64 to be a match, the first 64 bits must the destination IPv6 address of the packet. Only the first 48 bits match, so this route entry is not considered a match.

For the destination IPv6 packet with the address 2001:db8:c000::99, consider the following three route entries:

Route EntryPrefix/Prefix LengthDoes it match?12001:db8:c000::/40Match of 40 bits22001:db8:c000::/48Match of 48 bits (longest match)32001:db8:c000:5555::/64Does not match 64 bits
Route Entry Prefix/Prefix Length Does it match?
1 2001:db8:c000::/40 Match of 40 bits
2 2001:db8:c000::/48 Match of 48 bits (longest match)
3 2001:db8:c000:5555::/64 Does not match 64 bits
14.1.6

Build the Routing Table

A routing table consists of prefixes and their prefix lengths. But how does the router learn about these networks? How does R1 in the figure populate its routing table?

The figure depicts three types of networks Directed Connected Network, Remote Network, and Default Route. Router1 (R1) is the directly connected network with two switches S1 and S2 connected to two PCs PC1 and PC2. Each switch is connected to router R1. R1 and Router2(R2) are connected directly via point to point connection. R2 is connected two two switches S# and S4 with each switch having a PC PC3 and P4 connected to them. R2 forms the remoted network. R2 has an additional remote connection to the ISP by a point to point connection which is the Internet connection. The number scheme for each device is dual stack IPv4 and IPv6 addressees.

Networks from the Perspective of R1

The networks in the topology are highlighted and labelled from the perspective of R1. All the IPv4 and IPv6 networks highlighted in yellow are directly connected networks. All the IPv4 and IPv6 networks highlighted in blue are remote networks.

Click each button for more information about the different ways a router learns routes.

Directly Connected Networks

Directly connected networks are networks that are configured on the active interfaces of a router. A directly connected network is added to the routing table when an interface is configured with an IP address and subnet mask (prefix length) and is active (up and up).

Remote Networks

Remote networks are networks that are not directly connected to the router. Routers learn about remote networks in two ways:

  • Static routes – Added to the routing table when a route is manually configured.
  • Dynamic routing protocols – Added to the routing table when routing protocols dynamically learn about the remote network. Dynamic routing protocols include Enhanced Interior Gateway Routing Protocol (EIGRP), Open Shortest Path First (OSPF), as well as several others.

Default Route

A default route specifies a next-hop router to use when the routing table does not contain a specific route that matches the destination IP address. The default route can be entered manually as a static route or learned automatically from a dynamic routing protocol.

A default route over IPv4 has a route entry of 0.0.0.0/0 and a default route over IPv6 has a route entry of ::/0. The /0 prefix length indicates that zero bits or no bits need to match the destination IP address for this route entry to be used. If there are no routes with a longer match, more than 0 bits, then the default route is used to forward the packet. The default route is sometimes referred to as a gateway of last resort.

14.1.7 Check Your Understanding – Path Determination

Packet Forwarding

14.2.1

Packet Forwarding Decision Process

Now that the router has determined the best path for a packet based on the longest match, it must determine how to encapsulate the packet and forward it out the correct egress interface.

The figure demonstrates how a router first determines the best path, and then forwards the packet.

The following steps describe the packet forwarding process shown in the figure:

  1. The data link frame with an encapsulated IP packet arrives on the ingress interface.
  2. The router examines the destination IP address in the packet header and consults its IP routing table.
  3. The router finds the longest matching prefix in the routing table.
  4. The router encapsulates the packet in a data link frame and forwards it out the egress interface. The destination could be a device connected to the network or a next-hop router.
  5. However, if there is no matching route entry the packet is dropped.

Click each button for a description of the three things a router can do with a packet after it has determined the best path.

Forwards the Packet to a Device on a Directly Connected Network

If the route entry indicates that the egress interface is a directly connected network, this means that the destination IP address of the packet belongs to a device on the directly connected network. Therefore, the packet can be forwarded directly to the destination device. The destination device is typically an end device on an Ethernet LAN, which means the packet must be encapsulated in an Ethernet frame.

To encapsulate the packet in the Ethernet frame, the router needs to determine the destination MAC address associated with the destination IP address of the packet. The process varies based on whether the packet is an IPv4 or IPv6 packet:

  • IPv4 packet – The router checks its ARP table for the destination IPv4 address and an associated Ethernet MAC address. If there is no match, the router sends an ARP Request. The destination device will return an ARP Reply with its MAC address. The router can now forward the IPv4 packet in an Ethernet frame with the proper destination MAC address.
  • IPv6 packet – The router checks its neighbor cache for the destination IPv6 address and an associated Ethernet MAC address. If there is no match, the router sends an ICMPv6 Neighbor Solicitation (NS) message. The destination device will return an ICMPv6 Neighbor Advertisement (NA) message with its MAC address. The router can now forward the IPv6 packet in an Ethernet frame with the proper destination MAC address.

Forwards the Packet to a Next-Hop Router

If the route entry indicates that the destination IP address is on a remote network, this means the destination IP address of the packet belongs to a device on network that is not directly connected. Therefore, the packet must be forwarded to another router, specifically a next-hop router. The next-hop address is indicated in the route entry.

If the forwarding router and the next-hop router are on an Ethernet network, a similar process (ARP and ICMPv6 Neighbor Discovery) will occur for determining the destination MAC address of the packet as described previously. The difference is that the router will search for the IP address of the next-hop router in its ARP table or neighbor cache, instead of the destination IP address of the packet.

Note: This process will vary for other types of Layer 2 networks.

Drops the Packet – No Match in Routing Table

If there is no match between the destination IP address and a prefix in the routing table, and if there is no default route, the packet will be dropped.

14.2.2

End-to-End Packet Forwarding

The primary responsibility of the packet forwarding function is to encapsulate packets in the appropriate data link frame type for the outgoing interface. For example, the data link frame format for a serial link could be Point-to-Point (PPP) protocol, High-Level Data Link Control (HDLC) protocol, or some other Layer 2 protocol.

Click each button and play the animations of PC1 sending a packet to PC2. Notice how the contents and format of the data link frame change at each hop.

PC1 Sends Packet to PC2

In the first animation, PC1 sends a packet to PC2. Since PC2 is on a different network, PC1 will forward the packet to its default gateway. PC1 will look in its ARP cache for the MAC address of the default gateway and add the indicated frame information.

Note: If an ARP entry does not exist in the ARP table for the default gateway of 192.168.1.1, PC1 sends an ARP request. Router R1 would then return an ARP reply with its MAC address.

R1 Forwards the Packet to PC2

R1 now forwards the packet to PC2. Because the exit interface is on an Ethernet network, R1 must resolve the next-hop IPv4 address with a destination MAC address using its ARP table. If an ARP entry does not exist in the ARP table for the next-hop interface of 192.168.2.2, R1 sends an ARP request. R2 would then return an ARP Reply.

R2 Forwards the Packet to R3

R2 now forwards the packet to R3. Because the exit interface is not an Ethernet network, R2 does not have to resolve the next-hop IPv4 address with a destination MAC address. When the interface is a point-to-point (P2P) serial connection, the router encapsulates the IPv4 packet into the proper data link frame format used by the exit interface (HDLC, PPP, etc.). Because there are no MAC addresses on serial interfaces, R2 sets the data link destination address to an equivalent of a broadcast.

R3 Forwards the Packet to PC2

R3 now forwards the packet to PC2. Because the destination IPv4 address is on a directly connected Ethernet network, R3 must resolve the destination IPv4 address of the packet with its associated MAC address. If the entry is not in the ARP table, R3 sends an ARP request out of its FastEthernet 0/0 interface. PC2 would then return an ARP reply with its MAC address.

14.2.3

Packet Forwarding Mechanisms

As mentioned previously, the primary responsibility of the packet forwarding function is to encapsulate packets in the appropriate data link frame type for the outgoing interface. The more efficiently a router can perform this task, the faster packets can be forwarded by the router. Routers support the following three packet forwarding mechanisms:

  • Process switching
  • Fast switching
  • Cisco Express Forwarding (CEF)

Assume that there is a traffic flow which consists of five packets. They are all going to the same destination. Click each button for more information about the packet forwarding mechanisms.

Process Switching

An older packet forwarding mechanism still available for Cisco routers. When a packet arrives on an interface, it is forwarded to the control plane where the CPU matches the destination address with an entry in its routing table, and then determines the exit interface and forwards the packet. It is important to understand that the router does this for every packet, even if the destination is the same for a stream of packets. This process-switching mechanism is very slow and is rarely implemented in modern networks. Contrast this with fast switching.

Fast Switching

Fast switching is another, older packet forwarding mechanism which was the successor to process switching. Fast switching uses a fast-switching cache to store next-hop information. When a packet arrives on an interface, it is forwarded to the control plane where the CPU searches for a match in the fast-switching cache. If it is not there, it is process-switched and forwarded to the exit interface. The flow information for the packet is also stored in the fast-switching cache. If another packet going to the same destination arrives on an interface, the next-hop information in the cache is re-used without CPU intervention.

With fast switching, notice how only the first packet of a flow is process-switched and added to the fast-switching cache. The next four packets are quickly processed based on the information in the fast-switching cache.

Cisco Express Forwarding (CEF)

CEF is the most recent and default Cisco IOS packet-forwarding mechanism. Like fast switching, CEF builds a Forwarding Information Base (FIB), and an adjacency table. However, the table entries are not packet-triggered like fast switching but change-triggered, such as when something changes in the network topology. Therefore, when a network has converged, the FIB and adjacency tables contain all the information that a router would have to consider when forwarding a packet. Cisco Express Forwarding is the fastest forwarding mechanism and the default on Cisco routers and multilayer switches.

CEF builds the FIB and adjacency tables after the network has converged. All five packets are quickly processed in the data plane.

The diagram is similar to Process Switching and Fast switching however the packets go thru a Forwarding Information Base(FIB) and Adjacency Table built by the CEF so that the Control plane does not have to intervene after a network has converged.