A media session between a first device and a second device is established. The following candidate pairs are determined at the first device, by exchanging network addresses between the devices: (i) a relayed-relayed candidate pair comprising a first media relay server network address and a second media relay server, and (ii) at least one alternative candidate pair. Connectivity checks are performed for at least the alternative candidate pair to determine whether or not the alternative candidate pair is valid. However, the media session is established initially using the relayed-relayed candidate pair without any connectivity checks having been performed by the devices for the relayed-relayed candidate pair and before the connectivity checks for the alternative candidate pair have been completed. If the alternative candidate pair is determined to be valid in the connectivity checks, the established media session is switched to the alternative candidate pair in response.