Mechanisms that allow IPv4 and IPv6 clients to communicate with reduced server workload. The IPv4 client initiates communication by routing an IPv4 message to a server. The server sends a similar IPv6 message to the IPv6 client. A relay intercepts the IPv6 response, generates an IPv4 response, and forwards that IPv4 response to the IPv4 client if the NAT is a cone NAT. Otherwise, the relay sends the IPv4 response to the server. The server includes the IPv4 address of the relay in the response and sends the response to the IPv4 client. The IPv4 client then communicates with the IPv6 client using the relay. The IPv6 client may also initiate communication with the IPv4 client by sending an IPv6 message to the relay where it is queued.