Lock-free Radix Trees for IP Routing

Authors: Damian Ho (xho), Jessica Ruan (jwruan)

Summary

We implemented concurrent radix trees for IP routing and compared its performance to coarse-grained locking, fine-grained locking, and lock-free variants on the PSC Bridges-2 machines. Our lock-free implementation uses the single-word compare-and-swap (CAS) instruction for synchronization.

Background

IP Routing

In IP Routing, a router has to determine the next hop for a packet based on the IP address of its destination. To do this, the router uses a routing table that maps IP addresses to routers.

Figure 1: IP Address Matching

Routes are represented in CIDR notation, e.g. 10.10.1.32/27 where the 27 represents the number of bits in the network prefix (prefix length, a.k.a. cidr). This means that any IP address that has the same first 27 bits matches the route. In Figure 1, 10.10.1.44 matches the route 10.10.1.32/27 while 10.10.1.90 does not.

In the case that multiple routes match an IP address, the routing table returns the most specific route, or more rigorously, the route with the largest cidr value.

Thus, the routing table supports the following operations:

Insert(ip, cidr, router): associate the route ip/cidr with router
Delete(ip, cidr): remove the router associated with the route ip/cidr (if any)
Lookup(ip): find the next-hop router for ip

We refer to Inserts and Deletes as “updates,” or “update operations.”

Radix Tree

Figure 2: Structure of a Radix Tree

A commonly used data structure for the routing table is the radix tree, a specialization of a binary trie. Each node represents a route, but does not necessarily contain an entry if it serves only as a “branching point”. In the figure above, the nodes corresponding to the routes 128.0.0.0/2, 192.0.0.0/2, and 200.0.0.0/5 contain entries; the rest do not. As a space optimization, any node that is an only child is merged with its parent if the parent does not have an entry.

The cidr increases with depth, which means that the best match is the deepest entry associated with a matching route. The search complexity is thus O(k) where k is the number of bits in an IP address, i.e. k = 32 for IPv4 and k = 128 for IPv6.

Challenge

Update operations, comprised of inserts and deletes, can cause the structure of the radix tree to change in a non-trivial fashion. It is important to ensure that concurrent updates do not leave the tree in an inconsistent state. We also want to ensure that lookups do not view a tree in an inconsistent state.

Figure 3: Possible outcomes after performing an insert operation with a new route

Figure 4: Parent with no entry is merged with an only child

One solution is to use synchronization primitives such as locks. With coarse-grained locking, a simple approach is to use a global read-write lock on the entire tree to ensure that multiple readers or at most one writer can access the tree concurrently. However, this severely limits parallelism especially when updates are more frequent.

Figure 5: Hand-over-hand Locking

A better approach is to use fine-grained locking, where each node has a lock and threads only obtain locks when strictly necessary. We can perform hand-over-hand locking, where a lock is acquired on a parent and its child, and the lock on the parent is only released once it is deemed safe to do so – when we are confident that we do not need to backtrack to the parent, and that necessary updates to the parent have been made. Locks are acquired and released in this fashion as we traverse down the tree, enabling updates to operate concurrently on different portions of the tree.

Even better would be a lock-free implementation that guarantees system-wide progress even in the presence of multiple thread failures. We can use the compare-and-swap (CAS) instruction to achieve this, using the idea of marking individual child pointers from Velamuri [1]. This facilitates system-wide progress since any thread that is blocked by an ongoing operation can help to finish the ongoing operation before restarting. Furthermore, multiple threads can update a node simultaneously, improving parallelism. This is the approach that we will modify and present in this paper.

Resources

Velamuri, V.S. (2017). Efficient Non-blocking Radix Trees. European Conference on Parallel Processing.
Velamuri, V. (2017). Source code for efficient non-blocking radix trees. https://github.com/varun1312/RadixTrees
Donenfeld, J. (2019). WireGuard for Linux 3.10 - 5.5. https://github.com/WireGuard/wireguard-linux-compat
Donenfeld, J. (2018). Go implementation of WireGuard. https://github.com/WireGuard/wireguard-go
McKenney, P. (2007, December 17). What is RCU, fundamentally?. Linux Weekly News. https://lwn.net/Articles/262464/
Corbet, J. (2006, March 13). Trees I: Radix trees. Linux Weekly News. https://lwn.net/Articles/175432/

Goals and Deliverables

Plan to achieve

Sequential implementation of radix tree
Coarse-grained locking implementation of radix tree
Fine-grained locking implementation of radix tree
Lock-free implementation (CAS) of radix tree
Utilities to generate workloads and test performance
Test harness to check correctness of implementations
Detailed comparison of radix tree performances under different workloads

Hope to achieve

Userspace RCU lock-free implementation of radix tree, and comparison to CAS implementation

Demo: We will display graphs that demonstrate the speedup of the lock-free radix tree over the other implementations under different conditions.

The resultant data structure will be capable of concurrent lookups and updates while preserving integrity and correctness.

Platform Choice

Computer

GHC machines for development and debugging
PSC Bridges-2 “Regular Memory” machines for benchmarking heavy workloads

Language

C++23 for atomic library

Schedule

Week	Damian Ho	Jessica Ruan
Nov 6 - Nov 12	Work on proposal Design radix tree interface Implement linked list / binary trie Add basic correctness tests	Work on proposal Implement radix tree
Nov 13 - Nov 19 Project Proposal Due	Complete and submit proposal Add stress tests Implement coarse-grained radix tree Implement fine-grained radix tree	Write performance benchmarks Write workload generator
Nov 20 - Nov 27	Read lock-free papers Implement lock-free (CAS) radix tree	Read lock-free papers Implement lock-free (CAS) radix tree
Nov 27 - Dec 3 Milestone Report Due	Benchmark implementations Complete milestone report	Benchmark implementations Complete milestone report
Dec 4 - Dec 10	Implement lock-free (RCU) radix tree Further benchmarking of implementations	Implement lock-free (RCU) radix tree Further benchmarking of implementations
Dec 11 - Dec 15 Final Report Due Poster Session	Complete final report and poster	Complete final report and poster