Monitoring infrastructure should be reconfigured at a minimum cost to obtain up-to-date status information as the network evolves. This paper addresses the problem of optimally upgrading the existing monitoring infrastructure. It tries to minimize the total cost of upgrading the monitoring infrastructure, including adding new pollers and reconfiguring the existing pollers. It is shown that this problem is NP-hard. An approximation algorithm is proposed, and its time complexity and approximation ratio are analyzed.