A media session is configured between a first endpoint and a second endpoint on a communication network based on connectivity checks performed by the endpoints. When a reduced connectivity check condition is met, based on characteristics of the communication network operable between the first endpoint and the second endpoint, a reduced candidate pairing procedure is initiated. The reduced candidate pairing procedure includes connectivity checks performed from the first endpoint with a reduced set of candidate pairs that is smaller than an available set of candidate pairs. The reduced set of candidate pairs is identified based on the characteristics of the communication network at the respective pairs, and a particular candidate pair in the reduced set is determined to be valid based on a result of connectivity checks using the candidate pair.