Exact and heuristic algorithms for solving the generalized minimum filter placement problem

E. Chisonge Mofya, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication network. We also present three heuristics for solving the filter placement problem and evaluate their performance against the optimal solution provided by the mixed-integer programming model.

Original languageEnglish (US)
Pages (from-to)231-256
Number of pages26
JournalJournal of Combinatorial Optimization
Issue number3
StatePublished - Nov 2006
Externally publishedYes


  • Computer network security
  • Denial of service attacks
  • Facets
  • Heuristics
  • Mixed-integer programming

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Exact and heuristic algorithms for solving the generalized minimum filter placement problem'. Together they form a unique fingerprint.

Cite this