Highly available virtual machines with network coding

Erasure coding has been proposed in distributed storage systems for both high data reliability and low storage redundancy. With virtualization, virtual machines (VMs) are essentially defined by software and by their memory states, and erasure coding can be used in the same manner as in storage for high reliability and availability. Each VM can backup its memory state to a hot spare, and multiple memory states are coded at the hot spare to provide data reliability and low redundancy. This poses a new set of challenges. Both synchronization and recovery of the VMs consume significant bandwidth which may impede the performance of a data center. To guarantee high availability, recovery from a machine failure (decoding) at the hot spare must be fast. When (de)coding is done in-network, computation can be distributed over hosts, routers or switches and bandwidth for synchronization and recovery can be reduced significantly. We show the conditions needed to support optimal rates for synchronization and recovery for many-to-one backup in arbitrary networks. Furthermore, we propose routing and code construction algorithms that run in polynomial-time.