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 2128 -1.
thumb|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:
centro|Tabla de Encaminamiento. Imaginemos que tenemos la tabla de encaminamientoMachado 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. 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 2b 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 (2b -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 hojasMartí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. 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*2b.
centro|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: 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. 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’, etc, y así hasta completar el anillo de la red Pastry con el último nodo que la conforme (‘ni’). 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:Vallecillos Ruiz, Jesús; Corral Liria, Antonio Leopoldo; Iribarne Martínez, Luis Fernando. “Gestión de la Información Especial en Sistemas P2P”. Escuela Politécnica Superior, Universidad de Almería. Publicado en septiembre de 2013. 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,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. 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: 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’. 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.