The routing table is comprehensive but complex. It contains policy information, backup routes, and protocol-specific attributes—details essential for routing decisions but unnecessary (and too slow to query) for per-packet forwarding.

Enter the forwarding table (also known as the Forwarding Information Base or FIB). This is the streamlined, speed-optimized derivative of the routing table, designed for one purpose: looking up the next-hop for packets as fast as physically possible.

A forwarding table (Forwarding Information Base or FIB) is a data structure optimized for fast lookup that contains the essential information needed to forward packets: destination prefix, output interface, and next-hop (often pre-resolved to MAC address).

Formal Definition:

A forwarding table is a hardware-optimized data structure derived from the routing table that maps destination prefixes to forwarding actions, enabling per-packet lookup at line rate.

Key Characteristics:

1. Derived from RIB: Contains only the 'best' routes selected by the routing process
2. Minimal information: Stripped of policy and backup data—only what's needed for forwarding
3. Hardware-resident: Often stored in specialized memory (TCAM, SRAM) for fast access
4. Distributed: Replicated to each line card in distributed forwarding architectures

A FIB entry is stripped down to the essentials—everything needed to forward a packet, nothing more:

Core FIB Entry Fields:

Understanding Adjacencies:

The adjacency table is a companion to the FIB. While the FIB entry says 'send to next-hop 10.0.0.2 via Gig0/0,' the adjacency entry contains the actual Layer 2 encapsulation—destination MAC address, source MAC, ethertype, and any required VLAN tags.

By pre-computing this encapsulation, the router avoids per-packet ARP lookups. The forwarding engine simply:

1. Matches destination IP to FIB entry
2. Follows adjacency pointer
3. Prepends pre-built L2 header
4. Sends out the specified interface

This is how nanosecond-class forwarding becomes possible.

The FIB must perform longest-prefix match (LPM) for every packet at line rate. Various algorithms and data structures have been developed to achieve this:

1. Binary Tries (Patricia Tries)

A trie (retrieval tree) where each bit of the IP address determines the path through the tree. For every bit position, go left for 0, right for 1. The deepest node reached with a valid prefix is the match.

• Pros: Simple, deterministic, easy to update
• Cons: Deep trees (32 levels for IPv4, 128 for IPv6), one memory access per bit
• Optimization: Path compression (Patricia) skips unique paths

2. Multi-Bit Tries

Process multiple bits per step (e.g., 8 bits), creating a tree with higher fanout but fewer levels.

• Pros: Fewer memory accesses (4 for IPv4 with 8-bit strides)
• Cons: Higher memory usage (each node has up to 256 children)
• Optimization: Level compression for sparse trees

3. TCAM (Ternary Content-Addressable Memory)

Specialized hardware that searches all entries in parallel. Each entry can match 0, 1, or 'don't care' for each bit—perfect for prefix matching.

Hybrid Approaches:

Modern routers often combine techniques:

• Use TCAM for the first N bits (fast initial lookup)
• Fall back to trie for remaining bits (handles specificity)
• Cache frequent lookups in fast memory
• Use algorithmic optimization (Luleå algorithm, tree bitmap)

The Bottom Line: The choice of FIB data structure directly determines forwarding performance. This is why router architecture is a specialized discipline—general-purpose computing cannot match purpose-built forwarding hardware.

The FIB must accurately reflect the routing table's best routes. When routing changes occur, the FIB must be updated to match. This process has several stages:

FIB Population Flow:

Synchronization Challenges:

1. Delay Between RIB and FIB: There's inherent delay between a route appearing in the RIB and being installed in hardware FIB. During this window, packets may be forwarded incorrectly.

2. Batch Updates: To reduce overhead, FIB managers often batch multiple updates together. This improves efficiency but increases latency for individual updates.

3. TCAM Fragmentation: Deleting routes can leave holes in TCAM. Over time, these require compaction (moving entries), which can be disruptive.

4. Capacity Limits: If the FIB hardware fills up, new routes cannot be installed. This is a serious failure mode requiring careful capacity planning.

High-performance routers implement the FIB in specialized hardware. Understanding this hardware is essential for capacity planning and performance analysis:

TCAM (Ternary Content-Addressable Memory)

TCAM is the dominant technology for line-rate FIB lookup. Unlike regular CAM (which matches exact values), TCAM allows 'don't care' bits—essential for prefix matching.

How TCAM works:

1. Search key (destination IP) is broadcast to all entries simultaneously
2. Each entry compares the key against its pattern (0, 1, or don't care for each bit)
3. All matching entries signal their match in one clock cycle
4. Priority encoder selects the first (highest priority) match
5. Entries are ordered by prefix length (longest first) for LPM semantics

TCAM Capacity Considerations:

TCAM is expensive, power-hungry, and heat-generating. A typical high-end router might have:

• 1-4 million entry TCAM capacity
• Each entry: 40-80 bits (IPv4) or 144-160 bits (IPv6)
• Power: 15-20 watts per Mbit of TCAM
• Multiple TCAMs in parallel for different lookup tables (IPv4, IPv6, ACL, QoS)

When TCAM fills up:

• New routes cannot be installed
• Routes may be aggregated or dropped
• Existing routes remain but no new ones accepted
• This is a hard failure—careful capacity planning is essential

Cisco Express Forwarding (CEF) is a widely deployed example of FIB-based forwarding. Studying CEF illustrates practical FIB implementation:

CEF Components:

1. FIB Table: The actual forwarding table, a modified radix tree optimized for fast lookup. Contains prefix-to-adjacency mappings.

2. Adjacency Table: Contains L2 rewrite information (MAC addresses, encapsulation). Linked from FIB entries.

3. Software CEF (dCEF): FIB maintained in software on the route processor. Suitable for low-end routers.

4. Hardware CEF (distributed CEF): FIB replicated to line card hardware. Each line card forwards independently.

CEF Adjacency Types:

Software-Defined Networking (SDN) introduces a new paradigm for FIB management. Instead of routing protocols populating the FIB, a centralized controller programs forwarding tables directly:

Traditional vs. SDN Forwarding:

Traditional:

• Routing protocols run on the router
• RIB computed locally from protocol exchanges
• FIB derived from local RIB
• Distributed control, local decision-making

SDN:

• Controller maintains global network view
• Computes paths centrally
• Programs FIB entries via OpenFlow or P4
• Centralized control, switches are 'dumb' data plane

OpenFlow and Flow Tables:

OpenFlow extends the forwarding table concept to 'flow tables' with richer matching:

• Match on any header field (not just destination IP)
• Multiple tables in a pipeline (match-action chains)
• Programmable actions: forward, drop, modify, meter
• Statistics per-flow for traffic visibility

P4 (Programming Protocol-Independent Packet Processors):

P4 goes further, allowing the packet parser and match-action pipeline itself to be programmed:

• Define custom headers and protocols
• Specify match fields at compile time
• Maximum flexibility but requires specialized hardware

Implications:

SDN and programmable data planes blur the line between RIB and FIB. The 'routing table' may be an abstraction maintained by the controller, with flow rules pushed directly to hardware tables that don't resemble traditional FIBs.

We've explored the forwarding table as the hardware-optimized structure that enables line-rate packet forwarding. Let's consolidate the key concepts: