A method (and corresponding computer readable storage medium) of selective monitor deployment under budget constraints, wherein the mechanism includes iterating through each layer of an 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 the overall deployment cost. Also, a method (and corresponding computer readable storage medium) of selective monitor deployment under budget constraints, wherein a deployment budget is a residual budget after deployment at higher layers of an overlay network.