Evolving monitoring infrastructure in response to network growth is a critical aspect of network management. Previous work in network management primarily focused on optimizing monitoring systems for static networks. In this paper, we address the problem of optimally upgrading the existing monitoring infrastructure as the network evolves. The problem formulation presented here captures the trade off between adding new monitoring resources vs. disrupting the existing infrastructure. We show that this problem is NP hard and not approximable within a factor better than n^∊ in the general case and no better than Log(n) when only shortest paths are considered. We develop a heuristic algorithm and evaluate its performance using simulated network evolution scenarios. We show that in spite of not allowing poller relocation, our adaptive on-line algorithm has comparable performance to that of the offline algorithm where such constraint does not exist.