In one aspect, a method is implemented on a host platform on which a hypervisor (aka Virtual Machine Manager) and a plurality of virtual machines (VMs) are running, the plurality of VMs collectively hosting a plurality of Software Defined Networking (SDN) and/or Network Function Virtualization (NFV) appliances that are communicatively coupled via a virtual network. A software-based entity running on the host platform is configured to monitor the plurality of virtual network appliances to detect failures of the virtual network appliances. In response to detection of a virtual network appliance failure, messages containing configuration information are implemented to reconfigure packet flows to bypass the virtual network appliance that has failed.