A method, computer storage medium, computer system of performing monitor deployment under budget constraints includes 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 a ratio of the benefit to 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.