Systems, methods, and other embodiments associated with multiple NAT traversal are provided. A request is received from a host for a publicly-routable communication path identifier for the host, where the host is a member of a private network associated with a first network address translation device. The first network address translation device communicates with a second network address translation device using an address-port-borrowing-protocol to acquire information related to the publicly-routable communication path identifier. Information related to the publicly-routable communication path identifier is received with the first network address translation device and the publicly-routable communication path identifier is provided to the host.