[protocol] reactive forward ants have no flood bound in dense graphs — PDR 75.8→21.7, NRL 99.9→3071 on large-scale (#169 regression)

[danieljoppi]

Summary

Since PR #170 (the #169 hop-cap fix) landed on main, a single route discovery in a dense graph cost a combinatorial number of control packets — 30,090 reactive ants in a 7×7 testbench grid. In ns-3 it collapsed the two dense/large scenarios:

scenario	PDR before → after	NRL before → after
large-scale (100 nodes)	75.8 → 21.7	99.9 → 3071.1 (30×)
heavy-load (40 flows)	85.0 → 51.4	6.1 → 28.6
paper-base	81.7 → 82.2	59.1 → 84.8
high-mobility	82.4 → 85.8	55.9 → 72.2
dense-small	37.4 → 37.3	4.4 → 5.0
sparse-static	83.8 → 93.0	48.3 → 46.5

AODV/OLSR/DSDV were byte-identical across the two runs (untouched code, identical seeds), so this was ours. Source: the per-merge benchmarks refresh, 7835df4 → 60ab6ff, the first taxonomy measured after both #167 and #170.

#169's diagnosis was right and was not reverted — the sparse-static row is the proof: 83.8 → 93.0, ahead of AODV's 81.9, with the static/sparse inversion gone. The bug was that removing that bound left reactive forward ants with no flood bound.

Root cause: #96 and #170 each removed one of the two bounds

core/src/ant_router_logic.cpp:

if (config_.enableMultipath && incoming.isForward() &&
    incoming.type == AntType::Reactive) {
    ...
    if (!genQuality_.accept(...)) return {RouteDecision::drop()};
} else if (!history_.record(incoming.src, incoming.seqNum)) {
    return {RouteDecision::drop()};
}

With enableMultipath on (the default), a reactive forward ant took the first branch and so never touched history_ — strict (src,seq) duplicate suppression did not apply to it. GenerationTracker::accept() is not a suppressor: it admits any later same-generation copy within antAcceptanceFactor (1.5) of the best so far. In a dense graph a node receives the same generation from many neighbours at comparable cost, admits repeatedly, and each re-broadcast seeds more admissible copies.

Until PR #170 this was truncated by reactiveMaxBroadcasts = 2. Once that became -1, the only remaining ceiling was maxPathLength = 100 — no bound at all at these node counts. Each change was individually justified; nobody checked the interaction, and #169's own test used a line topology, where nothing can multiply.

Reproduction

core/tests/test_reactive_flood_bound.cpp — an 8-connected grid (dense and with a distant destination; a line shows nothing, a full mesh makes the destination a direct neighbour so discovery never runs):

grid	nodes	before the fix	after (shipped)	multipath=off
3×3	9	10	10	10
4×4	16	76	34	18
5×5	25	420	94	28
6×6	36	4,094	152	40
7×7	49	30,090	236	54

Fix (PR #174)

Bound re-broadcasts per (node, generation) instead of per ant-path: GenerationTracker gains a broadcast counter per generation, reactiveMaxBroadcasts is re-specified as that per-node bound (default 2), and a node that exhausts its allowance may still unicast-forward along pheromone, so reach is unaffected — verified by test_reactive_hop_reach.cpp, which still passes at 9 hops.

ns-3 verification

Run 30165318267, PDR / NRL:

scenario	v1.0.0	broken main	fixed	AODV
dense-small	37.4 / 4.4	37.3 / 5.0	37.1 / 5.0	32.8 / 2.3
paper-base	81.7 / 59.1	82.2 / 84.8	83.4 / 56.6	80.5 / 56.6
sparse-static	83.8 / 48.3	93.0 / 46.5	90.7 / 40.7	81.9 / 42.9
high-mobility	82.4 / 55.9	85.8 / 72.2	86.6 / 58.0	85.1 / 56.0
heavy-load	85.0 / 6.1	51.4 / 28.6	80.1 / 8.7	86.6 / 5.5
large-scale	75.8 / 99.9	21.7 / 3071.1	77.9 / 167.8	67.4 / 163.4

Closing as the regression is resolved: large-scale 21.7 → 77.9 with NRL down 18×, and every scenario at or above v1.0.0 except heavy-load.

Two things are explicitly not claimed, and both are carried forward in #177:

1. heavy-load is not fully recovered — 80.1 vs 85.0 pre-fix(core): stop bounding reactive floods — a broadcast budget is a hop limit (#169) #170, still behind AODV's 86.6. pdr_sd is 4.56 at 2 runs so some is dispersion, but not all of it.
2. The shipped bound has no basis in either primary source. The 2007 thesis records the authors abandoning band-multipath for precisely this overhead problem, and our factor of 1.5 is looser than the 0.9 base they ran. [protocol] decide the reactive route-setup design on measurement: thesis single-route (A) vs source-parameterised band (B) vs the repo bound (C, shipped) #177 evaluates the thesis's single-route design (A) and the source-parameterised band (B) against the shipped bound (C) at runs=5.

All numbers above are 2-run --quick values and need a runs=5 confirmation before being quoted anywhere.

[danieljoppi]

The primary source reframes this: our acceptance factor is the cause, and the authors dropped this mechanism

I checked the 2007 thesis before merging #174, because that PR ships a value (2) for a newly-invented unit and I had to label its provenance derived. The source says considerably more than expected, and it changes what the right fix is.

1. The thesis's final design does not do band-multipath at all

"In case the intermediate node i does not have routing information for d, it broadcasts the reactive forward ant. Due to this broadcasting … a reactive forward ant can proliferate quickly over the network … In order to limit the amount of overhead that is created this way, nodes only forward the first copy of the ant that they receive. Subsequent copies are [discarded]."
— 2007 thesis, §4 (lines 3773-3778)

"If more than one copy of the forward ant is received, only the first is accepted … This way, only one route is set up during the reactive route setup process. … For the creation of multiple routes, AntHocNet relies on the proactive route maintenance process, which extends the initially created route into a full mesh."
— lines 3785-3791

So in the canonical design, reactive setup builds one route and multipath comes from proactive maintenance — which we already have on by default (enableProactive, enableDiffusion).

2. Band-multipath is described as the older version — and it used different numbers

The thesis discusses it in an appendix explaining why they dropped it:

"The main difference in the reactive route setup process of the older version of AntHocNet is that not one but multiple routes are set up. … If the number of hops and travel time of a newly received ant are both within an acceptance factor a1 of those of the best previously received ant …, the new ant is accepted and forwarded; otherwise, it is discarded. a1 is set quite low (to 0.9), in order to only allow the best ants through and avoid too much proliferation of forward ants in the network."
— lines 4650-4659

"To boost the creation of disjoint paths, a different mechanism is applied, which takes into account the first hop taken by each ant. If this first hop is different from those taken by previously accepted ants, we apply a higher (less restrictive) acceptance factor a2 … (a2 was set to 2)."
— lines 4667-4671

"…through experiments we experienced that it is hard to get a good balance between the number of routes that are obtained and the overhead that is created. High levels of overhead were often experienced. Therefore, we decided to restrict reactive route setup to the creation of just one single route, and to rely on proactive route maintenance to obtain multiple routes."
— lines 4676-4681

That last sentence is this issue, reported by the protocol's own authors.

3. What we actually implement

We use a single factor of 1.5 for all ants. [1] (PPSN 2004) does say 1.5 — "a parameter which we empirically set to 1.5" (line 133) — so the value is correctly sourced to [1]. But the thesis supersedes [1] with a two-factor scheme, a1 = 0.9 for same-first-hop ants and a2 = 2 only for first-hop-disjoint ones. Note the direction: at 0.9 the band admits only ants better than the incumbent, so each admission tightens it and proliferation is self-limiting. At 1.5 it admits ants up to 50% worse, and in a dense graph almost every neighbour's copy qualifies.

docs/configuration.md currently records antAcceptanceFactor as sourced to [1] §3.1. That is true but incomplete, and the incompleteness is what hid this.

4. Measured, in the same grid harness

One discovery, ants put on the medium; delivery over 17 offered packets in the same runs:

design	5×5	7×7	delivered
A — thesis-final: enableMultipath=false (first copy only)	28	54	17/17
B — 2004 band as the thesis parameterises it, a1 = 0.9	28	54	17/17
— 2004 band as we implement it, factor 1.5	420	30,090	17/17
C — PR #174: factor 1.5 + per-node broadcast cap 2	94	236	17/17

The flood is caused by the acceptance factor, not by the absence of a broadcast cap. At the thesis's own parameterisation the band is self-limiting and needs no extra mechanism; at 1.5 it is not. My per-node cap (C) works, but it is a repo invention compensating for a mis-parameterised band — the shape of fix this repo has twice been burned by.

5. This also invalidates #96's evidence

#96 chose enableMultipath=true on an A/B measuring PDR 92.3 vs 89.4. That A/B ran with reactiveMaxBroadcasts = 2 in force, which truncated the flood at ~5 hops and so hid multipath's overhead cost. The decision needs re-measuring on current code before it can stand.

6. Options

• A — adopt the thesis's final design. enableMultipath = false by default; multipath comes from proactive maintenance, as the source intends. No new mechanism; bounded by construction. Biggest behavioural change, and it demotes [protocol][fidelity] Reactive-ant multipath setup (1.5× filter, paper §3.1) — implemented, but regresses PDR in the ns-3 harness #96's decision.
• B — keep band-multipath, parameterised as the source does. a1 = 0.9, plus the first-hop-disjoint a2 = 2 rule we do not implement at all. Faithful to the older design and self-limiting; needs the a2 first-hop mechanism written.
• C — PR fix(core): bound the reactive flood per (node, generation), not per ant path #174 as it stands. Keeps factor 1.5 and adds a per-node broadcast cap. Works, preserves [protocol][fidelity] Reactive-ant multipath setup (1.5× filter, paper §3.1) — implemented, but regresses PDR in the ns-3 harness #96's default, but is the only option with no basis in either source.

I am not merging #174 on my own judgement given the above — it is a protocol design choice with fidelity consequences, and the maintainer should pick. Whichever is chosen, antAcceptanceFactor's row in docs/configuration.md needs the thesis context added, and #96 needs a re-run.

Sources: 2007-ducatelle-thesis.pdf and 2004-ppsn-anthocnet.pdf in the private papers repo, read with the pdf-extract skill; line numbers are into its extracted text.

---

Generated by Claude Code

[danieljoppi]

ns-3 verification of PR #174 (option C): regression resolved, one residual

Discrete taxonomy on claude/reactive-flood-bound, run 30165318267, CSV rescued to docs/benchmarks/campaign/30165318267-run.csv. All three arms are the same scenarios and seeds; PDR / NRL:

scenario	v1.0.0 (7835df4)	broken main (60ab6ff)	#174	AODV
dense-small	37.4 / 4.4	37.3 / 5.0	37.1 / 5.0	32.8 / 2.3
paper-base	81.7 / 59.1	82.2 / 84.8	83.4 / 56.6	80.5 / 56.6
sparse-static	83.8 / 48.3	93.0 / 46.5	90.7 / 40.7	81.9 / 42.9
high-mobility	82.4 / 55.9	85.8 / 72.2	86.6 / 58.0	85.1 / 56.0
heavy-load	85.0 / 6.1	51.4 / 28.6	80.1 / 8.7	86.6 / 5.5
large-scale	75.8 / 99.9	21.7 / 3071.1	77.9 / 167.8	67.4 / 163.4

Against the acceptance criteria I wrote above

1. O(n) discovery cost — ✅ verified in the testbench (30,090 → 236 at 7×7).
2. sparse-static keeps the [protocol] reactiveMaxBroadcasts=2 caps discoverable paths at ~5 hops — routes beyond it are never found #169 gain — ✅ in substance, ⚠️ on the letter. I wrote "≥ ~93%"; it is 90.7. That bar was set from a 2-run number whose pdr_sd is 6.43, so 90.7 vs 93.0 is well inside dispersion — and both are far above the 83.8 that motivated [protocol] reactiveMaxBroadcasts=2 caps discoverable paths at ~5 hops — routes beyond it are never found #169, and clearly ahead of AODV's 81.9. I am not claiming the difference is meaningful in either direction.
3. large-scale back to pre-fix(core): stop bounding reactive floods — a broadcast budget is a hop limit (#169) #170 — ✅ on PDR (77.9 vs 75.8, and now +10.5 pp ahead of AODV), ❌ on NRL: 167.8 vs 99.9, i.e. 68% higher than v1.0.0. That is not a miss to wave away, but it is explainable and arguably correct: under the old hop cap, destinations beyond ~5 hops were never discovered, so no ants were ever spent looking for them — cheap because it wasn't doing the work. AntHocNet now finds those routes at an NRL of 167.8 against AODV's 163.4 on the identical scenario, i.e. par overhead for 10.5 pp more delivery.
4. heavy-load back to pre-fix(core): stop bounding reactive floods — a broadcast budget is a hop limit (#169) #170 — ❌ not met. 80.1 vs 85.0 (−4.9 pp), NRL 8.7 vs 6.1, and still behind AODV's 86.6. pdr_sd here is 4.56 at 2 runs, so part of the gap is dispersion, but I would not claim it is all noise.

Status

Option C removes the catastrophic regression — large-scale goes 21.7 → 77.9 and its NRL drops 18× — and leaves every scenario at or above v1.0.0 except heavy-load. It does not make this issue's story complete: heavy-load is a real residual, and the numbers above are 2-run --quick values that need a runs=5 confirmation before any of them are quoted anywhere.

This does not settle the design question from my previous comment (A: thesis-final single-route; B: band at the source's own a1=0.9/a2=2; C: this PR). Option C is the only one with no basis in either source, and the thesis records the authors abandoning the mechanism it patches. What has changed is that C is now measured rather than argued, so the trade is concrete: it un-breaks main today and preserves the gate for exploring A and B, at the cost of a repo-invented bound.

---

Generated by Claude Code