Recently, IoT, SDN and NFV have emerged as significant technological enablers for telemedicine. Because of specific characteristics of telemedicine services, reliability is one of the critical elements to guarantee the quality of services. To maintain high availability of services, existing backup solutions focus on resources constraints where backup instances are placed at the same node (vertical backup) or distributively deployed at different nodes (horizontal backup). While they put more effort to satisfy resource requirements, routing issues are often neglected such as end-to-end latency, multi-path routing, and synchronization in a multi-path scenario. Such aspects are key requirements to deploy high reliability telemedicine services. Therefore, we investigate the dynamic backup mechanism for a telemedicine system. We aim to optimize the reliability of telemedicine service function chains (TSFCs) where a joint horizontal/vertical backup (JHVB) optimization problem is first formulated. Since JHVB is a combinatorial optimization problem, which is NP-Hard, we then solve this problem in both offline and online fashions using Block Successive Upper Bound Minimization (BSUM) and Multi-Armed Bandit (MAB) frameworks. We compare our methods to the benchmarks via intensive simulations based on the Nano Datacenter solution that is used for enabling telemedicine services. The results demonstrates an outstanding performance in terms of failure awareness and service reliability.