In this paper, we describe the design and implementation of ShaRE, the first run-time system for the emerging class of high-performance, multi-service virtualized routers. ShaRE introduces two innovations. First, ShaRE includes Everest, a novel variable-quantum, non-work-conserving scheduler for allocating resources to network services in high-performance routers. Everest is agile; it copes with difficult to predict and significant fluctuations in packet arrival rates at small time-scales. Second, ShaRE~exploits unique characteristics of the network services to minimize the overhead of replicating services dynamically or check-pointing and migrating services from one processor to another in response to workload fluctuations. To facilitate such adaptation and to simplify programmability, ShaRE~provides a packet-processing-oriented resource abstraction layer (pRal). When combined with network overlays and programmable router hardware, ShaRE enables creation of commercial-scale overlay hosting facilities that greatly lowers the barrier for introducing new network architectures and services into the Internet.