Pastry (P2P)

Pastry fue desarrollado en el año 2001 por los investigadores de Microsoft Research, Antony Rowstron y Peter Druschel.

Se trata de un protocolo que se define como un sistema P2P, completamente descentralizado, escalable y autoorganizado. Emplea un protocolo de transporte UDP en la mayoría de los casos.

El modo de funcionamiento de este protocolo se basa en el encaminamiento en el nivel de aplicación y localización de objetos en una enorme red superpuesta de nodos conectados a través de Internet, teniendo cada nodo de la red de Pastry un único identificador, conocido como ‘NodeID’. Cada nodo Pastry realiza un seguimiento de sus vecinos más inmediatos en el espacio y notifica a las aplicaciones la llegada de nuevos nodos, además de los posibles fallos o desapariciones de nodos y las recuperaciones de estos. Para ello se establece un número esperado de pasos de encaminamiento, que denominaremos O (log N, siendo N el número de nodos en la red Pastry).

Características principales

• Localización independiente de los usuarios: Pastry se basa en la creación de una red en forma de anillo en la que cada uno de los usuarios son independientes y son localizados mediante el uso de la tabla de hojas, tabla de vecinos y la tabla de encaminamiento que posee cada nodo.
• Tolerancia a fallos: Si un nodo abandona la red Pastry tanto como si avisa o no de su desaparición, las responsabilidades del nodo abandonado son inmediatamente asumidas por sus nodos vecinos que actualizan sus correspondientes tablas y avisan al resto de nodos que participan en la red.
• Eficaz encaminamiento dinámico de mensajes.
• Descentralización: No requiere de ningún tipo de servidor central, ya que los usuarios actúan como nodos de la conexión y también de almacenamiento de la información (sistema peer-to-peer).
• Adaptabilidad alta.
• Económico: No se necesitan servidores de alto coste, el único coste que se asume es el propio mantenimiento de la máquina del usuario.
• Seguro: El uso de la función Hash de tipo SHA-1 hace que Pastry sea bastante seguro frente ataques.

Asignación de nodos

A cada nodo y cada clave de fichero se le asigna un identificador único e intransferible de 128 bits generado mediante una función hash SHA–1 o mediante Global Unique IDentifier (GUID), al que se denomina ‘NodeID’ que es expresado en base hexadecimal. Los identificadores de los nodos se representan en un anillo de identificadores de módulo . El rango de los valores de los identificadores de los nodos oscila desde 0 hasta 2¹²⁸ -1.

Red Pastry.

Las claves de los recursos serán almacenadas por los nodos cuyo identificador sea numéricamente más cercano a estas. Cada nodo de la red Pastry almacena referencias a otros nodos en una tabla de hojas, una tabla de vecinos y una tabla de encaminamiento, cada una con distintas características que veremos a continuación.

Para encaminar una clave k, el nodo de la red Pastry hace uso de las referencias contenidas en su tabla de encaminamiento y conjunto de hojas. En principio, cuando dicho nodo recibe una consulta por la clave ‘k’, verifica si k está en el rango de su tabla de hojas; si es así, la consulta se envía al nodo con identificador numéricamente más cercano. Si k se encuentra fuera del rango de la tabla de hojas entonces se emplea la tabla de encaminamiento.

Tabla de encaminamiento (D)

Para explicar el funcionamiento y utilidad de una tabla de encaminamiento, mostraremos el siguiente ejemplo:

Tabla de Encaminamiento.

Imaginemos que tenemos la tabla de encaminamiento^[1]​ del nodo 1234, como mostramos en la tabla. Esta tabla de encaminamiento está compuesta por un número de filas ‘i’, que tiene un rango de existencia entre 0 y el logaritmo en base 2^b de N, siendo N el número de nodos de nuestra red Pastry, y por un número de columnas ‘j’ con rango de existencia desde 0 hasta (2^b -1), siendo ‘b’ la base numérica de los identificadores.

En las filas de nuestra tabla de encaminamiento se almacenan haciendo referencia a los pares cuyos identificadores tienen un prefijo común de longitud ‘i’, es decir, en la fila 1 tendrá como prefijos común en todas las columnas, el 1. Además la tabla de encaminamiento hará coincidir el dígito ‘i+1’ del identificador con el valor de la columna ‘j’. Siendo así el resto de dígitos del identificador diferentes para cada nodo de la red. Si hay un nodo de nuestra red que no cumple las condiciones que acabamos de explicar la entrada en la tabla de encaminamiento quedara vacía.

También podemos destacar que cada identificador de la tabla de encaminamiento del par correspondiente sigue el siguiente formato ‘prefijo-columna-resto de dígitos del identificador’. Por ejemplo, fijándonos en el identificador que contiene la fila 3 con la columna 4: 1234 vemos que 123 es le prefijo común de la fila correspondiente, 4 es el número de la columna después iría el resto de números que podrían acompañar al identificador. Cada entrada de la tabla de encaminamiento además del identificador de su par tiene su dirección IP.

Tabla de hojas (H)

El conjunto de tablas de hojas^[2]​ H contiene nodos cuyo identificador es numéricamente cercano al nodo local, normalmente aparecen en la tabla de hojas los ocho nodos mayores y los ocho nodos menores numéricamente del nodo local. Esta lista de hojas es usada por el nodo que la contenga durante el algoritmo de búsqueda con el fin de reducir el tiempo de rastreo. El tamaño de la lista es de 2*2^b.

Tabla de Hojas.

Tabla de vecinos (V)

La tabla de vecinos V contiene la referencia a los nodos más próximos al nodo local según las métricas que usa la red, es decir, son los nodos más cercanos espacialmente a dicho nodo. Estas métricas de encaminamiento que usa la red Pastry, son proporcionadas por programas externos según la dirección IP de cada nodo. Esta lista no es usada en el algoritmo de búsqueda y su principal función es la de mantener lista y actualizada la tabla de encaminamiento. El tamaño de esta tabla es de 2b.

Incorporar un nodo a la tabla

Para llevar a cabo la incorporación de un nuevo nodo ‘n’ a la red Pastry se sigue el procedimiento que a continuación explicamos:

1. En primer lugar se le otorga al nodo ‘n’ un identificador único e intransferible de 128 bits, que se puede generar a través de, o bien una función hash SHA-1, o bien mediante Global Unique IDentifier (GUID). Una vez que disponga de dicho identificador (NodeID), el nodo ‘n’ se pone en contacto, mediante un mensaje de unión en el que indica su identificador, al nodo más cercano en latencia de la red, ya que una de las características principales de Pastry es el uso de sondas capaces de ubicar el nodo más cercano.
2. A continuación, el nodo más cercano al nodo ‘n’, denominado como nodo vecino, reenvía el mensaje de unión del nodo ‘n’ anteriormente mencionado a ‘n1’, éste vuelve a reenviarlo a ‘n2’, ‘n2’ a ‘n3’, ect, y así hasta completar el anillo de la red Pastry con el último nodo que la conforme (‘ni’).
3. Una vez completado el reenvío de mensajes por parte de todos los nodos de la red, el nuevo nodo recibe toda la información necesaria para poder completar su tabla de vecinos, al igual que su tabla de hojas y su tabla de enrutamiento. Para ello se realiza lo siguiente:^[3]​ El nodo más cercano al nodo ‘n’ inicia todo este proceso enviando a ‘n’ la fila 0 de su tabla de encaminamiento. Del mismo modo, el nodo ‘n’ recibe del nodo ‘n1’ la fila 1 de su encaminamiento. Lo mismo ocurre con el nodo ‘n2’, que envía a ‘n’ la fila 2 de su encaminamiento; y así ocurre sucesivamente con el resto de nodos que forman parte de la red.

Lo que sucede a continuación es que el nodo ‘ni’ envía la tabla de hojas al nodo ‘n’, ya que es el más próximo numéricamente hablando en esta red con forma de anillo. El último paso que se lleva a cabo consiste en que el nodo ‘n’ haga llegar al resto de nodos que conforman dicha red toda la información que ya ha recopilado sobre la tabla de encaminamiento, finalizando este proceso con la integración en la red Pastry del nuevo nodo ‘n’.

Desaparición de un nodo de la red

La desaparición de un nodo de la red,^[4]​ sea ésta avisada como no avisada, son tratadas igual, y se detecta cuando un nodo no responde a los mensajes que los demás nodos están enviando periódicamente por la red Pastry, si se consume un tiempo ’t’ ya predefinido, sin recibir respuesta, se activa el proceso para actualizar las listas de los demás nodos de la red, y se hace de la siguiente manera: el nodo, que no obtiene respuesta por parte del nodo desaparecido, localiza su identificador y averigua que nodo tiene el identificador más cercano al nodo desaparecido para sustituirlo y obtener su tabla de hojas, este nuevo nodo deberá informar de sus nuevas tablas al resto de la red, para proceder a actualizar todas las tablas de los demás nodos que forman la red Pastry.

Algoritmo de búsqueda

A continuación mostraremos como en Pastry se mandan mensajes para la localización de una clave ‘k’ de un nodo a otro mediante el uso de este algoritmo de búsqueda.

Para empezar, un nodo ’n’ recibe un mensaje de un nodo que llamaremos ‘x’ mediante un mensaje de búsqueda. Una vez recibido el mensaje de búsqueda del nodo ‘x’, el nodo ’n’ deberá hacer las siguientes comprobaciones:

1. El nodo ’n’ mirará si el identificador del nodo ‘x’ se encuentra en su tabla de hojas, si el identificador del nodo ‘x’ coincide con alguno de los identificadores que tiene el nodo ’n’ en su lista de hojas, el nodo ‘x’ solo tendrá que dirigir el paquete al nodo ‘x’.
2. Si al comprobar el nodo ’n’ en su tabla de hojas, no se encuentra el identificador del nodo ‘x’, el nodo ’n’ tendrá que hacer uso de su tabla de encaminamiento y hacer las comprobaciones oportunas dígito a dígito para encontrar el identificador más parecido al identificador del nodo ‘x’, si el nodo ’n’ no encuentra el identificador exacto del nodo ‘x’ en su tabla de encaminamiento, este tendrá que enviar un mensaje de búsqueda de tal identificador al identificador que ha encontrado en su tabla de encaminamiento más parecido al del nodo ‘x’.

Por ejemplo, para ilustrar el algoritmo de búsqueda que acabamos de explicar tomaremos de referencia la tabla que mostrábamos en la figura de la tabla de encaminamiento del nodo 1234.

Digamos entonces que el nodo 1234 recibe un mensaje de con nodo destino el 134D. En primer lugar el nodo 1234 busca en su tabla de hojas si el identificador destino se encuentra en ella, si es así, este enviara el mensaje y terminaríamos aquí. Si el identificador destino no se encuentra en la tabla de hojas el identificador destino 134D, el nodo 1234 tendrá que buscar en su tabla de encaminamiento el identificador más parecido dígito a dígito al identificador destino 134D, si no se encuentra el identificador destino en su totalidad, el nodo 1234 deberá hacer una petición de búsqueda al identificador más parecido al 134D.

En nuestro ejemplo vemos que el identificador más parecido dígito a dígito es el de la fila 1 que contiene el identificador 13. Ahora supongamos que el nodo con identificador 13 tiene la dirección IP del nodo de identificador 135A por lo que nos dirigiríamos a dicho nodo, una vez en el nodo con identificador 135A, haríamos el mismo proceso descrito antes y lo repetiremos hasta encontrar el nodo destino con el identificador 134D.

Este algoritmo de búsqueda tendrá una complejidad de orden O, siendo O el logaritmo de N, siendo N el número de nodos que forman la red Pastry.

Algoritmo Pastry

A continuación mostramos alguna de las acciones que permite la interfaz Pastry:^[5]​

• nodoId = pastryInit(Credentials): Esta operación incorpora un nodo a la red Pastry. El parámetro que tiene entre paréntesis esta operación (Credentials) es facilitado por la aplicación y dispone de toda la información necesaria para facilitar al nodo la entrada a la red de forma segura.
• route(msg, destId): Esta operación trata de orientar el mensaje del nodo que quiere entrar a la red a su nodo más cercano, el cual tiene el identificador numéricamente parecido al suyo.
• deliver(msg, destId): Con esta operación se recibe el mensaje que envía el nodo numéricamente más cercano con el nodo destino.
• forward(msg, destId, nextId): Esta operación se encarga de reenviar un mensaje al nodo que tenga el mismo identificador del nodo destino, en caso de que no exista el nodo destino, este mensaje ira destinado al nodo local.
• newLeafs(leafSet): Esta operación es usada para indicar que hay un cambio en las listas de hojas de los nodos para que se pueda actualizar y evitar errores de encaminamiento.

Seguridad en Pastry

Como todo sistema que se precie, Pastry tiene un cierto nivel de seguridad para garantizar la privacidad e integridad de la red, Pastry codifica los identificadores a través de una función Hash, que no es más que una función que recibe a la entrada un mensaje de longitud variable y a la salida muestra un código (hash) de rango finito. En concreto, la función Hash usada por nuestra red Pastry, es la SHA-1.

Aplicaciones

El sistema Peer to Peer Pastry ha sido empleado en una amplia variedad de aplicaciones entre las que destacamos: Scribe y PAST.

Scribe se trata de un sistema multipunto para la distribución de archivos desde el nivel de aplicación en él, Pastry se encarga de la creación de grupos de nodos y le permite la elaboración de árboles para hacer más sencilla la distribución multipunto con una sobrecarga mínima.

Past es un sistema Peer to Peer (P2P) que usa el protocolo Pastry para la creación de una red superpuesta en la que los archivos pueden ser compartidos discretamente por parte de su propietario, esta aplicación hace uso de archivos a gran escala. Past se basa en Pastry y su forma de direccionamiento de proximidad de claves para llegar a mejorar el sistema CFS en el almacenamiento de archivos

Referencias

1. Machado Illán, Sara; Verdejo López, José Alberto; Pita Andreu, Mª Isabel. “Especificación y análisis del protocolo Chord en Maude”. Facultad de Informática, Universidad Complutense de Madrid. Publicado el 10 de septiembre de 2012.
2. Martín Nevado, David; Machado, Sergio. “Diseño e implementación de un sistema de Telefonía IP sobre una red P2P I”. Escola Politècnica Superior de Castelldefels, Universidad Politécnica de Catalunya. Publicado el 20 de septiembre de 2006.
3. Vallecillos Ruiz, Jesús; Corral Liria, Antonio Leopoldo; Iribarne Martínez, Luis Fernando. “Gestión de la Información Especial en Sistemas P2P”. Archivado el 8 de diciembre de 2015 en Wayback Machine. Escuela Politécnica Superior, Universidad de Almería. Publicado en septiembre de 2013.
4. Ruiz, Cristian. “Programación de Sistemas Distribuidos”. Departamento de Ciencia de la Computación Pontificia, Universidad Católica de Chile. Publicado en el primer semestre de 2013.
5. Rowstron, Antony; Druschel, Peter. “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems”.