This article presents a novel method for evaluating the properties of distances between hosts in a computational grid. Our method allows obtaining several indicators about a given network. We demonstrate why the current monitoring tools are not sufficient in grid environments that lack high level tools taking into account particular constraints for some given applications. We show how this method has been embedded in a grid service, namely the network distance service (NDS). Basically, this service returns the evaluation and characterization of a distance between a given set of sources and destinations. We illustrate the benefit of our approach in terms of accuracy of the returned values. We explain some implementation issues and discuss how the proposed NDS service can be useful to any grid service who needs some accurate evaluation for a decision making process involving such distances.