Path Determination
Summary
This topic explain how routers determine the best path. Start learning CCNA 200-301 for free right now!!
Note: Welcome: This topic is part of Module 14 of the Cisco CCNA 2 course, for a better follow up of the course you can go to the CCNA 2 section to guide you through an order.
Table of Contents
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.
Router Functions Example
The router uses its IP routing table to determine which path (route) to use to forward a packet. Click Play in the figure to follow a packet from the source PC to the destination PC. Watch how both R1 and R2 use their respective IP routing tables to first determine the best path, and then forward the packet.
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.
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 Address | Address in Binary |
|---|---|
| 172.16.0.10 | 10101100.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 |
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 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 |
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?
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.
Glossary: If you have doubts about any special term, you can consult this computer network dictionary.
Ready to go! Keep visiting our networking course blog, give Like to our fanpage; and you will find more tools and concepts that will make you a networking professional.
