The Peer-To-Peer (P2P) computing paradigm is an emerging paradigm that aims to overcome most of the main limitations of the traditional client/server architecture. In the P2P setting, individual computers communicate directly with each other in order to share information and resources without relying on any kind of centralized server. To achieve this full decentralization, an application-level (or overlay) network is constructed using, for example, TCP connections.

In most of the existing P2P systems, the overlay network is built in a manner that does not guarantee that the overlay network is efficient with respect to a given metric (e.g. latency, hop count and bandwidth). Hence, an overlay node can be very far away, in terms of a given metric, from its overlay neighbors. This can result in both, an ine?cient routing at the overlay network and an ineffective use of the underlying IP network.

In this paper, we first introduce a new measure, "goodness of overlay networks", to quantify the quality of an overlay network for a given metric. Then, we propose NetProber, a simple, distributed and scalable component that can be combined with any connected overlay network in order to allow the latter to adapt, and to become "good" within a finite amount of time.