1. Сделал утилиту, привязанную к моему сокету. Которая определяет тип NAT, а также внешний IP:Port.
2. Как теперь обходить:
а) Address-Restricted cone NAT или Restricted cone NAT.
б) Port-Restricted cone NAT

В этих двух типах немного запутался.
Какие должны быть действия, чтобы 2 клиента могли общаться беспрепятственно между собой?

Ну на картинке
http://ilya-314.livejournal.com/109479.html
ведь разрисовано достаточно понятно ..

Симметричный не обойти.

Адрес-рестриктед - только через сервер-посредник (считай - никак)

Порт-рестриктед - сообщив клиенту через сервер-посредник с какого конкретно порта на какой адрес он может зайти (в течение ограниченного периода времени).

Полноконический - сообщив клиенту через сервер-посредник на какой адрес он может зайти (в течение ограниченного периода времени).

Есть еще возможность обойти NAT с помощью специальных протоколов: NAT PMP, NAT UPnP - они поддерживаются почти 100% современных роутеров. В Windows даже есть реализация UPnP:
http://msdn.microsoft.com/en-us/library/windows/desktop/aa366182(v=vs.85).aspx

UPnP не имеет ничего общего с "обходом"

Имеет. Он позволяет создать в роутере пару внешний адрес - внутренний адрес вручную.
Пример:
http://www.codeproject.com/Articles/13285/Using-UPnP-for-Programmatic-Port-Forwardings-and-N

> Он позволяет создать в роутере пару внешний адрес - внутренний
> адрес вручную


Ну и причем здесь "обход" ?

Притом. TCP Hole Punching, UDP Hole Punching и другие - это способы создания маппинга, основаные на принципе работы NAT. Поэтому они сильно зависят от типа NAT. NAT UPnP позволяет самому создать маппинг, который будет точно такой же, как и при создании с Hole Punching - разница в том, что вы сами можете управлять этим маппингом. Кроме того, этот способ также более стабилен - маппинг не нужно время от времени обновлять, как в случае с Hole Punching. NAT UPnP активно используют Skype, Miranda и другие приложения. И вообще, внимательно почитайте статью по ссылке

> внимательно почитайте статью по ссылке

Я прекрасно представляю как это работает.
Маппинг - это НЕ обход, это прямое прямое управление NAT'ом.
А обход предполагает использование особенностей конкретной реализации NAT без вмешательства в его конфигурацию.

Не будем придираться к словам. Если человек ищет пути обойти NAT - это в 99.9% значит что ему надо принимать входящие соединения, а каким способом это будет сделано ему все равно

все бы хорошо, но:

1. Нет никакой гарантии что UPnP-сервис будет доступен на произвольно взятой клиентской машине.

2. UPnP - это потенциальная дырища в системе сетевой безопасности.

Убиваю не глядя, дыра ужасная