Router

The router is a hardware component critical to computer networking. It has two functions: to examine the header fields in all IP datagrams passing through it, and to move datagrams from input ports to output ports to transfer datagrams along an end-to-end path.

Architecture

A high-level router architecture is below. The input port takes incoming data from a physical connection.

• The line termination functionality refers to bit-level reception in the physical layer.
• Then, the data is processed according to the link layer protocol (i.e., Ethernet).
• Then, there is functionality for the network layer.
  • There’s decentralised switching, i.e., using header field values, the output port is looked-up in the input port memory.
    • Destination-based forwarding is based only on the destination IP address.
    • Generalised forwarding forwards based on any set of header field values.
  • If datagrams arrive faster than the forwarding rate, then we get input port queueing. The forwarding table (or routing table) functions as a look-up table. Given the bit composition of the address, this determines which link interface the packet is forwarded to.

The switching fabric is a special piece of hardware that serves to transfer datagrams from the input port to the specified output port.

The output port is the analogue of the input port. See buffer management and scheduling.

Queueing

If the switching fabric than the input ports combined, then queueing may occur at input queues. This causes queueing delay and loss due to input buffer overflow. Another phenomenon is head-of-the-line (HOL) blocking. This happens when a queued datagram at the front of the queue prevents others in the queue from moving forward. At the output port, buffering is required when datagrams arrive from the fabric faster than the link transmission rate. The switch fabric may deliver datagrams at a rate of $NR$ ($N$: number of inputs, $R$: transmission rate).

• A packet drop policy is needed to determine which datagrams should be dropped if there are no free buffers (or congestion).
• A scheduling mechanism chooses among queued datagrams for transmission. Priority scheduling determines who gets the best performance.

In general, the average buffering (RFC 3439) is equal to the equal RTT times the link capacity $C$. More recent research suggests:

$$\frac{\text{RTT}\times C}{\sqrt{N}}$$

Too much buffering can cause longer RTT (poorer performance for real-time apps, sluggish TCP responses). We need to find the right amount to keep bottleneck link just full enough but not such that it gets slow.

See also

• Ethernet switch, the link-layer analogue that stores and forwards Ethernet frames