Certain embodiments herein are directed to a method of by a source virtual tunnel endpoint (VTEP) for selecting a tunneling protocol for encapsulating a packet destined for a destination VTEP. In some embodiments, the method includes receiving the packet for transmission to the destination VTEP. The method further includes determining whether the destination VTEP is configured with a first tunneling protocol. Upon determining that the destination VTEP is configured with the first tunneling protocol, the method includes encapsulating the packet using the first tunneling protocol, and transmitting the encapsulated packet to the destination VTEP. Upon determining that the destination VTEP is not configured with the first tunneling protocol, encapsulating the packet using a second tunneling protocol, and transmitting the encapsulated packet to the destination VTEP.