Network Address Translator (NAT) traversal is performed for a host located behind the NAT running a server, e.g., an HTTP server, using a relay server and a redirect server. The host (of the HTTP server) located behind the NAT uses a NAT-discovery process to determine the presence of the interposed NAT. Seamless IP communication over the IP network is provided using a Dynamic DNS (DDNS) system that is updated using a user registration database, which contains information about the presence or absence of a NAT relative to the HTTP server.