This proposal explores the design and utility of two broad-coverage network services: (1) a topology discovery service that overlay nodes use to locate itself with respect to its peers and the endpoints it serves; and (2) an information service that collects, stores, propagates, aggregates, analyzes, and reacts to the network's changing conditions. The research challenge is to design these services to both provide Internet-scale coverage, and meet the needs of a rich collection of wide-area overlay networks and applications. We will deploy and demonstrate both services on PlanetLab. The impact of this work is to provide "foundational" services that can be leveraged to improve the robustness, security, performance, and manageability of the Internet.