A media session is established between a first endpoint and a second endpoint via a communication network based on connectivity checks performed by the endpoints. A set of candidate pairs, each comprising a first network address available to the first endpoint and a second network address available to the second endpoint, is generated. Depending on whether or not at least one of a set of one or more reduced connectivity check criteria is determined to be met, a probe threshold for at least one of the candidate pairs. Connectivity checks are performed for the at least one candidate pair by transmitting, by the first endpoint, a number of probe messages from the first network address of that pair to the second network address of that pair that is limited by the probe threshold.