Repository: akvorado/akvorado

Issue:
BMP crash: cannot read BMP body
```
akvorado version 1.11.1

```

# Bug description

During operation I see no flows are collected anymore. When inspecting the logs this happened after this log message of the inlet docker image. A reboot of the ghcr.io/akvorado/akvorado:1.11.1 will fix this.

`{"level":"error","exporter":"10.255.255.167","error":"read tcp 172.18.0.8:10179->10.255.*.*:63720: read: connection reset by peer","time":"2024-10-28T21:31:51Z","caller":"akvorado/inlet/routing/provider/bmp/serve.go:119","module":"akvorado/inlet/routing/provider/bmp","message":"cannot read BMP body"}`



Hints from issue comments:
@vincentbernat: This error should not be fatal. Did you have more logs after this one? You should get "connection down for ...". I wonder if maybe there was another fatal error, if this is not just the consequence (we shouldn't log errors when shutting down, but maybe we are). The surrounding logs should help.@rinsekloek: What is the best way to get the logs when running the docker version ?@vincentbernat: docker compose logs akvorado-inlet@rinsekloek: Looks like some queue full. I changed the queues/workers to see if this fixed this.
```

/input/udp","message":"dropping flow due to queue full (size 100000)"}
akvorado-inlet-1  | {"level":"warn","worker":"1","listen":":9995","time":"2024-10-28T21:30:25Z","caller":"akvorado/inlet/flow/input/udp/root.go:207","module":"akvorado/inlet/flow/input/udp","message":"dropping flow due to queue full (size 100000)"}
akvorado-inlet-1  | {"level":"warn","worker":"2","listen":":9995","time":"2024-10-28T21:31:25Z","caller":"akvorado/inlet/flow/input/udp/root.go:207","module":"akvorado/inlet/flow/input/udp","message":"dropping flow due to queue full (size 100000)"}
akvorado-inlet-1  | {"level":"warn","worker":"1","listen":":9995","time":"2024-10-28T21:31:25Z","caller":"akvorado/inlet/flow/input/udp/root.go:207","module":"akvorado/inlet/flow/input/udp","message":"dropping flow due to queue full (size 100000)"}
akvorado-inlet-1  | {"level":"error","exporter":"*.*.*.*","error":"read tcp 172.18.0.8:10179->*.*.*.*:63720: read: connection reset by peer","time":"2024-10-28T21:31:51Z","caller":"akvorado/inlet/routing/provider/bmp/serve.go:119","module":"akvorado/inlet/routing/provider/bmp","message":"cannot read BMP body"}
akvorado-inlet-1  | {"level":"warn","worker":"2","listen":":9995","time":"2024-10-28T21:32:25Z","caller":"akvorado/inlet/flow/input/udp/root.go:207","module":"akvorado/inlet/flow/input/udp","message":"dropping flow due to queue full (size 100000)"}
akvorado-inlet-1  | {"level":"warn","worker":"1","listen":":9995","time":"2024-10-28T21:32:25Z","caller":"akvorado/inlet/flow/input/udp/root.go:207","module":"akvorado/inlet/flow/input/udp","message":"dropping flow due to queue full (size 100000)"}

```@rinsekloek: Crashes happened again. Seems to start after some BGP flaps:

![Image](https://github.com/user-attachments/assets/5f7907bb-1cab-4a35-8736-f003faa82267)

These are the surrounding logs:

10.255.255.168 (Nokia 7750 Router)

```
	2639154 2025/01/20 12:19:26.129 CET MINOR: BGP #2041 Base Akvorado inlet collctor
	"VR 1: BMP station Akvorado inlet collctor moved from state established to state idle, due to reason: station stuck"
	2639121 2025/01/20 12:15:55.112 CET MINOR: BGP #2041 Base Akvorado inlet collctor
	"VR 1: BMP station Akvorado inlet collctor moved from state welcoming to state established"
	2638997 2025/01/20 12:02:21.131 CET MINOR: BGP #2041 Base Akvorado inlet collctor
	"VR 1: BMP station Akvorado inlet collctor moved from state established to state idle, due to reason: station stuck"
	2638982 2025/01/20 12:01:16.114 CET MINOR: BGP #2041 Base Akvorado inlet collctor
	"VR 1: BMP station Akvorado inlet collctor moved from state welcoming to state established"
	2638839 2025/01/20 11:45:45.178 CET MINOR: BGP #2041 Base Akvorado inlet collctor

```

akvorado-logs:

```

"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.209.165 for exporter 10.255.255.167 (reason: stale)"}
Jan 20 12:04:01 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:01+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 193.239.116.91 for exporter 10.255.255.167 (reason: stale)"}
Jan 20 12:04:17 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:17+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 193.239.116.5 for exporter 10.255.255.168 (reason: stale)"}
Jan 20 12:04:32 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:32+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.210.35 for exporter 10.255.255.167 (reason: stale)"}
Jan 20 12:04:47 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:47+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.209.1 for exporter 10.255.255.167 (reason: stale)"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.209.41 for exporter 10.255.255.167 (reason: stale)"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"error","exporter":"*.*.*.168","error":"read tcp *.*.*.137:10179->*.*.*.168:57665: read: connection reset by peer","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:119","module":"akvorado/inlet/routing/provider/bmp","message":"cannot read BMP body"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","exporter":"*.*.*.168","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:32","module":"akvorado/inlet/routing/provider/bmp","message":"connection down for *.*.*.168"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.209.21 for exporter *.*.*.168 (reason: stale)"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"error","exporter":"*.*.*.168","error":"read tcp *.*.*.137:10179->*.*.*.168:57312: read: connection reset by peer","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:119","module":"akvorado/inlet/routing/provider/bmp","message":"cannot read BMP body"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","exporter":"*.*.*.168","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:32","module":"akvorado/inlet/routing/provider/bmp","message":"connection down for *.*.*.168"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.208.247 for exporter *.*.*.167 (reason: stale)"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"error","exporter":"*.*.*.167","error":"read tcp *.*.*.137:10179->*.*.*.167:59220: read: connection reset by peer","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:119","module":"akvorado/inlet/routing/provider/bmp","message":"cannot read BMP body"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","exporter":"*.*.*.167","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:32","module":"akvorado/inlet/routing/provider/bmp","message":"connection down for *.*.*.167"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 2001:7f8:13::a503:9647:2 for exporter *.*.*.168 (reason: stale)"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"error","exporter":"*.*.*.167","error":"read tcp *.*.*.137:10179->*.*.*.167:59469: read: connection reset by peer","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:119","module":"akvorado/inlet/routing/provider/bmp","message":"cannot read BMP body"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","exporter":"*.*.*.167","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:32","module":"akvorado/inlet/routing/provider/bmp","message":"connection down for *.*.*.167"}
Jan 20 12:04:58 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:04:58+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 2001:7f8:1::a505:673:1 for exporter *.*.*.168 (reason: stale)"}
Jan 20 12:11:17 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:11:17+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 2001:7f8:1:0:a500:39:6986:2 for exporter *.*.*.168 (reason: stale)"}
Jan 20 12:11:17 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","time":"2025-01-20T12:11:17+01:00","caller":"akvorado/inlet/routing/provider/bmp/events.go:102","module":"akvorado/inlet/routing/provider/bmp","message":"remove peer 80.249.209.189 for exporter *.*.*.167 (reason: stale)"}
....
....
Jan 20 12:15:54 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","exporter":"*.*.*.168","sysname":"***","time":"2025-01-20T12:15:54+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:185","module":"akvorado/inlet/routing/provider/bmp","message":"new connection"}
Jan 20 12:17:03 netflow-mon01.dfni.nl akvorado[371344]: {"level":"info","exporter":"*.*.*.167","sysname":"**","time":"2025-01-20T12:17:03+01:00","caller":"akvorado/inlet/routing/provider/bmp/serve.go:185","module":"akvorado/inlet/routing/provider/bmp","message":"new connection"}
```
@rinsekloek: This happens now every ~2 weeks.
Do you have some extra commands I could do to debug this issue ?@vincentbernat: Likely, the reason is that when we need to flush a peer after a BGP flap, any update is blocked while the peer is flushed and this makes the current session not reading more updates and get "stuck". This could be solved by #1894, which was just merged.

Do you know how long we can wait before being considered "stuck"? Is it configurable?@rinsekloek: Thanks for fixing this issue. Ironically I had shut down BMP last Friday, but will update and reenable it again shortly@vincentbernat: I thought I left a comment. The issue is not 100% fixed, but:
- code is now a bit faster to flush a peer
- it gives now the priority to flush the peer (previously, the priority was to the readers)
- there is documentation to increase the TCP buffer to avoid the BMP exporter reporting us as "stuck"

If that's not enough, it's still possible to do better. Either we can buffer inside Akvorado (instead of the kernel) or I can make the algorithm more parallel at the expense of the memory use.

Solution patch:
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index b56065f7..2806882c 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -2,7 +2,7 @@
 
 New features should be discussed. Open an issue before trying anything major.
 New features are not free to maintain and put a burden on the maintainers of the
-project, notably when it comes to fix bugs and when they interfer in future
+project, notably when it comes to fixing bugs and when they interfere with future
 evolutions.
 
 # User friendliness
@@ -19,7 +19,7 @@ users:
 
 Go formatter takes care of most issues. For the remaining points:
 
-- comments are sentence and should be capitalized
+- comments are sentences and should be capitalized
 - on the other hand, log messages are not and should *not* be capitalized
 - metrics should be named using [Prometheus conventions][]
 
@@ -49,7 +49,7 @@ can spawn them through `docker compose -f docker/docker-compose-dev.yml`:
 
 For manual end-to-end tests, you can use `make docker-dev` to build a Docker
 container of Akvorado, then use `docker compose up` to run Docker compose.
-Beware to not destroy the volume for GeoIP at each tentative as there is a
+Beware not to destroy the volume for GeoIP at each attempt as there is a
 per-day limit on the number of times one IP can fetch the GeoIP database.
 
 If you need to work on the frontend part, you can spawn the Docker compose
diff --git a/Makefile b/Makefile
index de71fcd8..054abcd1 100644
--- a/Makefile
+++ b/Makefile
@@ -8,7 +8,7 @@ PKGS     = $(or $(PKG),$(shell env GO111MODULE=on $(GO) list ./...))
 
 GO      = go
 NPM     = npm
-TIMEOUT = 45
+TIMEOUT = 45s
 LSFILES = git ls-files -cmo --exclude-standard --
 V = 0
 Q = $(if $(filter 1,$V),,@)
@@ -169,7 +169,7 @@ test-go-units: ; $(info $(M) running Go tests$(GOTEST_MORE)…)
 	$Q mkdir -p test/go
 	$Q env PATH=$(dir $(abspath $(shell command -v $(GO)))):$(PATH) $(GOTESTSUM) \
         --junitfile test/go/tests.xml -- \
-		-timeout $(TIMEOUT)s \
+		-timeout $(TIMEOUT) \
 		$(GOTEST_ARGS) $(PKGS)
 test-race: CGO_ENABLED=1
 test-race: GOTEST_ARGS=-race
@@ -180,8 +180,8 @@ test-short: GOTEST_MORE=, only short tests
 test-short: test-go  ## Run only short Go tests
 test-bench: ; $(info $(M) running benchmarks…) @ ## Run Go benchmarks
 	$Q $(GO) test \
-		-fullpath -timeout $(TIMEOUT)s -run=__absolutelynothing__ -bench=. -benchmem \
-		$(PKGS) # -memprofile test/go/memprofile.out -cpuprofile test/go/cpuprofile.out
+		-fullpath -run=__absolutelynothing__ -bench=. \
+		$(PKGS) # -benchmem -memprofile test/go/memprofile.out -cpuprofile test/go/cpuprofile.out
 test-coverage-go: ; $(info $(M) running Go coverage tests…) @ ## Run Go coverage tests
 	$Q mkdir -p test/go
 	$Q env PATH=$(dir $(abspath $(shell command -v $(GO)))):$(PATH) $(GOTESTSUM) -- \
diff --git a/README.md b/README.md
index 66c0ff44..8338fb48 100644
--- a/README.md
+++ b/README.md
@@ -15,7 +15,7 @@ and is licensed under the [AGPLv3 license](LICENSE.txt).
 A demo site using fake data and running the latest stable version is
 available on [demo.akvorado.net](https://demo.akvorado.net). It is the
 direct result of running `docker compose up` on a fresh checkout but
-port 2055 is not accessible (you cannot send you own flows). Please,
+port 2055 is not accessible (you cannot send your own flows). Please,
 be gentle with this resource. The demo site also enables you to browse
 the [documentation](https://demo.akvorado.net/docs) for the current version
 (the one in `docs/` is for the next version).
diff --git a/common/helpers/subnetmap.go b/common/helpers/subnetmap.go
index 415f0ae7..29a89344 100644
--- a/common/helpers/subnetmap.go
+++ b/common/helpers/subnetmap.go
@@ -5,34 +5,30 @@ package helpers
 
 import (
 	"fmt"
-	"net"
+	"iter"
 	"net/netip"
 	"reflect"
 	"regexp"
 	"strings"
 
+	"github.com/gaissmai/bart"
 	"github.com/gin-gonic/gin"
 	"github.com/go-viper/mapstructure/v2"
-	"github.com/kentik/patricia"
-	tree "github.com/kentik/patricia/generics_tree"
 )
 
 // SubnetMap maps subnets to values and allow to lookup by IP address.
-// Internally, everything is stored as an IPv6 (using v6-mapped IPv4
-// addresses).
 type SubnetMap[V any] struct {
-	tree *tree.TreeV6[V]
+	table *bart.Table[V]
 }
 
 // Lookup will search for the most specific subnet matching the
 // provided IP address and return the value associated with it.
 func (sm *SubnetMap[V]) Lookup(ip netip.Addr) (V, bool) {
-	if sm == nil || sm.tree == nil {
+	if sm == nil || sm.table == nil {
 		var value V
 		return value, false
 	}
-	ok, value := sm.tree.FindDeepestTag(patricia.NewIPv6Address(ip.AsSlice(), 128))
-	return value, ok
+	return sm.table.Lookup(ip)
 }
 
 // LookupOrDefault calls lookup and if not found, will return the
@@ -44,82 +40,98 @@ func (sm *SubnetMap[V]) LookupOrDefault(ip netip.Addr, fallback V) V {
 	return fallback
 }
 
-// ToMap return a map of the tree.
+// ToMap return a map of the tree. This should be used only when handling user
+// configuration or for debugging. Otherwise, it is better to use Iter().
 func (sm *SubnetMap[V]) ToMap() map[string]V {
 	output := map[string]V{}
-	if sm == nil || sm.tree == nil {
-		return output
-	}
-	iter := sm.tree.Iterate()
-	for iter.Next() {
-		output[iter.Address().String()] = iter.Tags()[0]
+	for prefix, value := range sm.All() {
+		if prefix.Addr().Is4In6() {
+			ipv4Addr := prefix.Addr().Unmap()
+			ipv4Prefix := netip.PrefixFrom(ipv4Addr, prefix.Bits()-96)
+			output[ipv4Prefix.String()] = value
+			continue
+		}
+		output[prefix.String()] = value
 	}
 	return output
 }
 
-// Set inserts the given key k into the SubnetMap, replacing any existing value if it exists.
-func (sm *SubnetMap[V]) Set(k string, v V) error {
-	subnetK, err := SubnetMapParseKey(k)
-	if err != nil {
-		return err
-	}
-	_, ipNet, err := net.ParseCIDR(subnetK)
-	if err != nil {
-		// Should not happen
-		return err
+// Set inserts the given key k into the SubnetMap, replacing any existing value
+// if it exists. It requires an IPv6 prefix or it will panic.
+func (sm *SubnetMap[V]) Set(prefix netip.Prefix, v V) {
+	if !prefix.Addr().Is6() {
+		panic(fmt.Errorf("%q is not an IPv6 subnet", prefix))
 	}
-	_, bits := ipNet.Mask.Size()
-	if bits != 128 {
-		return fmt.Errorf("%q is not an IPv6 subnet", ipNet)
+	if sm.table == nil {
+		sm.table = &bart.Table[V]{}
 	}
-	plen, _ := ipNet.Mask.Size()
-	sm.tree.Set(patricia.NewIPv6Address(ipNet.IP.To16(), uint(plen)), v)
-	return nil
+	sm.table.Insert(prefix, v)
 }
 
-// Update inserts the given key k into the SubnetMap, calling updateFunc with the existing value.
-func (sm *SubnetMap[V]) Update(k string, v V, updateFunc tree.UpdatesFunc[V]) error {
-	subnetK, err := SubnetMapParseKey(k)
-	if err != nil {
-		return err
+// Update inserts the given key k into the SubnetMap, calling cb with the
+// existing value. It requires an IPv6 prefix or it will panic.
+func (sm *SubnetMap[V]) Update(prefix netip.Prefix, cb func(V, bool) V) {
+	if !prefix.Addr().Is6() {
+		panic(fmt.Errorf("%q is not an IPv6 subnet", prefix))
 	}
-	_, ipNet, err := net.ParseCIDR(subnetK)
-	if err != nil {
-		// Should not happen
-		return err
+	if sm.table == nil {
+		sm.table = &bart.Table[V]{}
+	}
+	sm.table.Update(prefix, cb)
+}
+
+// All walks the whole subnet map.
+func (sm *SubnetMap[V]) All() iter.Seq2[netip.Prefix, V] {
+	return func(yield func(netip.Prefix, V) bool) {
+		if sm == nil || sm.table == nil {
+			return
+		}
+		sm.table.All6()(yield)
 	}
-	_, bits := ipNet.Mask.Size()
-	if bits != 128 {
-		return fmt.Errorf("%q is not an IPv6 subnet", ipNet)
+}
+
+// AllMaybeSorted walks the whole subnet map in sorted order during tests but
+// not when running tests.
+func (sm *SubnetMap[V]) AllMaybeSorted() iter.Seq2[netip.Prefix, V] {
+	return func(yield func(netip.Prefix, V) bool) {
+		if sm == nil || sm.table == nil {
+			return
+		}
+		if Testing() {
+			sm.table.AllSorted6()(yield)
+		} else {
+			sm.table.All6()(yield)
+		}
 	}
-	plen, _ := ipNet.Mask.Size()
-	sm.tree.SetOrUpdate(patricia.NewIPv6Address(ipNet.IP.To16(), uint(plen)), v, updateFunc)
-	return nil
 }
 
-// Iter enables iteration of the SubnetMap, calling f for every entry. If f returns an error, the iteration is aborted.
-func (sm *SubnetMap[V]) Iter(f func(address patricia.IPv6Address, tags [][]V) error) error {
-	iter := sm.tree.Iterate()
-	for iter.Next() {
-		if err := f(iter.Address(), iter.TagsFromRoot()); err != nil {
-			return err
+// Supernets returns an iterator over all supernet routes that cover the given
+// prefix. The iteration order is reverse-CIDR: from longest prefix match (LPM)
+// towards least-specific routes.
+func (sm *SubnetMap[V]) Supernets(prefix netip.Prefix) iter.Seq2[netip.Prefix, V] {
+	return func(yield func(netip.Prefix, V) bool) {
+		if sm == nil || sm.table == nil {
+			return
 		}
+		sm.table.Supernets(prefix)(yield)
 	}
-	return nil
 }
 
-// NewSubnetMap creates a subnetmap from a map. Unlike user-provided
-// configuration, this function is stricter and require everything to
-// be IPv6 subnets.
+// NewSubnetMap creates a subnetmap from a map. It should not be used in a hot
+// path as it builds the subnet from a map keyed by strings.
 func NewSubnetMap[V any](from map[string]V) (*SubnetMap[V], error) {
-	trie := &SubnetMap[V]{tree.NewTreeV6[V]()}
+	sm := &SubnetMap[V]{table: &bart.Table[V]{}}
 	if from == nil {
-		return trie, nil
+		return sm, nil
 	}
 	for k, v := range from {
-		trie.Set(k, v)
+		key, err := SubnetMapParseKey(k)
+		if err != nil {
+			return nil, fmt.Errorf("failed to parse key %s: %w", k, err)
+		}
+		sm.Set(key, v)
 	}
-	return trie, nil
+	return sm, nil
 }
 
 // MustNewSubnetMap creates a subnet from a map and panic in case of a
@@ -157,9 +169,10 @@ func LooksLikeSubnetMap(v reflect.Value) (result bool) {
 	return
 }
 
-// SubnetMapUnmarshallerHook decodes SubnetMap and notably check that
-// valid networks are provided as key. It also accepts a single value
-// instead of a map for backward compatibility.
+// SubnetMapUnmarshallerHook decodes SubnetMap and notably check that valid
+// networks are provided as key. It also accepts a single value instead of a map
+// for backward compatibility. It should not be used in hot paths as it builds
+// an intermediate map.
 func SubnetMapUnmarshallerHook[V any]() mapstructure.DecodeHookFunc {
 	return func(from, to reflect.Value) (any, error) {
 		if to.Type() != reflect.TypeOf(SubnetMap[V]{}) {
@@ -184,7 +197,7 @@ func SubnetMapUnmarshallerHook[V any]() mapstructure.DecodeHookFunc {
 				if err != nil {
 					return nil, fmt.Errorf("failed to parse key %s: %w", key, err)
 				}
-				output[key] = v.Interface()
+				output[key.String()] = v.Interface()
 			}
 		} else {
 			// Second case, we have a single value and we let mapstructure handles it
@@ -211,40 +224,36 @@ func SubnetMapUnmarshallerHook[V any]() mapstructure.DecodeHookFunc {
 	}
 }
 
-// SubnetMapParseKey decodes and validates a key used in SubnetMap from a network string.
-func SubnetMapParseKey(k string) (string, error) {
-	var key string
+// PrefixTo16 converts an IPv4 prefix to an IPv4-mapped IPv6 prefix.
+// IPv6 prefixes are returned as-is.
+func PrefixTo16(prefix netip.Prefix) netip.Prefix {
+	if prefix.Addr().Is6() {
+		return prefix
+	}
+	// Convert IPv4 to IPv4-mapped IPv6
+	return netip.PrefixFrom(netip.AddrFrom16(prefix.Addr().As16()), prefix.Bits()+96)
+}
+
+// SubnetMapParseKey parses a prefix or an IP address into a netip.Prefix that
+// can be used in a map.
+func SubnetMapParseKey(k string) (netip.Prefix, error) {
+	// Subnet
 	if strings.Contains(k, "/") {
-		// Subnet
-		_, ipNet, err := net.ParseCIDR(k)
+		key, err := netip.ParsePrefix(k)
 		if err != nil {
-			return "", err
-		}
-		// Convert key to IPv6
-		ones, bits := ipNet.Mask.Size()
-		if bits != 32 && bits != 128 {
-			return "", fmt.Errorf("key %s has invalid netmask", k)
-		}
-		if bits == 32 {
-			key = fmt.Sprintf("::ffff:%s/%d", ipNet.IP.String(), ones+96)
-		} else if ipNet.IP.To4() != nil {
-			key = fmt.Sprintf("::ffff:%s/%d", ipNet.IP.String(), ones)
-		} else {
-			key = ipNet.String()
-		}
-	} else {
-		// IP
-		ip := net.ParseIP(k)
-		if ip == nil {
-			return "", fmt.Errorf("key %s is not a valid subnet", k)
-		}
-		if ipv4 := ip.To4(); ipv4 != nil {
-			key = fmt.Sprintf("::ffff:%s/128", ipv4.String())
-		} else {
-			key = fmt.Sprintf("%s/128", ip.String())
+			return netip.Prefix{}, err
 		}
+		return PrefixTo16(key), nil
+	}
+	// IP address
+	key, err := netip.ParseAddr(k)
+	if err != nil {
+		return netip.Prefix{}, err
+	}
+	if key.Is4() {
+		return PrefixTo16(netip.PrefixFrom(key, 32)), nil
 	}
-	return key, nil
+	return netip.PrefixFrom(key, 128), nil
 }
 
 // MarshalYAML turns a subnet into a map that can be marshaled.
diff --git a/console/data/docs/06-internals.md b/console/data/docs/06-internals.md
index cc88999f..b48ace31 100644
--- a/console/data/docs/06-internals.md
+++ b/console/data/docs/06-internals.md
@@ -149,17 +149,18 @@ agent](https://github.com/slayercat/GoSNMPServer).
 The BMP server uses [GoBGP](http://github.com/osrg/gobgp)'s
 implementation. GoBGP does not have a BMP collector, but it's just a
 simple TCP connection receiving BMP messages and we use GoBGP to parse
-them. The data we need is stored in a Patricia tree.
+them.
 
-[github.com/kentik/patricia](https://github.com/kentik/patricia)
-implements a fast Patricia tree for IP lookup in a tree of subnets. It
-leverages Go generics to make the code safe. It is used both for
-configuring subnet-dependent settings (eg SNMP communities) and for
-storing data received using BMP.
+[github.com/gaissmai/bart](https://github.com/gaissmai/bart) implements a fast
+trie for IP lookup using an adaptation of Knuth's ART algoritjm. It is used both
+for configuring subnet-dependent settings and for storing data received using
+BMP. In case of BMP, we store the routes in a map indexed by a prefix index
+(dynamically allocated, with a free list) and a route index (contiguously
+allocated from 0). Only the prefix index is stored inside the tree.
 
 To save memory, *Akvorado* "interns" next-hops, origin AS, AS paths
 and communities. Each unique combination is associated to a
-reference-counter 32-bit integer, which is used in the RIB in place of
+reference-counted 32-bit integer, which is used in the RIB in place of
 the original information.
 
 ## Schema
diff --git a/console/data/docs/99-changelog.md b/console/data/docs/99-changelog.md
index 8dc7724f..861ad51f 100644
--- a/console/data/docs/99-changelog.md
+++ b/console/data/docs/99-changelog.md
@@ -10,6 +10,10 @@ identified with a specific icon:
 - 🩹: bug fix
 - 🌱: miscellaneous change
 
+## Unreleased
+
+- 🌱 *outlet*: improve performance of the BMP routing provider
+
 ## 2.0.0-beta.3 - 2025-08-11
 
 > [!CAUTION]
diff --git a/go.mod b/go.mod
index 98698628..986e9af4 100644
--- a/go.mod
+++ b/go.mod
@@ -16,6 +16,7 @@ require (
 	github.com/eapache/go-resiliency v1.7.0
 	github.com/expr-lang/expr v1.17.5
 	github.com/fsnotify/fsnotify v1.9.0
+	github.com/gaissmai/bart v0.23.0
 	github.com/gin-gonic/gin v1.10.1
 	github.com/glebarez/sqlite v1.11.0
 	github.com/go-playground/validator/v10 v10.20.0
@@ -26,7 +27,6 @@ require (
 	github.com/grpc-ecosystem/go-grpc-middleware/providers/prometheus v1.1.0
 	github.com/hashicorp/go-version v1.7.0
 	github.com/itchyny/gojq v0.12.17
-	github.com/kentik/patricia v1.2.1
 	github.com/kylelemons/godebug v1.1.0
 	github.com/mattn/go-isatty v0.0.20
 	github.com/netsampler/goflow2/v2 v2.2.3
@@ -35,6 +35,7 @@ require (
 	github.com/opencontainers/image-spec v1.1.1
 	github.com/oschwald/maxminddb-golang/v2 v2.0.0-beta.8
 	github.com/osrg/gobgp/v3 v3.37.0
+	github.com/planetscale/vtprotobuf v0.6.1-0.20240319094008-0393e58bdf10
 	github.com/prometheus/client_golang v1.23.0
 	github.com/rs/zerolog v1.34.0
 	github.com/scrapli/scrapligo v1.3.3
@@ -154,7 +155,6 @@ require (
 	github.com/pelletier/go-toml/v2 v2.2.2 // indirect
 	github.com/pierrec/lz4/v4 v4.1.22 // indirect
 	github.com/pkg/errors v0.9.1 // indirect
-	github.com/planetscale/vtprotobuf v0.6.1-0.20240319094008-0393e58bdf10 // indirect
 	github.com/pmezard/go-difflib v1.0.1-0.20181226105442-5d4384ee4fb2 // indirect
 	github.com/power-devops/perfstat v0.0.0-20210106213030-5aafc221ea8c // indirect
 	github.com/prometheus/client_model v0.6.2 // indirect
@@ -217,5 +217,3 @@ tool (
 	gotest.tools/gotestsum
 	honnef.co/go/tools/cmd/staticcheck
 )
-
-replace github.com/kentik/patricia => github.com/netixx/patricia v0.0.0-20240221142110-a89b0dc418dd
diff --git a/go.sum b/go.sum
index 97d508f3..ff5a9de2 100644
--- a/go.sum
+++ b/go.sum
@@ -112,6 +112,8 @@ github.com/fsnotify/fsnotify v1.9.0 h1:2Ml+OJNzbYCTzsxtv8vKSFD9PbJjmhYF14k/jKC7S
 github.com/fsnotify/fsnotify v1.9.0/go.mod h1:8jBTzvmWwFyi3Pb8djgCCO5IBqzKJ/Jwo8TRcHyHii0=
 github.com/gabriel-vasile/mimetype v1.4.3 h1:in2uUcidCuFcDKtdcBxlR0rJ1+fsokWf+uqxgUFjbI0=
 github.com/gabriel-vasile/mimetype v1.4.3/go.mod h1:d8uq/6HKRL6CGdk+aubisF/M5GcPfT7nKyLpA0lbSSk=
+github.com/gaissmai/bart v0.23.0 h1:ct+78nySK5MaO+citQAUeef7QZ0ApXM3b+AYuCZYGIk=
+github.com/gaissmai/bart v0.23.0/go.mod h1:RpLtt3lWq1BoRz3AAyDAJ7jhLWBkYhVCfi+ximB2t68=
 github.com/gin-contrib/sse v0.1.0 h1:Y/yl/+YNO8GZSjAhjMsSuLt29uWRFHdHYUb5lYOV9qE=
 github.com/gin-contrib/sse v0.1.0/go.mod h1:RHrZQHXnP2xjPF+u1gW/2HnVO7nvIa9PG3Gm+fLHvGI=
 github.com/gin-gonic/gin v1.7.7/go.mod h1:axIBovoeJpVj8S3BwE0uPMTeReE4+AfFtqpqaZ1qq1U=
@@ -301,8 +303,6 @@ github.com/morikuni/aec v1.0.0 h1:nP9CBfwrvYnBRgY6qfDQkygYDmYwOilePFkwzv4dU8A=
 github.com/morikuni/aec v1.0.0/go.mod h1:BbKIizmSmc5MMPqRYbxO4ZU0S0+P200+tUnFx7PXmsc=
 github.com/munnerz/goautoneg v0.0.0-20191010083416-a7dc8b61c822 h1:C3w9PqII01/Oq1c1nUAm88MOHcQC9l5mIlSMApZMrHA=
 github.com/munnerz/goautoneg v0.0.0-20191010083416-a7dc8b61c822/go.mod h1:+n7T8mK8HuQTcFwEeznm/DIxMOiR9yIdICNftLE1DvQ=
-github.com/netixx/patricia v0.0.0-20240221142110-a89b0dc418dd h1:9d/fcRKG/qQk8EYMix2r+zxWE7pEr7Zh+j/xTov4ZWI=
-github.com/netixx/patricia v0.0.0-20240221142110-a89b0dc418dd/go.mod h1:6jY40ESetsbfi04/S12iJlsiS6DYL2B2W+WAcqoDHtw=
 github.com/netsampler/goflow2/v2 v2.2.3 h1:uItOl69jDHuNJR+LGZ1JFs4/9qzBgbm95SP0QTMzGwo=
 github.com/netsampler/goflow2/v2 v2.2.3/go.mod h1:qC4yiY8Rw7SEwrpPy+w2ktnXc403Vilt2ZyBEYE5iJQ=
 github.com/niemeyer/pretty v0.0.0-20200227124842-a10e7caefd8e/go.mod h1:zD1mROLANZcx1PVRCS0qkT7pwLkGfwJo4zjcN/Tysno=
diff --git a/orchestrator/clickhouse/networks.go b/orchestrator/clickhouse/networks.go
index f356ba94..d9c9f4d2 100644
--- a/orchestrator/clickhouse/networks.go
+++ b/orchestrator/clickhouse/networks.go
@@ -13,8 +13,6 @@ import (
 	"strconv"
 	"time"
 
-	"github.com/kentik/patricia"
-
 	"akvorado/common/helpers"
 	"akvorado/common/schema"
 	"akvorado/orchestrator/geoip"
@@ -58,30 +56,30 @@ func (c *Component) networksCSVRefresher() {
 
 		// Add content of all geoip databases
 		err := c.d.GeoIP.IterASNDatabases(func(prefix netip.Prefix, data geoip.ASNInfo) error {
-			subV6Str, err := helpers.SubnetMapParseKey(prefix.String())
-			if err != nil {
-				return err
-			}
+			subV6Prefix := helpers.PrefixTo16(prefix)
 			attrs := NetworkAttributes{
 				ASN: data.ASNumber,
 			}
-			return networks.Update(subV6Str, attrs, overrideNetworkAttrs(attrs))
+			networks.Update(subV6Prefix, func(existing NetworkAttributes, _ bool) NetworkAttributes {
+				return mergeNetworkAttrs(existing, attrs)
+			})
+			return nil
 		})
 		if err != nil {
 			c.r.Err(err).Msg("unable to iter over ASN databases")
 			return
 		}
 		err = c.d.GeoIP.IterGeoDatabases(func(prefix netip.Prefix, data geoip.GeoInfo) error {
-			subV6Str, err := helpers.SubnetMapParseKey(prefix.String())
-			if err != nil {
-				return err
-			}
+			subV6Prefix := helpers.PrefixTo16(prefix)
 			attrs := NetworkAttributes{
 				State:   data.State,
 				Country: data.Country,
 				City:    data.City,
 			}
-			return networks.Update(subV6Str, attrs, overrideNetworkAttrs(attrs))
+			networks.Update(subV6Prefix, func(existing NetworkAttributes, _ bool) NetworkAttributes {
+				return mergeNetworkAttrs(existing, attrs)
+			})
+			return nil
 		})
 		if err != nil {
 			c.r.Err(err).Msg("unable to iter over geo databases")
@@ -93,13 +91,10 @@ func (c *Component) networksCSVRefresher() {
 			defer c.networkSourcesLock.RUnlock()
 			for _, networkList := range c.networkSources {
 				for _, val := range networkList {
-					if err := networks.Update(
-						val.Prefix.String(),
-						val.NetworkAttributes,
-						overrideNetworkAttrs(val.NetworkAttributes),
-					); err != nil {
-						return err
-					}
+					subV6Prefix := helpers.PrefixTo16(val.Prefix)
+					networks.Update(subV6Prefix, func(existing NetworkAttributes, _ bool) NetworkAttributes {
+						return mergeNetworkAttrs(existing, val.NetworkAttributes)
+					})
 				}
 			}
 			return nil
@@ -110,16 +105,10 @@ func (c *Component) networksCSVRefresher() {
 		// Add static network sources
 		if c.config.Networks != nil {
 			// Update networks with static network source
-			err := c.config.Networks.Iter(func(address patricia.IPv6Address, tags [][]NetworkAttributes) error {
-				return networks.Update(
-					address.String(),
-					tags[len(tags)-1][0],
-					overrideNetworkAttrs(tags[len(tags)-1][0]),
-				)
-			})
-			if err != nil {
-				c.r.Err(err).Msg("unable to update with static network sources")
-				return
+			for prefix, attrs := range c.config.Networks.All() {
+				networks.Update(prefix, func(existing NetworkAttributes, _ bool) NetworkAttributes {
+					return mergeNetworkAttrs(existing, attrs)
+				})
 			}
 		}
 
@@ -142,12 +131,13 @@ func (c *Component) networksCSVRefresher() {
 		gzipWriter := gzip.NewWriter(tmpfile)
 		csvWriter := csv.NewWriter(gzipWriter)
 		csvWriter.Write([]string{"network", "name", "role", "site", "region", "country", "state", "city", "tenant", "asn"})
-		networks.Iter(func(address patricia.IPv6Address, tags [][]NetworkAttributes) error {
-			current := NetworkAttributes{}
-			for _, nodeTags := range tags {
-				for _, tag := range nodeTags {
-					current = mergeNetworkAttrs(current, tag)
-				}
+		for prefix, leafAttrs := range networks.AllMaybeSorted() {
+			// Merge attributes from root to leaf for hierarchical inheritance.
+			// Supernets() returns in reverse-CIDR order (LPM to root), so we
+			// merge in that order.
+			current := leafAttrs
+			for _, attrs := range networks.Supernets(prefix) {
+				current = mergeNetworkAttrs(attrs, current)
 			}
 
 			var asnVal string
@@ -155,7 +145,7 @@ func (c *Component) networksCSVRefresher() {
 				asnVal = strconv.Itoa(int(current.ASN))
 			}
 			csvWriter.Write([]string{
-				address.String(),
+				prefix.String(),
 				current.Name,
 				current.Role,
 				current.Site,
@@ -166,8 +156,7 @@ func (c *Component) networksCSVRefresher() {
 				current.Tenant,
 				asnVal,
 			})
-			return nil
-		})
+		}
 		csvWriter.Flush()
 		gzipWriter.Close()
 
@@ -195,12 +184,6 @@ func (c *Component) networksCSVRefresher() {
 	}
 }
 
-func overrideNetworkAttrs(newAttrs NetworkAttributes) func(existing NetworkAttributes) NetworkAttributes {
-	return func(existing NetworkAttributes) NetworkAttributes {
-		return mergeNetworkAttrs(existing, newAttrs)
-	}
-}
-
 func mergeNetworkAttrs(existing, newAttrs NetworkAttributes) NetworkAttributes {
 	if newAttrs.ASN != 0 {
 		existing.ASN = newAttrs.ASN
diff --git a/outlet/metadata/provider/static/source.go b/outlet/metadata/provider/static/source.go
index 6999cbac..54c0920d 100644
--- a/outlet/metadata/provider/static/source.go
+++ b/outlet/metadata/provider/static/source.go
@@ -42,9 +42,9 @@ func (i exporterInfo) toExporterConfiguration() ExporterConfiguration {
 // initStaticExporters initializes the reconciliation map for exporter configurations
 // with the static prioritized data from exporters' Configuration.
 func (p *Provider) initStaticExporters() {
-	staticExportersMap := p.exporters.Load().ToMap()
-	staticExporters := make([]exporterInfo, 0, len(staticExportersMap))
-	for subnet, config := range staticExportersMap {
+	staticExporters := make([]exporterInfo, 0)
+	staticExportersMap := p.exporters.Load()
+	for subnet, config := range staticExportersMap.All() {
 		interfaces := make([]exporterInterface, 0, len(config.IfIndexes))
 		for ifindex, iface := range config.IfIndexes {
 			interfaces = append(interfaces, exporterInterface{
@@ -58,7 +58,7 @@ func (p *Provider) initStaticExporters() {
 				Exporter: provider.Exporter{
 					Name: config.Name,
 				},
-				ExporterSubnet: subnet,
+				ExporterSubnet: subnet.String(),
 				Default:        config.Default,
 				Interfaces:     interfaces,
 			},
@@ -88,7 +88,7 @@ func (p *Provider) UpdateSource(ctx context.Context, name string, source remoted
 				continue
 			}
 			// Concurrency for same Exporter config across multiple remote data sources is not handled
-			finalMap[exporterSubnet] = exporterData.toExporterConfiguration()
+			finalMap[exporterSubnet.String()] = exporterData.toExporterConfiguration()
 		}
 	}
 	for _, exporterData := range p.exportersMap["static"] {
@@ -98,10 +98,10 @@ func (p *Provider) UpdateSource(ctx context.Context, name string, source remoted
 			continue
 		}
 		// This overrides duplicates config for an Exporter if it's also defined as static
-		finalMap[exporterSubnet] = exporterData.toExporterConfiguration()
+		finalMap[exporterSubnet.String()] = exporterData.toExporterConfiguration()
 	}
 	p.exportersLock.Unlock()
-	exporters, err := helpers.NewSubnetMap[ExporterConfiguration](finalMap)
+	exporters, err := helpers.NewSubnetMap(finalMap)
 	if err != nil {
 		return 0, errors.New("cannot create subnetmap")
 	}
diff --git a/outlet/routing/provider/bmp/config.go b/outlet/routing/provider/bmp/config.go
index 1f9b0c16..e834b454 100644
--- a/outlet/routing/provider/bmp/config.go
+++ b/outlet/routing/provider/bmp/config.go
@@ -6,6 +6,7 @@ package bmp
 import (
 	"time"
 
+	"akvorado/common/helpers"
 	"akvorado/outlet/routing/provider"
 )
 
@@ -24,29 +25,24 @@ type Configuration struct {
 	CollectCommunities bool
 	// Keep tells how long to keep routes from a BMP client when it goes down
 	Keep time.Duration `validate:"min=1s"`
-	// RIBPeerRemovalMaxTime tells the maximum time the removal worker should run to remove a peer
-	RIBPeerRemovalMaxTime time.Duration `validate:"min=10ms"`
-	// RIBPeerRemovalSleepInterval tells how much time to sleep between two runs of the removal worker
-	RIBPeerRemovalSleepInterval time.Duration `validate:"min=10ms"`
-	// RIBPeerRemovalMaxQueue tells how many pending removal requests to keep
-	RIBPeerRemovalMaxQueue int `validate:"min=1"`
-	// RIBPeerRemovalBatchRoutes tells how many routes to remove before checking
-	// if we have a higher priority request. This is only if RIB is in memory
-	// mode.
-	RIBPeerRemovalBatchRoutes int `validate:"min=1"`
 }
 
 // DefaultConfiguration represents the default configuration for the BMP server
 func DefaultConfiguration() provider.Configuration {
 	return Configuration{
-		Listen:                      ":10179",
-		CollectASNs:                 true,
-		CollectASPaths:              true,
-		CollectCommunities:          true,
-		Keep:                        5 * time.Minute,
-		RIBPeerRemovalMaxTime:       100 * time.Millisecond,
-		RIBPeerRemovalSleepInterval: 500 * time.Millisecond,
-		RIBPeerRemovalMaxQueue:      10000,
-		RIBPeerRemovalBatchRoutes:   5000,
+		Listen:             ":10179",
+		CollectASNs:        true,
+		CollectASPaths:     true,
+		CollectCommunities: true,
+		Keep:               5 * time.Minute,
 	}
 }
+
+func init() {
+	helpers.RegisterMapstructureDeprecatedFields[Configuration](
+		"RIBPeerRemovalMaxTime",
+		"RIBPeerRemovalSleepInterval",
+		"RIBPeerRemovalMaxQueue",
+		"RIBPeerRemovalBatchRoutes",
+	)
+}
diff --git a/outlet/routing/provider/bmp/events.go b/outlet/routing/provider/bmp/events.go
index fe5fcc80..7f613489 100644
--- a/outlet/routing/provider/bmp/events.go
+++ b/outlet/routing/provider/bmp/events.go
@@ -100,18 +100,18 @@ func (p *Provider) removePeer(pkey peerKey, reason string) {
 	exporterStr := pkey.exporter.Addr().Unmap().String()
 	peerStr := pkey.ip.Unmap().String()
 	p.r.Info().Msgf("remove peer %s for exporter %s (reason: %s)", peerStr, exporterStr, reason)
-	select {
-	case p.peerRemovalChan <- pkey:
+	start := p.d.Clock.Now()
+	defer p.metrics.locked.WithLabelValues("peer-removal").Observe(
+		float64(p.d.Clock.Now().Sub(start).Nanoseconds()) / 1000 / 1000 / 1000)
+	pinfo, ok := p.peers[pkey]
+	if !ok {
 		return
-	default:
 	}
-	p.metrics.peerRemovalQueueFull.WithLabelValues(exporterStr).Inc()
-	p.mu.Unlock()
-	select {
-	case p.peerRemovalChan <- pkey:
-	case <-p.t.Dying():
-	}
-	p.mu.Lock()
+	removed := p.rib.flushPeer(pinfo.reference)
+	delete(p.peers, pkey)
+	p.metrics.routes.WithLabelValues(exporterStr).Sub(float64(removed))
+	p.metrics.peers.WithLabelValues(exporterStr).Dec()
+	p.metrics.peerRemovalDone.WithLabelValues(exporterStr).Inc()
 }
 
 // markExporterAsStale marks all peers from an exporter as stale.
@@ -300,8 +300,7 @@ func (p *Provider) handleRouteMonitoring(pkey peerKey, body *bmp.BMPRouteMonitor
 				plen += 96
 			}
 			pf, _ := netip.AddrFromSlice(prefix)
-			rta.plen = uint8(plen)
-			added += p.rib.addPrefix(pf, plen, route{
+			added += p.rib.addPrefix(netip.PrefixFrom(pf, plen), route{
 				peer: pinfo.reference,
 				nlri: p.rib.nlris.Put(nlri{
 					family: bgp.RF_IPv4_UC,
@@ -310,6 +309,7 @@ func (p *Provider) handleRouteMonitoring(pkey peerKey, body *bmp.BMPRouteMonitor
 				}),
 				nextHop:    p.rib.nextHops.Put(nextHop(nh)),
 				attributes: p.rib.rtas.Put(rta),
+				prefixLen:  uint8(plen),
 			})
 		}
 		for _, ipprefix := range update.WithdrawnRoutes {
@@ -325,7 +325,7 @@ func (p *Provider) handleRouteMonitoring(pkey peerKey, body *bmp.BMPRouteMonitor
 				path:   ipprefix.PathIdentifier(),
 				rd:     pkey.distinguisher,
 			}); ok {
-				removed += p.rib.removePrefix(pf, plen, route{
+				removed += p.rib.removePrefix(netip.PrefixFrom(pf, plen), route{
 					peer: pinfo.reference,
 					nlri: nlriRef,
 				})
@@ -394,8 +394,7 @@ func (p *Provider) handleRouteMonitoring(pkey peerKey, body *bmp.BMPRouteMonitor
 			}
 			switch attr.(type) {
 			case *bgp.PathAttributeMpReachNLRI:
-				rta.plen = uint8(plen)
-				added += p.rib.addPrefix(pf, plen, route{
+				added += p.rib.addPrefix(netip.PrefixFrom(pf, plen), route{
 					peer: pinfo.reference,
 					nlri: p.rib.nlris.Put(nlri{
 						family: bgp.AfiSafiToRouteFamily(ipprefix.AFI(), ipprefix.SAFI()),
@@ -404,6 +403,7 @@ func (p *Provider) handleRouteMonitoring(pkey peerKey, body *bmp.BMPRouteMonitor
 					}),
 					nextHop:    p.rib.nextHops.Put(nextHop(nh)),
 					attributes: p.rib.rtas.Put(rta),
+					prefixLen:  uint8(plen),
 				})
 			case *bgp.PathAttributeMpUnreachNLRI:
 				if nlriRef, ok := p.rib.nlris.Ref(nlri{
@@ -411,7 +411,7 @@ func (p *Provider) handleRouteMonitoring(pkey peerKey, body *bmp.BMPRouteMonitor
 					rd:     rd,
 					path:   ipprefix.PathIdentifier(),
 				}); ok {
-					removed += p.rib.removePrefix(pf, plen, route{
+					removed += p.rib.removePrefix(netip.PrefixFrom(pf, plen), route{
 						peer: pinfo.reference,
 						nlri: nlriRef,
 					})
@@ -427,6 +427,6 @@ func (p *Provider) isAcceptedRD(rd RD) bool {
 	if len(p.acceptedRDs) == 0 {
 		return true
 	}
-	_, ok := p.acceptedRDs[uint64(rd)]
+	_, ok := p.acceptedRDs[rd]
 	return ok
 }
diff --git a/outlet/routing/provider/bmp/lookup.go b/outlet/routing/provider/bmp/lookup.go
index 0b77ff2c..f0d1e2f6 100644
--- a/outlet/routing/provider/bmp/lookup.go
+++ b/outlet/routing/provider/bmp/lookup.go
@@ -8,8 +8,6 @@ import (
 	"errors"
 	"net/netip"
 
-	"github.com/kentik/patricia"
-
 	"akvorado/outlet/routing/provider"
 )
 
@@ -30,43 +28,44 @@ func (p *Provider) Lookup(_ context.Context, ip netip.Addr, nh netip.Addr, _ net
 	if !p.active.Load() {
 		return LookupResult{}, nil
 	}
-	v6 := patricia.NewIPv6Address(ip.AsSlice(), 128)
-
 	p.mu.RLock()
 	defer p.mu.RUnlock()
 
-	bestFound := false
-	found := false
-	_, routes := p.rib.tree.FindDeepestTagsWithFilter(v6, func(route route) bool {
-		if bestFound {
-			// We already have the best route, skip remaining routes
-			return false
+	// Find the most specific prefix for this IP
+	prefixIdx, found := p.rib.tree.Lookup(ip)
+	if !found {
+		return LookupResult{}, errNoRouteFound
+	}
+
+	// Find the best route, preferring exact next hop match
+	var selectedRoute route
+	routeFound := false
+
+	for route := range p.rib.iterateRoutesForPrefixIndex(prefixIdx) {
+		// If we don't have a match already, use this one.
+		if !routeFound {
+			selectedRoute = route
+			routeFound = true
 		}
 		if p.rib.nextHops.Get(route.nextHop) == nextHop(nh) {
 			// Exact match found, use it and don't search further
-			bestFound = true
-			return true
-		}
-		// If we don't have a match already, use this one.
-		if !found {
-			found = true
-			return true
+			selectedRoute = route
+			break
 		}
-		// Otherwise, skip it
-		return false
-	})
-	if len(routes) == 0 {
+	}
+
+	if !routeFound {
 		return LookupResult{}, errNoRouteFound
 	}
-	route := routes[len(routes)-1]
-	attributes := p.rib.rtas.Get(route.attributes)
+
+	attributes := p.rib.rtas.Get(selectedRoute.attributes)
 	// The next hop is updated from the rib in every case, because the user
 	// "opted in" for bmp as source if the lookup result is evaluated
-	nh = netip.Addr(p.rib.nextHops.Get(route.nextHop))
+	nh = netip.Addr(p.rib.nextHops.Get(selectedRoute.nextHop))
 
 	// Prefix len is v6 coded in the bmp rib. We need to substract 96 if it's a v4 prefix
-	plen := attributes.plen
-	if ip.Is4() || ip.Is4In6() {
+	plen := selectedRoute.prefixLen
+	if ip.Is4In6() {
 		plen = plen - 96
 	}
 	return LookupResult{
diff --git a/outlet/routing/provider/bmp/metrics.go b/outlet/routing/provider/bmp/metrics.go
index 6dd7e443..60564cd5 100644
--- a/outlet/routing/provider/bmp/metrics.go
+++ b/outlet/routing/provider/bmp/metrics.go
@@ -6,19 +6,17 @@ package bmp
 import "akvorado/common/reporter"
 
 type metrics struct {
-	openedConnections    *reporter.CounterVec
-	closedConnections    *reporter.CounterVec
-	peers                *reporter.GaugeVec
-	routes               *reporter.GaugeVec
-	ignoredNlri          *reporter.CounterVec
-	messages             *reporter.CounterVec
-	errors               *reporter.CounterVec
-	ignored              *reporter.CounterVec
-	panics               *reporter.CounterVec
-	locked               *reporter.SummaryVec
-	peerRemovalDone      *reporter.CounterVec
-	peerRemovalPartial   *reporter.CounterVec
-	peerRemovalQueueFull *reporter.CounterVec
+	openedConnections *reporter.CounterVec
+	closedConnections *reporter.CounterVec
+	peers             *reporter.GaugeVec
+	routes            *reporter.GaugeVec
+	ignoredNlri       *reporter.CounterVec
+	messages          *reporter.CounterVec
+	errors            *reporter.CounterVec
+	ignored           *reporter.CounterVec
+	panics            *reporter.CounterVec
+	locked            *reporter.SummaryVec
+	peerRemovalDone   *reporter.CounterVec
 }
 
 // initMetrics initialize the metrics for the BMP component.
@@ -101,18 +99,4 @@ func (p *Provider) initMetrics() {
 		},
 		[]string{"exporter"},
 	)
-	p.metrics.peerRemovalPartial = p.r.CounterVec(
-		reporter.CounterOpts{
-			Name: "removed_partial_peers_total",
-			Help: "Number of peers partially removed from the RIB.",
-		},
-		[]string{"exporter"},
-	)
-	p.metrics.peerRemovalQueueFull = p.r.CounterVec(
-		reporter.CounterOpts{
-			Name: "removal_queue_full_total",
-			Help: "Number of time the removal queue was full.",
-		},
-		[]string{"exporter"},
-	)
 }
diff --git a/outlet/routing/provider/bmp/release.go b/outlet/routing/provider/bmp/release.go
deleted file mode 100644
index 52cd9172..00000000
--- a/outlet/routing/provider/bmp/release.go
+++ /dev/null
@@ -1,8 +0,0 @@
-// SPDX-FileCopyrightText: 2022 Free Mobile
-// SPDX-License-Identifier: AGPL-3.0-only
-
-//go:build release
-
-package bmp
-
-const rtaHashMask = 0xffffffffffffffff
diff --git a/outlet/routing/provider/bmp/remove.go b/outlet/routing/provider/bmp/remove.go
deleted file mode 100644
index 8c3bf060..00000000
--- a/outlet/routing/provider/bmp/remove.go
+++ /dev/null
@@ -1,66 +0,0 @@
-// SPDX-FileCopyrightText: 2022 Free Mobile
-// SPDX-License-Identifier: AGPL-3.0-only
-
-package bmp
-
-import (
-	"context"
-	"time"
-)
-
-func (p *Provider) peerRemovalWorker() error {
-	dying := p.t.Dying()
-	for {
-		select {
-		case <-dying:
-			return nil
-		case pkey := <-p.peerRemovalChan:
-			exporterStr := pkey.exporter.Addr().Unmap().String()
-			for {
-				// Do one run of removal (read/write lock)
-				removed, done, duplicate := func() (int, bool, bool) {
-					start := p.d.Clock.Now()
-					ctx, cancel := context.WithTimeout(p.t.Context(context.Background()),
-						p.config.RIBPeerRemovalMaxTime)
-					p.mu.Lock()
-					defer func() {
-						cancel()
-						p.mu.Unlock()
-						p.metrics.locked.WithLabelValues("peer-removal").Observe(
-							float64(p.d.Clock.Now().Sub(start).Nanoseconds()) / 1000 / 1000 / 1000)
-					}()
-					pinfo := p.peers[pkey]
-					if pinfo == nil {
-						// Already removed (removal can be queued several times)
-						return 0, true, true
-					}
-					removed, done := p.rib.flushPeerContext(ctx, pinfo.reference,
-						p.config.RIBPeerRemovalBatchRoutes)
-					if done {
-						// Run was complete, remove the peer (we need the lock)
-						delete(p.peers, pkey)
-					}
-					return removed, done, false
-				}()
-
-				// Update stats and optionally sleep
-				p.metrics.routes.WithLabelValues(exporterStr).Sub(float64(removed))
-				if done {
-					// Run was complete, update metrics
-					if !duplicate {
-						p.metrics.peers.WithLabelValues(exporterStr).Dec()
-						p.metrics.peerRemovalDone.WithLabelValues(exporterStr).Inc()
-					}
-					break
-				}
-				// Run is incomplete, update metrics and sleep a bit
-				p.metrics.peerRemovalPartial.WithLabelValues(exporterStr).Inc()
-				select {
-				case <-dying:
-					return nil
-				case <-time.After(p.config.RIBPeerRemovalSleepInterval):
-				}
-			}
-		}
-	}
-}
diff --git a/outlet/routing/provider/bmp/rib.go b/outlet/routing/provider/bmp/rib.go
index be9a1769..e4ec85e1 100644
--- a/outlet/routing/provider/bmp/rib.go
+++ b/outlet/routing/provider/bmp/rib.go
@@ -4,25 +4,34 @@
 package bmp
 
 import (
-	"context"
+	"iter"
 	"net/netip"
-	"runtime"
-	"sync/atomic"
 	"unsafe"
 
 	"akvorado/common/helpers/intern"
 
-	"github.com/kentik/patricia"
-	tree "github.com/kentik/patricia/generics_tree"
+	"github.com/gaissmai/bart"
 	"github.com/osrg/gobgp/v3/pkg/packet/bgp"
 )
 
+// prefixIndex is a typed index for prefixes in the RIB
+type prefixIndex uint32
+
+// routeIndex is a typed index for routes within a prefix
+type routeIndex uint32
+
+// routeKey is a typed key for route map entries
+type routeKey uint64
+
 // rib represents the RIB.
 type rib struct {
-	tree     *tree.TreeV6[route]
-	nlris    *intern.Pool[nlri]
-	nextHops *intern.Pool[nextHop]
-	rtas     *intern.Pool[routeAttributes]
+	tree          *bart.Table[prefixIndex] // stores prefix indices
+	routes        map[routeKey]route       // map[routeKey]route where routeKey = (prefixIdx << 32) | routeIdx
+	nlris         *intern.Pool[nlri]
+	nextHops      *intern.Pool[nextHop]
+	rtas          *intern.Pool[routeAttributes]
+	nextPrefixID  prefixIndex   // counter for next prefix index
+	freePrefixIDs []prefixIndex // free list for reused prefix indices
 }
 
 // route contains the peer (external opaque value), the NLRI, the next
@@ -33,6 +42,7 @@ type route struct {
 	nlri       intern.Reference[nlri]
 	nextHop    intern.Reference[nextHop]
 	attributes intern.Reference[routeAttributes]
+	prefixLen  uint8
 }
 
 // nlri is the NLRI for the route (when combined with prefix). The
@@ -78,7 +88,6 @@ type routeAttributes struct {
 	asn         uint32
 	asPath      []uint32
 	communities []uint32
-	plen        uint8
 	// extendedCommunities []uint64
 	largeCommunities []bgp.LargeCommunity
 }
@@ -94,14 +103,13 @@ func (rta routeAttributes) Hash() uint64 {
 	if len(rta.communities) > 0 {
 		state.Add((*byte)(unsafe.Pointer(&rta.communities[0])), len(rta.communities)*int(unsafe.Sizeof(rta.communities[0])))
 	}
-	state.Add((*byte)(unsafe.Pointer(&rta.plen)), 1)
 	if len(rta.largeCommunities) > 0 {
 		// There is a test to check that this computation is
 		// correct (the struct is 12-byte aligned, not
 		// 16-byte).
 		state.Add((*byte)(unsafe.Pointer(&rta.largeCommunities[0])), len(rta.largeCommunities)*int(unsafe.Sizeof(rta.largeCommunities[0])))
 	}
-	return state.Sum() & rtaHashMask
+	return state.Sum()
 }
 
 // Equal tells if two route attributes are equal.
@@ -115,9 +123,6 @@ func (rta routeAttributes) Equal(orta routeAttributes) bool {
 	if len(rta.communities) != len(orta.communities) {
 		return false
 	}
-	if rta.plen != orta.plen {
-		return false
-	}
 	if len(rta.largeCommunities) != len(orta.largeCommunities) {
 		return false
 	}
@@ -139,98 +144,189 @@ func (rta routeAttributes) Equal(orta routeAttributes) bool {
 	return true
 }
 
+// newPrefixIndex allocates a new prefix index, reusing from free list if available
+func (r *rib) newPrefixIndex() prefixIndex {
+	if len(r.freePrefixIDs) > 0 {
+		id := r.freePrefixIDs[len(r.freePrefixIDs)-1]
+		r.freePrefixIDs = r.freePrefixIDs[:len(r.freePrefixIDs)-1]
+		return id
+	}
+	id := r.nextPrefixID
+	r.nextPrefixID++
+	return id
+}
+
+// freePrefixIndex returns a prefix ID to the free list
+func (r *rib) freePrefixIndex(id prefixIndex) {
+	r.freePrefixIDs = append(r.freePrefixIDs, id)
+}
+
+// makeRouteKey creates a route key from prefix and route indices
+func makeRouteKey(prefixIdx prefixIndex, routeIdx routeIndex) routeKey {
+	return routeKey((uint64(prefixIdx) << 32) | uint64(routeIdx))
+}
+
+// iterateRoutesForPrefix returns an iterator over all routes for a given prefix index
+func (r *rib) iterateRoutesForPrefixIndex(prefixIdx prefixIndex) iter.Seq[route] {
+	return func(yield func(route) bool) {
+		key := makeRouteKey(prefixIdx, 0)
+		for {
+			route, exists := r.routes[key]
+			if !exists {
+				break
+			}
+			if !yield(route) {
+				break
+			}
+			key++
+		}
+	}
+}
+
+// removeRoutes removes routes matching the predicate and compacts remaining
+// routes. If once is true, stops after removing the first matching route. If
+// prefix becomes empty, removes it from the tree and frees the prefix ID. It
+// returns the number of routes removed and a boolean to say if the prefix
+// should be removed from the tree.
+func (r *rib) removeRoutes(prefixIdx prefixIndex, shouldRemove func(route) bool, once bool) (int, bool) {
+	removed := 0
+	checkKey := makeRouteKey(prefixIdx, 0)
+	nextKey := checkKey
+	skip := false // skip remaining routes if once is true
+
+	for {
+		existingRoute, exists := r.routes[checkKey]
+		if !exists {
+			break
+		}
+
+		if !skip && shouldRemove(existingRoute) {
+			// Remove this route
+			r.nlris.Take(existingRoute.nlri)
+			r.nextHops.Take(existingRoute.nextHop)
+			r.rtas.Take(existingRoute.attributes)
+			delete(r.routes, checkKey)
+			removed++
+			if once {
+				skip = true
+			}
+		} else {
+			// Keep this route, move it to nextKey if needed
+			if checkKey != nextKey {
+				r.routes[nextKey] = existingRoute
+				delete(r.routes, checkKey)
+			}
+			nextKey++ // advance to next position for kept routes
+		}
+		checkKey++ // always advance check position
+	}
+
+	return removed, nextKey == makeRouteKey(prefixIdx, 0)
+}
+
 // addPrefix add a new route to the RIB. It returns the number of routes really added.
-func (r *rib) addPrefix(ip netip.Addr, bits int, newRoute route) int {
-	v6 := patricia.NewIPv6Address(ip.AsSlice(), uint(bits))
-	added, _ := r.tree.AddOrUpdate(v6, newRoute,
-		func(r1, r2 route) bool {
-			return r1.peer == r2.peer && r1.nlri == r2.nlri
-		}, func(old route) route {
-			r.nlris.Take(old.nlri)
-			r.nextHops.Take(old.nextHop)
-			r.rtas.Take(old.attributes)
-			return newRoute
-		})
-	if !added {
-		return 0
+func (r *rib) addPrefix(prefix netip.Prefix, newRoute route) int {
+	var prefixIdx prefixIndex
+	r.tree.Update(prefix, func(existing prefixIndex, found bool) prefixIndex {
+		if found {
+			prefixIdx = existing
+		} else {
+			prefixIdx = r.newPrefixIndex()
+		}
+		return prefixIdx
+	})
+
+	// Check if route already exists (same peer and nlri)
+	key := makeRouteKey(prefixIdx, 0)
+	for {
+		existingRoute, exists := r.routes[key]
+		if !exists {
+			// Found empty slot, add new route
+			r.routes[key] = newRoute
+			return 1
+		}
+		if existingRoute.peer == newRoute.peer && existingRoute.nlri == newRoute.nlri {
+			// Found existing route, update it
+			r.nlris.Take(existingRoute.nlri)
+			r.nextHops.Take(existingRoute.nextHop)
+			r.rtas.Take(existingRoute.attributes)
+			r.routes[key] = newRoute
+			return 0 // Not really added, just updated
+		}
+		key++
 	}
-	return 1
 }
 
 // removePrefix removes a route from the RIB. It returns the number of routes really removed.
-func (r *rib) removePrefix(ip netip.Addr, bits int, oldRoute route) int {
-	v6 := patricia.NewIPv6Address(ip.AsSlice(), uint(bits))
-	removed := r.tree.Delete(v6, func(r1, r2 route) bool {
-		// This is not enforced/documented, but the route in the tree is the first one.
-		if r1.peer == r2.peer && r1.nlri == r2.nlri {
-			r.nlris.Take(r1.nlri)
-			r.nextHops.Take(r1.nextHop)
-			r.rtas.Take(r1.attributes)
-			return true
+func (r *rib) removePrefix(prefix netip.Prefix, oldRoute route) int {
+	removedCount := 0
+	empty := false
+
+	// Use Update to access prefix and remove route
+	r.tree.Update(prefix, func(existing prefixIndex, found bool) prefixIndex {
+		if found {
+			removedCount, empty = r.removeRoutes(existing, func(route route) bool {
+				return route.peer == oldRoute.peer && route.nlri == oldRoute.nlri
+			}, true)
+			if empty {
+				r.freePrefixIndex(existing)
+				return 0
+			}
+			return existing
 		}
-		return false
-	}, oldRoute)
-	return removed
+		// We use Update() to avoid to do a double lookup because in most cases,
+		// we will remove prefix that exists. However, it is also valid to
+		// remove a prefix that does not exist. In this case, Update() created a
+		// node while we don't need it. We remove it, making this operation costly.
+		empty = true
+		return 0
+	})
+
+	if empty {
+		r.tree.Delete(prefix)
+	}
+	return removedCount
 }
 
 // flushPeer removes a whole peer from the RIB, returning the number
 // of removed routes.
 func (r *rib) flushPeer(peer uint32) int {
-	removed, _ := r.flushPeerContext(nil, peer, 0)
-	return removed
-}
-
-// flushPeerContext removes a whole peer from the RIB, with a context returning
-// the number of removed routes and a bool to say if the operation was completed
-// before cancellation.
-func (r *rib) flushPeerContext(ctx context.Context, peer uint32, steps int) (int, bool) {
-	done := atomic.Bool{}
-	stop := make(chan struct{})
-	lastStep := 0
-	if ctx != nil {
-		defer close(stop)
-		go func() {
-			select {
-			case <-stop:
-				return
-			case <-ctx.Done():
-				done.Store(true)
-			}
-		}()
+	removedTotal := 0
+	anyEmpty := false
+
+	// Iterate through all prefixes and remove peer routes.
+	for _, prefixIdx := range r.tree.All6() {
+		removed, empty := r.removeRoutes(prefixIdx, func(route route) bool {
+			return route.peer == peer
+		}, false)
+		removedTotal += removed
+		anyEmpty = anyEmpty || empty
 	}
 
-	// Flush routes
-	removed := 0
-	buf := make([]route, 0)
-	iter := r.tree.Iterate()
-	runtime.Gosched()
-	for iter.Next() {
-		removed += iter.DeleteWithBuffer(buf, func(payload route, _ route) bool {
-			if payload.peer == peer {
-				r.nlris.Take(payload.nlri)
-				r.nextHops.Take(payload.nextHop)
-				r.rtas.Take(payload.attributes)
-				return true
-			}
-			return false
-		}, route{})
-		if ctx != nil && removed/steps > lastStep {
-			runtime.Gosched()
-			lastStep = removed / steps
-			if done.Load() {
-				return removed, false
+	if anyEmpty {
+		// We need to rebuild the tree. A typical tree is 1M routes, this should
+		// be pretty fast. Moreover, loosing a peer is not a condition happening
+		// often.
+		newTree := &bart.Table[prefixIndex]{}
+		for prefix, prefixIdx := range r.tree.All6() {
+			if prefixIdx != 0 {
+				newTree.Insert(prefix, prefixIdx)
 			}
 		}
+		r.tree = newTree
 	}
-	return removed, true
+	return removedTotal
 }
 
 // newRIB initializes a new RIB.
 func newRIB() *rib {
 	return &rib{
-		tree:     tree.NewTreeV6[route](),
-		nlris:    intern.NewPool[nlri](),
-		nextHops: intern.NewPool[nextHop](),
-		rtas:     intern.NewPool[routeAttributes](),
+		tree:          &bart.Table[prefixIndex]{},
+		routes:        make(map[routeKey]route),
+		nlris:         intern.NewPool[nlri](),
+		nextHops:      intern.NewPool[nextHop](),
+		rtas:          intern.NewPool[routeAttributes](),
+		nextPrefixID:  1, // Start from 1, 0 means to be removed
+		freePrefixIDs: make([]prefixIndex, 0),
 	}
 }
diff --git a/outlet/routing/provider/bmp/root.go b/outlet/routing/provider/bmp/root.go
index 1e2e7d1d..67b1c677 100644
--- a/outlet/routing/provider/bmp/root.go
+++ b/outlet/routing/provider/bmp/root.go
@@ -25,7 +25,7 @@ type Provider struct {
 	d           *Dependencies
 	t           tomb.Tomb
 	config      Configuration
-	acceptedRDs map[uint64]struct{}
+	acceptedRDs map[RD]struct{}
 	active      atomic.Bool
 
 	address net.Addr
@@ -34,7 +34,6 @@ type Provider struct {
 	// RIB management with peers
 	rib               *rib
 	peers             map[peerKey]*peerInfo
-	peerRemovalChan   chan peerKey
 	lastPeerReference uint32
 	staleTimer        *clock.Timer
 	mu                sync.RWMutex
@@ -53,14 +52,13 @@ func (configuration Configuration) New(r *reporter.Reporter, dependencies Depend
 		d:      &dependencies,
 		config: configuration,
 
-		rib:             newRIB(),
-		peers:           make(map[peerKey]*peerInfo),
-		peerRemovalChan: make(chan peerKey, configuration.RIBPeerRemovalMaxQueue),
+		rib:   newRIB(),
+		peers: make(map[peerKey]*peerInfo),
 	}
 	if len(p.config.RDs) > 0 {
-		p.acceptedRDs = make(map[uint64]struct{})
+		p.acceptedRDs = make(map[RD]struct{})
 		for _, rd := range p.config.RDs {
-			p.acceptedRDs[uint64(rd)] = struct{}{}
+			p.acceptedRDs[rd] = struct{}{}
 		}
 	}
 	p.staleTimer = p.d.Clock.AfterFunc(time.Hour, p.removeStalePeers)
@@ -79,9 +77,6 @@ func (p *Provider) Start() error {
 	}
 	p.address = listener.Addr()
 
-	// Peer removal
-	p.t.Go(p.peerRemovalWorker)
-
 	// Listener
 	p.t.Go(func() error {
 		for {
@@ -108,10 +103,7 @@ func (p *Provider) Start() error {
 
 // Stop stops the BMP provider.
 func (p *Provider) Stop() error {
-	defer func() {
-		close(p.peerRemovalChan)
-		p.r.Info().Msg("BMP component stopped")
-	}()
+	defer p.r.Info().Msg("BMP component stopped")
 	p.r.Info().Msg("stopping BMP component")
 	p.t.Kill(nil)
 	return p.t.Wait()



Test patch:
diff --git a/cmd/testdata/configurations/bmp-to-routing/expected.yaml b/cmd/testdata/configurations/bmp-to-routing/expected.yaml
index 1f9104ad..59df94f7 100644
--- a/cmd/testdata/configurations/bmp-to-routing/expected.yaml
+++ b/cmd/testdata/configurations/bmp-to-routing/expected.yaml
@@ -9,10 +9,6 @@ paths:
       collectcommunities: true
       keep: 1h0m0s
       rds: []
-      ribpeerremovalbatchroutes: 5000
-      ribpeerremovalmaxqueue: 10000
-      ribpeerremovalmaxtime: 100ms
-      ribpeerremovalsleepinterval: 500ms
   outlet.0.core.asnproviders:
     - flow
     - routing
diff --git a/cmd/testdata/configurations/bmp-to-routing/in.yaml b/cmd/testdata/configurations/bmp-to-routing/in.yaml
index 41816752..ef4602ca 100644
--- a/cmd/testdata/configurations/bmp-to-routing/in.yaml
+++ b/cmd/testdata/configurations/bmp-to-routing/in.yaml
@@ -5,6 +5,7 @@ inlet:
     collect-asns: true
     collect-aspaths: false
     keep: 1h
+    rib-peer-removal-batch-routes: 5000
   core:
     asn-providers:
       - flow
diff --git a/common/helpers/subnetmap_test.go b/common/helpers/subnetmap_test.go
index 17d9832e..c40794cf 100644
--- a/common/helpers/subnetmap_test.go
+++ b/common/helpers/subnetmap_test.go
@@ -5,6 +5,7 @@ package helpers_test
 
 import (
 	"net/netip"
+	"slices"
 	"testing"
 
 	"github.com/gin-gonic/gin"
@@ -282,7 +283,7 @@ func TestSubnetMapParseKey(t *testing.T) {
 			} else if err == nil && tc.Error {
 				t.Fatal("SubnetMapParseKey() did not return an error")
 			}
-			if diff := helpers.Diff(res, tc.Expected); diff != "" {
+			if diff := helpers.Diff(res.String(), tc.Expected); err == nil && diff != "" {
 				t.Fatalf("Decode() (-got, +want):\n%s", diff)
 			}
 		})
@@ -303,3 +304,416 @@ func TestToMap(t *testing.T) {
 		t.Fatalf("ToMap() (-got, +want):\n%s", diff)
 	}
 }
+
+func TestSubnetMapLookup(t *testing.T) {
+	t.Run("nil", func(t *testing.T) {
+		var sm *helpers.SubnetMap[string]
+		value, ok := sm.Lookup(netip.MustParseAddr("::ffff:192.0.2.1"))
+		if ok || value != "" {
+			t.Fatalf("Lookup() == value=%q, ok=%v", value, ok)
+		}
+	})
+
+	t.Run("empty", func(t *testing.T) {
+		sm := &helpers.SubnetMap[string]{}
+		value, ok := sm.Lookup(netip.MustParseAddr("::ffff:192.0.2.1"))
+		if ok || value != "" {
+			t.Fatalf("Lookup() == value=%q, ok=%v", value, ok)
+		}
+	})
+
+	t.Run("populated", func(t *testing.T) {
+		sm := helpers.MustNewSubnetMap(map[string]string{
+			"192.0.2.0/24":  "customer1",
+			"2001:db8::/64": "customer2",
+			"10.0.0.1":      "specific",
+		})
+
+		cases := []struct {
+			ip       string
+			expected string
+			found    bool
+		}{
+			{"::ffff:192.0.2.1", "customer1", true},
+			{"::ffff:192.0.2.255", "customer1", true},
+			{"::ffff:192.0.3.1", "", false},
+			{"::ffff:10.0.0.1", "specific", true},
+			{"::ffff:10.0.0.2", "", false},
+			{"2001:db8::1", "customer2", true},
+			{"2001:db8:1::1", "", false},
+		}
+
+		for _, tc := range cases {
+			t.Run(tc.ip, func(t *testing.T) {
+				value, ok := sm.Lookup(netip.MustParseAddr(tc.ip))
+				if ok != tc.found || value != tc.expected {
+					t.Fatalf("Lookup(%s) = (%q, %v), want (%q, %v)", tc.ip, value, ok, tc.expected, tc.found)
+				}
+			})
+		}
+	})
+}
+
+func TestSubnetMapLookupOrDefault(t *testing.T) {
+	sm := helpers.MustNewSubnetMap(map[string]string{
+		"192.0.2.0/24": "customer1",
+	})
+
+	t.Run("found", func(t *testing.T) {
+		value := sm.LookupOrDefault(netip.MustParseAddr("::ffff:192.0.2.1"), "default")
+		if value != "customer1" {
+			t.Fatalf("LookupOrDefault() = %q, want %q", value, "customer1")
+		}
+	})
+
+	t.Run("not found", func(t *testing.T) {
+		value := sm.LookupOrDefault(netip.MustParseAddr("::ffff:192.0.3.1"), "default")
+		if value != "default" {
+			t.Fatalf("LookupOrDefault() = %q, want %q", value, "default")
+		}
+	})
+
+	t.Run("nil", func(t *testing.T) {
+		var sm *helpers.SubnetMap[string]
+		value := sm.LookupOrDefault(netip.MustParseAddr("::ffff:192.0.2.1"), "default")
+		if value != "default" {
+			t.Fatalf("LookupOrDefault() = %q, want %q", value, "default")
+		}
+	})
+}
+
+func TestSubnetMapSet(t *testing.T) {
+	sm := &helpers.SubnetMap[string]{}
+
+	t.Run("set IPv6 subnet", func(t *testing.T) {
+		prefix := netip.MustParsePrefix("2001:db8::/64")
+		sm.Set(prefix, "test-value")
+
+		value, ok := sm.Lookup(netip.MustParseAddr("2001:db8::1"))
+		if !ok || value != "test-value" {
+			t.Fatalf("Lookup() = (%q, %v), want (%q, %v)", value, ok, "test-value", true)
+		}
+	})
+
+	t.Run("set IPv4-mapped IPv6 subnet", func(t *testing.T) {
+		prefix := netip.MustParsePrefix("::ffff:192.0.2.0/120")
+		sm.Set(prefix, "ipv4-mapped")
+
+		value, ok := sm.Lookup(netip.MustParseAddr("::ffff:192.0.2.1"))
+		if !ok || value != "ipv4-mapped" {
+			t.Fatalf("Lookup() = (%q, %v), want (%q, %v)", value, ok, "ipv4-mapped", true)
+		}
+	})
+
+	t.Run("overwrite existing value", func(t *testing.T) {
+		prefix := netip.MustParsePrefix("2001:db8::/64")
+		sm.Set(prefix, "new-value")
+
+		value, ok := sm.Lookup(netip.MustParseAddr("2001:db8::1"))
+		if !ok || value != "new-value" {
+			t.Fatalf("Lookup() = (%q, %v), want (%q, %v)", value, ok, "new-value", true)
+		}
+	})
+}
+
+func TestSubnetMapSetPanic(t *testing.T) {
+	sm := &helpers.SubnetMap[string]{}
+
+	t.Run("panic on IPv4 subnet", func(t *testing.T) {
+		defer func() {
+			if r := recover(); r == nil {
+				t.Fatal("Set() should panic with IPv4")
+			}
+		}()
+		prefix := netip.MustParsePrefix("192.0.2.0/24")
+		sm.Set(prefix, "should-panic")
+	})
+}
+
+func TestSubnetMapUpdate(t *testing.T) {
+	sm := &helpers.SubnetMap[int]{}
+
+	t.Run("update new value", func(t *testing.T) {
+		prefix := netip.MustParsePrefix("2001:db8::/64")
+		sm.Update(prefix, func(old int, exists bool) int {
+			if !exists {
+				return 42
+			}
+			return old + 1
+		})
+
+		value, ok := sm.Lookup(netip.MustParseAddr("2001:db8::1"))
+		if !ok || value != 42 {
+			t.Fatalf("Lookup() = (%d, %v), want (%d, %v)", value, ok, 42, true)
+		}
+	})
+
+	t.Run("update existing value", func(t *testing.T) {
+		prefix := netip.MustParsePrefix("2001:db8::/64")
+		sm.Update(prefix, func(old int, exists bool) int {
+			if exists {
+				return old + 10
+			}
+			return 0
+		})
+
+		value, ok := sm.Lookup(netip.MustParseAddr("2001:db8::1"))
+		if !ok || value != 52 {
+			t.Fatalf("Lookup() = (%d, %v), want (%d, %v)", value, ok, 52, true)
+		}
+	})
+}
+
+func TestSubnetMapUpdatePanic(t *testing.T) {
+	sm := &helpers.SubnetMap[int]{}
+
+	t.Run("panic on IPv4 subnet", func(t *testing.T) {
+		defer func() {
+			if r := recover(); r == nil {
+				t.Fatal("Update() should panic with IPv4")
+			}
+		}()
+		prefix := netip.MustParsePrefix("192.0.2.0/24")
+		sm.Update(prefix, func(old int, exists bool) int { return 1 })
+	})
+}
+
+func TestSubnetMapAll(t *testing.T) {
+	t.Run("nil", func(t *testing.T) {
+		var sm *helpers.SubnetMap[string]
+		count := 0
+		for range sm.All() {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("All() count = %d, want %d", count, 0)
+		}
+	})
+
+	t.Run("empty", func(t *testing.T) {
+		sm := &helpers.SubnetMap[string]{}
+		count := 0
+		for range sm.All() {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("All() count = %d, want %d", count, 0)
+		}
+	})
+
+	t.Run("populated", func(t *testing.T) {
+		sm := helpers.MustNewSubnetMap(map[string]string{
+			"2001:db8::/64":        "ipv6",
+			"::ffff:192.0.2.0/120": "ipv4-mapped",
+		})
+
+		items := make(map[string]string)
+		for prefix, value := range sm.All() {
+			items[prefix.String()] = value
+		}
+
+		expected := map[string]string{
+			"2001:db8::/64":        "ipv6",
+			"::ffff:192.0.2.0/120": "ipv4-mapped",
+		}
+
+		if diff := helpers.Diff(items, expected); diff != "" {
+			t.Fatalf("All() (-got, +want):\n%s", diff)
+		}
+	})
+}
+
+func TestSubnetMapString(t *testing.T) {
+	t.Run("empty", func(t *testing.T) {
+		sm := &helpers.SubnetMap[string]{}
+		str := sm.String()
+		expected := "map[]"
+		if str != expected {
+			t.Fatalf("String() = %q, want %q", str, expected)
+		}
+	})
+
+	t.Run("populated", func(t *testing.T) {
+		sm := helpers.MustNewSubnetMap(map[string]string{
+			"192.0.2.0/24": "customer",
+		})
+		str := sm.String()
+		if diff := helpers.Diff(str, "map[192.0.2.0/24:customer]"); diff != "" {
+			t.Fatalf("String() (-got, +want):\n%s", diff)
+		}
+	})
+}
+
+func TestPrefixTo16(t *testing.T) {
+	cases := []struct {
+		name     string
+		input    string
+		expected string
+	}{
+		{
+			name:     "IPv4 prefix",
+			input:    "192.0.2.0/24",
+			expected: "::ffff:192.0.2.0/120",
+		},
+		{
+			name:     "IPv4 host",
+			input:    "192.0.2.1/32",
+			expected: "::ffff:192.0.2.1/128",
+		},
+		{
+			name:     "IPv6 prefix unchanged",
+			input:    "2001:db8::/64",
+			expected: "2001:db8::/64",
+		},
+		{
+			name:     "IPv6 host unchanged",
+			input:    "2001:db8::1/128",
+			expected: "2001:db8::1/128",
+		},
+		{
+			name:     "IPv4-mapped IPv6 unchanged",
+			input:    "::ffff:192.0.2.0/120",
+			expected: "::ffff:192.0.2.0/120",
+		},
+	}
+
+	for _, tc := range cases {
+		t.Run(tc.name, func(t *testing.T) {
+			prefix := netip.MustParsePrefix(tc.input)
+			result := helpers.PrefixTo16(prefix)
+			if result.String() != tc.expected {
+				t.Fatalf("PrefixTo16(%s) = %s, want %s", tc.input, result, tc.expected)
+			}
+		})
+	}
+}
+
+func TestSubnetMapSupernets(t *testing.T) {
+	t.Run("nil", func(t *testing.T) {
+		var sm *helpers.SubnetMap[string]
+		count := 0
+		for range sm.Supernets(netip.MustParsePrefix("::ffff:192.0.2.1/128")) {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("Supernets() count = %d, want %d", count, 0)
+		}
+	})
+
+	t.Run("empty", func(t *testing.T) {
+		sm := &helpers.SubnetMap[string]{}
+		count := 0
+		for range sm.Supernets(netip.MustParsePrefix("::ffff:192.0.2.1/128")) {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("Supernets() count = %d, want %d", count, 0)
+		}
+	})
+
+	t.Run("hierarchical supernets", func(t *testing.T) {
+		sm := helpers.MustNewSubnetMap(map[string]string{
+			"192.0.0.0/16": "region",
+			"192.0.2.0/24": "site",
+			"192.0.2.0/28": "rack",
+		})
+
+		// Query for 192.0.2.1/32 should find supernets in reverse-CIDR order
+		var results []string
+		var prefixes []string
+		for prefix, value := range sm.Supernets(netip.MustParsePrefix("::ffff:192.0.2.1/128")) {
+			results = append(results, value)
+			prefixes = append(prefixes, prefix.String())
+		}
+
+		expectedValues := []string{"rack", "site", "region"}
+		expectedPrefixes := []string{"::ffff:192.0.2.0/124", "::ffff:192.0.2.0/120", "::ffff:192.0.0.0/112"}
+
+		if diff := helpers.Diff(results, expectedValues); diff != "" {
+			t.Errorf("Supernets() values (-got, +want):\n%s", diff)
+		}
+		if diff := helpers.Diff(prefixes, expectedPrefixes); diff != "" {
+			t.Errorf("Supernets() prefixes (-got, +want):\n%s", diff)
+		}
+
+		count := 0
+		for range sm.Supernets(netip.MustParsePrefix("::ffff:10.0.0.1/128")) {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("Supernets() count = %d, want %d", count, 0)
+		}
+	})
+}
+
+func TestSubnetMapAllMaybeSorted(t *testing.T) {
+	t.Run("nil", func(t *testing.T) {
+		var sm *helpers.SubnetMap[string]
+		count := 0
+		for range sm.AllMaybeSorted() {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("AllMaybeSorted() count = %d, want %d", count, 0)
+		}
+	})
+
+	t.Run("empty", func(t *testing.T) {
+		sm := &helpers.SubnetMap[string]{}
+		count := 0
+		for range sm.AllMaybeSorted() {
+			count++
+		}
+		if count != 0 {
+			t.Fatalf("AllMaybeSorted() count = %d, want %d", count, 0)
+		}
+	})
+
+	t.Run("sorted vs unsorted", func(t *testing.T) {
+		sm := helpers.MustNewSubnetMap(map[string]string{
+			"192.0.2.0/28":    "rack",
+			"192.0.0.0/16":    "region",
+			"192.0.2.0/24":    "site",
+			"2001:db8:1::/64": "ipv6-site1",
+			"2001:db8::/32":   "ipv6-region",
+			"2001:db8:2::/64": "ipv6-site2",
+		})
+
+		// Collect results from All() (potentially unsorted)
+		var allPrefixes []string
+		for prefix := range sm.All() {
+			allPrefixes = append(allPrefixes, prefix.String())
+		}
+
+		// Collect results from AllMaybeSorted() (sorted during tests)
+		var sortedPrefixes []string
+		for prefix := range sm.AllMaybeSorted() {
+			sortedPrefixes = append(sortedPrefixes, prefix.String())
+		}
+
+		// Expected sorted order: IPv6 addresses first (sorted), then IPv4-mapped IPv6 (sorted)
+		expectedPrefixes := []string{
+			"::ffff:192.0.0.0/112",
+			"::ffff:192.0.2.0/120",
+			"::ffff:192.0.2.0/124",
+			"2001:db8::/32",
+			"2001:db8:1::/64",
+			"2001:db8:2::/64",
+		}
+
+		// AllMaybeSorted() should be sorted during tests
+		if diff := helpers.Diff(sortedPrefixes, expectedPrefixes); diff != "" {
+			t.Errorf("AllMaybeSorted() prefixes (-got, +want):\n%s", diff)
+		}
+
+		// All() and AllMaybeSorted() should contain the same elements (but potentially different order)
+		if len(allPrefixes) != len(sortedPrefixes) {
+			t.Errorf("All() returned %d prefixes, AllMaybeSorted() returned %d", len(allPrefixes), len(sortedPrefixes))
+		}
+
+		// Verify that All() and AllMaybeSorted() return different orders (otherwise test is meaningless)
+		if slices.Equal(allPrefixes, sortedPrefixes) {
+			t.Skip("All() and AllMaybeSorted() returned identical order")
+		}
+	})
+}
diff --git a/common/helpers/tests_diff.go b/common/helpers/tests_diff.go
index f0bff2af..d33747fc 100644
--- a/common/helpers/tests_diff.go
+++ b/common/helpers/tests_diff.go
@@ -30,6 +30,7 @@ func defaultPrettyFormatters() map[reflect.Type]any {
 	result := map[reflect.Type]any{
 		reflect.TypeOf(net.IP{}):            fmt.Sprint,
 		reflect.TypeOf(netip.Addr{}):        fmt.Sprint,
+		reflect.TypeOf(netip.Prefix{}):      fmt.Sprint,
 		reflect.TypeOf(time.Time{}):         fmt.Sprint,
 		reflect.TypeOf(SubnetMap[string]{}): fmt.Sprint,
 		reflect.TypeOf(SubnetMap[uint]{}):   fmt.Sprint,
diff --git a/orchestrator/clickhouse/http_test.go b/orchestrator/clickhouse/http_test.go
index c14ed6a0..f46d571c 100644
--- a/orchestrator/clickhouse/http_test.go
+++ b/orchestrator/clickhouse/http_test.go
@@ -71,7 +71,7 @@ func TestHTTPEndpoints(t *testing.T) {
 			ContentType: "text/csv; charset=utf-8",
 			FirstLines: []string{
 				`network,name,role,site,region,country,state,city,tenant,asn`,
-				`192.0.2.0/24,infra,,,,,,,,`,
+				`::ffff:192.0.2.0/120,infra,,,,,,,,`,
 			},
 		}, {
 			URL:         "/api/v0/orchestrator/clickhouse/custom_dict_none.csv",
diff --git a/orchestrator/clickhouse/networks_test.go b/orchestrator/clickhouse/networks_test.go
index d8bec29f..4a1be273 100644
--- a/orchestrator/clickhouse/networks_test.go
+++ b/orchestrator/clickhouse/networks_test.go
@@ -44,22 +44,22 @@ func TestNetworksCSVWithGeoip(t *testing.T) {
 				ContentType: "text/csv; charset=utf-8",
 				FirstLines: []string{
 					"network,name,role,site,region,country,state,city,tenant,asn",
-					"1.0.0.0/24,,,,,AU,Queensland,Brisbane,,15169",
-					"1.0.1.0/24,,,,,CN,Fujian,Xiamen,,",
-					"1.0.2.0/23,,,,,CN,Fujian,Xiamen,,",
-					"1.0.4.0/22,,,,,AU,Victoria,Melbourne,,",
-					"1.0.8.0/21,,,,,CN,Guangdong,Shenzhen,,",
-					"1.0.16.0/29,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.8/30,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.12/31,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.14/32,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.16.15/32,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.16/28,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.32/27,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.64/26,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.128/25,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.17.0/24,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.18.0/23,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.0.0/120,,,,,AU,Queensland,Brisbane,,15169",
+					"::ffff:1.0.1.0/120,,,,,CN,Fujian,Xiamen,,",
+					"::ffff:1.0.2.0/119,,,,,CN,Fujian,Xiamen,,",
+					"::ffff:1.0.4.0/118,,,,,AU,Victoria,Melbourne,,",
+					"::ffff:1.0.8.0/117,,,,,CN,Guangdong,Shenzhen,,",
+					"::ffff:1.0.16.0/125,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.8/126,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.12/127,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.14/128,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.16.15/128,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.16/124,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.32/123,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.64/122,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.128/121,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.17.0/120,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.18.0/119,,,,,JP,Tokyo,Asagaya-minami,,",
 				},
 			},
 		})
@@ -92,29 +92,29 @@ func TestNetworksCSVWithGeoip(t *testing.T) {
 				ContentType: "text/csv; charset=utf-8",
 				FirstLines: []string{
 					"network,name,role,site,region,country,state,city,tenant,asn",
-					"0.80.0.0/16,,,,,,,,Alfred,",                        // not covered by GeoIP
-					"1.0.0.0/20,infra,,,,,,,,",                          // not covered by GeoIP...
-					"1.0.0.0/24,infra,,,,AU,Queensland,Brisbane,,15169", // but covers GeoIP entries
-					"1.0.1.0/24,infra,,,,CN,Fujian,Xiamen,,",            // but covers GeoIP entries
-					"1.0.2.0/23,infra,,,,CN,Fujian,Xiamen,,",            // but covers GeoIP entries
-					"1.0.4.0/22,infra,,,,AU,Victoria,Melbourne,,",       // but covers GeoIP entries
-					"1.0.8.0/21,infra,,,,CN,Guangdong,Shenzhen,,",       // but covers GeoIP entries
-					"1.0.16.0/29,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.8/30,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.12/31,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.14/32,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.16.15/32,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.16/28,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.32/27,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.16.64/26,infra,,,,JP,Tokyo,Tokyo,,",       // matching a GeoIP entry
-					"1.0.16.66/32,infra,,,,JP,Tokyo,Tokyo,Alfred,", // nested in previous one
-					"1.0.16.128/25,,,,,JP,Tokyo,Tokyo,,",
-					"1.0.17.0/24,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.18.0/23,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.20.0/22,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.24.0/21,,,,,JP,Tokyo,Asagaya-minami,,",
-					"1.0.32.0/19,,,,,CN,Guangdong,Shenzhen,,",
-					"1.0.64.0/20,,,,,JP,Hiroshima,Hiroshima,,",
+					"::ffff:0.80.0.0/112,,,,,,,,Alfred,",                        // not covered by GeoIP
+					"::ffff:1.0.0.0/116,infra,,,,,,,,",                          // not covered by GeoIP...
+					"::ffff:1.0.0.0/120,infra,,,,AU,Queensland,Brisbane,,15169", // but covers GeoIP entries
+					"::ffff:1.0.1.0/120,infra,,,,CN,Fujian,Xiamen,,",            // but covers GeoIP entries
+					"::ffff:1.0.2.0/119,infra,,,,CN,Fujian,Xiamen,,",            // but covers GeoIP entries
+					"::ffff:1.0.4.0/118,infra,,,,AU,Victoria,Melbourne,,",       // but covers GeoIP entries
+					"::ffff:1.0.8.0/117,infra,,,,CN,Guangdong,Shenzhen,,",       // but covers GeoIP entries
+					"::ffff:1.0.16.0/125,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.8/126,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.12/127,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.14/128,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.16.15/128,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.16/124,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.32/123,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.16.64/122,infra,,,,JP,Tokyo,Tokyo,,",       // matching a GeoIP entry
+					"::ffff:1.0.16.66/128,infra,,,,JP,Tokyo,Tokyo,Alfred,", // nested in previous one
+					"::ffff:1.0.16.128/121,,,,,JP,Tokyo,Tokyo,,",
+					"::ffff:1.0.17.0/120,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.18.0/119,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.20.0/118,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.24.0/117,,,,,JP,Tokyo,Asagaya-minami,,",
+					"::ffff:1.0.32.0/115,,,,,CN,Guangdong,Shenzhen,,",
+					"::ffff:1.0.64.0/116,,,,,JP,Hiroshima,Hiroshima,,",
 				},
 			},
 		})
diff --git a/orchestrator/clickhouse/source_test.go b/orchestrator/clickhouse/source_test.go
index 50143b15..61c014c7 100644
--- a/orchestrator/clickhouse/source_test.go
+++ b/orchestrator/clickhouse/source_test.go
@@ -128,7 +128,7 @@ func TestNetworkSources(t *testing.T) {
 			ContentType: "text/csv; charset=utf-8",
 			FirstLines: []string{
 				`network,name,role,site,region,country,state,city,tenant,asn`,
-				`3.2.34.0/26,,amazon,,af-south-1,,,,amazon,`,
+				`::ffff:3.2.34.0/122,,amazon,,af-south-1,,,,amazon,`,
 				`2600:1f14:fff:f800::/56,,route53_healthchecks,,us-west-2,,,,amazon,`,
 				`2600:1ff2:4000::/40,,amazon,,us-west-2,,,,amazon,`,
 			},
diff --git a/outlet/metadata/provider/static/source_test.go b/outlet/metadata/provider/static/source_test.go
index ab132fb1..1248dc05 100644
--- a/outlet/metadata/provider/static/source_test.go
+++ b/outlet/metadata/provider/static/source_test.go
@@ -50,7 +50,7 @@ func TestInitStaticExporters(t *testing.T) {
 
 	expected["static"] = []exporterInfo{
 		{
-			ExporterSubnet: "203.0.113.0/24",
+			ExporterSubnet: "::ffff:203.0.113.0/120",
 			Exporter: provider.Exporter{
 				Name: "something",
 			},
diff --git a/outlet/routing/provider/bmp/prefixes_test.go b/outlet/routing/provider/bmp/prefixes_test.go
new file mode 100644
index 00000000..24891263
--- /dev/null
+++ b/outlet/routing/provider/bmp/prefixes_test.go
@@ -0,0 +1,371 @@
+// SPDX-FileCopyrightText: 2025 Free Mobile
+// SPDX-License-Identifier: AGPL-3.0-only
+
+package bmp
+
+import (
+	"fmt"
+	"iter"
+	"math/rand"
+	"net/netip"
+	"runtime"
+	"slices"
+	"testing"
+
+	"akvorado/common/helpers"
+
+	"github.com/osrg/gobgp/v3/pkg/packet/bgp"
+)
+
+var asPathCache [][]uint32
+var uniqueASPaths = 254123
+
+// Data from https://bgp.potaroo.net/as2.0/bgp-prefix-vector.txt
+var prefixSizeDistribution = [33]int{
+	0, // /0
+	0, 0, 0, 0, 0, 0, 0, 16,
+	14, 41, 92, 298, 581, 1210, 2161, 13854,
+	8369, 13785, 25080, 45910, 53311, 114177, 108013, 632625,
+	793, 0, 0, 0, 0, 0, 0, 0,
+}
+
+func init() {
+	prng := rand.New(rand.NewSource(0))
+	// Data from https://bgp.potaroo.net/as2.0/bgp-asbyhop-vector.txt
+	asDistanceDistribution := []int{
+		1, 2, 366, 9645, 29251, 28984, 7340, 1423, 383, 63, 14, 2, 4, 4, 4, 4, 1, 0,
+	}
+
+	totalAS := 0
+	for _, v := range asDistanceDistribution {
+		totalAS += v
+	}
+
+	// Generate a cache for the AS paths. We should pick one at random.
+	asPathCache = make([][]uint32, uniqueASPaths)
+	for i := range uniqueASPaths {
+		// Generate AS path length based on distribution
+		asPathLen := 1
+		r := prng.Intn(totalAS)
+		cumulative := 0
+		for len, count := range asDistanceDistribution {
+			cumulative += count
+			if r < cumulative {
+				asPathLen = len
+				if asPathLen == 0 {
+					asPathLen = 1
+				}
+				break
+			}
+		}
+
+		// Generate unique AS path
+		asPath := make([]uint32, asPathLen)
+		for j := 0; j < asPathLen; j++ {
+			asPath[j] = uint32(prng.Intn(64494) + 1)
+		}
+		asPathCache[i] = asPath
+	}
+}
+
+type randomRoute struct {
+	Prefix           netip.Prefix
+	ASPath           []uint32
+	Communities      []uint32
+	LargeCommunities []bgp.LargeCommunity
+}
+
+// randomRealWorldRoutes4 generates random IPv4 routes matching the size distribution
+// found on the Internet. Using data from https://bgp.potaroo.net/as2.0/index.html
+func randomRealWorldRoutes4(prngPrefixes, prngASPaths *rand.Rand, n int) iter.Seq[randomRoute] {
+	totalRoutes := 0
+	for _, v := range prefixSizeDistribution {
+		totalRoutes += v
+	}
+
+	return func(yield func(randomRoute) bool) {
+		for range n {
+			// Generate prefix length based on distribution
+			prefixLen := 0
+			r := prngPrefixes.Intn(totalRoutes)
+			cumulative := 0
+			for len, count := range prefixSizeDistribution {
+				cumulative += count
+				if r < cumulative {
+					prefixLen = len
+					break
+				}
+			}
+
+			// Generate random IPv4 prefix
+			ip := netip.AddrFrom4([4]byte{
+				byte(prngPrefixes.Intn(224)),
+				byte(prngPrefixes.Intn(256)),
+				byte(prngPrefixes.Intn(256)),
+				byte(prngPrefixes.Intn(256)),
+			})
+			prefix := netip.PrefixFrom(ip, prefixLen).Masked()
+
+			// Select a random AS path from the pre-generated cache
+			asPath := asPathCache[prngASPaths.Intn(len(asPathCache))]
+
+			// Generate communities (0-5 communities per route)
+			numCommunities := max(0, prngASPaths.Intn(10)-4)
+			communities := make([]uint32, numCommunities)
+			for j := range numCommunities {
+				asFromPath := asPath[prngASPaths.Intn(len(asPath))]
+				communities[j] = asFromPath<<16 | uint32(prngASPaths.Intn(3))
+			}
+			slices.Sort(communities)
+			communities = slices.Compact(communities)
+
+			// Generate large communities (0-3 per route, but they are rare)
+			numLargeCommunities := max(0, prngASPaths.Intn(100)-97)
+			largeCommunities := make([]bgp.LargeCommunity, numLargeCommunities)
+			for j := range numLargeCommunities {
+				largeCommunities[j] = bgp.LargeCommunity{
+					ASN:        asPath[prngASPaths.Intn(len(asPath))],
+					LocalData1: uint32(prngASPaths.Intn(2)) + 1,
+					LocalData2: uint32(prngASPaths.Intn(2)) + 1,
+				}
+			}
+
+			route := randomRoute{
+				Prefix:           prefix,
+				ASPath:           asPath,
+				Communities:      communities,
+				LargeCommunities: largeCommunities,
+			}
+
+			if !yield(route) {
+				return
+			}
+		}
+	}
+}
+
+func TestRandomRealWorldRoutes4(t *testing.T) {
+	prng1 := rand.New(rand.NewSource(1))
+	prng2 := rand.New(rand.NewSource(2))
+	routes := []randomRoute{}
+	for route := range randomRealWorldRoutes4(prng1, prng2, 2) {
+		routes = append(routes, route)
+	}
+	expectedRoutes := []randomRoute{
+		{
+			Prefix:           netip.MustParsePrefix("79.199.187.0/24"),
+			ASPath:           []uint32{29418, 57855, 38297},
+			Communities:      []uint32{1927938050, 2509832194},
+			LargeCommunities: []bgp.LargeCommunity{},
+		},
+		{
+			Prefix:           netip.MustParsePrefix("185.172.72.0/24"),
+			ASPath:           []uint32{25258, 9490, 64459, 11892, 37685},
+			Communities:      []uint32{},
+			LargeCommunities: []bgp.LargeCommunity{},
+		},
+	}
+	if diff := helpers.Diff(routes, expectedRoutes); diff != "" {
+		t.Fatalf("randomRealWorldRoutes4() (-got, +want):\n%s", diff)
+	}
+}
+
+func TestRandomRealWorldRoutes4Distribution(t *testing.T) {
+	prng1 := rand.New(rand.NewSource(42))
+	prng2 := rand.New(rand.NewSource(43))
+
+	totalRoutes := 0
+	for _, v := range prefixSizeDistribution {
+		totalRoutes += v
+	}
+
+	// Generate many routes and count prefix lengths
+	n := 1_000_000
+	prefixLengthCounts := make(map[int]int)
+	for route := range randomRealWorldRoutes4(prng1, prng2, n) {
+		prefixLen := route.Prefix.Bits()
+		prefixLengthCounts[prefixLen]++
+	}
+
+	// Check distribution within 10% margin
+	for prefixLen := range 33 {
+		expected := float64(prefixSizeDistribution[prefixLen]) / float64(totalRoutes) * float64(n)
+		actual := float64(prefixLengthCounts[prefixLen])
+
+		if expected > 0 {
+			errorMargin := 0.3 * expected
+			if actual < expected-errorMargin || actual > expected+errorMargin {
+				t.Errorf("Prefix length /%d: expected %.1f±%.1f, got %.0f",
+					prefixLen, expected, errorMargin, actual)
+			}
+		} else if actual > 0 {
+			t.Errorf("Prefix length /%d: expected 0, got %d", prefixLen, prefixLengthCounts[prefixLen])
+		}
+	}
+}
+
+func BenchmarkRandomRealWorldRoutes4(b *testing.B) {
+	prng1 := rand.New(rand.NewSource(1))
+	prng2 := rand.New(rand.NewSource(2))
+	for b.Loop() {
+		for route := range randomRealWorldRoutes4(prng1, prng2, 1000) {
+			_ = route
+		}
+	}
+	b.ReportMetric(0, "ns/op")
+	b.ReportMetric(float64(b.Elapsed())/float64(b.N)/1000, "ns/route")
+}
+
+func BenchmarkRIBInsertion(b *testing.B) {
+	for _, routes := range []int{1_000, 10_000, 100_000} {
+		for _, peers := range []int{1, 2, 5} {
+			name := fmt.Sprintf("%d routes, %d peers", routes, peers)
+
+			b.Run(name, func(b *testing.B) {
+				var startMem, endMem runtime.MemStats
+				runtime.GC()
+				runtime.ReadMemStats(&startMem)
+
+				var rib *rib
+				inserted := 0
+				tentative := 0
+				for b.Loop() {
+					rib = newRIB()
+					nh := netip.MustParseAddr("::ffff:198.51.100.0")
+					prng1 := rand.New(rand.NewSource(10))
+					prng2 := make([]*rand.Rand, peers)
+					for p := range peers {
+						prng2[p] = rand.New(rand.NewSource(int64(p)))
+					}
+					for p := range peers {
+						nh = nh.Next()
+						for r := range randomRealWorldRoutes4(prng1, prng2[p], routes) {
+							if prng2[p].Intn(10) == 0 {
+								continue
+							}
+							pfx := netip.PrefixFrom(netip.AddrFrom16(r.Prefix.Addr().As16()), r.Prefix.Bits()+96)
+							tentative++
+							inserted += rib.addPrefix(pfx, route{
+								peer:    uint32(p),
+								nlri:    rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC}),
+								nextHop: rib.nextHops.Put(nextHop(nh)),
+								attributes: rib.rtas.Put(routeAttributes{
+									asn:              r.ASPath[len(r.ASPath)-1],
+									asPath:           r.ASPath,
+									communities:      r.Communities,
+									largeCommunities: r.LargeCommunities,
+								}),
+								prefixLen: uint8(pfx.Bits()),
+							})
+						}
+					}
+				}
+				runtime.GC()
+				runtime.ReadMemStats(&endMem)
+				b.ReportMetric(0, "ns/op")
+				b.ReportMetric(float64(b.Elapsed())/float64(inserted), "ns/route")
+				b.ReportMetric(float64(endMem.HeapAlloc-startMem.HeapAlloc)/float64(rib.tree.Size()), "bytes/route")
+				b.ReportMetric(float64(inserted)/float64(tentative)*100, "%ins")
+
+				// Avoid elimination of the RIB
+				rib.tree.Lookup(netip.MustParseAddr("::ffff:192.168.1.1"))
+			})
+		}
+	}
+}
+
+func BenchmarkRIBLookup(b *testing.B) {
+	for _, routes := range []int{1_000, 10_000, 100_000} {
+		for _, peers := range []int{1, 2, 5} {
+			name := fmt.Sprintf("%d routes, %d peers", routes, peers)
+
+			b.Run(name, func(b *testing.B) {
+				rib := newRIB()
+				nh := netip.MustParseAddr("::ffff:198.51.100.0")
+				prng1 := rand.New(rand.NewSource(10))
+				prng2 := make([]*rand.Rand, peers)
+				for p := range peers {
+					prng2[p] = rand.New(rand.NewSource(int64(p)))
+				}
+				for p := range peers {
+					nh = nh.Next()
+					for r := range randomRealWorldRoutes4(prng1, prng2[p], routes) {
+						if prng2[p].Intn(10) == 0 {
+							continue
+						}
+						pfx := netip.PrefixFrom(netip.AddrFrom16(r.Prefix.Addr().As16()), r.Prefix.Bits()+96)
+						rib.addPrefix(pfx, route{
+							peer:    uint32(p),
+							nlri:    rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC}),
+							nextHop: rib.nextHops.Put(nextHop(nh)),
+							attributes: rib.rtas.Put(routeAttributes{
+								asn:              r.ASPath[len(r.ASPath)-1],
+								asPath:           r.ASPath,
+								communities:      r.Communities,
+								largeCommunities: r.LargeCommunities,
+							}),
+							prefixLen: uint8(pfx.Bits()),
+						})
+					}
+				}
+
+				prng1 = rand.New(rand.NewSource(10))
+				lookups := 0
+				for b.Loop() {
+					for r := range randomRealWorldRoutes4(prng1, prng2[0], routes/10) {
+						_, _ = rib.tree.Lookup(netip.AddrFrom16(r.Prefix.Addr().As16()))
+						lookups++
+					}
+				}
+				b.ReportMetric(float64(b.Elapsed())/float64(lookups), "ns/op")
+			})
+		}
+	}
+}
+
+func BenchmarkRIBFlush(b *testing.B) {
+	for _, routes := range []int{1_000, 10_000, 100_000} {
+		for _, peers := range []int{1, 2, 5} {
+			name := fmt.Sprintf("%d routes, %d peers", routes, peers)
+
+			b.Run(name, func(b *testing.B) {
+				for b.Loop() {
+					b.StopTimer()
+					rib := newRIB()
+					nh := netip.MustParseAddr("::ffff:198.51.100.0")
+					prng1 := rand.New(rand.NewSource(10))
+					prng2 := make([]*rand.Rand, peers)
+					for p := range peers {
+						prng2[p] = rand.New(rand.NewSource(int64(p)))
+					}
+					for p := range peers {
+						nh = nh.Next()
+						for r := range randomRealWorldRoutes4(prng1, prng2[p], routes) {
+							if prng2[p].Intn(10) == 0 {
+								continue
+							}
+							pfx := netip.PrefixFrom(netip.AddrFrom16(r.Prefix.Addr().As16()), r.Prefix.Bits()+96)
+							rib.addPrefix(pfx, route{
+								peer:    uint32(p),
+								nlri:    rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC}),
+								nextHop: rib.nextHops.Put(nextHop(nh)),
+								attributes: rib.rtas.Put(routeAttributes{
+									asn:              r.ASPath[len(r.ASPath)-1],
+									asPath:           r.ASPath,
+									communities:      r.Communities,
+									largeCommunities: r.LargeCommunities,
+								}),
+								prefixLen: uint8(pfx.Bits()),
+							})
+						}
+					}
+
+					b.StartTimer()
+					rib.flushPeer(0)
+				}
+				b.ReportMetric(0, "ns/op")
+				b.ReportMetric(float64(b.Elapsed())/float64(b.N)/1_000_000, "ms/op")
+			})
+		}
+	}
+}
diff --git a/outlet/routing/provider/bmp/rib_test.go b/outlet/routing/provider/bmp/rib_test.go
index f396e9a2..f0adc542 100644
--- a/outlet/routing/provider/bmp/rib_test.go
+++ b/outlet/routing/provider/bmp/rib_test.go
@@ -5,7 +5,6 @@ package bmp
 
 import (
 	"fmt"
-	"hash/maphash"
 	"math/rand"
 	"net/netip"
 	"testing"
@@ -13,7 +12,6 @@ import (
 
 	"akvorado/common/helpers"
 
-	"github.com/kentik/patricia"
 	"github.com/osrg/gobgp/v3/pkg/packet/bgp"
 )
 
@@ -166,55 +164,190 @@ func TestRTAEqual(t *testing.T) {
 			routeAttributes{asn: 2038, largeCommunities: []bgp.LargeCommunity{{ASN: 1, LocalData1: 2, LocalData2: 3}, {ASN: 3, LocalData1: 4, LocalData2: 5}, {ASN: 5, LocalData1: 6, LocalData2: 7}}},
 			false,
 		},
-		{
-			helpers.Mark(),
-			routeAttributes{plen: 48},
-			routeAttributes{plen: 48},
-			true,
-		},
-		{
-			helpers.Mark(),
-			routeAttributes{plen: 48},
-			routeAttributes{plen: 49},
-			false,
-		},
 	}
-outer:
-	for try := 3; try >= 0; try-- {
-		// We may have to try a few times because of
-		// collisions due to reduced hash efficiency during
-		// tests.
-		for _, tc := range cases {
-			equal := tc.rta1.Equal(tc.rta2)
+
+	for _, tc := range cases {
+		equal := tc.rta1.Equal(tc.rta2)
+		if equal && !tc.equal {
+			t.Errorf("%s%+v == %+v", tc.pos, tc.rta1, tc.rta2)
+		} else if !equal && tc.equal {
+			t.Errorf("%s%+v != %+v", tc.pos, tc.rta1, tc.rta2)
+		} else {
+			equal := tc.rta1.Hash() == tc.rta2.Hash()
 			if equal && !tc.equal {
-				t.Errorf("%s%+v == %+v", tc.pos, tc.rta1, tc.rta2)
+				t.Errorf("%s%+v.hash == %+v.hash", tc.pos, tc.rta1, tc.rta2)
 			} else if !equal && tc.equal {
-				t.Errorf("%s%+v != %+v", tc.pos, tc.rta1, tc.rta2)
-			} else {
-				equal := tc.rta1.Hash() == tc.rta2.Hash()
-				if equal && !tc.equal {
-					if try > 0 {
-						// We may have a collision, change the seed and retry
-						rtaHashSeed = maphash.MakeSeed()
-						continue outer
-					}
-					t.Errorf("%s%+v.hash == %+v.hash", tc.pos, tc.rta1, tc.rta2)
-				} else if !equal && tc.equal {
-					t.Errorf("%s%+v.hash != %+v.hash", tc.pos, tc.rta1, tc.rta2)
-				}
+				t.Errorf("%s%+v.hash != %+v.hash", tc.pos, tc.rta1, tc.rta2)
 			}
 		}
 	}
 }
 
-func TestRIB(t *testing.T) {
-	for i := range 5 {
-		t.Logf("Run %d", i+1)
+func TestRemoveRoutes(t *testing.T) {
+	nr := func(r *rib, peer uint32) route {
+		return route{
+			peer:    peer,
+			nlri:    r.nlris.Put(nlri{family: bgp.RF_IPv4_UC, path: 1}),
+			nextHop: r.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:198.51.100.8"))),
+			attributes: r.rtas.Put(routeAttributes{
+				asn: 65300,
+			}),
+			prefixLen: 96 + 24,
+		}
+	}
+	t.Run("only route", func(t *testing.T) {
+		r := newRIB()
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), nr(r, 10))
+		idx, _ := r.tree.Lookup(netip.MustParseAddr("::ffff:192.168.144.10"))
+		count, empty := r.removeRoutes(idx, func(route) bool { return true }, true)
+		if !empty {
+			t.Error("removeRoutes() should have removed all routes from node")
+		}
+		if count != 1 {
+			t.Error("removeRoutes() should have removed 1 route")
+		}
+		if diff := helpers.Diff(r.routes, map[prefixIndex]route{}); diff != "" {
+			t.Errorf("removeRoutes() (-got, +want):\n%s", diff)
+		}
+	})
+
+	t.Run("first route", func(t *testing.T) {
+		r := newRIB()
+		r1 := nr(r, 10)
+		r2 := nr(r, 11)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r1)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r2)
+		idx, _ := r.tree.Lookup(netip.MustParseAddr("::ffff:192.168.144.10"))
+		count, empty := r.removeRoutes(idx, func(r route) bool { return r.peer == 10 }, true)
+		if empty {
+			t.Error("removeRoutes() should not have removed all routes from node")
+		}
+		if count != 1 {
+			t.Error("removeRoutes() should have removed 1 route")
+		}
+		if diff := helpers.Diff(r.routes, map[routeKey]route{
+			makeRouteKey(idx, 0): r2,
+		}); diff != "" {
+			t.Errorf("removeRoutes() (-got, +want):\n%s", diff)
+		}
+	})
+
+	t.Run("second route", func(t *testing.T) {
+		r := newRIB()
+		r1 := nr(r, 10)
+		r2 := nr(r, 11)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r1)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r2)
+		idx, _ := r.tree.Lookup(netip.MustParseAddr("::ffff:192.168.144.10"))
+		count, empty := r.removeRoutes(idx, func(r route) bool { return r.peer == 11 }, true)
+		if empty {
+			t.Error("removeRoutes() should not have removed all routes from node")
+		}
+		if count != 1 {
+			t.Error("removeRoutes() should have removed 1 route")
+		}
+		if diff := helpers.Diff(r.routes, map[routeKey]route{
+			makeRouteKey(idx, 0): r1,
+		}); diff != "" {
+			t.Errorf("removeRoutes() (-got, +want):\n%s", diff)
+		}
+	})
+	t.Run("middle route", func(t *testing.T) {
+		r := newRIB()
+		r1 := nr(r, 10)
+		r2 := nr(r, 11)
+		r3 := nr(r, 12)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r1)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r2)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r3)
+		idx, _ := r.tree.Lookup(netip.MustParseAddr("::ffff:192.168.144.10"))
+		count, empty := r.removeRoutes(idx, func(r route) bool { return r.peer == 11 }, true)
+		if empty {
+			t.Error("removeRoutes() should not have removed all routes from node")
+		}
+		if count != 1 {
+			t.Error("removeRoutes() should have removed 1 route")
+		}
+		if diff := helpers.Diff(r.routes, map[routeKey]route{
+			makeRouteKey(idx, 0): r1,
+			makeRouteKey(idx, 1): r3,
+		}); diff != "" {
+			t.Errorf("removeRoutes() (-got, +want):\n%s", diff)
+		}
+	})
+	t.Run("one route out of two", func(t *testing.T) {
+		r := newRIB()
+		r1 := nr(r, 10)
+		r2 := nr(r, 11)
+		r3 := nr(r, 12)
+		r4 := nr(r, 13)
+		r5 := nr(r, 14)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r1)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r2)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r3)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r4)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r5)
+		idx, _ := r.tree.Lookup(netip.MustParseAddr("::ffff:192.168.144.10"))
+		count, empty := r.removeRoutes(idx, func(r route) bool { return r.peer%2 == 0 }, false)
+		if empty {
+			t.Error("removeRoutes() should not have removed all routes from node")
+		}
+		if count != 3 {
+			t.Error("removeRoutes() should have removed 3 route")
+		}
+		if diff := helpers.Diff(r.routes, map[routeKey]route{
+			makeRouteKey(idx, 0): r2,
+			makeRouteKey(idx, 1): r4,
+		}); diff != "" {
+			t.Errorf("removeRoutes() (-got, +want):\n%s", diff)
+		}
+	})
+
+	t.Run("all routes", func(t *testing.T) {
+		r := newRIB()
+		r1 := nr(r, 10)
+		r2 := nr(r, 11)
+		r3 := nr(r, 12)
+		r4 := nr(r, 13)
+		r5 := nr(r, 14)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r1)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r2)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r3)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r4)
+		r.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/120"), r5)
+		idx, _ := r.tree.Lookup(netip.MustParseAddr("::ffff:192.168.144.10"))
+		count, empty := r.removeRoutes(idx, func(route) bool { return true }, false)
+		if !empty {
+			t.Error("removeRoutes() should have removed all routes from node")
+		}
+		if count != 5 {
+			t.Error("removeRoutes() should have removed 5 route")
+		}
+		if diff := helpers.Diff(r.routes, map[routeKey]route{}); diff != "" {
+			t.Errorf("removeRoutes() (-got, +want):\n%s", diff)
+		}
+	})
+}
+
+func TestRIBHarness(t *testing.T) {
+	for run := range 5 {
+		random := rand.New(rand.NewSource(int64(run)))
+		run++
+
+		// Ramp up the test
+		totalExporters := run
+		peerPerExporter := 1 + run/2
+		maxInitialRoutePerPeer := 500 * run
+		maxRemovedRoutePerPeer := 100 * run
+		maxReaddedRoutePerPeer := 50 * run
+		t.Logf("Run %d. Exporters=%d, Peers=%d, Initial=max %d, Removed=max %d, Readded=max %d",
+			run, totalExporters, peerPerExporter,
+			maxInitialRoutePerPeer, maxRemovedRoutePerPeer, maxReaddedRoutePerPeer)
+
 		r := newRIB()
-		random := rand.New(rand.NewSource(100 * int64(i)))
 		type lookup struct {
 			peer    uint32
-			prefix  netip.Addr // Assume /64
+			addr    netip.Addr
 			nextHop netip.Addr
 			rd      RD
 			asn     uint32
@@ -227,7 +360,7 @@ func TestRIB(t *testing.T) {
 				if lookups[idx].peer != lookup.peer {
 					continue
 				}
-				if lookups[idx].prefix != lookup.prefix || lookups[idx].rd != lookup.rd {
+				if lookups[idx].addr != lookup.addr || lookups[idx].rd != lookup.rd {
 					continue
 				}
 				if lookups[idx].removed {
@@ -238,24 +371,24 @@ func TestRIB(t *testing.T) {
 			}
 		}
 
-		totalExporters := 20
 		peers := []uint32{}
-		for i := 0; i < totalExporters; i++ {
-			for j := 0; j < int(random.Uint32()%14); j++ {
-				peer := uint32((i << 16) + j)
+		for i := range totalExporters {
+			for j := range peerPerExporter {
+				peer := uint32((i << 16) + int(j))
 				peers = append(peers, peer)
-				// TODO: it fails if we replace with for range ... This is suspicious!
-				for k := 0; k < int(random.Uint32()%10000); k++ {
+				toAdd := random.Intn(maxInitialRoutePerPeer)
+				added := 0
+				for range toAdd {
 					lookup := lookup{
 						peer: peer,
-						prefix: netip.MustParseAddr(fmt.Sprintf("2001:db8:f:%x::",
-							random.Uint32()%300)),
+						addr: netip.MustParseAddr(fmt.Sprintf("2001:db8:f:%x::",
+							random.Intn(300))),
 						nextHop: netip.MustParseAddr(
-							fmt.Sprintf("2001:db8:c::%x", random.Uint32()%500)),
-						rd:  RD(random.Uint64() % 3),
-						asn: random.Uint32() % 1000,
+							fmt.Sprintf("2001:db8:c::%x", random.Intn(500))),
+						rd:  RD(random.Intn(3)),
+						asn: uint32(random.Intn(1000)),
 					}
-					r.addPrefix(lookup.prefix, 64,
+					added += r.addPrefix(netip.PrefixFrom(lookup.addr, 64),
 						route{
 							peer:    peer,
 							nlri:    r.nlris.Put(nlri{rd: lookup.rd}),
@@ -267,35 +400,43 @@ func TestRIB(t *testing.T) {
 					removeLookup(lookup)
 					lookups = append(lookups, lookup)
 				}
-				for k := 0; k < int(random.Uint32()%500); k++ {
+				t.Logf("Run %d: added = %d/%d", run, added, toAdd)
+
+				toRemove := random.Intn(maxRemovedRoutePerPeer)
+				removed := 0
+				for range toRemove {
 					prefix := netip.MustParseAddr(fmt.Sprintf("2001:db8:f:%x::",
-						random.Uint32()%300))
-					rd := RD(random.Uint64() % 4)
+						random.Intn(300)))
+					rd := RD(random.Intn(4))
 					if nlriRef, ok := r.nlris.Ref(nlri{
 						rd: rd,
 					}); ok {
-						r.removePrefix(prefix, 64,
+						removed += r.removePrefix(netip.PrefixFrom(prefix, 64),
 							route{
 								peer: peer,
 								nlri: nlriRef,
 							})
+						removeLookup(lookup{
+							peer: peer,
+							addr: prefix,
+							rd:   rd,
+						})
 					}
-					removeLookup(lookup{
-						peer:   peer,
-						prefix: prefix,
-						rd:     rd,
-					})
 				}
-				for k := 0; k < int(random.Uint32()%200); k++ {
+				t.Logf("Run %d: removed = %d/%d", run, removed, toRemove)
+
+				toAdd = random.Intn(maxReaddedRoutePerPeer)
+				added = 0
+				for range toAdd {
 					lookup := lookup{
 						peer: peer,
-						prefix: netip.MustParseAddr(fmt.Sprintf("2001:db8:f:%x::",
-							random.Uint32()%300)),
+						addr: netip.MustParseAddr(fmt.Sprintf("2001:db8:f:%x::",
+							random.Intn(300))),
 						nextHop: netip.MustParseAddr(
 							fmt.Sprintf("2001:db8:c::%x", random.Uint32()%500)),
-						asn: random.Uint32() % 1010,
+						asn: uint32(random.Intn(1010)),
 					}
-					r.addPrefix(lookup.prefix, 64,
+					added += r.addPrefix(netip.PrefixFrom(lookup.addr, 64),
 						route{
 							peer:    peer,
 							nlri:    r.nlris.Put(nlri{}),
@@ -307,6 +448,7 @@ func TestRIB(t *testing.T) {
 					removeLookup(lookup)
 					lookups = append(lookups, lookup)
 				}
+				t.Logf("Run %d: readedd = %d/%d", run, added, toAdd)
 			}
 		}
 
@@ -316,14 +458,20 @@ func TestRIB(t *testing.T) {
 				removed++
 				continue
 			}
-			v6 := patricia.NewIPv6Address(lookup.prefix.AsSlice(), 128)
-			ok, tags := r.tree.FindDeepestTags(v6)
+			// Find prefix in tree
+			prefixIdx, ok := r.tree.Lookup(lookup.addr)
 			if !ok {
-				t.Errorf("cannot find %s/128 for %d",
-					lookup.prefix, lookup.peer)
+				t.Errorf("cannot find %s for %d",
+					lookup.addr, lookup.peer)
+				continue
 			}
+
+			// Check if routes exist for this prefix
 			found := false
-			for _, route := range tags {
+			routeFound := false
+
+			for route := range r.iterateRoutesForPrefixIndex(prefixIdx) {
+				routeFound = true // At least one route exists
 				if r.nextHops.Get(route.nextHop) != nextHop(lookup.nextHop) || r.nlris.Get(route.nlri).rd != lookup.rd {
 					continue
 				}
@@ -333,14 +481,23 @@ func TestRIB(t *testing.T) {
 				found = true
 				break
 			}
+
+			if !routeFound {
+				t.Errorf("no routes found for %s for %d",
+					lookup.addr, lookup.peer)
+				continue
+			}
+
 			if !found {
-				for _, route := range tags {
-					t.Logf("route NH: %s, RD: %s, ASN: %d",
+				t.Logf("Available routes for %s:", lookup.addr)
+				for route := range r.iterateRoutesForPrefixIndex(prefixIdx) {
+					t.Logf("peer %d, NH: %s, RD: %s, ASN: %d",
+						route.peer,
 						netip.Addr(r.nextHops.Get(route.nextHop)),
 						r.nlris.Get(route.nlri).rd, r.rtas.Get(route.attributes).asn)
 				}
-				t.Errorf("cannot find %s/128 for %d; NH: %s, RD: %s, ASN: %d",
-					lookup.prefix, lookup.peer,
+				t.Errorf("cannot find %s for peer %d; NH: %s, RD: %s, ASN: %d",
+					lookup.addr, lookup.peer,
 					lookup.nextHop, lookup.rd, lookup.asn)
 			}
 		}
@@ -363,6 +520,10 @@ func TestRIB(t *testing.T) {
 		if r.rtas.Len() > 0 {
 			t.Errorf("%d route attributes have leaked", r.rtas.Len())
 		}
+
+		if t.Failed() {
+			break
+		}
 	}
 }
 
diff --git a/outlet/routing/provider/bmp/root_test.go b/outlet/routing/provider/bmp/root_test.go
index 05e3e833..10df209f 100644
--- a/outlet/routing/provider/bmp/root_test.go
+++ b/outlet/routing/provider/bmp/root_test.go
@@ -9,7 +9,7 @@ import (
 	"net"
 	"net/netip"
 	"path"
-	"strconv"
+	"slices"
 	"testing"
 	"time"
 
@@ -44,10 +44,8 @@ func TestBMP(t *testing.T) {
 		c.mu.RLock()
 		defer c.mu.RUnlock()
 		result := map[netip.Addr][]string{}
-		iter := c.rib.tree.Iterate()
-		for iter.Next() {
-			addr := iter.Address()
-			for _, route := range iter.Tags() {
+		for prefix, prefixIdx := range c.rib.tree.All6() {
+			for route := range c.rib.iterateRoutesForPrefixIndex(prefixIdx) {
 				nlriRef := c.rib.nlris.Get(route.nlri)
 				nh := c.rib.nextHops.Get(route.nextHop)
 				attrs := c.rib.rtas.Get(route.attributes)
@@ -61,14 +59,22 @@ func TestBMP(t *testing.T) {
 				if _, ok := result[peer.Unmap()]; !ok {
 					result[peer.Unmap()] = []string{}
 				}
-				result[peer.Unmap()] = append(result[peer.Unmap()],
-					fmt.Sprintf("[%s] %s via %s %s/%d %d %v %v %v",
+				addr := prefix.Addr()
+				plen := prefix.Bits()
+				if prefix.Addr().Is4In6() {
+					addr = addr.Unmap()
+					plen -= 96
+				}
+				peer = peer.Unmap()
+				result[peer] = append(result[peer],
+					fmt.Sprintf("[%s] %s/%d via %s %s/%d %d %v %v %v",
 						nlriRef.family,
-						addr, netip.Addr(nh).Unmap(),
+						addr, plen, netip.Addr(nh).Unmap(),
 						nlriRef.rd,
 						nlriRef.path,
 						attrs.asn, attrs.asPath,
 						attrs.communities, attrs.largeCommunities))
+				slices.Sort(result[peer])
 			}
 		}
 		return result
@@ -197,21 +203,21 @@ func TestBMP(t *testing.T) {
 
 		expectedRIB := map[netip.Addr][]string{
 			netip.MustParseAddr("2001:db8::3"): {
-				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [65013] [] []",
 				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::3 0:0/0 174 [65013 65013 174 174 174] [4260691978 4260691988] []",
 				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::3 0:0/0 12322 [65013 65013 1299 1299 1299 12322] [4260691998] []",
+				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [65013] [] []",
 			},
 			netip.MustParseAddr("2001:db8::7"): {
 				"[ipv4-unicast] 192.0.2.6/31 via 192.0.2.7 0:0/0 65017 [65017] [] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:102/0 64476 [65017 65017 174 3356 3356 3356 64476] [4260954122 4260954132] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:101/0 64476 [65017 65017 174 1299 64476] [4260954122 4260954132] []",
+				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [65017 65013 174 174 174] [4260954122 4260954132] [{65017 300 4}]",
+				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [65017 65017 1299 1299 1299 12322] [4260954142] [{65017 400 2}]",
+				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [65017] [] []",
 				"[l2vpn-evpn] 198.51.100.0/26 via 2001:db8::7 65017:104/0 64476 [65017 65017 3356 64476] [4260955215] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:101/0 64476 [65017 65017 174 1299 64476] [4260954122 4260954132] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:102/0 64476 [65017 65017 174 3356 3356 3356 64476] [4260954122 4260954132] []",
 				"[l3vpn-ipv4-unicast] 198.51.100.0/26 via 192.0.2.7 65017:103/0 64476 [65017 65017 3356 64476] [4260955215] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:102/0 396919 [65017 65017 6453 396919] [4260954131] []",
 				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:101/0 396919 [65017 65017 174 29447 396919] [4260954124] []",
-				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [65017] [] []",
-				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [65017 65013 174 174 174] [4260954122 4260954132] [{65017 300 4}]",
-				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [65017 65017 1299 1299 1299 12322] [4260954142] [{65017 400 2}]",
+				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:102/0 396919 [65017 65017 6453 396919] [4260954131] []",
 				"[l3vpn-ipv6-unicast] 2001:db8:4::/64 via 2001:db8::7 65017:101/0 29447 [65017 65017 1299 1299 1299 29447] [4260954412] []",
 			},
 			netip.MustParseAddr("192.0.2.1"): {
@@ -311,21 +317,21 @@ func TestBMP(t *testing.T) {
 
 		expectedRIB := map[netip.Addr][]string{
 			netip.MustParseAddr("2001:db8::3"): {
-				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [65013] [] []",
 				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::3 0:0/0 174 [65013 65013 174 174 174] [4260691978 4260691988] []",
 				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::3 0:0/0 12322 [65013 65013 1299 1299 1299 12322] [4260691998] []",
+				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [65013] [] []",
 			},
 			netip.MustParseAddr("2001:db8::7"): {
 				"[ipv4-unicast] 192.0.2.6/31 via 192.0.2.7 0:0/0 65017 [65017] [] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:102/0 64476 [65017 65017 174 3356 3356 3356 64476] [4260954122 4260954132] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:101/0 64476 [65017 65017 174 1299 64476] [4260954122 4260954132] []",
+				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [65017 65013 174 174 174] [4260954122 4260954132] [{65017 300 4}]",
+				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [65017 65017 1299 1299 1299 12322] [4260954142] [{65017 400 2}]",
+				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [65017] [] []",
 				"[l2vpn-evpn] 198.51.100.0/26 via 2001:db8::7 65017:104/0 64476 [65017 65017 3356 64476] [4260955215] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:101/0 64476 [65017 65017 174 1299 64476] [4260954122 4260954132] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:102/0 64476 [65017 65017 174 3356 3356 3356 64476] [4260954122 4260954132] []",
 				"[l3vpn-ipv4-unicast] 198.51.100.0/26 via 192.0.2.7 65017:103/0 64476 [65017 65017 3356 64476] [4260955215] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:102/0 396919 [65017 65017 6453 396919] [4260954131] []",
 				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:101/0 396919 [65017 65017 174 29447 396919] [4260954124] []",
-				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [65017] [] []",
-				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [65017 65013 174 174 174] [4260954122 4260954132] [{65017 300 4}]",
-				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [65017 65017 1299 1299 1299 12322] [4260954142] [{65017 400 2}]",
+				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:102/0 396919 [65017 65017 6453 396919] [4260954131] []",
 				"[l3vpn-ipv6-unicast] 2001:db8:4::/64 via 2001:db8::7 65017:101/0 29447 [65017 65017 1299 1299 1299 29447] [4260954412] []",
 			},
 		}
@@ -404,15 +410,15 @@ func TestBMP(t *testing.T) {
 
 		expectedRIB := map[netip.Addr][]string{
 			netip.MustParseAddr("2001:db8::3"): {
-				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [65013] [] []",
 				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::3 0:0/0 174 [65013 65013 174 174 174] [4260691978 4260691988] []",
 				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::3 0:0/0 12322 [65013 65013 1299 1299 1299 12322] [4260691998] []",
+				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [65013] [] []",
 			},
 			netip.MustParseAddr("2001:db8::7"): {
 				"[ipv4-unicast] 192.0.2.6/31 via 192.0.2.7 0:0/0 65017 [65017] [] []",
-				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [65017] [] []",
 				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [65017 65013 174 174 174] [4260954122 4260954132] [{65017 300 4}]",
 				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [65017 65017 1299 1299 1299 12322] [4260954142] [{65017 400 2}]",
+				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [65017] [] []",
 			},
 			netip.MustParseAddr("192.0.2.1"): {
 				"[ipv4-unicast] 192.0.2.0/31 via 192.0.2.1 0:0/0 65011 [65011] [] []",
@@ -737,21 +743,21 @@ func TestBMP(t *testing.T) {
 
 		expectedRIB := map[netip.Addr][]string{
 			netip.MustParseAddr("2001:db8::3"): {
-				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [] [] []",
 				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::3 0:0/0 174 [] [] []",
 				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::3 0:0/0 12322 [] [] []",
+				"[ipv6-unicast] 2001:db8::2/127 via 2001:db8::3 0:0/0 65013 [] [] []",
 			},
 			netip.MustParseAddr("2001:db8::7"): {
 				"[ipv4-unicast] 192.0.2.6/31 via 192.0.2.7 0:0/0 65017 [] [] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:102/0 64476 [] [] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:101/0 64476 [] [] []",
+				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [] [] []",
+				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [] [] []",
+				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [] [] []",
 				"[l2vpn-evpn] 198.51.100.0/26 via 2001:db8::7 65017:104/0 64476 [] [] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:101/0 64476 [] [] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.0/25 via 192.0.2.7 65017:102/0 64476 [] [] []",
 				"[l3vpn-ipv4-unicast] 198.51.100.0/26 via 192.0.2.7 65017:103/0 64476 [] [] []",
-				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:102/0 396919 [] [] []",
 				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:101/0 396919 [] [] []",
-				"[ipv6-unicast] 2001:db8::6/127 via 2001:db8::7 0:0/0 65017 [] [] []",
-				"[ipv6-unicast] 2001:db8:1::/64 via 2001:db8::7 0:0/0 174 [] [] []",
-				"[ipv6-unicast] 2001:db8:2::/64 via 2001:db8::7 0:0/0 12322 [] [] []",
+				"[l3vpn-ipv4-unicast] 198.51.100.128/25 via 192.0.2.7 65017:102/0 396919 [] [] []",
 				"[l3vpn-ipv6-unicast] 2001:db8:4::/64 via 2001:db8::7 65017:101/0 29447 [] [] []",
 			},
 			netip.MustParseAddr("192.0.2.1"): {
@@ -1019,65 +1025,6 @@ func TestBMP(t *testing.T) {
 		}
 	})
 
-	t.Run("init, peers up, eor, reach NLRI, conn down, immediate timeout", func(t *testing.T) {
-		r := reporter.NewMock(t)
-		config := DefaultConfiguration()
-		configP := config.(Configuration)
-		configP.RIBPeerRemovalMaxTime = 1
-		configP.RIBPeerRemovalSleepInterval = 1
-		configP.RIBPeerRemovalBatchRoutes = 1
-		p, mockClock := NewMock(t, r, configP)
-		helpers.StartStop(t, p)
-		conn := dial(t, p)
-
-		send(t, conn, "bmp-init.pcap")
-		send(t, conn, "bmp-peers-up.pcap")
-		send(t, conn, "bmp-eor.pcap")
-		send(t, conn, "bmp-reach.pcap")
-		conn.Close()
-		time.Sleep(20 * time.Millisecond)
-		mockClock.Add(2 * time.Hour)
-		for tries := 20; tries >= 0; tries-- {
-			time.Sleep(5 * time.Millisecond)
-			gotMetrics := r.GetMetrics("akvorado_outlet_routing_provider_bmp_", "-locked_duration")
-			// For removed_partial_peers_total, we have 18 routes, but only 14 routes
-			// can be removed while keeping 1 route on each peer. 14 is the max, but
-			// we rely on good-willing from the scheduler to get this number.
-			peerRemovalPartial, _ := strconv.Atoi(gotMetrics[`removed_partial_peers_total{exporter="127.0.0.1"}`])
-			if peerRemovalPartial > 14 {
-				if tries > 0 {
-					continue
-				}
-				t.Errorf("Metrics: removed_partial_peers_total %d > 14", peerRemovalPartial)
-			}
-			if peerRemovalPartial < 5 {
-				if tries > 0 {
-					continue
-				}
-				t.Errorf("Metrics: removed_partial_peers_total %d < 5", peerRemovalPartial)
-			}
-			expectedMetrics := map[string]string{
-				`received_messages_total{exporter="127.0.0.1",type="initiation"}`:           "1",
-				`received_messages_total{exporter="127.0.0.1",type="peer-up-notification"}`: "4",
-				`received_messages_total{exporter="127.0.0.1",type="route-monitoring"}`:     "25",
-				`received_messages_total{exporter="127.0.0.1",type="statistics-report"}`:    "4",
-				`opened_connections_total{exporter="127.0.0.1"}`:                            "1",
-				`closed_connections_total{exporter="127.0.0.1"}`:                            "1",
-				`peers{exporter="127.0.0.1"}`:                                               "0",
-				`routes{exporter="127.0.0.1"}`:                                              "0",
-				`removed_peers_total{exporter="127.0.0.1"}`:                                 "4",
-				`removed_partial_peers_total{exporter="127.0.0.1"}`:                         fmt.Sprintf("%d", peerRemovalPartial),
-			}
-			if diff := helpers.Diff(gotMetrics, expectedMetrics); diff != "" {
-				if tries > 0 {
-					continue
-				}
-				t.Errorf("Metrics (-got, +want):\n%s", diff)
-			}
-			break
-		}
-	})
-
 	t.Run("lookup", func(t *testing.T) {
 		r := reporter.NewMock(t)
 		config := DefaultConfiguration()
@@ -1099,7 +1046,7 @@ func TestBMP(t *testing.T) {
 		}
 
 		// Add another prefix
-		p.rib.addPrefix(netip.MustParseAddr("2001:db8:1::"), 64, route{
+		p.rib.addPrefix(netip.MustParsePrefix("2001:db8:1::/64"), route{
 			peer:       1,
 			nlri:       p.rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC}),
 			nextHop:    p.rib.nextHops.Put(nextHop(netip.MustParseAddr("2001:db8::a"))),
diff --git a/outlet/routing/provider/bmp/tests.go b/outlet/routing/provider/bmp/tests.go
index b29711d1..3f20bbb6 100644
--- a/outlet/routing/provider/bmp/tests.go
+++ b/outlet/routing/provider/bmp/tests.go
@@ -6,11 +6,14 @@
 package bmp
 
 import (
+	"fmt"
 	"net"
 	"net/netip"
+	"reflect"
 	"testing"
 
 	"akvorado/common/daemon"
+	"akvorado/common/helpers"
 	"akvorado/common/reporter"
 	"akvorado/outlet/routing/provider"
 
@@ -46,7 +49,7 @@ func (p *Provider) PopulateRIB(t *testing.T) {
 		ptype:    bmp.BMP_PEER_TYPE_GLOBAL,
 		asn:      64500,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.0.2.0"), 96+27, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.0.2.0/123"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC, path: 1}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:198.51.100.4"))),
@@ -55,10 +58,10 @@ func (p *Provider) PopulateRIB(t *testing.T) {
 			asPath:           []uint32{64200, 1299, 174},
 			communities:      []uint32{100, 200, 400},
 			largeCommunities: []bgp.LargeCommunity{{ASN: 64200, LocalData1: 2, LocalData2: 3}},
-			plen:             96 + 27,
 		}),
+		prefixLen: 96 + 27,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.0.2.0"), 96+27, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.0.2.0/123"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC, path: 2}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:198.51.100.8"))),
@@ -66,10 +69,10 @@ func (p *Provider) PopulateRIB(t *testing.T) {
 			asn:         174,
 			asPath:      []uint32{64200, 174, 174, 174},
 			communities: []uint32{100},
-			plen:        96 + 27,
 		}),
+		prefixLen: 96 + 27,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.0.2.128"), 96+27, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.0.2.128/123"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:198.51.100.8"))),
@@ -77,57 +80,57 @@ func (p *Provider) PopulateRIB(t *testing.T) {
 			asn:         1299,
 			asPath:      []uint32{64200, 1299},
 			communities: []uint32{500},
-			plen:        96 + 27,
 		}),
+		prefixLen: 96 + 27,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:1.0.0.0"), 96+24, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:1.0.0.0/120"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{family: bgp.RF_IPv4_UC}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:198.51.100.8"))),
 		attributes: p.rib.rtas.Put(routeAttributes{
-			asn:  65300,
-			plen: 96 + 24,
+			asn: 65300,
 		}),
+		prefixLen: 96 + 24,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.168.144.0"), 96+21, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/117"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{rd: 10, family: bgp.RF_IPv4_UC, path: 0}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:203.0.113.14"))),
 		attributes: p.rib.rtas.Put(routeAttributes{
 			asn:    1234,
 			asPath: []uint32{54321, 1234},
-			plen:   96 + 21,
 		}),
+		prefixLen: 96 + 21,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.168.144.0"), 96+22, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.168.144.0/118"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{rd: 10, family: bgp.RF_IPv4_UC, path: 0}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:203.0.113.15"))),
 		attributes: p.rib.rtas.Put(routeAttributes{
 			asn:    1234,
 			asPath: []uint32{1234},
-			plen:   96 + 22,
 		}),
+		prefixLen: 96 + 22,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.168.148.0"), 96+22, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.168.148.0/118"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{rd: 10, family: bgp.RF_IPv4_UC, path: 0}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:203.0.113.15"))),
 		attributes: p.rib.rtas.Put(routeAttributes{
 			asn:    1234,
 			asPath: []uint32{1234},
-			plen:   96 + 22,
 		}),
+		prefixLen: 96 + 22,
 	})
-	p.rib.addPrefix(netip.MustParseAddr("::ffff:192.168.148.1"), 96+32, route{
+	p.rib.addPrefix(netip.MustParsePrefix("::ffff:192.168.148.1/128"), route{
 		peer:    pinfo.reference,
 		nlri:    p.rib.nlris.Put(nlri{rd: 10, family: bgp.RF_IPv4_UC, path: 0}),
 		nextHop: p.rib.nextHops.Put(nextHop(netip.MustParseAddr("::ffff:203.0.113.14"))),
 		attributes: p.rib.rtas.Put(routeAttributes{
 			asn:    1234,
 			asPath: []uint32{1234},
-			plen:   96 + 32,
 		}),
+		prefixLen: 96 + 32,
 	})
 }
 
@@ -136,10 +139,6 @@ func (p *Provider) LocalAddr() net.Addr {
 	return p.address
 }
 
-// Reduce hash mask to generate collisions during tests (this should
-// be optimized out by the compiler)
-const rtaHashMask = 0xff
-
 // MustParseRD parse a route distinguisher and panic on error.
 func MustParseRD(input string) RD {
 	var output RD
@@ -148,3 +147,7 @@ func MustParseRD(input string) RD {
 	}
 	return output
 }
+
+func init() {
+	helpers.AddPrettyFormatter(reflect.TypeOf(route{}), fmt.Sprint)
+}