A relay service enables two peers attempting to communicate with one another to each connect to a publicly-accessible relay server, which servers are associated with an overlay network and are selected by a directory service. After end-to-end connectivity is established, preferably the hosts communicate with each other by relaying data packets via the overlay network relay servers. Communications (both connection control messages and data being relayed) between a host and a relay server occurs at an application layer using a modified version of the TURN protocol.