Path Determination Routing CCNA
Path Determination Routing CCNA

Path Determination

Path Determination
5

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.

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.

Router Functions Example
Router Functions Example

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

Networks from the Perspective of R1
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 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 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.

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.

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.

More Goodies
Small Network Applications and Protocols
Small Network Applications and Protocols