Genetic Simulated Annealing Algorithm for Optimal Deployment of Flow Monitors

In order to monitor a large fraction of IP flows in an IP network concurrently, a set of flow monitors are needed to be deployed at multiple locations within the network. The problem of optimal deployment of flow monitors (ODFM) concerns that where to place monitors and how to control their sampling rate so that the maximum monitoring reward can be got under certain monitoring cost constraint. After modeling the monitoring reward and the monitoring cost appropriately, we formulate ODFM as a non-linear programming problem, and propose a genetic simulated annealing (GSA) algorithm which combines the standard genetic (SG) algorithm and the simulated annealing algorithm to solve it. We evaluate the performance of the GSA and compare it to that of the SG through experiments on synthetic network topologies. The experimental results show that the GSA outperforms the SG by up to 15% in terms of quality of solutions.