A computing environment containing a mesh network that is adapted to provide a reliable transport mechanism over which services may be delivered. Nodes of the mesh can automatically select routable addresses without conflicts, which allows nodes of the mesh to be accessed, even as the mesh changes through the addition or deletion of nodes. Also, nodes communicate with a protocol that supports service advertisements. These advertisements can identify mesh nodes that supply services, such as file or print servers, for which devices that have not yet connected to the network may be searching. Advertisements can also identify services to be used by nodes in the network, allowing, for example, a node to select a gateway providing a reliable connection to an external network. The mesh network can be used as a transport for communication using protocols, such as TCP/IP, that generally exhibit poor performance when using unreliable transports.