Online Tree Caching

I. INTRODUCTION

• If a node is cached, all nodes in its rooted subtree must also be cached, so the cache is a subforest of the item tree.Source: §I · p. 1
• Requests may be positive or negative, and fetching or evicting each node costs α; the goal is to minimize service and cache-maintenance costs.Source: §I · p. 1

A. Our Contributions and Paper Organization

• TC is deterministic and O(h(T) · kONL/(kONL − kOPT + 1))-competitive, matching an Ω(kONL/(kONL − kOPT + 1)) lower bound up to O(h(T)).The paper also reports an experimental comparison on synthetic workloads and real-world packet traces.Source: A. Our Contributions and Paper… · p. 1

B. Related Work on Caching

• Prior work studied dependency-aware caching, but related models differ in their dependency structure, request rules, or cost measures.Dallot et al. [16] give a randomized bypassing algorithm for DAG dependencies; the paper positions its work as providing theoretical foundations for tree dependencies.Source: B. Related Work on Caching · p. 2

• The model is motivated by router memory constraints and applies to SDN architectures where a controller manages expensive router memory.Source: §II · p. 2
• The router serves packets whose longest matching rule is cached; otherwise, requests go to the controller, while cache changes incur a fixed cost α.Source: §II · p. 2, Figure 1 · p. 3
• Keeping a less-specific rule while evicting a more-specific descendant can route packets incorrectly, motivating the requirement that cached nodes form a subforest.Source: §II · p. 3
• Earlier approaches avoided dependencies or lacked worst-case guarantees for caching cost, while CacheFlow supports dependencies but was evaluated experimentally.Source: §II · p. 3
• Rule updates are modeled by α negative requests to the updated node, simulating the router update penalty with at most a factor-2 change in cost.Source: §II · p. 3

III. PRELIMINARIES

• A feasible cache is a subforest of T and must respect capacity; each node fetch or eviction costs α, and the algorithm starts with an empty cache.Source: §III · p. 3

IV. ALGORITHM

• TC applies a valid changeset when its accumulated request cost reaches the cost of fetching or evicting that set.It maintains per-node counters, resets a node’s counter when that node changes cache state, and starts a new phase if a fetch would exceed capacity.Source: §IV · p. 4

V. ANALYSIS OF TC

• After TC applies a changeset, no valid changeset is saturated, and any valid changeset’s accumulated counter total is at most its size times α.Source: §IV · p. 4, §V · p. 4
• The analysis shifts requests up or down the tree to make them more structured without increasing OPT’s cost.Source: §V · p. 4

A. Event Space and Fields

• The event space indexes tree nodes and phase rounds; each request occupies a node-round slot, and fields partition these slots.Source: A. Event Space and Fields · p. 4
• Each field contains requests tied to a TC changeset, and its request count equals α times its number of involved nodes.Positive and negative fields contain requests of their respective types.Source: A. Event Space and Fields · p. 4
• TC’s phase cost is bounded by 2α times the total field size, plus open-field requests and a final-eviction term.Source: A. Event Space and Fields · p. 5

B. Shifting Requests

• Legal shifting moves positive requests to descendants or the same node and negative requests to ancestors or the same node, ensuring OPT’s cost does not increase.The construction aims to distribute negative requests evenly within their fields and positive requests approximately evenly while keeping them within positive fields.Source: B. Shifting Requests · p. 5

C. Shifting Negative Requests Up

• Each negative field can be shifted legally within that field so every node of Xt receives exactly α requests.The proof processes leaves, retaining α requests at each leaf and shifting any excess to its parent.Source: C. Shifting Negative Requests Up · p. 5

D. Shifting Positive Requests Down

• Within a single positive field, no shifting strategy can guarantee even a constant fraction of nodes with Ω(α) requests.The star example places root requests before leaf slots, preventing those requests from being shifted to leaves within the field.Source: D. Shifting Positive Requests Down · p. 6
• For any tree cap D in a positive field, the request count is at least |D|·α.The bound uses the complement of D as a valid positive changeset when D is not the whole changeset.Source: D. Shifting Positive Requests Down · p. 6
• At least N/(2h(T)) positive-field rows become full after shifting requests downward across fields.A full row has at least α/2 requests; the shifts may move a request to a different positive field.Source: D. Shifting Positive Requests Down · p. 6
• The positive-request guarantee follows by charging wasted requests to full rows, with each row receiving at most h(T)·α total charge.The resulting bound is M ≥ N/(2h(T)) full rows.Source: D. Shifting Positive Requests Down · p. 6

E. Using Request Shifting for Bounding OPT

• For any phase P, OPT(P) ≥ (size(F)/(4h(T)) − kP)·α/2.The proof transforms the phase using legal request shifts and charges each full OUT-IN pair at least α/2 to OPT.Source: E. Using Request Shifting for Bounding… · pp. 6–7

F. Competitive Ratio

• For any phase, req(F∞) ≤ 2·kONL·α + 2·OPT(P).This bound applies to finished and unfinished phases.Source: F. Competitive Ratio · p. 7
• TC’s per-phase cost is at most O(h(T))·OPT(P) + O(h(T)·(kP+kONL)·α).For an unfinished phase, kP ≤ kONL.Source: F. Competitive Ratio · p. 7
• For a finished phase, kP·α ≤ OPT(P)·(kONL+1)/(kONL+1−kOPT).The bound uses that a finished phase has kP ≥ kONL+1.Source: F. Competitive Ratio · p. 7
• TC is O(h(T)·kONL/(kONL−kOPT+1))-competitive.The theorem follows by combining the finished-phase bound with the unfinished-phase cost bound and summing across phases.Source: F. Competitive Ratio · pp. 7–8

VI. IMPLEMENTATION OF TC

• TC uses O(|T|) additional memory and makes each decision in O(h(T)+max{h(T),deg(T)}·|Xt|) operations.Here deg(T) is the maximum node degree, and |Xt| is zero when no changeset is applied.Source: §VI · p. 8
• After a positive request, TC checks at most h(T) possible positive changesets using an auxiliary data structure.Updating that structure costs O(h(T)+h(T)·|Xt|).Source: §VI · p. 8
• For negative changesets, an auxiliary structure returns a viable candidate in O(h(T)+deg(T)·|Xt|) time.Its update has the same operation bound.Source: §VI · p. 8

A. Positive Requests and Fetches

• After a positive request, TC scans ancestor-rooted tree caps from the root toward the requested node and fetches the first saturated candidate, if any.The scan takes O(h(T)) time; the maintained counters and sizes are updated along affected ancestor paths.Source: A. Positive Requests and Fetches · p. 8

B. Negative Requests and Evictions

• TC defines a set value from request counts and size, and this value is additive across disjoint sets.The value is never zero for a non-empty set.Source: B. Negative Requests and Evictions · p. 8
• TC maintains H_t(u) recursively, retaining it as H′_t(u) only when its value is positive and combining it with positive-valued sets for children of u.The sets are used to find a valid changeset for eviction without naively checking exponentially many tree caps.Source: B. Negative Requests and Evictions · p. 8
• TC reconstructs H_t(u) from stored values at its children in O(deg(T) · |H_t(u)|) time and updates stored values along cached ancestors in O(h(T)) time.Finding the eviction set takes O(h(T) + deg(T) · |X_t|) time.Source: B. Negative Requests and Evictions · pp. 8–9
• If the relevant H_t(u) has negative value, TC does nothing; if its value is positive, TC may evict it because it is saturated and maximal.The candidate tree cap is rooted at the root of the cached tree containing the negatively requested node.Source: B. Negative Requests and Evictions · p. 9

VII. SIMULATOR AND METHODOLOGY

• All algorithms run on the same rule tree and packet stream, with the same cache capacity and update-cost accounting; the simulator abstracts away switch-specific details.It focuses on caching decisions rather than TCAM layout or update-message encoding.Source: §VII · p. 9

A. Simulator Structure

• Each rule is a prefix-tree node, and packets are mapped to their longest matching rule; a virtual root supports lookups but is never cached.For TC and dependency-aware online baselines, cached rules form a subforest; batch heuristics may instead use cover rules to preserve correct classification.Source: A. Simulator Structure · p. 9
• A packet is a hit when its longest matching rule is cached on arrival; every other packet is a miss, including bypassed requests and packets matching only the virtual root.The simulator reports hits and misses, fetches and evictions, reconfigurations, maximum changes per reconfiguration, and runtime.Source: A. Simulator Structure · p. 9

B. Algorithm Implementations

• Experiments evaluate TC’s positive-request path only: packet arrivals create no negative requests, so its eviction procedure is not invoked.TC uses the counter and fetching procedure and evicts the whole cache if fetching a saturated tree cap would exceed capacity.Source: B. Algorithm Implementations · p. 9
• BUCKETING and BUCKETINGBYPASS use randomized eviction for dependencies; bypassing can avoid large fetches, but both may still update rules frequently.BUCKETINGBYPASS is the main baseline; requests whose dependency subtrees exceed capacity are left uncached and counted as misses.Source: B. Algorithm Implementations · p. 10
• CacheFlow-style heuristics recompute caches at fixed packet-count epochs, trading responsiveness against update frequency as epoch length changes.DEPENDENTSET selects whole subtrees, COVERSET may add cover rules, and MIXEDSET greedily chooses between these options.Source: B. Algorithm Implementations · p. 10
• Batch reconfiguration is modeled as one atomic step, while LRU is included only as a hit-rate reference because it ignores the subforest constraint.The simulator calls the batch algorithms CacheFlow-style because it omits other CacheFlow components, including dependency-graph maintenance and TCAM update ordering.Source: B. Algorithm Implementations · p. 10

C. Traces and Rule Trees

• Synthetic traces assign Zipf popularity independently of rule depth; stationary traces hold the distribution fixed, while phase-shifted traces move popularity among depth-2 subtrees.Each shifted phase draws 60% of packets from one subtree, and phase boundaries align with epoch boundaries to avoid partially mixing phases.Source: C. Traces and Rule Trees · p. 10
• 589,630,714 packets yielded a traffic-derived tree of 7,542 rules and height 5, built from 16 CAIDA captures collected on January 17, 2019.Prefixes at lengths 8, 12, 16, 20, and 24 were retained using length-specific packet thresholds.Source: C. Traces and Rule Trees · p. 10
• The CAIDA trace’s popular rules change moderately: consecutive 500,000-packet windows replace about 109 of the 754 most frequent rules on average.The Jaccard distance is approximately 0.253 and Jensen–Shannon divergence approximately 0.044; abrupt shifts like the synthetic phase changes do not occur.Source: C. Traces and Rule Trees · p. 11
• The traffic-derived tree preserves packet order and locality but is not a full router table: its retained prefixes, height, and 7,542-rule size are constructed from the trace and chosen prefix lengths.Without next hops, every containment relation is treated as a dependency, although a real rule with its parent’s next hop imposes none.Source: C. Traces and Rule Trees · p. 11

D. Cost Accounting

• Total cost is computed as misses plus α times rules fetched and evicted; individual changed TCAM entries count once regardless of message batching.Cover-rule installation or removal is charged like any other rule change.Source: D. Cost Accounting · p. 11
• For TC, α sets both update cost and the saturation threshold, while for other algorithms it only computes total cost; the default is α = 200, with α = 500 and 800 also tested.The default reflects a reported update-to-miss cost ratio of roughly 200–250.Source: D. Cost Accounting · p. 11

E. Reproducibility

• The simulator stores each run's configuration and counters, allowing plots to be reevaluated under another cost measure; scripts and results are available, but CAIDA captures are access-restricted.Source: E. Reproducibility · p. 11
• The base scenario uses the traffic-derived tree, 10% cache, and real-trace Zipf exponent; sensitivity experiments vary skew, cache ratio, or phase length, but not tree depth.Source: E. Reproducibility · p. 11
• Sensitivity costs exclude a 2.5M-packet warm-up, while full-trace experiments start with empty caches; choosing batch configurations on their evaluation traces favors those algorithms.Source: E. Reproducibility · p. 11

A. Real Backbone Trace

• CacheFlow variants lose about 4.1 percentage points of hit rate versus BUCKETINGBYPASS for about 300 times lower cost; TC costs 336.9M (2.9 times tuned batch, 104 times below BUCKETINGBYPASS) at 0.708 hit rate.Table II reports the CAIDA comparison under formal per-rule accounting.Source: Table II · p. 12, A. Real Backbone Trace · p. 12

VIII. EMPIRICAL EVALUATION

• The evaluation compares hit rates and costs when cache updates are charged, but does not compute empirical competitive ratios because optimizing offline solutions for these inputs requires a separate procedure.Source: §VIII · p. 12

A. Real Backbone Trace

• For the real-trace comparison, each CacheFlow-style variant uses its cost-minimizing 5M-packet epoch, selected on that same trace; cache-ratio sensitivity is studied on synthetic traffic only.Source: A. Real Backbone Trace · p. 12

B. Real Traffic versus Synthetic Zipf

• On stationary synthetic Zipf traffic, all algorithms reach hit rates of at least 0.947 and costs between 51M and 55M; TC's hit rate is 24 percentage points higher than on real traffic.The authors conclude that a globally fitted Zipf distribution misses real traffic's temporal and topological correlations.Source: B. Real Traffic versus Synthetic Zipf · p. 12, Table III · p. 13

C. Epoch Sensitivity of Batch Caching

• The cost across epoch lengths is U-shaped: 500K packets gives the highest hit rate and 5M the lowest cost, but the cheapest epoch implies an aggressive 8-second schedule.The simulator does not check whether rule changes for that schedule can be installed at this rate, so the best configuration depends on deployment.Source: C. Epoch Sensitivity of Batch Caching · p. 13

D. Sensitivity Around the Measured Base

• As Zipf exponent rises from 0.9 to 1.5, TC hit rate increases from 0.507 ± 0.007 to 0.956 ± 0.004 and cost decreases from 7.46 ± 0.14M to 0.77 ± 0.06M; tuned CacheFlow is cheapest at every skew.The tuned CacheFlow-style mean cost decreases from 3.60 ± 0.04M to 0.29 ± 0.01M across those skew values.Source: D. Sensitivity Around the Measured Base · p. 13
• At a 40% cache ratio, TC's mean cost is 0.49 ± 0.04M versus 0.51 ± 0.05M for batch algorithms, a non-significant reversal because the bands overlap.TC reaches the same mean cost at 20% and 40% once it stops ending phases because of cache-capacity exceedance.Source: D. Sensitivity Around the Measured Base · p. 13
• TC is cheaper than optimistically configured batch algorithms at every tested phase length; both approaches benefit from longer phases, and the real trace lacks such abrupt shifts.The phase-shifted traces are stress tests for adaptation, not a feature of the real trace.Source: D. Sensitivity Around the Measured Base · p. 13
• Raising α from 200 to 800 reduces TC updates from 824K to 213K, while hit rate falls from 0.708 to 0.693 and cost rises from 336.9M to 351.5M.The passage reports that total cost changes only slightly across these settings.Source: D. Sensitivity Around the Measured Base · p. 13

IX. CONCLUSIONS

• The paper concludes that deterministic TC provides a provably competitive trade-off between caching benefit and update costs.Source: §IX · p. 13
• On CAIDA, per-request algorithms cost over two orders of magnitude more than tuned batch algorithms, while TC costs 2.9 times as much; on abrupt-shift traces TC is cheapest at every tested phase length.The conclusions concern positive requests only.Source: Figure 4 · p. 14, §IX · p. 14

APPENDIX A PROOF OF LEMMA 1

• For each phase, valid changeset counters remain at most |X| · α; an applied changeset reaches that threshold and is a single tree cap.The proof also establishes that an applied changeset cannot be decomposed into multiple disjoint valid changesets.Source: Appendix A · p. 16

APPENDIX B MINIMIZING FORWARDING TABLES USING TREE CACHING

• A q-competitive tree-caching algorithm yields a 2q-competitive forwarding-table algorithm by canonicalizing cache modifications within α-request chunks and replaying them.Canonicalization postpones modifications made during a chunk until after it, increasing cost by at most a factor of two.Source: Appendix B · p. 16

APPENDIX C LOWER BOUND ON THE COMPETITIVE RATIO

• A bidirectional reduction from paging preserves competitive ratios up to constant factors, transferring the lower bound Ω(kONL/(kONL − kOPT + 1)) to tree caching.The reduction encodes paging requests as repeated requests to corresponding tree leaves.Source: Appendix C · pp. 16–17