This post is a repost of a technical blog originally published by Denys Haryachyy, shared here with permission as part of ongoing research and engineering work around FastNetMon’s inline traffic processing capabilities.
TL;DR. TupleMerge, the classifier inside VPP’s ACL plugin, is tuple-space search plus one liberty: a rule may live in a table coarser than its own mask. Insert = join or relax; buckets past 39 candidates split; lookup = one probe per merged partition into a single shared bihash, plus an exact re-verify of every candidate. Worst case per packet: P probes + 39·P exact checks.
The previous post compared plain TSS and TupleMerge at the trade-off level. This one opens the hood: how the merge happens, rule by rule, in hash_lookup.c, and what a lookup costs. TupleMerge is on by default (use_tuple_merge = 1).
The Machinery
Three structures. Partitions are the merged tables, one mask each, kept sorted by their best rule’s position. One shared bihash_48_8 holds every partition’s entries — a partition id in 16 spare key bits keeps them apart. colliding_rules is the list on each hash entry, where the relaxed-away bits are re-checked.
Two Rulesets to Follow
Two rulesets run through the rest of the post. Ruleset A — a slice of a general ACL: four rules, four mask shapes. Ruleset B — the canonical DDoS filter (CISA’s source-port list): five reflection rules of one shape, dropping UDP from the amplification ports.
Ruleset A — general ACL (4 shapes) #1 dst 203.0.113.0/24 #2 dst 203.0.113.64/26 #3 dst 192.0.2.9/32 #4 src 198.51.100.0/24 dport 443 Ruleset B — reflection filter (1 shape) drop udp → dst 203.0.113.45/32 #1 src-port 53 (DNS) #2 src-port 123 (NTP) #3 src-port 1900 (SSDP) #4 src-port 11211 (memcached) #5 src-port 19 (CharGen)
Insert: Join, Relax, or Split
Merging happens per rule, at insert. A rule joins any partition whose mask is a subset of its own (key truncated to the table mask; full mask kept for verify). If none fits, the plugin creates one with a relaxed mask. Relax compares the two address prefix lengths and, when they differ by more than 4 bits, drops the less specific address together with its port (source address → source port, dest → dest port); protocol and other exact-match fields are never touched. It then shortens the surviving prefix (/32 → /26, and so on), reverting the step entirely if the coarser mask would stop matching the rule. If a bucket’s chain exceeds TM_SPLIT_THRESHOLD (default 39, tunable — the paper’s collision limit c), split_partition() carves a finer mask.
Ruleset A merges: #1 relaxes to dst /20 (P_dst), #2 and #3 join it — #1/#2 share bucket 203.0.112.0 (their 203.0.113.x dst masked to /20), #3 lands in 192.0.0.0; #4 constrains src, so it starts P_src — four shapes, two partitions. Ruleset B collapses: with dst /32 far more specific than the unconstrained source, relax drops the source port (and shortens dst to /26), so all five rules share one key and pile into a single 5-deep bucket. The difference is what relax drops: in A the weaker address is always empty (#1’s source, #4’s destination), so nothing that separates rules is lost; in B the port dropped with the empty source is the source port — the one field telling the five rules apart. Same heuristic, opposite outcome.
Lookup: Probes, Verifies, and One Early Exit
The per-packet loop (multi_acl_match_get_applied_ace_index) walks the sorted partitions: for each, six ANDs build the masked key, one bihash probe, then an exact re-check of every candidate.
Two rules govern the walk. A hit can’t end the loop — priorities are scattered across partitions, so only the priority sort can break early. And the coarse key can only over-match (a wrong rule the verify rejects), never hide a real one — a match is never lost. In Ruleset A the packet probes P_dst, verifies two rules, and the sort breaks before P_src: one probe, two verifies. In Ruleset B one probe hits the 5-deep bucket and pays a five-way verify.
The Verdict: When TupleMerge Wins, When It Loses
The scoreboard falls out of the partition counts, against the plain-TSS baseline of one exact table per shape.
Ruleset A — TupleMerge wins: four shapes cost TSS four tables → four probes; TupleMerge’s two partitions cost one or two probes and ≤2 verifies, and the gap grows with every added shape. Ruleset B — plain TSS wins: one shape is one exact table → one probe, no verify (its floor); TupleMerge’s collision costs one probe plus a five-way verify, on a 48-byte key.
Three costs bound the loss: the 39 cap holds only while split_partition() can find a separating mask; the 48-byte key is heavier than an exact per-shape key; and a miss that false-hits a full bucket still pays the whole verify list — worst case P probes + 39·P checks. Rule of thumb: many shapes that merge → TupleMerge wins; already one or a few shapes (a reflection filter) → plain TSS wins.
Summary
- TupleMerge = TSS + one liberty: a rule may live in a partition coarser than its mask; the relaxed-away bits are re-checked on every hit.
- Insert = join or relax (pre-coarsened so later rules pile in); a bucket past 39 candidates splits.
- Lookup, per partition: 6 ANDs + 1 probe + up to 39 verifies; only the priority sort breaks early. Worst case = P probes + 39·P checks.
- Many shapes that merge into few partitions → TupleMerge wins; already one or a few shapes (a reflection filter) → plain TSS wins.
References
- Daly et al. — TupleMerge: Fast Software Packet Processing for Online Packet Classification (IEEE/ACM ToN 2019)
- Srinivasan, Suri & Varghese — Packet Classification using Tuple Space Search (SIGCOMM ’99)
- VPP
acl/hash_lookup.c - VPP
acl/public_inlines.h - Learning VPP: Filtering Packets at 100GbE Line Rate
- Learning VPP: Inside bihash, the Lock-Free Hash Table
- CISA — UDP-Based Amplification Attacks (Alert TA14-017A)
- APNIC — DDoS defences in the terabit era: SSDP, memcached
