In one embodiment, a source device (e.g., a VOIP phone) establishes a call connection with a remote device depending on which of multiple network paths provides an acceptable latency (e.g., a lower latency). For example, in response to receiving a request to establish a connection with a remote destination device over a network, the source device (e.g., a caller's phone) obtains multiple service code values. The source device encodes each of multiple data packets to include a unique service code value for transmission of the messages over different network topologies to a remote destination. Thus, when transmitted, each of the multiple messages follows a different logical network topology of a network as specified by a respective service code value. Based on feedback from a remote device that receives the multiple messages, the source learns a preferred logical network topology of the network for establishing the call connection.