A method includes defining a pattern of time intervals, each time interval having a respective assigned communication speed, which alternates among multiple communication speeds supported by a first communication device. Synchronization requests are transmitted over a communication medium from the first communication device to a second communication device at the respective communication speed that is assigned in each interval in accordance with the pattern. While transmitting the synchronization requests, synchronization replies sent over the communication medium in response to the synchronization requests are received only at the respective communication speed that is assigned in each interval. Responsively to receiving the synchronization replies from the second communication device, one or more common communication speeds that are supported by both the first and the second communication devices are identified. Communication is established between the first and second communication devices over the communication medium using one of the common communication speeds.