Matching-first Route Origin Validation

1.1. Requirements Language

In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in RFC 2119 [RFC2119] when they appear in all upper case.¶

1.2. Terminology

Besides, the terms "VRP", "VRP Prefix", "VRP ASN", "Route", "Route Prefix", "Route Origin ASN", "Covered", "Matched", "NotFound", "Valid", "Invalid" are to be interpreted as described in RFC 6811 [RFC6811] when they appear in all upper case.¶

If a Route is Covered by a VRP, it is termed a covering VRP of that Route. Similarly, if a Route is Matched by a VRP, it is termed a matching VRP of that Route. For a given Route, a matching VRP is a special covering VRP such that: 1) its VRP ASN is the same as the Route Origin ASN and 2) its maxLength value is greater than or equal to the length of Route Prefix.¶

For a given Route, the process of finding out a covering VRP or figuring out whether there exists a covering VRP is termed FC, while the process of finding out a matching VRP or figuring out whether there exists a matching VRP is termed FM. The process to examine whether a covering VRP is a matching VRP is termed EM.¶

3.1. Comparative Validation Latency Impact by Validity Distribution

Validation of the full RIB (collected from RIPE NCC RIS RRC00 collector on 1st July, 2025) against ROAs (collected from RIPE NCC on 1st July, 2025) classifies routes into three subsets: Valid, Invalid, and NotFound. Using these subsets, we synthesized 55 test RIBs of fixed size (1,050,986 routes each) with controlled validity distributions. Each test RIB was constructed by randomly sampling specified quantities of routes from the Valid, Invalid, and NotFound subsets. The four ROV mechanisms preloaded with the collected ROAs were evaluated against all 55 synthetic RIBs, with results detailed below.¶

Experimental results confirm an inverse correlation between the proportion of Valid routes and validation efficiency in RTRLib, BGP-SRX, and BIRD-opt when the sum of routes in Valid or NotFound states is held constant. In tests with no Invalid routes, increasing the Valid ratio from 0 to 100% in 10% increments induced latency multipliers of 1.6, 1.9, and 3.5 for the respective implementations. With 10% of routes in Invalid state, the latency multipliers become 1.5, 1.8, and 3.1 under identical conditions. The root inefficiency stems from how non-covering first validation defers validation of Valid routes, where the latency penalty compounds as the proportion of Valid routes increases.¶

Contrasting with other implementations, BIRD-basic exhibits an inverse performance relationship: mean validation latency decreases with higher Valid route proportions. This anomaly stems from its structural divergence from true non-covering first validation. Without Trie optimization, BIRD-basic employs iterative hash probes to identify covering VRPs and cannot output NotFound until all probes complete. This design causes severe inefficiency in NotFound-dominant environments. This is the reason why BIRD-opt was developed. However, as Valid routes become prevalent, the way using iterative hash probes show its advantage since many Valid routes could be confirmed within few probes. Experimental results show BIRD-basic outperforming BIRD-opt in pure-Valid scenarios. Thus, BIRD-basic accidentally approximates (though inefficiently) the validation model proposed in Section 4.¶

The Validation Latency with RTRLib (nanosecond):¶

The Validation Latency with BGP-SRX (nanosecond):¶

The Validation Latency with BIRD-opt (nanosecond):¶

The Validation Latency with BIRD-basic (nanosecond):¶

3.2. Temporal Dynamics in ROV Efficiency

To evaluate ROV efficiency over time, quarterly snapshots of RIBs and ROAs were collected from January 2015 to July 2025 (January 1, April 1, July 1, and October 1 annually). These form 43 paired datasets, each containing a RIB and ROAs collected on the same date. Every dataset was evaluated by validating all routes in its RIB against corresponding ROAs using the four ROV mechanisms respectively, with results detailed below.¶

The Validation Latency with Five ROV Implementations (nanosecond):¶

Over time, Valid route prevalence increases significantly, with particularly rapid growth after 2019. This correlates with a proportional decline in NotFound states. Meanwhile, Invalid routes remain stable below 3.0%, exhibiting minor fluctuations. Consequently, ROV efficiency becomes predominantly governed by the latency performance for either Valid or NotFound route processing. Concurrently, expanding ROA datasets can also compound ROV computational demands.¶

Expanding ROA datasets and rising Valid route prevalence collectively drive significant latency growth in RTRLib, BGP-SRX, and BIRD-opt, which have increased by factors of 1.6, 2.4, and 2.2, respectively since 2020. However, BIRD-basic, while consistently outperformed by its Trie-optimized variant (BIRD-opt) throughout the observation period, exhibits marginal throughput gains since April 2025. This confirms that validity distribution has become the dominant factor to ROV efficiency of BIRD-basic.¶

3.3. A Brief Summary

• While non-covering first validation provided efficiency advantages during RPKI's initial deployment phase, it has become unsuitable for present-day validity distributions and will exhibit progressively worse scalability as RPKI adoption continues to grow.¶

• As RPKI adoption increases, two distinct factors, expanding ROA datasets and rising Valid route prevalence, independently yet collectively impact ROV efficiency. These separable influences warrant distinct optimization strategies.¶

4.1. Another Reference Implementation

BIRD-basic constitutes an implementation of this model, thus benefiting significantly from rising Valid route proportions. However, its efficiency remains suboptimal due to requiring multiple hash probes, each involving sequential FM examinations, to confirm Valid state. In contrast, h-ROV [h-ROV] provides a more efficient reference implementation through bitmap-encoded VRPs. This approach guarantees most Valid routes are identified via a single hash probe followed with a bitwise operation.¶

Experimental results (detailed below) for h-ROV, evaluated per the methodology described in Section 3.1, demonstrate 66.3%~85.7% lower validation latency than BIRD-basic under identical validity distributions. When Valid routes exceed 30%, h-ROV achieves the lowest latency among all evaluated ROV mechanisms.¶

The Validation Latency with h-ROV (nanosecond):¶

Experimental results for h-ROV (methodology per Section 3.2) show latency escalation consistent with other implementations due to expanding ROA datasets. However, h-ROV exhibits more moderate latency growth, offset by efficiency gains from rising Valid route prevalence. While BIRD-opt demonstrated the lowest latency before July 2019, h-ROV became the most efficient implementation after October 2019, with its performance advantage widening over time.¶

4.2. Lessons Lenard from Reference Implementations

• While the matching-first validation model enables scalable performance amid expanding ROA coverage, realized ROV efficiency remains contingent on implementation-specific optimizations.¶

• Prefix-level VRP management enables highly efficient implementations of the matching first validation model.¶

7.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

7.2. Informative References

[BGP-SRX]

NIST, "BGP Secure Routing Extension (BGP‑SRx) Software Suite", Web https://github.com/usnistgov/NIST-BGP-SRx, 2022.

[BIRD]

CZ.NIC, "The BIRD Internet Routing Daemon", Web https://bird.network.cz/, 2023.

[h-ROV]

ZD Ni, "From Address Blocks to Authorized Prefixes Redesigning RPKI ROV with a Hierarchical Hashing Scheme for Fast and Memory-Efficient Validation", 2025, <https://www.usenix.org/system/files/nsdi25-ni.pdf>.

[RFC6483]

Huston, G. and G. Michaelson, "Validation of Route Origination Using the Resource Certificate Public Key Infrastructure (PKI) and Route Origin Authorizations (ROAs)", RFC 6483, DOI 10.17487/RFC6483, February 2012, <https://www.rfc-editor.org/rfc/rfc6483>.

[RFC6811]

Mohapatra, P., Scudder, J., Ward, D., Bush, R., and R. Austein, "BGP Prefix Origin Validation", RFC 6811, DOI 10.17487/RFC6811, January 2013, <https://www.rfc-editor.org/rfc/rfc6811>.

[RTRLib]

NIST ANTD, "RTRlib. The RPKI RTR Client C Library.", Web https://rtrlib.realmv6.org/, 2023.