Technology - IP Routing & Addressing Crisis 2 - Forwarding Information Base


We discuss the three major Forwarding Information Base (FIB) techniques by which a router can classify incoming packets to decide which of its interfaces to forward the packet on: Ternary Content-Addressable Memory (TCAM), Tree-Bitmap and similar algorithms and direct memory lookup. The FIB and RIB tasks of routers are the fundamental determinants of Internet routing system scalability.

Table of Contents

  • 1. Synopsis
  • 2. Forwarding Information Base (FIB) rules
    • 2.1 Three techniques
  • 3. Costs and limitations of three FIB technologies
    • 3.1 TCAM
      • 3.1.1 Content Addressable Memory
      • 3.1.2 Limited number of rules
      • 3.1.3 High, low and don’t care comparison
      • 3.1.4 Priority encoding
      • 3.1.5 Pipelined SRAM chip
      • 3.1.6 Output interfaces and queues
      • 3.1.7 Power-hungry and hot
      • 3.1.8 Impossible to upgrade
      • 3.1.9 Slow updates
      • 3.1.10 Rules on bit-boundaries
      • 3.1.11 Route aggregation and FIB optimisation
    • 3.2 Tree-Bitmap and other trie-based algorithms
      • 3.2.1 4 or more bits of address per memory access
      • 3.2.2 Trading off memory usage for speed
      • 3.2.3 CRS-1 implementation
    • 3.3 Direct memory lookup
      • 3.3.1 DRAM and SRAM cycle times
      • 3.3.2 24 bit FIB rules
  • 4. The ideal of ‘flat routing’
    • 4.1 Difficulties with the control plane
    • 4.2 Flat routing to 256 IP address granularity
  • 5. Related reports

Related Reports

Purchase this Report


Licence Information

Focus Report Profile


Telecoms Infrastructure

Number of pages 15

Status Archived

Last updated 12 Dec 2007
Update History

Analyst: Robin Whittle

Share this Report

Purchase with Confidence

This is all fascinating and your way of presenting the information is extraordinary.

Gary Sorkin, Pacific Communication Group

Special Offers

Caribbean - Telecoms, Mobile, and Broadband - Statistics and Analyses
US$795.00 until 30 Oct 2019
(normal price US$1,590.00)

Venezuela - Telecoms, Mobile and Broadband - Statistics and Analyses
US$575.00 until 30 Oct 2019
(normal price US$1,150.00)

Sample Reports

A selection of downloadable samples from our Annual Publications catalogue.

Download a Sample Report

More than 4,000 customers from 140 countries utilise BuddeComm Research

Are you interested in BuddeComm's Custom Research Service?

News & Views

Have the latest telecommunications industry news delivered to your inbox by subscribing to Paul's FREE weekly News & Views.