jueves, 27 de marzo de 2008

Redes Peer-to-Peer

¡Las vueltas que da la vida! Uno comienza trabajando en Bluetooth mucho antes que lo metiesen en todos los teléfonos móviles y acaba trabajando en redes peer-to-peer (p2p) cuando es algo más viejo que Matusalem.

La verdad es que siempre me interesó saber cómo demonios iba tan rápido el BitTorrent. Bajarse cosas con el torrent (legales, por supuesto) es cosa de la velocidad de línea que tengas (nota mental: hablar de velocidad de línea, que mis alumnos me lo agradecerán).

Pero no hay nada perfecto. Con sistemas estilo eMule (red edonkey), uno tiene una sección de búsqueda y luego sólo hay que darle al botón de descargar, cuando encontramos lo que queremos. Sin embargo, en otros clientes nos encontramos con otros problemas a la hora de descargar contenido. Esto es así de complicado, ya que utilizan lo que se llama la DHT (Distributed Hash Table). Vayamos desmenuzando cada una de estas palabras.

Hash. No es más que un valor generado a partir de otro utilizando una función. Por ejemplo: hash = funcion (dirección IP). La función puede ser cualquiera (buena, claro) como por ejemplo las SHA que son muy utilizadas. La SHA1 genera un hash de 160 bits, independientemente del argumento que se le ponga (si metemos una dirección IPv4 nos dará un hash de 160 bits, y si metemos una dirección IPv6 nos dará otro hash, pero también de 160 bits). Lo importante de todo esto, es que podemos identificar cosas diferentes, utilizando la misma notación (si tengo un fichero de vídeo y le calculo su SHA1, me dará un identificador de 160 bits, y si tengo un fichero de audio, su hash será otro identificador de 160 bits). Estas funciones no son elegidas al azar, ya que deben cumplir muchas cosas. Una de ellas es la siguiente: dados dos valores a y b, los hashes generados f(a) y f(b) serán distintos. Lógicamente, hay una pequeña probabilidad que esto no ocurra, pero esto ya depende de lo bueno que sea el método. A quien le interese, hay un problema estadística muy interesante, en donde se trata de buscar la probabilidad de que, dado un conjunto de personas en una sala, dos personas tengan la misma fecha de nacimiento (Birthday Paradox).

Table. En este caso, se generarán identificadores (hashes) para cada nodo de la red peer-to-peer, pero también para los objetos que se estén compartiendo (cada fichero que se comparta, tendrá su correspondiente identificador o hash). La tabla en este caso, es una lista, almacenada en cada nodo, de los diferentes identificadores que ese nodo sabe (no tenemos porqué saber todos los identificadores de la red p2p, pero sí una visión parcial de la misma).

Distributed. Más o menos ya lo he explicado en el párrafo anterior. Los identificadores de la red p2p estarán distribuidos entre todos los nodos que la forman.

Por ejemplo. En la red Kademlia (más o menos famosa, porque eMule soporta esta red), cada nodo (ordenador, equipo) tendrá un identificador de 160 bits (como se ha comentado anteriormente, la probabilidad de que dos equipos tengan el mismo identificador, es muy baja). Podemos representar a cada equipo en un círculo, como en la siguiente figura. A cada objeto (fichero de vídeo, imagen, audio, etc.) que cada equipo comparta, tendrá también un identificador de la misma longitud.

Imaginemos que arranco mi Kademlia (nodo A) y me dan un identificador A0B1A (está en hexadecimal) y tengo dos ficheros que quiero compartir (00000 y CCCCC). Uno de los primeros pasos es detectar a otros equipos que ya formen parte de la red p2p y almacenaré sus identificadores y sus correspondientes direcciones IP y puertos en mi tabla DHT (esto es más complicado, pero para nosotros nos sobra). Imaginemos que sólo consigo un equipo (nodo B) en esa tabla y tiene como identificador CCCC0 y dirección IP 163.117.139.X.

El paso más importante es el de distribuir mi información local en la red P2P. Para ello, enviaré un mensaje a la red por cada objeto que quiera compartir (en nuestro ejemplo, dos). La idea clave de todo es lo siguiente: cada nodo de la red P2P, almacenará un localizador para aquellos objetos cuyo identificador esté muy próximo al propio identificador del nodo. Por ejemplo, cuando nuestro nodo arranca, querrá informar a la red que él tiene los objetos cuyos identificadores son el 00000 y el CCCCC. Comencemos por el último.

Como el nodo en cuestión sólo tiene un punto de contacto en la red (CCCC0), le mandaremos un mensaje diciéndole que tenemos un objeto cuyo identificador es el CCCCC. Si este nodo, no tiene constancia de que exista otro nodo en la red, con un idenficador más parecido, él se encargará de mantener el localizador de este objeto (CCCCC -objectID- y CCCC0 -nodeID- se parecen mucho). Por lo tanto, el nodo B almacenará un localizador diciendo: si alguien me pregunta por el localizador CCCCC, yo le responderé que es el nodo A (guardo también su IP y puerto) quien lo tiene. Fijaros que pueden haber más equipos que tengan ese objeto. Pues el nodo B tendrá varios localizadores para el mismo objeto.

En la figura podéis ver un ejemplo de qué pasaría si el nodo 3D8C7810 quiere localizar el objeto D78AE154. Buscaría en su tabla DHT y el nodoID más parecido sería el D0017854. Le enviaremos un mensaje a ese que a su vez buscará en su tabla, encontrando que el más parecido al objeto buscado es el D785DD10. Este haría lo mismo hasta que encontramos un nodo (D78AE135) que es el más cercano de toda la red a dicho objeto y que, por lo tanto, debería tener el localizador para dicho objeto.