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

Synopsis

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