This paper proposes the concept of a fault-tolerant virtual private network (FVPN) within an autonumous system — a framework for supporting seamless network fail-over by leveraging the inherent redundancy of the underlying Internet infrastructure. The proposed architecture includes an application-level module, which is integrated into gateways at VPN end-points. This module enables fail-over to a redundant path without waiting for the underlying routing protocol converging to a new route. The paper introduces two algorithms for establishing redundant backup paths while minimizing overlapping network links. The proposed schemes are evaluated using topology information and sample routing logs from a regional Internet service provider network.