In today's Internet routing architecture, end-to-end paths are selected based on the complex interaction of several protocols. While these protocols operate at different levels, some within autonomous systems (ASes) and some across autonomous systems, all of them aim to provide customizability (e.g. traffic engineering within an AS or route choice across ASes), and resilience to failures of links and nodes. However, today's Internet's routing falls short of both these goals. Customization across ASes is at best indirect and is often achieved by tweaking knobs in BGP, the inter-domain routing protocol. Furthermore, the complexity of providing flexible routing makes failure recovery hard even with a single domain. In this thesis, we propose an alternate routing architecture that decouples the goals of providing customizability and resilience. We propose a routing protocol based on a technique called Failure-Carrying Packets (FCP) that provides basic connectivity between hosts in the face of link failures. Sophisticated routing protocols, tuned to various specific needs, can be layered on top of FCP. We argue that such sophisticated routing should be provided as a service by third-party providers, and design a architecture in which such routing service provides can contract with ISPs and provide specialized routes to customers. We present the design and implementation of both the underlying routing protocol (FCP), as well as the architecture for providing routing as a service.