Embodiments are directed to managing communication over networks. A gateway identifier (GID), a network address, source nodes, relays, or the like, may be determined based on an overlay network. Two or more relays may be ranked based on metrics associated with each relay such that a top ranked relay is designated as a preferred relay.