1. A method of selective monitor deployment under budget constraints, the method comprising: obtaining a network topology and a deployment budget; decomposing the network topology into a plurality of components having a predetermined property; computing a benefit and a cost for identifying each of the components; selecting at least one targeted component based on the benefit and the cost for identifying each of the components; and deploying monitors to identify links in the at least one targeted component within a remaining portion of the deployment budget; wherein the deployment budget is a residual budget after deployment at higher layers of the overlay network.