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. 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 full or a reduced set of candidate pairs is generated, each candidate pair of whichever set is generated comprising a first network address available to the first endpoint and a second network address available to the second endpoint. Connectivity checks are not performed for any candidate pair in the full candidate pair set that is not also in the reduced candidate pair set if it is determined that at least one of the reduced connectivity check criteria is met.