Предполагая, что, как вы сказали, порты переадресованы правильно, вы можете отправлять пакеты UDP двум клиентам за маршрутизаторами.
Хороший способ обнаружения клиентов в локальной интрасети может использовать многоадресную рассылку, однако этого не происходит.широко распространенная поддержка интернет-провайдеров (по крайней мере, здесь, в Великобритании), поэтому нельзя полагаться.Многоадресная рассылка используется многими платформами обнаружения устройств, такими как mDNS (используется в Bonjour от Apple)
http://en.wikipedia.org/wiki/Multicast
(в основном это работает, когда клиенты подписываются на группы, а затем отправляют сообщения в эту группу)
Я думаю, что лучший способ обнаружения новых клиентов через Интернет - это иметь один сервер, с которым новые клиенты связываются, чтобы сообщить ему о своем существовании, тогда централизованный сервер расскажет обо всех других клиентах о вас.Это используется, например, в P2P-играх, таких как Modern Warfare 2, и это то, что «трекеры» делают в протоколе BitTorrent.
Это не совсем децентрализовано, но, вероятно, наиболее просто для реализации и наиболеенадежно.