In one embodiment, a packet switching device is configured to operate as a spoke or a hub in a Dynamic Multipoint Virtual Private Network (DMVPN) using one or more initially negotiated service overlay capabilities including service encapsulation to use in communicating service overlay data packets between the packet switching device and another device (e.g., spoke, hub) of the DMVPN over an established tunnel (e.g., secure protocol channel). The packet switching device is further configured to negotiate updated one or more service overlay capabilities including updated service encapsulation to use in communicating service overlay data packets with another device (e.g., spoke, hub) without dropping the already established tunnel. In one embodiment, the negotiation between the packet switching device and another device (e.g., spoke, hub) of the DMVPN uses Next Hop Resolution Protocol (NHRP). In one embodiment, the service encapsulation uses Network Service Header (NSH).