La mayor parte de los nodos de Internet no disponen de una dirección IP fija o siquiera accesible para otros nodos de Internet. Este es el caso, por ejemplo, de los nodos que se conectan a través de redes locales como Wifi o Ethernet, de aquellos que tienen algún tipo de cortafuegos y NAT o de los que se conectan a través de la mayor parte de los ISPs del mundo. Para el correcto funcionamiento de una red P2P, hay que resolver dos problemas fundamentales: cómo se encuentra un nodo que ya esté conectado a la red P2P y cómo se conectan los nodos sin dirección IP pública entre ellos.
Para resolver el primer problema, la solución habitual es realizar una conexión a un servidor (o servidores) inicial con dirección bien conocida (normalmente IP fija) que el programa P2P tiene almacenada. Este servidor inicial se encarga de mantener una lista con las direcciones de otros nodos que están actualmente conectados a la red. Tras esto, los clientes ya tienen información suficiente para entrar en la red y pueden intercambiar información con otro nodos, ya sin intervención de los servidores iniciales.
Para resolver el problema de conexión cuando los nodos no tienen dirección pública, estos se conectan a través de otro nodo que funciona como proxy de la conexión. Los dos nodos se conectan al proxy y éste envía la información que llega de uno al otro. Cualquier nodo con una dirección IP pública puede ser escogido como proxy de una conexión entre dos nodos. Por ejemplo, en la red Skype a través de nuestro ordenador pueden pasar conversaciones de otras personas. En estos casos, es imprescindible la implementación de algún mecanismo de seguridad para evitar que los proxies pueden llegar a entender la comunicación entre los dos nodos.