Systems and methods are described for a connection service that identifies routing paths for providing a data flow between a client computing device and a target computing device. A client computing device can send an API-based connection request to various servers hosting the connection service. The connection service processes the requests to determine a routing path for the connection. Advantageously, the connection service selects a routing path from a plurality of available routing paths if a client computing device is associated with a network address translator. The connection service may provide an externally addressable network address if it determines that no such address is available for routing of a data flow.