Course: COMP347 Computer Networks (Revision 10) | Textbook: Kurose & Ross, Computer Networking: A Top‑Down Approach (9th ed.)
Upon completion of this tutorial, students should be able to:
Forwarding tables are the cornerstone of the data plane. They are used by routers to determine the output port for each incoming packet based on the destination IP address. In modern IP networks with CIDR (Classless Inter‑Domain Routing), the forwarding table contains variable‑length prefixes, and the router must perform longest‑prefix matching (LPM) to select the most specific match.
This tutorial delves into the structure of forwarding tables, the LPM algorithm, and the data structures and hardware technologies (TCAM, tries) used to implement fast lookups. We also discuss address aggregation, which reduces table size, and packet classification, which extends forwarding decisions beyond destination addresses. Advanced topics include compressed forwarding tables, programmable data planes, and the challenges of scaling to ever‑larger routing tables.
A forwarding table (also called Forwarding Information Base, FIB) contains entries that map destination IP address prefixes to an output port (and optionally a next‑hop address). Each entry consists of:
The FIB is derived from the Routing Information Base (RIB), which contains all possible routes. The FIB contains only the best routes, optimized for fast lookup.
As of 2025, the global IPv4 BGP routing table has over 950,000 prefixes, while IPv6 has over 150,000 prefixes. This growth challenges both table size (memory) and lookup speed.
Longest‑prefix matching is the algorithm used to select the forwarding entry that matches the destination address with the most specific (longest) prefix. This is necessary because CIDR allows multiple prefixes to match a given address.
Algorithm: Given destination IP address D, the router finds all prefixes P such that D matches P (i.e., P is a prefix of D). Among these, it selects the one with the longest prefix length.
Example: D = 192.168.5.10. Table entries: 192.168.0.0/16, 192.168.5.0/24, 192.168.5.0/28. The /28 match is longest, so it wins.
CIDR (Classless Inter‑Domain Routing) allows arbitrary prefix lengths, enabling efficient address allocation and route aggregation. Route aggregation (route summarization) reduces the size of forwarding tables by combining multiple routes into a single, less specific prefix.
Example: Instead of advertising separate routes for 192.168.1.0/24, 192.168.2.0/24, ..., 192.168.15.0/24, a provider can advertise 192.168.0.0/20 if all these subnets are contiguous.
Several data structures are used to implement LPM efficiently. The choice depends on the required speed, update frequency, and memory constraints.
A binary trie is a tree where each node represents a bit (0 or 1). The path from root to a node corresponds to a prefix. Each node may store a forwarding entry. Lookup requires traversing the trie according to the bits of the destination address, remembering the last matching prefix. Complexity O(W), where W is the address length (32 for IPv4).
Patricia trie (Practical Algorithm To Retrieve Information Coded in Alphanumeric) compresses the binary trie by eliminating single‑child nodes. This reduces memory and lookup time.
A multi‑bit trie uses strides (multiple bits per level) to speed up lookup by increasing branching factor (e.g., 4‑bit stride means 16 children per node). This reduces the number of steps but increases memory. Optimal stride size is a design trade‑off.
LC‑trie combines path compression and level compression, achieving very fast lookup with moderate memory.
Lulea uses a compressed trie with bitmap techniques to reduce memory, enabling forwarding tables to fit in on‑chip memory.
Ternary Content Addressable Memory (TCAM) is a hardware device that performs parallel search of all entries in a single clock cycle. It stores (prefix, output port) pairs; the prefix includes don't‑care bits (X). The TCAM returns the first matching entry, which is the longest prefix if entries are ordered by prefix length (longest first). TCAM is fast but expensive and power‑hungry; typical capacities range from 512K to 1M entries.
Packet classification is the process of categorizing packets based on multiple header fields (destination IP, source IP, protocol, ports, etc.). It is used for firewalls, QoS, policy‑based routing, and SDN. In SDN, the match‑action paradigm extends forwarding to include arbitrary fields. While forwarding is based primarily on destination IP, packet classification allows more fine‑grained forwarding decisions.
Optimizations include:
With the rise of programmable data planes (P4) and SmartNICs, forwarding table lookup can be offloaded to programmable hardware that can implement custom LPM algorithms. Additionally, compression techniques (e.g., Lulea) are crucial to fit large tables into limited memory.
Q1. What is the primary purpose of a forwarding table in a router?
B)
Q2. Longest‑prefix matching is required because:
B)
Q3. Which data structure typically provides the fastest lookup time for LPM?
C) TCAM provides constant‑time lookup.
Q4. In a binary trie, what is the time complexity of a lookup?
C) The trie depth is at most W bits.
Q5. Which of the following is NOT a technique to reduce forwarding table size?
C) Increasing prefix length makes routes more specific, increasing table size.
Q6. In TCAM, the "don't care" (X) bits are used to represent:
D) TCAM uses X to indicate don't‑care bits for prefix matching.
Q7. What is the main disadvantage of TCAM compared to algorithmic lookup?
B) TCAM is expensive and consumes significant power.
Q8. A forwarding table entry with prefix 192.168.0.0/16 matches which of the following destination addresses?
D) The /16 prefix covers addresses 192.168.0.0 to 192.168.255.255.
Q9. The Patricia trie compresses a binary trie by:
A) Patricia trie eliminates unary nodes to reduce height.
Q10. What is route aggregation?
A)
Q11. In a multi‑bit trie with stride k, how many child pointers per node?
B) A node at a stride‑k level has 2^k children.
Q12. Packet classification differs from forwarding in that it:
B) Packet classification uses fields like source IP, ports, protocol, etc.
Q13. The size of the global IPv4 BGP table is approximately:
C) As of 2025, it is nearly 1 million.
Q14. Which algorithm is typically used for packet classification in high‑speed routers?
D) TCAM is common for classification, but software methods also exist.
Q15. Forwarding table updates are typically:
B) Updates are frequent due to network changes.
Q16. Explain the relationship between the RIB and the FIB.
The Routing Information Base (RIB) contains all routes learned from routing protocols, including multiple paths and metrics. The Forwarding Information Base (FIB) is a subset of the RIB optimized for fast lookup; it contains the best routes for forwarding. The FIB is installed in the data plane hardware (input ports) for per‑packet lookups.
Q17. Why is longest‑prefix matching necessary in CIDR?
CIDR allows variable‑length prefixes, so a destination address may match multiple prefixes. Longest‑prefix matching ensures the most specific (longest) prefix is chosen, which corresponds to the most precise route. This is essential for correct routing and aggregation.
Q18. What are the advantages and disadvantages of using a binary trie for forwarding lookup?
Advantages: Simple, supports prefix insert/delete, memory efficient (worst‑case O(N*W)). Disadvantages: Lookup time O(W) (32 steps for IPv4, 128 for IPv6), which can be slow for high speeds; memory can be high if unary nodes are not compressed.
Q19. Describe how TCAM performs longest‑prefix matching.
TCAM stores prefixes with don't‑care bits for the host portion. When a destination address is presented, the TCAM compares it in parallel with all entries. The first matching entry (ordered by prefix length) is returned; this yields the longest prefix because entries are sorted by prefix length descending.
Q20. What is the purpose of route aggregation in the context of forwarding tables?
Route aggregation reduces the number of entries in forwarding tables by combining multiple contiguous prefixes into a single, shorter prefix. This decreases memory requirements and lookup time, and reduces routing protocol overhead.
Q21. A router receives a packet with destination address 10.10.10.10. The forwarding table has the following entries: 10.0.0.0/8 → A, 10.10.0.0/16 → B, 10.10.10.0/24 → C. Which output port is used?
The longest match is /24 (10.10.10.0/24), so output port C is used.
Q22. A network administrator wants to summarize the following subnets into a single prefix: 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24, 192.168.3.0/24. What is the summary prefix?
These four subnets cover 192.168.0.0 – 192.168.3.255, which is a /22 prefix: 192.168.0.0/22.
Q23. A router uses a binary trie for LPM. The trie contains prefixes: 192.168.0.0/16, 192.168.5.0/24, 192.168.5.128/25. Draw the trie structure for these prefixes and trace the lookup for destination 192.168.5.130.
The binary trie would have branches for each bit. The lookup for 192.168.5.130: follows bits 11000000.10101000.00000101.10000010. It will match 192.168.0.0/16 (at depth 16), then 192.168.5.0/24 (at depth 24), then 192.168.5.128/25 (at depth 25) if the 25th bit is 1. Since 130 has 25th bit 1, it matches the /25, so the result is that prefix.
Q24. Discuss the trade‑offs between TCAM and algorithmic (trie) based LPM in terms of speed, power, capacity, and flexibility.
TCAM: very fast (constant time), high power consumption, limited capacity (expensive), inflexible (hard‑coded). Algorithmic: slower (O(W) steps), lower power, scalable to larger tables, flexible (can be updated easily). High‑end routers often combine both: TCAM for a cache of frequently used prefixes, and algorithmic for the rest.
Q25. A router's forwarding table has 500,000 entries. The hardware can perform a lookup in 50 ns. How many packets per second can it process? If the average packet size is 1500 bytes, what is the maximum link speed that can be supported?
Lookup capacity = 1 / 50e-9 = 20 million packets/sec. At 1500 bytes (12,000 bits), maximum throughput = 20e6 * 12,000 = 240 Gbps. However, this ignores switching and output overhead; practical throughput is lower.
Q26. Explain the concept of "prefix compression" and its importance in routing tables.
Prefix compression techniques (like Lulea) reduce the memory needed to store forwarding tables by using bitmap structures and eliminating redundant entries. This is crucial because routing tables are large and must fit in fast on‑chip memory for high‑speed lookup.
Q27. What is the difference between a forwarding table and a routing table?
A routing table (RIB) contains all known routes, including multiple paths and metrics, used by routing protocols. A forwarding table (FIB) is a distilled version containing only the best routes, optimized for quick lookup and installed in the data plane.
Q28. In an SDN environment, how does the control plane update the forwarding tables in the switches?
The SDN controller computes forwarding decisions and uses a protocol like OpenFlow to install flow entries in the switches' flow tables (which act as forwarding tables). Updates can be pushed reactively (per flow) or proactively (pre‑installed).
Q29. Consider a router that uses a multi‑bit trie with a stride of 4. How many levels are needed for an IPv4 address? What is the maximum number of nodes at level 2?
IPv4 has 32 bits; with stride 4, there are 32/4 = 8 levels. At level 2, the depth is 8 bits; the maximum number of nodes is 2^8 = 256.
Q30. What is the impact of IPv6 address length on LPM data structures?
IPv6 uses 128‑bit addresses, doubling the lookup depth in binary tries. This increases lookup time and memory unless optimized (e.g., using multi‑bit tries with larger strides). TCAM for IPv6 also requires wider entries, increasing cost.
Q31. What is the role of a default route (0.0.0.0/0) in a forwarding table?
The default route is used as a catch‑all for destinations that do not match any other prefix. It is the least specific match (prefix length 0) and is chosen only if no longer prefix matches.
Q32. Explain how a router handles the case where two entries have the same prefix length but different next hops.
If two entries have the same prefix and length, the router would typically use the one with lower metric (e.g., administrative distance) or the one that was installed later. The FIB contains only one best route per prefix.
Q33. Why is TCAM not suitable for packet classification with many fields?
TCAM entries are typically wide; matching on 5‑tuple fields (IPs, ports, protocol) requires very wide TCAM, which is expensive and power‑hungry. Also, the number of rules can be large, so algorithmic methods or hybrid solutions are used.
Q34. What is the benefit of using a Patricia trie over a binary trie?
Patricia trie removes nodes with a single child, reducing tree height and memory usage. This speeds up lookup because fewer nodes are visited, especially for sparse prefixes.
Q35. In the context of forwarding tables, what is "route flapping" and how does it affect table updates?
Route flapping is frequent changes in the availability of a route (up/down). This causes frequent updates to the forwarding table, which can stress the control plane and cause instability. BGP uses route damping to mitigate this.
Given the following forwarding table, determine the output port for each destination address:
| Prefix | Output Port |
|---|---|
| 192.168.0.0/16 | P1 |
| 192.168.5.0/24 | P2 |
| 192.168.5.128/25 | P3 |
| 0.0.0.0/0 | P4 |
Destinations: a) 192.168.5.10, b) 192.168.5.200, c) 192.168.10.5, d) 10.0.0.1
a) 192.168.5.10: matches /16, /24, but not /25 (since 10 < 128). Longest is /24 → P2.
b) 192.168.5.200: matches /16, /24, and /25 (200 ≥ 128). Longest is /25 → P3.
c) 192.168.10.5: matches /16 only → P1.
d) 10.0.0.1: no match except default → P4.
Aggregate the following prefixes into the smallest possible set of prefixes: 10.1.0.0/24, 10.1.1.0/24, 10.1.2.0/24, 10.1.3.0/24, 10.1.4.0/24, 10.1.5.0/24.
These are 6 contiguous /24 subnets from 10.1.0.0 to 10.1.5.255. The first 4 (0‑3) can be summarized as 10.1.0.0/22. The remaining 4 and 5 can be summarized as 10.1.4.0/23? Actually 10.1.4.0/23 covers 4.0‑5.255. So the set is {10.1.0.0/22, 10.1.4.0/23}.
Design a binary trie for the prefixes: 192.168.0.0/16, 192.168.5.0/24, 192.168.5.128/25, 10.0.0.0/8. Show the trie structure.
The binary trie would have a root, then branches for bits of addresses. Since the prefixes start with different first bits (192 = 11000000, 10 = 00001010), they diverge early. The trie would have nodes representing the common bits. For 192.168, the path would go to depth 16, then split for .5, etc. (Drawing is not possible in text, but description: root → 0 and 1 branches; 10 prefix goes under 0 branch; 192 prefix under 1 branch; under 192 branch, continues with bits of 168, etc.)
A router uses a multi‑bit trie with stride 4. How many memory accesses are needed for an IPv4 lookup? Assume the trie is complete.
32 bits / 4 bits per stride = 8 levels. Each level requires one memory access (assuming node fits in one access). So 8 accesses. In practice, some nodes may be compressed.
Explain why TCAM entries are ordered by prefix length for LPM. What happens if they are not ordered?
TCAM returns the first matching entry. If entries are not ordered by prefix length, a shorter prefix might be returned before a longer one, causing incorrect forwarding. Therefore, entries must be sorted with longer prefixes first (higher priority).
A forwarding table has 100,000 entries. A binary trie lookup takes on average 20 memory accesses per packet. If each memory access is 10 ns, what is the maximum packet rate?
Time per lookup = 20 * 10 ns = 200 ns. Max packets/sec = 1 / 200e-9 = 5,000,000 pps.
Compare the memory requirements of a binary trie vs. a Patricia trie for the prefix set: 192.168.0.0/16, 192.168.5.0/24, 192.168.5.128/25.
Binary trie: nodes for each bit; for /16, 16 nodes; for /24, additional 8 nodes; for /25, additional 1 node, but many unary nodes. Patricia trie compresses chains, so it has fewer nodes (e.g., it will skip unary nodes and only have nodes at branching points). Patricia trie uses less memory.
What is the effect of increasing the stride in a multi‑bit trie on lookup speed and memory usage?
Increasing stride reduces the number of levels (faster lookup) but increases the branching factor (2^k children per node), which increases memory usage exponentially. There is a trade‑off; optimal stride depends on the table size and available memory.
A router uses a TCAM with 512K entries. The forwarding table has 600K prefixes. How can the router handle this?
The router can use a two‑level scheme: a TCAM for the most specific prefixes (e.g., longest prefixes) and algorithmic (trie) for the rest. Or use route aggregation to reduce the number of entries, or use multiple TCAMs.
Explain the concept of "wildcard" matching in packet classification and give an example.
Wildcard matching allows a rule to specify a value for some fields and ignore others (e.g., source IP = any, destination port = 80). This is used in firewalls and SDN. Example: rule: "if destination port = 80 then forward to web server" ignores source IP.
Given prefixes: 10.0.0.0/8, 10.1.0.0/16, 10.1.1.0/24, 10.1.1.128/25. What is the longest prefix match for address 10.1.1.200?
10.1.1.200 matches /8, /16, /24, and /25 (since 200 ≥ 128). Longest is /25.
What is the default route's prefix length, and when is it used?
Default route is 0.0.0.0/0 (prefix length 0). It is used only when no other prefix matches the destination address.
Compare the update time of a binary trie vs. TCAM when a route is added or removed.
Binary trie updates are O(W) and can be done incrementally with moderate effort. TCAM updates require rewriting entries and may involve moving entries to maintain priority ordering, which can be complex and may cause temporary forwarding disruption.
Explain how the Lulea algorithm reduces memory for forwarding tables.
Lulea uses a compressed trie with bitmaps: it uses a bitmap to represent children, and a separate array for actual child pointers. It also uses a technique called "leaf‑pushing" to move prefixes to leaves. This reduces memory significantly, allowing large tables to fit in fast SRAM.
In an SDN switch, the forwarding table is called a flow table. How does it differ from a traditional IP forwarding table?
A flow table uses the match‑action paradigm, matching on multiple fields (not just destination IP) and specifying actions beyond output (e.g., drop, modify, send to controller). It is more flexible and programmable, but typically has more entries per flow.
Research the concept of "IP routing table compression". Write a 500‑word summary covering the Lulea algorithm and its impact on router design.
Lulea is a compression algorithm that reduces the memory needed for IP forwarding tables by using bitmaps and leaf‑pushing. It enables large tables to fit in fast on‑chip memory, improving lookup speed. It has been widely adopted in high‑speed routers. The algorithm compresses the trie by representing children with bitmaps and using a compact array for pointers. This reduces memory usage by up to 90% compared to a standard trie.
Compare the performance of binary trie, Patricia trie, and multi‑bit trie in terms of lookup time, update time, and memory usage. Give examples where each would be preferred.
Binary trie: simple, O(32) lookup, O(32) update, memory O(N*W). Patricia: compressed, faster lookup, lower memory. Multi‑bit: tunable, faster lookup (fewer levels), but memory grows exponentially with stride. Binary trie is suitable for small tables; Patricia for medium; multi‑bit for high‑speed with large tables.
Design a forwarding table for a router with three interfaces: interface A connects to 10.0.0.0/8, interface B to 192.168.0.0/16, and interface C to the rest of the Internet via a default route. Additionally, interface B has a sub‑interface for 192.168.5.0/24 that should go to a different next‑hop (same output port, but different next‑hop). Write the forwarding table entries.
Entries:
10.0.0.0/8 → next‑hop via interface A
192.168.0.0/16 → next‑hop via interface B (default)
192.168.5.0/24 → next‑hop via interface B (specific next‑hop for that subnet)
0.0.0.0/0 → next‑hop via interface C
Explain the concept of "flow‑based forwarding" in SDN and how it differs from traditional destination‑based forwarding.
Flow‑based forwarding uses multiple header fields (e.g., IPs, ports, protocol) to classify packets into flows, and applies actions per flow. This allows fine‑grained policies and traffic engineering. Traditional forwarding is based solely on destination IP and is stateless. Flow‑based forwarding requires more table entries and is more flexible.
Calculate the number of forwarding entries needed for a hierarchical network with three levels: core, distribution, and access. Assume aggregation at each level. Provide an example with IP addressing.
Example: Each access network uses /24 subnets. Distribution routers aggregate many /24s into /16 or /20. Core routers aggregate distribution prefixes into /8. The number of entries reduces as we go up. For instance, 256 access subnets can be summarized into one /16 at distribution, and several distributions into a /8 at core.
Discuss the challenges of updating forwarding tables in a high‑speed router without interrupting packet forwarding.
Challenges include: maintaining consistency (no incorrect forwarding during update), minimizing packet loss, and handling high update rates. Techniques: dual FIB with atomic pointer switch, batch updates, and using version numbers. Updates must be fast to keep up with routing changes.
What is the role of the prefix length in determining the number of addresses in a subnet? How does this affect route aggregation?
Prefix length determines the number of host bits (32 – length). A shorter prefix covers more addresses, which aids aggregation but reduces specificity. Route aggregation combines multiple longer prefixes into a shorter one, reducing table size but may cause less specific routing.
Explain how a router handles a packet when the destination address matches multiple prefixes with the same length.
If prefixes have the same length but different values, a given address can match only one of them (unless they overlap, which is not allowed). If there are duplicates (same prefix from different sources), the router selects one based on administrative distance or other metrics.
Describe the "match‑action" paradigm in programmable data planes and how it relates to forwarding tables.
In match‑action, the forwarding table becomes a set of rules that match on any packet header fields and specify actions (output, drop, modify, etc.). This extends forwarding to include classification. In P4, the pipeline is defined by the programmer, and the tables can be updated dynamically by the control plane.
Research the size of the global BGP table over time. Write a short report on the growth trends and implications for router forwarding table memory and lookup speed.
Global BGP table has grown from ~100k prefixes in 2000 to ~950k in 2025. This growth requires routers to have larger TCAM or more memory for algorithmic lookups. It also increases update frequency, straining control planes. Techniques like FIB aggregation and compression are essential.
Explain the concept of "TCAM power consumption" and why it is a concern in large data centers.
TCAM consumes significant power per bit because all entries are searched in parallel. For large tables (1M entries), power can be hundreds of watts per chip. In data centers with many switches, this adds to cooling and energy costs, driving the need for algorithmic lookups or hybrid approaches.
What is the difference between a "flow table" in OpenFlow and a traditional IP forwarding table?
OpenFlow flow table matches on up to 12 header fields (including Ethernet, IP, transport). It has a priority field to resolve conflicts and supports multiple actions (output, drop, modify). Traditional IP table matches only destination IP and has a single action (output port).
Explain the use of "wildcard masks" in ACLs and how they relate to prefix matching.
Wildcard masks (inverse masks) specify which bits of an address must match and which are ignored. For example, 192.168.0.0 0.0.255.255 matches any address in 192.168.0.0/16. This is similar to prefix notation but expressed as a mask.
Describe the challenges of implementing LPM for IPv6 in hardware. How do multi‑bit tries help?
IPv6 has 128‑bit addresses, doubling the depth of binary tries. This increases lookup time and memory. Multi‑bit tries with larger strides (e.g., stride 8) reduce the number of levels to 16 (128/8) and are more efficient in hardware. TCAM for IPv6 also requires wider entries, increasing cost.
Write a pseudocode function that performs longest‑prefix matching given a binary trie and a destination address.
``` function lookup(trie_root, address): node = trie_root best = null for i = 0 to 31: bit = (address >> (31 - i)) & 1 if node has entry: best = node.entry if node.child[bit] exists: node = node.child[bit] else: break return best ```
This tutorial has provided an in‑depth exploration of forwarding tables and longest‑prefix matching. Key takeaways:
Understanding these concepts prepares you for the next tutorial on IPv4 datagram structure and addressing.