SIDR Operations Y. Li Internet-Draft H. Zou Intended status: Standards Track G. Xie Expires: 8 January 2026 CNIC, CAS 7 July 2025 Matching-first Route Origin Validation draft-li-sidrops-matching-rov-00 Abstract Route Origin Validation (ROV) using the Resource Public Key Infrastructure (RPKI) enables BGP routers to identify illegitimate routes that violate Route Origin Authorizations (ROAs). However, widespread deployment of RPKI requires validation systems to process high volumes of route announcements against increasingly large ROA datasets, where ROV adoption faces significant barriers due to concerns about its processing efficiency. This document identifies a performance issue inherent in current ROV procedure, which could be exacerbated as the expanding coverage of ROAs. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 8 January 2026. Copyright Notice Copyright (c) 2025 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights Li, et al. Expires 8 January 2026 [Page 1] Internet-Draft MF-ROV July 2025 and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 2. Overview of Current ROV Procedure . . . . . . . . . . . . . . 3 3. Performance Issue Analysis and Evaluation . . . . . . . . . . 4 3.1. Comparative Validation Latency Impact by Validity Distribution . . . . . . . . . . . . . . . . . . . . . . 4 3.2. Temporal Dynamics in ROV Efficiency . . . . . . . . . . . 9 3.3. A Brief Summary . . . . . . . . . . . . . . . . . . . . . 12 4. Matching First Route Origin Validation . . . . . . . . . . . 12 4.1. Another Reference Implementation . . . . . . . . . . . . 13 4.2. Lessons Lenard from Reference Implementations . . . . . . 14 5. Security Considerations . . . . . . . . . . . . . . . . . . . 15 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 7.1. Normative References . . . . . . . . . . . . . . . . . . 15 7.2. Informative References . . . . . . . . . . . . . . . . . 15 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15 1. Introduction The rapid deployment of RPKI has significantly expanded Route Origin Authorization (ROA) coverage. However, validating large volumes of route announcements against increasingly massive ROA datasets poses a significant challenge for routers. These efficiency concerns regarding Route Origin Validation (ROV) create a barrier to its wider adoption. Current ROV implementations, defined in RFCs 6483 and 6811, typically perform an initial coarse-grained match of a BGP route against all ROAs before verifying an exact match. This approach optimizes for routes without ROA coverage, allowing their validity state (e.g., NotFound) to be determined quickly. However, as ROA coverage expands, this method suffers performance degradation: validation latency increases proportionally with the expanding ROA datasets, especially the increasing number of BGP routes that can pass the validation. Evaluations of open-source ROV implementations confirm this scaling issue. Li, et al. Expires 8 January 2026 [Page 2] Internet-Draft MF-ROV July 2025 To mitigate performance degradation caused by shifting validity distributions, this document defines a modified validation model through step reordering. The optimized workflow first performs precise matching against all ROAs to immediately identify Valid routes, followed by coverage verification to determine NotFound status. Performance evaluations of reference implementations confirm the model's superiority. 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*. 2. Overview of Current ROV Procedure As a informational, RFC 6483 [RFC6483] describes a general procedure to determine the validity state of a given Route against a set of VRPs, which can be summarized as follows using the terms FC and EM. * FC step: iteratively perform FC to find out all covering VRPs, output NotFound if there is no covering VRP; otherwise go to the EM step. * EM step: iteratively perform EM to examine every covering VRP, output Invalid if there is no matching VRP; otherwise output Valid once a matching VRP is found. Li, et al. Expires 8 January 2026 [Page 3] Internet-Draft MF-ROV July 2025 RFC 6811 [RFC6811] has standardized the validation procedure and provides the corresponding pseudo-code, which illustrates a similar procedure as the above one but could be more efficient regarding system implementation. This validation procedure can be summarized as follows using the terms FC and EM. * FC step: perform FC to find out the first covering VRP, output NotFound if this step fails; otherwise go to the EM step. * EM step: iteratively perform EM to examine the current covering VRP and perform FC to find out the next covering VRP, output Invalid if there is no matching VRP; otherwise output Valid once a matching VRP is found. Actually, the ROV implementations with the RTRLib [RTRLib], BIRD [BIRD] and BGP-SRX [BGP-SRX] all follow the above validation procedure. They all adopt Trie-like structures for FC and can output NotFound fast at the earliest stage. We call this validation procedure the *non-covering* first validation. 3. Performance Issue Analysis and Evaluation Non-covering first validation optimizes for BGP routes in the NotFound state. However, this approach delays determining the validity state of Valid routes, which was a tolerable tradeoff during early RPKI deployment when sparse ROA coverage resulted in predominantly NotFound states. However, today, with more than half of global BGP routes are in the Valid state (and growing), non- covering first validation incurs escalating latency as both ROA volume and Valid routes increase simultaneously. To quantify this scaling limitation, we measured ROV efficiency using real-world ROA datasets and BGP routing tables. We evaluated four implementations: RTRLib, BGP-SRX, BIRD's basic ROV (BIRD-basic), and BIRD's Trie-optimized ROV (BIRD-opt). The mean validation latency per route during full-table processing served as the efficiency metric. Related source code, datasets and results can be accessed via: https://github.com/FIRLab-CNIC/h-2ROV 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 Li, et al. Expires 8 January 2026 [Page 4] Internet-Draft MF-ROV July 2025 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):* Li, et al. Expires 8 January 2026 [Page 5] Internet-Draft MF-ROV July 2025 +============+====+====+====+====+====+====+====+====+====+====+====+ | % of |0% |10% |20% |30% |40% |50% |60% |70% |80% |90% |100%| | Valid | | | | | | | | | | | | +============+====+====+====+====+====+====+====+====+====+====+====+ | % of | | | | | | | | | | | | | NotFound | | | | | | | | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 0% |1190|1214|1241|1266|1282|1306|1351|1359|1376|1406|1464| +------------+----+----+----+----+----+----+----+----+----+----+----+ | 10% |1173|1192|1215|1237|1361|1280|1321|1346|1476|1399| | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 20% |1147|1170|1194|1221|1232|1254|1281|1315|1321| | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 30% |1123|1148|1170|1195|1206|1245|1268|1351| | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 40% |1092|1119|1141|1237|1189|1218|1238| | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 50% |1072|1095|1119|1144|1165|1184| | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 60% |1047|1069|1092|1117|1137| | | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 70% |1018|1048|1062|1092| | | | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 80% |996 |1020|1038| | | | | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 90% |962 |984 | | | | | | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ | 100% |929 | | | | | | | | | | | +------------+----+----+----+----+----+----+----+----+----+----+----+ Table 1 *The Validation Latency with BGP-SRX (nanosecond):* Li, et al. Expires 8 January 2026 [Page 6] Internet-Draft MF-ROV July 2025 +==========+===+===+===+===+===+===+===+======+======+======+======+ | % of |0% |10%|20%|30%|40%|50%|60%| 70% | 80% | 90% | 100% | | Valid | | | | | | | | | | | | +==========+===+===+===+===+===+===+===+======+======+======+======+ | % of | | | | | | | | | | | | | NotFound | | | | | | | | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 0% |580|650|703|761|817|872|946| 994 | 1022 | 1115 | 1138 | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 10% |597|653|701|765|804|859|947| 1007 | 1054 | 1115 | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 20% |605|650|706|760|813|865|951| 1002 | 1019 | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 30% |601|653|706|765|809|892|945| 974 | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 40% |606|655|725|770|840|877|941| | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 50% |609|664|719|767|835|872| | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 60% |614|659|715|775|823| | | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 70% |616|668|720|771| | | | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 80% |617|667|724| | | | | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 90% |621|669| | | | | | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ | 100% |616| | | | | | | | | | | +----------+---+---+---+---+---+---+---+------+------+------+------+ Table 2 *The Validation Latency with BIRD-opt (nanosecond):* Li, et al. Expires 8 January 2026 [Page 7] Internet-Draft MF-ROV July 2025 +============+===+===+===+===+===+===+=====+=====+=====+=====+======+ | % of |0% |10%|20%|30%|40%|50%| 60% | 70% | 80% | 90% | 100% | | Valid | | | | | | | | | | | | +============+===+===+===+===+===+===+=====+=====+=====+=====+======+ | % of | | | | | | | | | | | | | NotFound | | | | | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 0% |442|458|474|494|508|522| 534 | 564 | 564 | 616 | 591 | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 10% |420|439|449|466|475|496| 524 | 557 | 569 | 589 | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 20% |392|416|421|439|450|466| 511 | 519 | 502 | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 30% |366|381|411|410|419|449| 513 | 464 | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 40% |337|353|372|398|405|411| 435 | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 50% |309|323|343|353|385|382| | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 60% |279|296|310|327|362| | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 70% |253|270|299|296| | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 80% |225|240|254| | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 90% |198|220| | | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 100% |168| | | | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ Table 3 *The Validation Latency with BIRD-basic (nanosecond):* Li, et al. Expires 8 January 2026 [Page 8] Internet-Draft MF-ROV July 2025 +==========+====+====+====+====+====+====+======+===+===+===+======+ | % of |0% |10% |20% |30% |40% |50% | 60% |70%|80%|90%| 100% | | Valid | | | | | | | | | | | | +==========+====+====+====+====+====+====+======+===+===+===+======+ | % of | | | | | | | | | | | | | NotFound | | | | | | | | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 0% |1457|1358|1259|1169|1076|995 | 882 |800|699|602| 508 | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 10% |1501|1418|1314|1215|1123|1031| 947 |859|757|685| | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 20% |1542|1456|1354|1273|1171|1080| 980 |916|793| | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 30% |1594|1502|1437|1329|1219|1150| 1068 |931| | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 40% |1646|1559|1494|1423|1295|1224| 1101 | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 50% |1681|1592|1513|1410|1351|1226| | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 60% |1757|1637|1553|1458|1399| | | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 70% |1777|1735|1634|1513| | | | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 80% |1842|1742|1647| | | | | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 90% |1931|1853| | | | | | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ | 100% |1969| | | | | | | | | | | +----------+----+----+----+----+----+----+------+---+---+---+------+ Table 4 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):* Li, et al. Expires 8 January 2026 [Page 9] Internet-Draft MF-ROV July 2025 +==========+=========+==========+============+==========+=========+ | | h-ROV | RTRLib | BIRD-basic | BIRD-opt | BGP-SRX | +==========+=========+==========+============+==========+=========+ | 20150101 | 165.098 | 523.560 | 757.002 | 118.413 | 175.254 | +----------+---------+----------+------------+----------+---------+ | 20150401 | 158.655 | 491.642 | 791.139 | 115.407 | 178.476 | +----------+---------+----------+------------+----------+---------+ | 20150701 | 155.087 | 497.265 | 827.130 | 113.161 | 180.930 | +----------+---------+----------+------------+----------+---------+ | 20151001 | 154.083 | 497.265 | 834.028 | 113.122 | 182.548 | +----------+---------+----------+------------+----------+---------+ | 20160101 | 163.399 | 503.778 | 863.558 | 113.804 | 185.322 | +----------+---------+----------+------------+----------+---------+ | 20160401 | 149.410 | 504.032 | 689.180 | 113.623 | 184.570 | +----------+---------+----------+------------+----------+---------+ | 20160701 | 165.920 | 514.139 | 738.007 | 114.837 | 188.005 | +----------+---------+----------+------------+----------+---------+ | 20161001 | 146.649 | 517.331 | 744.602 | 115.580 | 189.179 | +----------+---------+----------+------------+----------+---------+ | 20170101 | 147.189 | 519.751 | 755.858 | 116.618 | 192.976 | +----------+---------+----------+------------+----------+---------+ | 20170401 | 151.378 | 528.262 | 791.766 | 117.495 | 195.810 | +----------+---------+----------+------------+----------+---------+ | 20170701 | 155.063 | 531.632 | 819.672 | 119.775 | 201.450 | +----------+---------+----------+------------+----------+---------+ | 20171001 | 158.403 | 542.005 | 884.956 | 121.907 | 204.583 | +----------+---------+----------+------------+----------+---------+ | 20180101 | 161.316 | 541.712 | 924.214 | 123.305 | 212.811 | +----------+---------+----------+------------+----------+---------+ | 20180401 | 171.438 | 553.403 | 732.601 | 125.109 | 216.967 | +----------+---------+----------+------------+----------+---------+ | 20180701 | 154.154 | 634.921 | 823.723 | 143.740 | 264.971 | +----------+---------+----------+------------+----------+---------+ | 20181001 | 159.668 | 648.508 | 838.926 | 145.879 | 273.973 | +----------+---------+----------+------------+----------+---------+ | 20190101 | 154.967 | 668.003 | 923.361 | 154.727 | 298.063 | +----------+---------+----------+------------+----------+---------+ | 20190401 | 164.123 | 684.463 | 759.301 | 160.436 | 314.367 | +----------+---------+----------+------------+----------+---------+ | 20190701 | 174.307 | 699.790 | 759.301 | 164.177 | 328.192 | +----------+---------+----------+------------+----------+---------+ | 20191001 | 158.957 | 722.543 | 872.600 | 174.917 | 353.982 | +----------+---------+----------+------------+----------+---------+ | 20200101 | 178.987 | 742.390 | 985.222 | 185.632 | 371.609 | +----------+---------+----------+------------+----------+---------+ | 20200401 | 173.370 | 771.010 | 1025.641 | 195.313 | 405.186 | +----------+---------+----------+------------+----------+---------+ | 20200701 | 179.340 | 800.000 | 827.815 | 210.793 | 448.029 | Li, et al. Expires 8 January 2026 [Page 10] Internet-Draft MF-ROV July 2025 +----------+---------+----------+------------+----------+---------+ | 20201001 | 188.076 | 835.422 | 912.409 | 228.102 | 490.677 | +----------+---------+----------+------------+----------+---------+ | 20210101 | 205.719 | 865.801 | 989.120 | 244.141 | 529.661 | +----------+---------+----------+------------+----------+---------+ | 20210401 | 194.970 | 882.613 | 1109.878 | 254.582 | 559.284 | +----------+---------+----------+------------+----------+---------+ | 20210701 | 205.592 | 906.618 | 1273.885 | 265.816 | 575.705 | +----------+---------+----------+------------+----------+---------+ | 20211001 | 198.570 | 883.392 | 1140.251 | 242.307 | 544.959 | +----------+---------+----------+------------+----------+---------+ | 20220101 | 206.313 | 930.233 | 1406.470 | 271.370 | 592.417 | +----------+---------+----------+------------+----------+---------+ | 20220401 | 210.881 | 962.464 | 1034.126 | 285.225 | 651.466 | +----------+---------+----------+------------+----------+---------+ | 20220701 | 211.685 | 982.318 | 1046.025 | 298.954 | 678.887 | +----------+---------+----------+------------+----------+---------+ | 20221001 | 212.811 | 1005.025 | 1101.322 | 314.169 | 707.714 | +----------+---------+----------+------------+----------+---------+ | 20230101 | 216.263 | 1000.000 | 1187.648 | 303.767 | 679.348 | +----------+---------+----------+------------+----------+---------+ | 20230401 | 223.115 | 1034.126 | 1254.705 | 328.947 | 695.894 | +----------+---------+----------+------------+----------+---------+ | 20230701 | 225.785 | 1039.501 | 1245.330 | 329.056 | 767.460 | +----------+---------+----------+------------+----------+---------+ | 20231001 | 255.754 | 1062.699 | 1333.333 | 355.999 | 775.795 | +----------+---------+----------+------------+----------+---------+ | 20240101 | 257.533 | 1079.914 | 1362.398 | 370.096 | 795.545 | +----------+---------+----------+------------+----------+---------+ | 20240401 | 239.292 | 1062.699 | 1443.001 | 350.140 | 747.384 | +----------+---------+----------+------------+----------+---------+ | 20240701 | 244.618 | 1104.972 | 1631.321 | 383.877 | 823.045 | +----------+---------+----------+------------+----------+---------+ | 20241001 | 246.488 | 1097.695 | 1510.574 | 376.506 | 794.913 | +----------+---------+----------+------------+----------+---------+ | 20250101 | 246.488 | 1106.195 | 1555.210 | 385.654 | 859.845 | +----------+---------+----------+------------+----------+---------+ | 20250401 | 255.493 | 1156.069 | 1049.318 | 397.298 | 884.173 | +----------+---------+----------+------------+----------+---------+ | 20250701 | 254.001 | 1173.709 | 1089.325 | 409.668 | 892.857 | +----------+---------+----------+------------+----------+---------+ Table 5 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. Li, et al. Expires 8 January 2026 [Page 11] Internet-Draft MF-ROV July 2025 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. Matching First Route Origin Validation Non-covering first validation, though pivotal during initial RPKI deployment, fails to scale in modern environments where Valid routes have exceed 50% and continue growing, rendering it fundamentally mismatched to current validity distributions and those in future. Revisiting the validation model is now imperative to guide ROV implementations toward capitalizing on rising Valid route prevalence while mitigating scaling challenges from expanding ROA datasets. The critical optimization involves prioritizing matching VRP discovery over covering VRP searches. Such a matching first validation procedure can be defined as follows. * FM step: find out a matching VRP or figuring out whether there exists a matching VRP, output Valid if there is one; otherwise go to the FC step. * FC step: find out a covering VRP or figuring out whether there exists a covering VRP, output Invalid if there is one; otherwise output NotFound. Li, et al. Expires 8 January 2026 [Page 12] Internet-Draft MF-ROV July 2025 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):* Li, et al. Expires 8 January 2026 [Page 13] Internet-Draft MF-ROV July 2025 +============+===+===+===+===+===+===+=====+=====+=====+=====+======+ | % of |0% |10%|20%|30%|40%|50%| 60% | 70% | 80% | 90% | 100% | | Valid | | | | | | | | | | | | +============+===+===+===+===+===+===+=====+=====+=====+=====+======+ | % of | | | | | | | | | | | | | NotFound | | | | | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 0% |209|207|204|199|195|192| 187 | 186 | 192 | 174 | 171 | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 10% |218|217|213|211|205|202| 200 | 197 | 192 | 189 | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 20% |228|225|222|220|215|211| 206 | 206 | 199 | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 30% |236|236|235|229|222|223| 218 | 199 | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 40% |246|245|242|220|234|232| 227 | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 50% |255|251|251|247|245|239| | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 60% |265|263|257|257|253| | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 70% |276|271|266|266| | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 80% |283|281|276| | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 90% |294|293| | | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ | 100% |298| | | | | | | | | | | +------------+---+---+---+---+---+---+-----+-----+-----+-----+------+ Table 6 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. Li, et al. Expires 8 January 2026 [Page 14] Internet-Draft MF-ROV July 2025 5. Security Considerations The security considerations in Section 6 of RFC6811 [RFC6811] are also applied to this document. 6. IANA Considerations This document has no IANA actions. 7. References 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, . 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, . [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, . [RFC6811] Mohapatra, P., Scudder, J., Ward, D., Bush, R., and R. Austein, "BGP Prefix Origin Validation", RFC 6811, DOI 10.17487/RFC6811, January 2013, . [RTRLib] NIST ANTD, "RTRlib. The RPKI RTR Client C Library.", Web https://rtrlib.realmv6.org/, 2023. Authors' Addresses Li, et al. Expires 8 January 2026 [Page 15] Internet-Draft MF-ROV July 2025 Yanbiao Li CNIC, CAS Email: lybmath@cnic.cn Hui Zou CNIC, CAS Email: zouhui@cnic.cn Gaogang Xie CNIC, CAS Email: xie@cnic.cn Li, et al. Expires 8 January 2026 [Page 16]