Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Free Pastry

No description
by

alvaro fernandez

on 4 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Free Pastry

INDICE
Free Pastry
El mecanismo de encaminamiento depende de dos parámetros de configuración:
L :
Cada nodo mantiene una lista de nodos en la red que tienen los IDs más cercanos al nodo (16 o 32) .
b:
Cuando los mensajes de routing,
nodeIds
y claves son convertidos a base 2b. Cada salto durante la fase de encaminamiento envía el mensaje a un nodo que comparte un dígito más con la clave que en el salto anterior (4).

Esto permite que el algoritmo envíe mensajes al nodo con el número más cercano a la clave en
O (log2bN)
.

N
es el número de nodos en la red Pastry.
Algoritmo de encaminamiento (Routing)
Resuelven el problema de localizar objetos y enrutamiento de objetos en sistemas P2P
.

Redes Estructuradas:
Chord, CAN,
Pastry
, Tapestry, Kademlia, ...

Dada una clave (key) del objeto deseado, el nodo que contiene el objeto se puede encontrar de forma rápida y eficientemente.

 No se necesitan de servidores centralizados.
    
No hace falta realizar consultas mediante inundaciones o utilizar técnicas de búsqueda que requieren gran ancho de banda consulta.


¿Qué es Pastry?
Free Pastry
Álvaro Fernández & Jon Larizgoitia
Funcionamiento
Funcionamiento
Algoritmo de encaminamiento (Routing)
Diseñado para enviar el mensaje al
nodo más cercano
y
minimizar la distancia física recorrida
(saltos IP).

Cada nodo mantiene una tabla de encaminamiento.

El criterio para elegir el nodo más cercano depende de:
Valor más cercano
nodeIds

Métrica de proximidad

Los nodos y objetos tienen un GUID de 128 bits

Envía los mensajes en O(log N) pasos

Emplea un protocolo de transporte (normalmente UDP)

Los mensajes se envían a un nodo cercano, según el GUID.

La tabla de enrutado se rellena con nodos cercanos, según la distancia de la red.

Pastry: Sw Intermediación P2P
Aplicación peer-to-peer:
Genérica
Escalable
Eficiente

Nodos Pastry forman una red:
Descentralizada
Auto-organizativa
Tolerancia a fallos

1- ¿Qué es Pastry?
2- ¿Qué nos proporciona?
3- Funcionamiento
4- Algoritmo de encaminamiento (Routing)
5- Aplicaciones
6- Conclusiones
Pastry proporciona las siguientes capacidades.
En primer lugar,
Cada nodo tiene un único identificador de 128 bits
Los nodos se organizan en una estructura de anillo
Cuando se envia un mensaje y una clave, un nodo se encarga enrutar el mensaje al nodo que tiene el nodeID numericamente más cercano a la clave dada.
En segundo lugar, cada nodo Pastry realiza un seguimiento de sus L vecinos más cercanos en el espacio NodeID (llamado el conjunto de la hoja), y notifica a las aplicaciones de las nuevas llegadas de nodos, fallos en los nodos y las recuperaciones de nodos dentro del conjunto de la hoja
En tercer lugar, Pastry
tiene en cuenta localización (proximidad) en el Internet subyacente; se busca minimizar la distancia que viajan los mensajes, de acuerdo con una métrica de proximidad escalar como el retardo ping.
Proporciona:
+ Encaminamiento eficaz de grandes sistemas P2P
+ Localización determinista de objetos
+ Balanceo de carga independiente de aplicación
Extras:
+ Mecanismos que apoyen redundancia
+ Almacenamiento en caché
+ Recuperación de fallos
¿Qué nos proporciona?

Enlaces:

http://www.freepastry.org/

http://www.dit.upm.es/~aalonso/sodt/p2p.pdf

http://research.microsoft.com/en-us/um/people/antr/PAST/pastry.pdf

Bibliografía
Encaminamiento Circular
El protocolo se arranca con la dirección IP de un compañero que ya está en la red y de ahí en adelante a través de la tabla de enrutamiento que se crea y actualiza de forma dinámica.

Debido a su naturaleza descentralizada redundante no existe ningún punto único de fallo, por lo que cualquier nodo puede salir de la red en cualquier momento (sin avisar) y esto no supone ninguna pérdida de datos.

El protocolo también es capaz de usar una métrica de encaminamiento suministrada por un programa externo, como ping o traceroute, para determinar las mejores rutas para almacenar en su tabla de encaminamiento.

Los recursos son situados en sitios (nodos) precisos. El emplazamiento de cada recurso es calculado mediante una función hash.

Esta función indica qué nodo ha de encargarse (saber la localización) de cada recurso.

Es un sistema P2P auto-organizativo basado en tablas hash distribuidas.

Conclusiones
Pastry es un sistema genérico de
localización de contenido peer-to-peer
(P2P) y
encaminamiento
basado en una red superpuesta de auto-organización de nodos conectados a través de Internet.

Es completamente
descentralizado, tolerante a fallos, escalable
y de manera fiable
envía los mensajes al nodo mas cercano con un NodeID
numéricamente más cercano a una clave.

Las rutas Pastry a cualquier nodo de la red tiene en cuenta la ubicación al encaminar los mensajes.

Es
eficiente
y funciona bien, es un sistema
auto-organizativo
y
adaptativo
ante posibles fallos de nodos, con buenas propiedades locales.

Aplicaciones
Es un sistema que se puede utilizar para una serie de aplicaciones como:

PAST
Sistema de archivos distribuido
A cada nombre de archivo se le aplica un algoritmo hash para conseguir un
fileID
.
El campo se utiliza como clave Pastry para el archivo.
    
Para recuperar un archivo, basta con enviar un mensaje a la red Pastry con el fileID como clave.

Se guardan todos los archivos en los nodos k con nodeIds cercanos al fileID para tener redundancia y por posibles errores de nodo.
SCRIBE
Sistema de Publicación y Suscripción
Se aplica el algoritmo hash a los temas para obtener
topicIDs
que se utilizan como identificación por un grupo particular de suscripción .

Los suscriptores pueden suscribirse a un tema utilizando un
topicId
concreto.

El nodo más cercano al
topicId
mantiene una lista de suscriptores formando un sistema multicast de temas.

L
nodos que son numéricamente más cercanos al nodo
(L / 2 más pequeño y L / 2 más grande) .

La tabla de encaminamiento contiene una fila para cada dígito en el
nodeID
(filas log2bN). Cada fila contiene una entrada para cada posible valor para ese dígito.

Todas las cifras anteriores de la entrada deben coincidir con los
nodeIds
actuales, mientras que los siguientes dígitos pueden tener cualquier combinación.

Encaminamiento (Routing)
Un mensaje con la clave
D
llega a un nodo con NodeID
A
.

El nodo comprueba primero el
LeafSet
(conjunto de la tabla):
Si D esta dentro del rango de nodeIDs de la tabla, el mensaje se reenvía al nodo en la tabla que tiene el nodeID más cercano a D.

Si no, se utiliza la
tabla de Routing
(encaminamiento):


Algoritmo de encaminamiento (Routing)
k
: número de dígitos que D y A tienen en común

Envía el mensaje al nodo en la fila de orden k que tiene el dígito k1 en común con D.

Si esta entrada no existe, reenviará el mensaje al nodo que tiene el valor numérico más próximo de todos los nodos en
la tabla de LeafSet
y

de
Routing
.
Mantenimiento de las tablas:
En forma periódica, se estudia una entrada al azar de cada fila de la
tabla. Se le pide esa fila, y se actualiza la información basándose en
la métrica.

Actualización
o
Reparación lenta:
La información del estado de un nodo no se actualiza hasta que se produce un fallo a la hora de ponerse en contacto con ese nodo.
Si el nodo está en el
LeafSet
, se pone en contacto con el nodo de ID más alto y actualiza la información utilizando la tabla de ese nodo.
Si el nodo está en la tabla de
Routing
:
Se pone en contacto con un nodo diferente en la misma fila.
Si no hay ningún nodo, se pide a la siguiente fila y así sucesivamente.
Gestión de Fallos/Salidas nodos
Tablas Hash Distribuidas (DHT)
Full transcript