Routing Table Size Calculator
Calculate routing table memory footprint from route count and kernel FIB entry size.
About Routing Table Size Calculator
The Linux kernel's IPv4 routing table (FIB) uses an LC-trie (level-compressed trie) structure that supports lookup in roughly O(log n) time relative to the number of routes — a significant improvement over a naive linear scan, which is what makes full-Internet-scale routing tables (800,000+ IPv4 routes) practically searchable in nanoseconds per lookup. Memory usage scales roughly linearly with route count, with per-route overhead depending on kernel version and how many route attributes (metrics, next-hops, source-specific routing) each entry carries.
Formula
Table memory and lookup complexity
memory ≈ routes × bytes_per_route; lookup_time ∝ log2(routes)
- R
- number of routes
- b
- bytes per route
Worked example
With the default values below, Routing Table Size Calculator returns Estimated Routing Table Memory (MB) of 6.104. Change any input above and every figure here is recalculated in your browser.
Inputs used
- Number of Routesminimum 1
- 50,000
- Memory per Route (bytes)minimum 1
- 128
Results
- Estimated Routing Table Memory (MB)
- 6.104
- Lookup Complexity (log₂ n comparisons)
- 15.61
- Estimated Memory (bytes)
- 6,400,000
Step by step
- 1Values used
- 2Table memory and lookup complexity
- 3Estimated Routing Table Memory (MB)= 6.104
- 4Lookup Complexity (log₂ n comparisons)= 15.61
- 5Estimated Memory (bytes)= 6,400,000
Assumptions and limits
- The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to 3 decimal places, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
How do I check the current route count on a Linux system?
`ip route show table all | wc -l` counts entries across all tables; `wc -l < /proc/net/route` gives the IPv4 main table count directly from the kernel's exposed route file.
What is an LC-trie and why does the kernel use it for routing?
An LC-trie (level-compressed trie) is a compact prefix-tree structure optimized for longest-prefix-match lookups, which is exactly the operation IP routing requires (finding the most specific matching route for a destination) — it offers good average-case lookup time and reasonable memory usage even with hundreds of thousands of routes.
Does route count affect anything besides lookup time and memory?
Yes — route table changes (additions/deletions/updates from routing protocols like BGP or OSPF) trigger FIB rebuilds or incremental updates, and very large or frequently-changing tables can increase CPU load during convergence events, which matters for routers handling full Internet routing tables.