Many recent proposals have argued for giving end-hosts control over routing in the network to satisfy the growing demands of applications. However, these proposals either run at an overlay level independent of one another, or else lack support for end-hosts to discover the desired routes. In this paper, we propose a network architecture that addresses these limitations. At the basis of our solution lies the idea that specialized route computation should be provided as a service and not embedded in the infrastructure. This design allows the routing functionality to evolve without changing the infrastructure. Our architecture consists of three entities: (a) a forwarding infrastructure that enables end-hosts to setup routes, (b) Routing Service (ROSE) providers that compute routes (conforming to application requirements) based on network information that the infrastructure provides, and (c) end-hosts that setup the routes, obtained by querying ROSE, in the infrastructure. We address the issues of trust, scalability of the ROSE architecture, and deployability. We demonstrate the feasibility of our solution by conducting experiments on a prototype deployed on PlanetLab. To illustrate the benefits of our architecture we evaluate two applications: metric-sensitive multicast, and resilient routing.