We propose a novel cellular core network architecture, SoftBox, combining software-defined networking and network function virtualization to achieve greater flexibility, efficiency, and scalability compared to today's cellular core. Aligned with 5G use cases, SoftBox enables the creation of customized, low latency, and signaling-efficient services on a per user equipment (UE) basis. SoftBox consolidates network policies needed for processing each UE's data and signaling traffic into a light-weight, in-network, and per-UE agent. We design a number of mobility-aware techniques to further optimize: 1) resource usage of agents; 2) forwarding rules and updates needed for steering a UE's traffic through its agent; 3) migration costs of agents needed to ensure their proximity to mobile UEs; and 4) complexity of distributing the LTE mobility function on agents. Extensive evaluations demonstrate the scalability, performance, and flexibility of the SoftBox design. For example, basic Softbox has 86%, 51%, and 87% lower signaling overheads, data plane delay, and CPU core usage, respectively, than two open source EPC systems. Moreover, our optimizations efficiently cut different types of data and control plane loads in the basic SoftBox by 51%-98%.