In an NHRP-enabled network, a router is configured with NHRP as a next-hop server (NHS). The NHS becomes a kind of route server, maintaining an NHRP database mapping the NBMA next hop to IP addresses.

The NHRP database is dynamically built and kept accurate using an ARP-like query-and-reply mechanism. Devices that need to communicate register dynamically with the NHS as a next-hop client (NHC). Having determined the existence of the NHC, the NHS adds it to the NBMA network without configuration. The NHC dynamically determines the locations of the other devices in the network from the NHS. The first communication of an NHC to a given device in the network initially flows through the NHS. During its first communication to a destination device, the NHC queries for the IP address of the destination device from the NHS and determines it. Thereafter, the NHC initiates a dynamic GRE/IPSec tunnel to the destination device and traffic flows directly from the NHC to the device. The tunnel is torn down when traffic is no longer flowing between the two devices.