We envision that a single set of overlay infrastructure nodes, supporting a few simple primitives, would allow end-hosts to choose routes over the infrastructure, thus enabing the end-hosts to achieve various services they desire. The foremost challenge we face here is to design flexible primitives that the infrastructure should export. The second requirement is to support a mechanism that allows end-hosts to find paths based on application-sensitive metrics. We achieve this by building a NEtwork Weather Service (NEWS) that measures performance characteristics of the infrastructure. The final requirement, also of paramount importance, is to make sure that the infrastructure is DoS resistant. Thus, end-hosts, by querying the NEWS nodes build application-specific services using the routing primitives that the infrastructure exports. Experiments using an initial deployment of NEWS over PlanetLab have shown that our techniques perform very well.