Concurrent testing of NAT connections using different timeout values to compute a keep-alive value for the NAT device. Computation of the approximate timeout value is accomplished concurrently over multiple test connections within about a time equivalent to the actual NAT timeout value. The architecture validates the computation of the approximate timeout value by distinguishing NAT connection failure from external failure using a control connection. Moreover, computation of the keep-alive value is performed only once for a given NAT device rather than being an on-going process for that NAT device. When one of the test connections fails, it is determined that the NAT timeout value is less than the test timeout value associated with the failed test connection. Accordingly, a smaller test timeout value is then selected as the keep-alive value for keep-alive processing of the NAT device.