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 the 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.