1. A method of performing monitor deployment under budget constraints, wherein the method implemented in a computer system, comprising: obtaining, using at least one processor coupled to the computer system, a network topology and a deployment budget; decomposing, using the at least one processor, the network topology into a plurality of components having a predetermined property; computing, using the at least one processor, a benefit and a cost for identifying each of the components; selecting using the at least one processor at least one targeted component based on a ratio of the benefit to the cost for identifying each of the components; and deploying using the at least one processor 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 other layers than the first layer in the overlay network.