Network devices include proxies and where multiple proxies are present on a network, they can probe to determine the existence of other proxies. Where more than two proxies are present and thus different proxy pairings are possible, the proxies are programmed to determine which proxies should form a proxy pair. Marked probe packets are used by proxies to discover each other and probing is done such a connection can be eventually formed even if some probe packets fail due to the marking. Asymmetric routing can be detected and proxies configured for connection forwarding as necessary.