A method of establishing a connection traversing at least one network address translation, NAT, gateway (130,131), the method comprising: sending a bind request from a source device to a first element via a NAT gateway; receiving at the source device a bind response including a source combination address that is the public address of the source device, the source combination address comprising a combination of an IP address and a port number; establishing a connection request at the source device and including the source combination address, and causing the connection request to be sent from the source device to a destination device via at least one NAT gateway (130,131) and via the first element; receiving at the source device a connection response sent by the destination device and including a destination combination address that is the public address of the destination device, the destination combination address comprising a combination of an IP address and a port number; sending a hello message to a predicted destination combination address based on the destination combination address received; and establishing a data connection between the source device and the destination device using the predicted destination combination address; wherein the connection request is sent to a destination device via the first element and via a message server; and in that the message server maintains a persistent connection with the destination device so that the message server was in communication with the destination device prior to the bind request from the source device wherein the connection request sent from the source device also includes the IP address of the first element so that, in response to the connection request, the destination device is enabled to send a bind request to said first element; and in that after receiving a bind response from the first element, destination device sends said connection response to the first element which contains said destination combination address of the destination device. sending a bind request from a source device to a first element via a NAT gateway; receiving at the source device a bind response including a source combination address that is the public address of the source device, the source combination address comprising a combination of an IP address and a port number; establishing a connection request at the source device and including the source combination address, and causing the connection request to be sent from the source device to a destination device via at least one NAT gateway (130,131) and via the first element; receiving at the source device a connection response sent by the destination device and including a destination combination address that is the public address of the destination device, the destination combination address comprising a combination of an IP address and a port number; sending a hello message to a predicted destination combination address based on the destination combination address received; and establishing a data connection between the source device and the destination device using the predicted destination combination address; wherein the connection request is sent to a destination device via the first element and via a message server; and in that the message server maintains a persistent connection with the destination device so that the message server was in communication with the destination device prior to the bind request from the source device wherein the connection request sent from the source device also includes the IP address of the first element so that, in response to the connection request, the destination device is enabled to send a bind request to said first element; and in that after receiving a bind response from the first element, destination device sends said connection response to the first element which contains said destination combination address of the destination device.