High availability (HA) is one of the most critical requirements of a service provider network and HA solutions for storage and compute have been deployed for some time. HA is also a major concern when considering network function virtualization (NFV) for service provider networks. The cloud culture of “just spin a new Virtual Machine (VM)” in case of a software or hardware fault seems at odds with the %99.999 availability requirements for service providera. This paper explores ways to meet the HA requirements of a service provider network with the relatively unreliable cloud infrastructure.