Example methods are provided for a first host to restore control-plane connectivity with a network management entity. The method may comprise: detecting a loss of control-plane connectivity between the first host and the network management entity; and determining connectivity status information associated with one or more second hosts. The method may also comprise, based on the connectivity status information, selecting, from the one or more second hosts, a proxy host having data-plane connectivity with the first host and control-plane connectivity with the network management entity. The method may further comprise restoring control-plane connectivity between the first host with the network management entity via the proxy host such that the first host is able to send control information to, or receive control information from, the network management entity via the proxy host.