Tutorial 9

Intro

In PA5 you will implement the forwarding function of a router. You will extend the provided code (download PA5 on Prairielearn) to:

1. Given a collection of networks and interface numbers, construct a forwarding table
2. Perform the forwarding function for incoming IP datagrams, sending them out on the appropriate interface

Router Forwarding - Longest Prefix Match

With a router's forwarding table set up, it will use the longest prefix match rule to decide which interface to forward a given packet to.

Suppose a router has the above forwarding table, and a packet with destination IP address 115.8.107.64 arrives.

The router will check whether the IP address falls into the range of each network entry in the forwarding table, and then send it to the matching interface with the longest prefix.

As a student on a quiz - we can do this by manually checking whether the X prefix bits of the network and the given dest IP match. For example, the first network on the table has a prefix of 19 bits, so we check whether the first 19 bits of 115.8.96.0 and 115.8.107.64 match.

A router can do this easily by using the netmask. Recall the netmask is made by setting the first X prefix bits to 1, and the rest of the IP address to 0. The first network on the table has a prefix of 19 bits, so its netmask is 255.255.224.0. A computer/router can simply AND the network's IP with the netmask, and AND the dest IP with the netmask, and check whether these are equal.

In this case, the address 115.8.107.64 falls in the range 115.8.96.0/19, 115.8.104.0/21, 115.8.104.0/22. 22 is the longest prefix, so the packet is forwarded to interface G.