Routers

Overview

A router is a networking device that forwards data packets between computer networks, from one interface to another. It performs the "traffic directing" functions of network protocols, e.g. reading the network address information in a packet header to determine the ultimate destination.

Forwarding Table

When an IP datagram is received by a router, the router performs a lookup against its forwarding table to determine on what interface it should send the packet. The table is expected to contain at least the following information:

Destination. An N-bit value used for matching the result of the masking operation.
Mask. An N-bit value applied as a bitwise AND mask to the destination IP address of the datagram being looked up.
Gateway. The N-bit address of the next IP entity (router or host) to which the datagram should be sent.
Interface. An identifier used by the IP layer to reference the network interface that the datagram should be forwarded to.

IP forwarding persists the destination IP address but updates the lower-layer addresses (e.g. MAC addresses) on a per-hop basis.

Longest Prefix Match

Let $D$ be a destination IP address. An entry in the forwarding table is said to match if $(D \land m_{j}) = d_{j}$ , where $m_{j}$ and $d_{j}$ are the values of the mask and destination field respectively of the $j$ th entry.

The best matching entry is the one with the largest number of $1$ bits in its mask. This is the entry chosen for forwarding. This process is called the longest prefix match algorithm.

Route Aggregation

Using CIDR, one can reduce the number of forwarding table entries by route aggregation. This is the process of grouping numerically adjacent IP addresses behind an entry with a shorter common prefix.