With the increasing development of overlay service network which contributes a significant portion of todays network traffic, the selection of good service providers becomes more and more essential.In the selection,network distance is a very important parameter, and estimating network proximity is part of the network distance estimation.Although there exists a number of network proximity estimation technologies, they either require the distance measurement to all the potential targets, or fail when some landmark nodes are not available at a given instant of time.In this paper, we propose a network proximity technique that uses information obtained from probing a small number of landmarks.We firstly partite all the notes into different clusters based on their level vector such that nodes that fall within the same given cluster are relatively closer than those in the different clusters in terms of network latency.Then, for each cluster, the vector distance between the client and each service provider is combined with their ISP information to determine the K closest ones for the selection of the good service providers to consult.Our network proximity estimation strategy is simple, scalable, distributed with little support from the measurement infrastructures and no direct communications between the client and the service providers, and most importantly, it works well when some landmarks are invalid.Our strategy is tested using simulation.Our results indicate that the performance of network distance estimation in the service provider selection can be significantly improved by our scheme with limited measurements.