Certified Bank-Aware Fast-Path Coverage for Hardware-Constrained NDN Forwarding Lookup

1 Introduction

• Certificates let a selected shallow prefix stand in for deeper true-LPM classes only when their forwarding actions match and a sound guard identifies the target class.Packets the guard cannot certify fall back to an exact path.Source: §1 · p. 3
• BPC-Greedy evaluates certificate-aware marginal gains for prefix closures, and BPC-Portfolio returns the best feasible candidate from structurally different heuristics.A shallow prefix can be worthwhile when it enables high-weight same-action descendant classes despite modest traffic for its own exact-LPM class.Source: §1 · p. 3
• The extended preprint decomposes mapping into tree-closure placement, certificate selection, bank assignment, and budget splitting, with an exact memory-only dynamic program and bank-repair search.Source: §1 · p. 3
• For fixed selected state, top-k certificate selection is optimal under the unit-cost trace model, but adding a prefix changes the deepest match and available certificate pairs.Source: §1 · p. 3
• The preprint clarifies the oracle guard and bank abstraction and identifies guard-aware physical cost models as a next step.Source: §1 · p. 3

2 NDN Lookup and a Running Example

• The running example separates forwarding semantics from workload: FIB actions determine which descendant classes can safely share a shallow action, while the trace supplies their frequencies.Source: §2 · p. 4

• The mapper selects a parser-visible, prefix-closed trie set; structural closure nodes may be selected without being FIB entries, and no match yields ⊥.Source: §3 · pp. 4–5
• A certificate links selected state to a deeper target class without requiring that target to be selected, and certification requires a sound guard for that class.Source: §3 · p. 5
• Selected nodes are assigned to abstract banks under a shared object-equivalent budget; the reference certificate cost γ = 1 is a normalization, not a measured silicon-area equality.Source: §3 · p. 5
• The current bank-load proxy uses trace-derived true-LPM counts for action-bearing FIB nodes, zero for structural nodes, and does not charge certificates.The paper characterizes this as a feasibility proxy rather than a runtime memory model.Source: §3 · p. 5
• A positive target-class guard must imply that the packet’s true LPM is that class; false negatives may fall back, but false positives could change the forwarding action.Source: §3 · p. 5

4 Combinatorial Anatomy of the Placement Problem

• The mapper combines tree closure, certificate choice, bank partitioning, and budget splitting; certificate selection is easy for fixed S, but placement changes the other layers.Figure 2 summarizes this decomposition.Source: §4 · p. 5, Figure 2 · p. 6

4.1 Prefix closure creates reusable path cost

• Adding a prefix costs only its missing ancestors, so already-selected ancestors make the same deeper prefix cheaper.The marginal cost must be recomputed after each selection; a static traffic-to-depth ranking misses this reuse.Source: §4.1 · p. 6

4.2 Memory-only exact placement is a tree-knapsack dynamic program

• Prefix-closed exact placement alone admits a tree dynamic program, but bank assignment and certificate-aware state-dependent value break its clean one-dimensional budget structure.PCT-DP models the memory-only subproblem through subtree budget tables merged across children.Source: §4.2 · p. 6

4.3 For fixed S, certificate selection is exactly top-k

• For fixed S and uniform certificate cost, selecting the mC eligible pairs with largest qS(s, t) maximizes certificate hits.Distinct pairs cover disjoint traffic, so this fixed-set certificate subproblem needs no approximate solver.Source: §4.3 · p. 7

4.4 The hard coupling: S changes the certificate universe

• Changing S changes deepest selected matches and therefore removes or creates certificate pairs, making certificate value dependent on the selected prefix set.BPC-Greedy evaluates a candidate through its joint exact-plus-certificate effect.Source: §4.4 · p. 7

4.5 Bank assignment is a separate load-partition problem

• Bank assignment is a separate feasibility filter on selected prefixes, not part of the certificate top-k proof or a simulation of packet lookup scheduling.The implementation uses least-loaded-bank placement and checks feasibility.Source: §4.5 · p. 7

4.6 The generalized optimum contains exact-only placement as a special case

• The generalized optimum is at least the exact-only optimum because exact-only solutions remain feasible when certificates are unused; this is a model-level result, not a heuristic guarantee.BPC-Greedy has no approximation guarantee, while BPC-Portfolio includes exact-heavy candidates to partly mitigate that risk.Source: §4.6 · p. 8

5.1 Exact and bank-aware baselines

• Exact and bank-aware baselines range from popularity-only TopK and memory-only PCT-DP to bank-feasible greedy selection and leaf-removal repair.BankRepairOnly accepts a repaired trial only when feasible and when exact-prefix value improves.Source: §5.1 · p. 8

5.2 BPC-Greedy

• BPC-Greedy evaluates each prefix closure by certificate-aware marginal gain, rejecting trials that exceed the prefix budget or fail bank feasibility.For each budget split, it selects the top-mC certificate pairs for each trial, commits the best positive-gain trial, and retains the best split; its final name reflects that infeasible trials are skipped rather than repaired.Source: §5.2 · pp. 8–9

5.3 Why BPC is not “exact greedy + certificates”

• Unlike exact-first scoring, BPC values total safe traffic after certificates are recomputed, so a shallow prefix can win despite modest direct exact-LPM traffic.In the example, two certificate slots enable 65 hits from same-action descendant classes with weights 40 and 25.Source: §5.3 · p. 9

5.4 BPC-Portfolio as multi-bias search

• BPC-Portfolio compares structurally different candidate generators under common validation; its BPC-Greedy branch is selected in every reported real-name configuration.Other branches favor exact-LPM traffic or shallow shortcut anchors, and the portfolio retains the candidate with the best certified coverage, then exact value, then fewer nodes.Source: §5.4 · pp. 9–10, Figure 3 · p. 11

5.5 Complexity and why the current implementation is expensive

• The current candidate-evaluation bound is O(rIn (Nh + |S| log |S|)), making the full 50k sweep an offline design-space exploration rather than a runtime algorithm.Proposed speedups include caching closures and LPM labels, incremental certificate counts, lazy-greedy bounds, budget-split pruning, and action-homogeneous-region compression.Source: §5.5 · pp. 10–11

6 The Guard Abstraction and the Next Architectural Problem

• The evaluator uses the known true LPM to instantiate the target-class guard, so its results do not establish that a low-cost runtime guard exists.The paper identifies the guard as the key unresolved architectural component.Source: §6 · p. 11
• A practical guard need not solve full multi-class LPM; it can ask only whether there is sufficient evidence to certify one target class, with uncertainty falling back.This is a conservative one-sided classification role.Source: §6 · p. 11
• A future cost model could price each certificate by metadata, guard bits, and expected access cost, targeting high-traffic action-equivalent classes with cheap one-sided signatures.The paper presents this as a future optimization connecting semantic opportunity to implementable hardware cost.Source: §6 · p. 11

7 Implementation Correspondence and Reproducibility

• Table 1 maps mathematical concepts to the released code structure used for the experiments.The implementation is a Python package with experiment drivers.Source: §7 · p. 11, Table 1 · p. 12
• The trace construction inserts FIB prefixes and observed Interest paths, then replays Interests against the full FIB trie to derive true-LPM counts used as weights and bank-load proxies.The repository test suite contains 13 automated tests covering trie/name behavior, certificates, bank repair, BPC, portfolio, and other listed components.Source: §7 · p. 12
• The real-name run uses deterministic sample seed 1 and preserves raw rows, summary CSVs, metadata, and source totals; all 18 portfolio winners report the legacy BPC-Repair label.The final sweep’s BPC-Repair label refers to the BPC-Greedy branch.Source: §7 · p. 12
• The main real-name configuration derives a pruned FIB and action classes from observed names, so it represents a synthetic forwarding-action snapshot rather than live-router routing state.The configuration is identified as the main real-name experiment configuration.Source: Table 2 · p. 13

8.1 Workloads

• The workloads comprise a 1,200-Interest synthetic trace and a 50,000-name sample from public NDN testbed data, of which 49,961 names have a matched FIB LPM.The sampled run uses seed 1; the synthetic trace uses seed 7 and Zipf parameter α = 1.1.Source: §8.1 · p. 13
• The public-name replay uses a pruned 143-prefix FIB with six synthetic action classes, not a live router’s forwarding state.Actions are assigned from first name components; at D = 8, 34,076 matched Interests are parser-visible.Source: §8.1 · p. 13

8.2 Configuration

• The two bank regimes represent different capacity assumptions: fixed-total partitions fixed capacity, while fixed-per-bank grows total capacity as banks are added.The supplied passages do not specify further configuration values.Source: §8.2 · p. 13

8.3 Metrics

• The metrics count exact hits plus accepted same-action certificate hits as coverage, send remaining traffic to fallback, and report prefix-bank feasibility separately.Would-be unsafe traffic is the fallback subset matching selected shallow state but neither exact nor certified.Source: §8.3 · p. 13, Table 3 · p. 14

9.1 Parser depth is a first-order constraint

• Parser-visible traffic rises from 36.83% at D = 6 to 91.92% at D = 8 and reaches 100% at D = 10, before placement can help.Packets whose required name structure is not visible cannot benefit from a prefix or certificate.Source: §9.1 · p. 14

9.2 Certificate-aware placement increases modeled coverage

• At M = 48, selected BPC states contain 16 trie nodes and use γ = 1 as a reference normalization, not a measured equality of physical cost.The reported states at M = 16, 32, and 48 contain 4, 8, and 16 trie nodes, with certificate budgets of 12, 24, and 32, respectively.Source: §9.2 · p. 14
• At M = 48, modeled coverage increases from 46.48% for BankRepairOnly to 64.06% for BPC-Portfolio, a gain of 17.58 percentage points.The figure covers modeled certified coverage on the 50k real-name replay under the synthetic action snapshot; BankRepairOnly is the best exact-only result across tested bank settings at each budget.Source: §9.2 · p. 14, Figure 6 · p. 15

9.3 The bank results require careful interpretation

• At M = 48, BPC remains at 64.06% because its selected prefix state is small enough to be feasible in every tested bank setting, while exact-only coverage is strongly affected by the tested regime.Source: §9.3 · p. 15
• The bank model omits certificate and guard accesses, charges shallow nodes their trace-derived true-LPM load, and does not simulate runtime bank operations.The experiments therefore represent an abstract resource-pressure dimension; a concrete certificate-table datapath remains a follow-up evaluation.Source: §9.3 · p. 15

When Certificates Are Most Valuable

• A shallow prefix can safely cover high-traffic same-action descendant classes while conflicting classes fall back; the example covers 65 traffic units with three certificates and leaves the conflicting class uncovered.If all descendants share the action, direct FIB compression may be more suitable; if most differ, certificate opportunity is small.Source: §10 · p. 15
• The most promising classes combine high traffic with same-action equivalence and cheap one-sided guards.A proposed future value model weighs safely certified traffic against certificate bits, guard cost, and expected access cost.Source: §10 · p. 16

11 Related Work

• Related systems demonstrate fast paths across software, specialized lookup structures, FPGA, programmable-switch, and probabilistic-summary substrates; this paper asks a complementary offline placement question.The cited examples include NFD and NDN-DPDK, FPGA FIB lookup engines, and Vision and Pegasus.Source: §11 · p. 16

12 Limitations and Research Directions

• The evaluator uses known true LPM as an oracle-style guard; a practical design needs a bounded, sound runtime guard, potentially based on one-sided signatures.Uncertain classes are to be rejected to fallback rather than certified.Source: §12 · p. 16
• The replay uses synthetic forwarding actions, so action-model sensitivity and live forwarding-state snapshots are needed before making claims about operational routing policies.The public traces do not provide a complete live FIB snapshot.Source: §12 · pp. 16–17
• Certificate and guard bank load is omitted, runtime bank lookup is unmodeled, and the paper reports no synthesis, timing, power, area, or calibrated-throughput results.The stated contribution is offline placement formulation and opportunity characterization.Source: §12 · p. 17
• Naive certificate-aware candidate evaluation repeatedly scans the trace; incremental counts, lazy evaluation, subtree compression, and guard-aware pruning are proposed engineering improvements.Source: §12 · p. 17

13 Conclusion

• The formulation separates tree-closure placement, fixed-state top-k certificate selection, and bank feasibility, but selected state changes the certificate universe and couples the full problem.The work frames the question as offline placement and design-space characterization, rather than an end-to-end forwarding datapath.Source: §11 · p. 16, §13 · p. 17
• On the reported real-name replay under a synthetic action snapshot, modeled certified coverage rises from 46.48% to 64.06% at M = 48.The conclusion attributes the result to BPC-Greedy’s certificate-aware scoring and BPC-Portfolio’s combination of search biases.Source: §13 · p. 17

A Worked Microexample

• Top-2 certificates cover 65 packets: (s, t1) and (s, t2) are valid, while (s, t3) is invalid because its forwarding action differs.The trace weights are 40, 25, and 20 for t1, t2, and t3; selecting s costs one new trie node and the certificate budget is two.Source: A Worked Microexample · pp. 17–18
• Adding a deeper selected node s′ in the t1 branch can shift packets from (s, t1) to exact hits or a new pair (s′, t1), so prefix selection is not trivial.Source: A Worked Microexample · p. 18

B Implementation-Level Pseudocode for Certificate Evaluation

• Evaluation labels an Interest an exact hit when the deepest selected match equals its true LPM, a certificate hit when their pair is chosen, and otherwise falls back.The certificate branch currently uses trace-known true LPM as an oracle guard; physical implementation requires a sound runtime guard.Source: B Implementation-Level Pseudocode for… · p. 18

C Why Certificates Are Not Prefix-Closed

• Trie-state prefix closure applies to selected nodes S, not certificate metadata K; a certificate target may remain unselected if it is a deeper same-action target of a selected parser-visible prefix.Requiring certificate targets to be selected would defeat the construction’s main storage advantage.Source: C Why Certificates Are Not Prefix-Closed · p. 18