Data centers are the key of cloud computing. Current data center architectures, which are based on electronic switches, conventional multi-stage switch network, and centralized deployment and management, cannot meet the requirements of survivability, high-availability and design flexibility of high-performance data centers for future cloud services. We optimize data center placement with service routing and protection to achieve survivability and cost minimization. An integer linear program (ILP) is first formulated to achieve optimal design. It integrates preconfigured protection cycle (p-cycle) for fast protection against a single link failure, and a data center replicas and fast service rerouting against a service failure. We then propose a two-step heuristic algorithm for large-size network scenarios. The first step solves data center placement and service routing problem in the failure-free scenario, and the second step takes fast service protection into account. The proposed design is validated by extensive simulations.