Scientific knowledge map · Paper #6
Optimal Filtering for DDoS Attacks
2007 · Information Theory and Applications Workshop (ITA)
- Theory
- Applied
- algorithm
Research question
What does the paper try to establish?
Given a congested victim link and too few packet filters, which individual attackers or aggregate gateways should be filtered or rate-limited to maximize preserved legitimate traffic?
Central answer
What is the proposed answer?
At one aggregation tier the binary formulation is a computationally hard 0-1 knapsack; its fractional, rate-limiting relaxation admits a greedy optimum using filters plus one rate limiter. Across gateway and attacker tiers the problem becomes a cardinality-constrained optimization with an exact dynamic program over gateways, capacity, and filters. Simulations compare these optimized policies and a lower-cost heuristic on synthetic, worm, and commercial-attack scenarios.
Evidence profile
Six dimensions, kept separate
The chart summarizes documented evidence and process. It is not a correctness probability, confidence score, or ranking, and no composite score is calculated.
LowMediumHighN/A = not assessed
A smaller value means less documented support for that dimension, not that the paper is false or unimportant.
- Epistemic evidence High
-
The optimization problems, algorithms, optimal-substructure argument, complexity, and comparative simulations are documented; operational detection and deployment are outside the evidence.
Single-tier knapsack formulation and greedy optimum Two-tier formulation and dynamic program Optimal-substructure proposition and complexity Synthetic and realistic simulation scenarios - Auditability High
-
A fixed public arXiv full text is checked in with page count and hash, enabling direct inspection of definitions, algorithms, arguments, and results.
Public manuscript provenance Optimal-substructure proposition and complexity Synthetic and realistic simulation scenarios - Production provenance Medium
-
Named authorship and public manuscript lineage are documented; roles, revision/effort history, tool use, and simulation-code lineage are not.
Public manuscript provenance - External scrutiny Medium
-
The paper has a workshop publication and public preprint, but review reports, code review, and independent replication were not located.
Public manuscript provenance - Reception Low
-
No citations were verifiably located in the constrained dated search. Under the author's 0-8 rule this is low, but it is not a claim that the paper has no citations.
Citation search attempted - Contribution significance High
-
The work identifies the precise filter/granularity tradeoff, supplies exact algorithms for two settings, and evaluates practical approximations while exposing computational limits.
Problem and contributions Two-tier formulation and dynamic program Synthetic and realistic simulation scenarios
Assessment: Ai draft author review pending · 2026-07-11 · rubric 0.2. These dimensions describe documented support and process, not truth, correctness, or a universal ranking. No composite score is calculated.
Top-down and bottom-up view
Hierarchical knowledge map
Collapse a branch for a top-level reading, or follow its source links and child nodes to audit the evidence and boundaries underneath it.
Optimal Filtering for DDoS Attacks
An optimization and algorithm paper for allocating scarce router filters under DDoS traffic while preserving legitimate throughput.
Problem and contributions Public manuscript provenance-
question Research question
research questionHow should a victim choose filtering granularity under simultaneous link-capacity and filter-count constraints?
Problem and contributions -
contribution Central answer
proved and simulatedUse greedy knapsack allocation at one tier and a Bellman dynamic program when filters may be assigned at both gateway and individual-attacker tiers.
Single-tier knapsack formulation and greedy optimum Two-tier formulation and dynamic program Synthetic and realistic simulation scenarios -
model Traffic and resource model
formalizedA victim gateway knows good and bad traffic rates per attack gateway and attacker, has link capacity C and at most F filters, and optimizes admitted legitimate traffic.
Filtering model and detection boundary Single-tier knapsack formulation and greedy optimum -
algorithm Single-tier fractional-knapsack allocation
optimally solvedBlocking entire gateways yields a computationally hard 0-1 knapsack. Relaxing each decision to a passed traffic fraction models rate limiting; sorting by legitimate-traffic efficiency then gives a fractional-knapsack optimum with filters on later gateways and one rate limiter at the capacity boundary.
Single-tier knapsack formulation and greedy optimum -
algorithm Two-tier dynamic program optimally solved
The algorithm considers each gateway, residual capacity, and filter budget, choosing how many filters to assign within that gateway and reusing stored optima for the previous gateways.
Two-tier formulation and dynamic program-
theorem Optimal-substructure justification
provedA proposition shows that an optimal allocation for n gateways contains an optimal allocation for its first n-1 gateways under the induced capacity and filter budgets, justifying the recurrence.
Optimal-substructure proposition and complexity -
limitation Pseudo-polynomial cost
analyzedThe exact table scales with N, discretized capacity C, and filter budget F and can be prohibitively large; the paper therefore also studies a simpler heuristic.
Optimal-substructure proposition and complexity
-
-
evidence group Comparative simulations simulation
The algorithms are compared with uniform, random, max-min, and heuristic policies on generated traffic plus Code Red, Slammer, and commercial DDoS-report distributions.
Synthetic and realistic simulation scenarios-
result Goodput/filter tradeoff
simulation supportedAcross the reported scenarios, optimized placement preserves more good traffic and can use fewer filters than baselines; exact magnitudes depend on the assumed traffic distributions and capacity.
Synthetic and realistic simulation scenarios
-
-
limitation group Model boundaries
materialAttack identification is assumed rather than solved, good/bad rates are treated as known, one victim-side hierarchy is optimized, and experiments are simulations rather than router deployment.
Filtering model and detection boundary Synthetic and realistic simulation scenarios Conclusions and scope -
artifact Artifacts
paper available no codeA fixed arXiv full text is available locally; algorithm code, scenario inputs, and simulation outputs were not located.
Synthetic and realistic simulation scenarios Public manuscript provenance -
scrutiny Scrutiny
peer reviewedThe work appeared at ITA 2007 and has a public preprint; review reports and independent reproduction were not located.
Public manuscript provenance
Audit trail
Source index
Locators state the depth of the current audit. PDF page numbers, where present, are one-based file pages; metadata-, summary-, and abstract-bounded records explicitly identify their limitations.
- Problem and contributions Abstract and Section 1, PDF pages 1-2
- Filtering model and detection boundary Section 2, PDF pages 2-3
- Single-tier knapsack formulation and greedy optimum Section 3.1 and Algorithm 1, PDF pages 3-5
- Two-tier formulation and dynamic program Sections 3.2-3.3 and Algorithm 2, PDF pages 5-8
- Optimal-substructure proposition and complexity Section 3.3, PDF pages 7-8
- Synthetic and realistic simulation scenarios Section 4, PDF pages 9-12
- Conclusions and scope Section 5, PDF page 13
- Public manuscript provenance arXiv cs/0612066
- Citation search attempted Exact-title search, 2026-07-11; no verified count retrieved