At the core of every router—from a humble home gateway to a carrier-class backbone router handling terabits of traffic—lies a critical data structure: the routing table. This table is the distilled wisdom of the routing process, encoding everything the router knows about how to reach any destination in the network.

When a packet arrives, the router doesn't engage in complex deliberation. It performs a rapid lookup in its routing table, finds the matching entry, and forwards the packet accordingly. This happens billions of times per second across the global Internet. The routing table's design directly impacts network performance, convergence speed, and operational simplicity.

Understanding routing tables is not academic—it's essential for every networking professional. Whether you're troubleshooting connectivity issues, capacity planning, or designing network architecture, you'll be reading, interpreting, and manipulating routing tables constantly.

A routing table (also called a Routing Information Base or RIB) is a data structure stored in a router's memory that contains entries for network destinations and information about how to reach them.

Formal Definition

A routing table is an ordered set of rules that maps destination network addresses to outgoing interfaces and next-hop addresses, enabling routers to determine the appropriate path for forwarding IP packets.

Core Purpose

The routing table answers one fundamental question:

"Given a destination IP address, where should I send the packet next?"

This question gets answered millions of times per second on busy routers. The routing table must be:

• Fast to query: Packet forwarding can't wait
• Complete: Must cover all reachable destinations
• Accurate: Must reflect current network topology
• Consistent: All paths must be loop-free

The Internet's Full Routing Table

The Internet's global routing table (full BGP table) is a remarkable data structure:

• IPv4 prefixes: ~950,000 routes (as of 2024)
• IPv6 prefixes: ~190,000 routes (and growing fast)
• Growth rate: ~5-10% per year
• Memory requirement: Several GB per router
• Routers carrying full table: Core/backbone routers at ISPs and IXPs

Not every router needs the full table. Most carry only local routes plus a default route pointing toward the Internet core. But core routers at Tier-1 ISPs must know about every publicly routable network.

Each entry in a routing table contains several fields that collectively describe how to reach a destination network. While exact formats vary by vendor and protocol, the core components are universal.

Essential Fields in a Routing Table Entry

Additional Fields (Protocol-Specific)

Beyond the core fields, routes may carry additional attributes:

Example: Complete Routing Entry

Destination:        172.16.0.0/16
Next-Hop:           10.1.1.2
Interface:          GigabitEthernet0/0
Protocol:           OSPF
Metric:             110
Admin Distance:     110
Age:                00:24:42
OSPF Area:          0
Route Type:         Intra-area (O)
Tag:                0

This entry tells the router:

• Packets destined for any address in 172.16.0.0/16 (172.16.0.0 - 172.16.255.255)
• Should be sent to 10.1.1.2 (the next-hop router)
• Via interface GigabitEthernet0/0
• Learned via OSPF with a cost of 110
• Has been stable for about 24 minutes

Modern routers actually maintain two distinct tables: the Routing Information Base (RIB) and the Forwarding Information Base (FIB). Understanding their relationship is crucial for advanced troubleshooting.

The Routing Information Base (RIB)

The RIB is the control plane table—the comprehensive database of all routing information:

• Contains ALL learned routes, including multiple paths to the same destination
• Maintained by the router's CPU/control processor
• Updated by routing protocols (OSPF, BGP, etc.)
• May contain routes that aren't actively used
• Size limited by available memory
• Queried during route selection, not during forwarding

The Selection Process

When the RIB contains multiple routes to the same destination:

1. Administrative Distance comparison: Routes from more trusted sources win
2. Metric comparison: Among routes from the same protocol, lowest metric wins
3. Best path installation: The winning route is copied to the FIB

Example Scenario

RIB Contents for 10.0.0.0/8:
┌────────────────────────────────────────────────────────────────┐
│ Source    │ AD   │ Metric  │ Next-Hop    │ Status             │
├────────────────────────────────────────────────────────────────┤
│ Static    │ 1    │ 0       │ 192.168.1.1 │ ★ Installed in FIB │
│ OSPF      │ 110  │ 100     │ 192.168.2.1 │ ✗ Not used        │
│ BGP       │ 20   │ 50      │ 192.168.3.1 │ ✗ Not used        │
└────────────────────────────────────────────────────────────────┘

FIB Entry for 10.0.0.0/8:
┌────────────────────────────────────────────────────────────────┐
│ Prefix     │ Next-Hop    │ Interface        │ Action          │
├────────────────────────────────────────────────────────────────┤
│ 10.0.0.0/8 │ 192.168.1.1 │ GigabitEthernet0 │ Forward         │
└────────────────────────────────────────────────────────────────┘

The static route wins (AD=1 < AD=20 < AD=110), so it's installed in the FIB. If the static route fails, the FIB is immediately updated with the BGP route (next lowest AD).

Let's examine how routing tables appear on actual network devices. Understanding output format is essential for troubleshooting.

Cisco IOS Routing Table Output

Router# show ip route
Codes: C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2
       * - candidate default

Gateway of last resort is 10.0.0.1 to network 0.0.0.0

     10.0.0.0/8 is variably subnetted, 4 subnets, 3 masks
C       10.1.1.0/24 is directly connected, GigabitEthernet0/0
L       10.1.1.1/32 is directly connected, GigabitEthernet0/0
O       10.2.0.0/16 [110/20] via 10.1.1.2, 00:05:23, GigabitEthernet0/0
S       10.3.0.0/16 [1/0] via 10.1.1.3

     172.16.0.0/16 is variably subnetted, 2 subnets, 2 masks
O IA    172.16.0.0/16 [110/30] via 10.1.1.2, 00:05:20, GigabitEthernet0/0
B       172.16.100.0/24 [20/0] via 192.168.1.1, 00:10:15

S*   0.0.0.0/0 [1/0] via 10.0.0.1

Decoding the Output

Let's break down the key elements:

Route Codes (First Letter):

• C = Directly Connected (interface on this router)
• L = Local (router's own interface IP, /32)
• S = Static (manually configured)
• O = OSPF (intra-area)
• O IA = OSPF Inter-Area
• B = BGP
• * = Candidate default route

Metric Format [AD/Metric]:

• [110/20] = Administrative Distance 110, OSPF cost 20
• [1/0] = Administrative Distance 1, Metric 0 (static route)
• [20/0] = Administrative Distance 20, BGP metric 0

Next-Hop and Interface:

• via 10.1.1.2 = Next-hop IP address
• GigabitEthernet0/0 = Outgoing interface

Age:

• 00:05:23 = Route has been stable for 5 minutes and 23 seconds

When a packet arrives, the router must quickly find the matching route. This lookup process is optimized for speed while maintaining correctness.

The Longest Prefix Match Algorithm

Routers don't simply find 'a' matching route—they find the most specific matching route. This is called Longest Prefix Match (LPM).

Why Longest Prefix?

Consider these routes:

0.0.0.0/0      → Internet (default)
10.0.0.0/8     → Corporate network
10.100.0.0/16  → Engineering division  
10.100.50.0/24 → Server farm
10.100.50.128/25 → Production servers

A packet to 10.100.50.200 matches ALL of these routes. Which should be used?

With LPM, the router selects 10.100.50.128/25 (prefix length 25) because it's the most specific match. The packet reaches the production servers, not the general corporate network.

Lookup Implementation

For high-speed forwarding, routers use specialized data structures:

1. TCAM (Ternary Content-Addressable Memory)

TCAM can look up any entry in a single clock cycle (O(1)). Each entry stores:

• Prefix pattern with wildcards (0, 1, or 'don't care')
• Mask indicating which bits matter
• Action (next-hop, interface, etc.)

TCAM enables wire-speed forwarding but is expensive and power-hungry.

2. Patricia Trie (Radix Tree)

A tree structure where each node represents a bit position. Software-based routers often use this approach:

                    Root
                   /    
                  0      1
                 / \    / 
               0   1  0    1
              ...  ...

Traversal time is O(prefix length), so at most 32 operations for IPv4, 128 for IPv6.

3. Multi-bit Trie

Looks at multiple bits per level, trading memory for speed. An 8-bit stride trie only needs 4 levels for IPv4.

Several types of routing table entries have special meanings and behaviors.

Connected Routes

When you configure an IP address on an interface, the router automatically creates a connected route for that network. This is fundamental—the router must know about networks directly attached to it.

Configuration:
  interface GigabitEthernet0/0
    ip address 192.168.1.1 255.255.255.0

Resulting routes:
  C    192.168.1.0/24 is directly connected, GigabitEthernet0/0
  L    192.168.1.1/32 is directly connected, GigabitEthernet0/0

Local Routes (/32 or /128)

The L entries represent the router's own IP addresses. These are /32 (IPv4) or /128 (IPv6) host routes that ensure traffic destined for the router itself is processed locally, not forwarded.

Null Routes for Route Aggregation

Null routes serve an important purpose in route aggregation:

Scenario: ISP advertises 198.51.100.0/22 to upstream
Actual customer allocations:
  198.51.100.0/24 - Customer A
  198.51.101.0/24 - Customer B
  198.51.102.0/24 - (unallocated)
  198.51.103.0/24 - Customer C

Problem: Traffic to 198.51.102.0/24 has no destination

Solution:
  ip route 198.51.100.0 255.255.252.0 Null0
  
This null route ensures:
1. The summary can be advertised (route exists in table)
2. Traffic to unallocated space is dropped locally
3. Rather than bouncing around the Internet

Routing tables aren't static—they're living documents that change constantly as the network evolves.

Route Lifecycle

Routes go through several states:

1. Learning: Route is received from a routing protocol or configured statically
2. Validation: Route is verified (next-hop reachable, interface up, etc.)
3. Installation: Route is added to RIB; best route installed in FIB
4. Active: Route is used for forwarding decisions
5. Update: Route attributes change (metric, path, etc.)
6. Withdrawal: Route is removed when no longer valid

Convergence

Convergence is the process of all routers agreeing on network topology after a change. During convergence:

• Packets may be dropped (no valid route)
• Packets may loop (inconsistent views)
• Packets may take suboptimal paths

Convergence time targets:

• Modern IGPs (OSPF, IS-IS): Sub-second to a few seconds
• BGP: Seconds to minutes (depends on configuration)
• RIP: 30-180 seconds (why it's rarely used)

Route Dampening

To prevent instability from flapping routes (repeatedly appearing/disappearing), BGP implements route dampening:

• Each flap accumulates a penalty
• When penalty exceeds threshold, route is suppressed
• Penalty decays over time
• Route unsuppressed when penalty drops below reuse threshold

This prevents a single unstable link from disrupting the global routing table.

We've explored the routing table in depth—the data structure that enables all routing decisions. Let's consolidate the key concepts:

What's Next

We've seen that routing entries point to 'next hops.' But what exactly is a next hop? How does a router determine the next hop for any destination? The next page examines the next hop concept in detail—the gateway that bridges your local network to remote destinations.