There is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal content Web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggest an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast groups, in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We also presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area.