Path Determination

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.

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?

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