1. A method of selective monitor deployment under budget constraints, the method comprising: obtaining a network topology, a structure of an overlay network having a plurality of layers of monitoring interest, and a deployment budget; and from a top layer of the overlay network towards a bottom layer of the overlay network: computing a minimum deployment cost to fully identify links in a current layer of the overlay network; if the computed minimum deployment cost is no more than a remaining portion of the deployment budget: then deploying monitors so that the current layer of the overlay network is identified with the minimum deployment cost, reducing the remaining portion of the deployment budget, and going to a next layer; otherwise, deploying monitors within the remaining portion of the deployment budget so as to identify a fraction of link metrics of the current layer of the overlay network; wherein the method further comprises iterating through each layer of the overlay network multiple times; and wherein monitor deployment in a lower layer results in recommending adjustments of monitor deployment in an upper layer so as to reduce an overall deployment cost.