Sistemas Distribuidos Módulo 4 - Departamento de Ciencias ...

1

Sistemas Distribuidos

Módulo 4

Sistemas Peer-to-Peer

Sistemas Distribuidos – Peer-to-PeerKMC © 2019

Sistemas Peer-to-Peer

Característica

Evolución

Aplicaciones

Primera, Segunda y Tercera Generación

Métodos de Búsqueda. DHT

2


Peer-to-Peer (P2P)

«Peer-to-peer es un Sistema auto-organizado de entidadesiguales, autónomas (peers), cuyo objetivo es el usocompartido de recursos distribuidos en un ambiente de redevitando servicios centralizados» Oram y otros, 2001.


Peer-to-Peer (P2P)

P2P representa un paradigma para la construcción desistemas distribuidos y aplicaciones en los cuales datos yrecursos computacionales son provistos por varioshuéspedes en Internet, todos los cuales participan en laprovisión de un servicio uniforme.

Un problema clave es la UBICACIÓN de los objetosde datos en muchos huéspedes y el subsecuenteACCESO a los mismos de manera de balancear lacarga y asegurar la disponibilidad sin agregarsobrecarga.

3


P2P: Características

Cada usuario contribuye con recursos al sistema.

Los nodos tienen la misma capacidad funcional yreponsabilidades, aunque pueden diferir en los recursos queproveen.

La administración no depende de la existencia de un sistemaadministrativo central.

Pueden ofrecer un limitado grado de anonimato a provedoresy usuarios de recursos.

Un aspecto clave es la elección de un algoritmo de ubicaciónde los datos a lo largo de muchos huéspedes y su subsecuenteacceso.


Ejemplos de P2P

Napster

Gnutella

Audiogalaxy

FastTrack/KaZaA

iMesh

Freenet

eDonkey

Bittorrent

Skype

4

Áreas de Aplicación


No hay una clara distinción

Algunos casos tienden a confundir

Aplicaciones P2P Clasificación

Clasificación Convencional Clasificación

de P2P

Archivos Compartidos (Napster,

Gnutella, Freenet)

Grid Computing (SETI@home)

Mensajería Instantánea (ICQ, AIM)

Colaboración (Espacio de trabajo

Groove)

Clasificación por medio de recursos

compartidos

Información

Archivos

Ancho de Banda

Espacio de almacenaje

Ciclos de Procesador

5


Aplicaciones - Búsqueda

Problema de Búsqueda:

Localizar recursos es, en general, un problema central

de las redes P2P y compartir archivos en particular.

Las redes P2P proveen diferentes métodos para

almacenaje, búsqueda y recuperación de los archivos:

Modelo de Directorio Centralizado.

Modelo de requerimieno por “inundación” .

Modelo de ruteo de Documentos.


Tráfico en las redes

América Latina – Acceso Fijo (Reporte del año 2016)

6


Tráfico en las redes

América Latina – Acceso Móvil (Reporte del año 2016)

Sistemas Peer-to-PeerPrimera y Segunda Generación

7


Servents

Red P2P Datos

Servidor

Cliente

Encaminamiento


Modelo de Directorio Centralizado

Sistema P2P híbrido

El servicio de indexado es provisto centralmente por una entidadde coordinación.

Un requerimiento de búsqueda es atendido por la entidadcoordinadora que presenta una lista de peers que tienen losarchivos requeridos .

Luego el peer obtiene los archivos respectivos directamente delos otros peers que los ofrecen.

Características

La búsqueda de documentos existentes puede ser garantizada.

El servicio de indexado es “Un Único Punto de Falla”.

Ejemplo: “Primer” Napster

Compartía archivos de música.

8


Definición de P2P centralizada Todos los peers están conectados a una entidad central

Los Peers establecen conexiones entre ellos para intercambiar datos (e.g. mp3)

La entidad central es necesaria para proveer el servicio.

La entidad central es una clase DB índice/grupos

La entidad central es la tabla de búsqueda/ruteo

ServentConexión entre

2 servents (TCP)

Conexión entre ruteadores y serventsConexión entre ruteadores (Core)

TOPOLOGÍA


P2P Centralizada - Napster

Metaservidor

Servidor

Napster:8888Servidor

Napster:8888

Servidor

Napster:8888

Servidor

Napster:8888

ClienteCliente

Cliente

Cliente

Cliente

Cliente

Cliente

Cliente

Cliente

Cliente

Descarga

DescargaLogin

Cliente

9


Napster - Protocolo


Modelo de Requerimiento por “Inundación”

Sistema P2P atómico Sin autoridad central de coordinación (todos los peers son iguales).

El requerimiento de búsqueda pasa por un determinado número depeers.

Si no pueden responder el requerimiento, lo pasan sobre otros nodoshasta cierto nivel de profundidad (ttl=time-to-live).

Cuando el archivo requerido ha sido localizado, los resultadospositivos de la búsqueda son enviados a la entidad que los requirió.

El peer puede ahora bajar el archivo deseado directamente de lasentidades que lo ofrecen.

CARACTERÍSTICAS

La búsqueda de documentos existentes no puede ser garantizada.

El sistema no escala bien.

10


Modelo de Requerimiento por “Inundación”

Ejemplo: Gnutella

Extensión: FastTrack

“Super Peers” como proxies.

El sistema P2P no es más atómico.

TOPOLOGÍA DE P2P PURO

ServentConexión entre

2 servents (TCP)

Conexión entreruteadores y serventConexión entreruteadores (Core)


Gnutella

Constituye una red solapada virtual con mecanismos propios de ruteo

No hay coordinación central de actividades en la red.

El software de soporte son “servents”.

Usa IP como red subyacente, mientras que la comunicación entreservents está especificada en forma de protocolo a nivel deaplicación.

PROTOCOLOPing: Requerimiento de un host para autoanunciarse

Pong: Respuesta al Ping. Contiene el IP y el Puerto del host, el número ytamaño de archivos compartidos.

Query: Un requerimiento de búsqueda. Contiene un string de búsqueday los mínimos requerimientos de velocidad del host que responde.

QueryHits: respuesta a Query. Contiene IP, puerto y velocidad, el númerode archivos encontrados y el conjunto de índices resultado.

11


Gnutella - Protocolo

La localización de un archivo se hace por una búsqueda nodeterminística dado que los nodos no pueden adivinar dondeestán los archivos. Utiliza broadcast para distribuir Ping yQuery.CARACTERÍSTICAS

- Cada nodo los envía a sus vecinos y las respuestas hacen elcamino inverso.- Para limitar los mensajes los mismos tienen un TTL (time tolive), en cada hop este TTL es decrementado y cuando llega a 0el mensaje se “cae”- Se eliminan lazos de mensajes por medio de un identificador.- Una vez que el nodo recibe un QueryHints inicia con esosdatos una conexión directa entre dos nodos.- La imposición del TTL impone un horizonte a cada cliente.


1

7

3

2

4

5

6

8

Gnu-ConGnu-Con

Peer7 Peer3 Peer1 Peer5 Peer2 Peer4 Peer6

Gnu-ConOKOK

OK

PINGPING

PINGPING

PING PING

PING

PONG

PINGPING

PING

PONG

PONG

PONG

Peer8

PING

PONG

PONG

PONG

PONG

PONG

PONGPONG

PONG

PING

Gnutella – Ejemplo de red 0.4

Secuencia de mensajes de acuerdo al ejemplo de red.

12


Definición de P2P híbrida

Principal característica comparada con P2P puro: Introducción de otracapa dinámica jerárquica

Red basado en hub

Reduce la carga de señalamiento sin reducir la confiabilidad

Proceso de elección para seleccionar la asignación de un Superpeer

Superpeers: alto grado (>>20, dependiendo del tamaño de la red)

Leafnodes: conectado a uno o más Superpeers (<7)

Superpeer

leafnode


Sistemas P2P basados en P2P híbridos

Edonkey

Kazaa/FastTrack

Emule

OpenNap

…

13


Secuencia de mensajes de acuerdo al ejemplo de red:4L1 L3

S2

S3

S1

L2

L5

L4

L6

L7

Gnu-Con

L2 L3 L1 S1 S3 S2 L7

OK

PONG

L6 L5 L4

RTU

PING

PONG

PONG

PING

PINGPONG

PONG

PINGPING

QUERYQUERY

QUERY

QUERYQUERY

QUERYQUERY

QUERY

QUHIT

QUHIT QUHITQUHIT

QUHITQUHIT

QUHITQUHIT

Gnutella – Ejemplo de red 0.6

Tablas Hash Distribuidas

14


Modelo de ruteo de Documentos

Sin autoridad central de coordinación (todos los peers soniguales).

Los archivos no están almacenados en el HW de los peers quelo proveen.

Los archivos está almacenados en otras locaciones de la redP2P.

Asigna responsabilidad por un conjunto de archivos a cadapeer (de acuerdo a una función definida).

Rutea archivos a peers asociados que los almacenan.

Se usa una función definida para determinar el peer asociadocuando hay un requerimiento.

Se baja el archivo del peer asociado.

Usa una función hash: “Distributed Hash Table (DHT)”


Modelo de ruteo de Documentos

CARACTERÍSTICAS

La autoorganización permite la adaptación en casos de entrada y salida necesaria de peers.

Ejemplos

Pastry, Chord, CAN, Tapestry, Freenet.

15


Fundamentos de Búsqueda

D

?

Data item „D“

distributed system

7.31.10.25

peer-to-peer.info

12.5.7.31

95.7.6.10

86.8.10.18

planet-lab.orgberkeley.edu 89.11.20.15

I have item "D".Where to place

“D“?

I want item “D“.Where can I find

“D“?


Fundamentos de Búsqueda

Centralizada

Inundación

16


Motivación de Indexado Distribuido

Sobrecarga de Comunicación vs. estado del nodo

Sob

recarg

a C

om

mu

nic

ació

n

Estado Nodo

Flooding

CentralServer

O(N)

O(N)O(1)

O(1)

O(log N)

O(log N)

Cuello de botella:•Sobrecarga Comunicación

•Falso negativos

Cuellos de botella:•Memoria, CPU, red•Disponibilidad

?Solución escalable

entre ambos extremos?


Motivación de Indexado Distribuido

Sobrecarga de Comunicación vs. estado del nodo

Sob

recarg

a C

om

mu

nic

ació

n

Estado Nodo

Flooding

CentralServer

O(N)

O(N)O(1)

O(1)

O(log N)

O(log N)

Cuello de botella:•Sobrecarga Comunicación

•Falso negativos

Cuellos de botella:•Memoria, CPU, red•DisponibilidadDistributed

Hash Table

Escalabilidad: O(log N)

No falsos negativos

Resistencia contra cambios

Fallas, Ataques

Usuarios por corto tiempo

17


Fundamentos de DHT

Desafíos en el diseño de DHTs

Características Deseadas

Flexibilidad

Confiabilidad

Escalabilidad

Igual distribución de contenidos entre nodos

Crucial para una eficiente búsqueda de contenido

Permanente adaptación a fallas, agregados y salidas de nodos

Asignamiento de responsabilidades a nuevos nodos

Reasignamientos y redistribución de responsibilidades encaso de fallas de nodo o partida del mismo


Manejo Distribuido de Datos

SECUENCIA DE OPERACIONES

1. Mapeo de nodos y datos en el mismo espacio de direcciones

Peers y contenidos son direccionados usando identificadores flat(IDs)

Espacio común de direcciones para datos y nodos

Los nodos son responsables por datos en ciertas partes delespacio de direcciones

La asociación de datos a nodos puede cambiar dado que losnodos pueden desaparecer

2. Almacenamiento/Búsqueda de datos en DHT

Búsqueda de datos = ruteo al nodo responsable

El nodo responsable no necesariamente es conocido en avance

Sentencia definitiva acerca de la disponibilidad de datos

18


Direccionamiento en DHT

PASO 1: Mapeo de contenido/nodo en espacio lineal Usualmente: 0, …, 2m-1 >> número de objetos a ser

almacenados Mapeo de datos y nodos en el espacio de direcciones (con

hash) Ej., Hash(String) mod 2m: H(“my data“) 2313

Asociación de partes de espacio de direcciones a nodos HT

H(Node Y)=3485

3485 -610

1622 -2010

611 -709

2011 -2206

2207-2905

(3485 -610)

2906 -3484

1008 -1621

Y

X

2m-1 0

Frecuentemente, el espacio de direccioneses visto como un círculo.

Data item “D”:

H(“D”)=3107 H(Node X)=2906


Asociación del espacio de direcciones con nodos Cada nodo es responsable por una parte del rango de valores

Frecuentemente con redundancia (solapado de partes)

Adaptación continua

Las topologías real (underlay) y lógica (overlay) no correlacionan

Vista lógica de DHT

Mapeo a la topología real

2207

29063485

201116221008709

611

Nodo 3485 esresponsable poritems de datos enrango 2907 to 3485

19


Ruteo de un ítem de dato

PASO 2: Localización del dato (ruteo basado en contenido)

Objetivo: Pequeño y esfuerzo escalable

O(1) con tabla hash centralizada

Pero: Su manejo es muy costoso (servidor)

Sobrecarga mínima con DHT

O(log N): Orden en DHT para localizar un objeto

O(log N): número de claves e información de ruteopor nodo (N = # nodos)



Ruteo de un par K/V

Comienza la búsqueda en un nodo arbitrario de DHT

Ruteo del dato requerido (key)

(3107, (ip, port))

Value = puntero a la locación del dato

Key = H(“my data”)

Nodo 3485 administralas claves 2907-3485,

Initial node(arbitrary)

H(“my data“)= 3107

2207

2906

3485

20111622

1008

709

611

20



Obteniendo el contenido

El par K/V es atendido por el peticionante

El peticionante analiza la K/V-tupla(y baja el dato de la actual locación – en caso de almacenaje indirecto)

H(“my data“)= 3107

2207

2906

3485

20111622

1008

709

611

Get_Data(ip, port)

Nodo 3485 envía

(3107, (ip/port)) al peticionante

En caso de almacenaje indirecto:

Luego de conocer la locación

El dato es requerido


Asociación de datos con IDs – AlmacenajeDirecto

¿Cómo es almacenado el contenido en los nodos? Ejemplo:

H(“my data”) = 3107 es mapeado en el espacio de direcciones DHT

Almacenaje Directo El contenido es almacenado en el nodo responsable para

H(“my data”) Inflexible para grandes contenidos – o.k., si los datos son

pequeños (<1KB)

DD

134.2.11.68

2207

29063485

201116221008709

611

HSHA-1(“D“)=3107

D

21


Asociación de datos con IDs – AlmacenajeIndirecto Almacenaje Indirecto

Nodos en una DHT almacenan tuplas como (key,value)

Key = Hash(“my data”) 2313

Value es una dirección real de almacenaje de contenido:(IP, Port) = (134.2.11.140, 4711)

Más flexible, pero un paso más para alcanzar el contenido

2207

29063485

201116221008709

611

HSHA-1(“D“)=3107

Item D: 134.2.11.68D

134.2.11.68


Llegada de Nodo Agregando un nuevo nodo

1. Cálculo del ID del nodo

2. El nuevo nodo contacta DHT vía un nodo arbitrario

3. Le asigna un particular rango hash

4. Copia de los pares K/V del rango hash (usualmente con redundancia)

5. Mapeo en el ambiente de ruteo2207

29063485

201116221008709

611

ID: 3485134.2.11.68

22


Falla del Nodo/Partida

Falla del nodo

Uso de pares redundantes K/V (si el nodo falla)

Uso caminos de ruteo redundantes/ alternativos

El par Key-value usualmente continua recuperable en al menos una copia

Partida de un nodo

Particionado del rango hash entre los nodos vecinos

Copia de los pares K/V en los nodos correspondientes

Se quita del ambiente de ruteo


DHT Interfaces

Put(Key,Value) Get(Key)

Value

Aplicación Distribuida

Nodo 1 Nodo NNodo 2 . . . .Nodo 3

Distributed Hash Table (CAN, Chord, Pastry, Tapestry, …)

23


DHT Ejemplo - Pastry

Asigna los nodos y objetos a números b-arios de m dígitos.

Asigna cada objeto al nodo con el que comparte el prefijo más

grande.

Por ejemplo:

b = 4 and m = 6

321002

321302

321333


DHT Ejemplo - Pastry Tabla Ruteo (# 65a1fcx)

Fila 0 0x

1x

2 x

3x

4x

5x

7x

8x

9x

ax

bx

cx

dx

ex

f x

Fila 1 6

0x

6

1x

6

2x

6

3x

6

4x

6

6x

6

7x

6

8x

6

9x

6

ax

6

bx

6

cx

6

dx

6

ex

6

fx

Fila 2 6

5

0x

6

5

1x

6

5

2x

6

5

3x

6

5

4x

6

5

5x

6

5

6x

6

5

7x

6

5

8x

6

5

9x

6

5

bx

6

5

cx

6

5

dx

6

5

ex

6

5

fx

Fila 3 6

5

a

0x

6

5

a

2x

6

5

a

3x

6

5

a

4x

6

5

a

5x

6

5

a

6x

6

5

a

7x

6

5

a

8x

6

5

a

9x

6

5

a

ax

6

5

a

bx

6

5

a

cx

6

5

a

dx

6

5

a

ex

6

5

a

fx

log16 Nfilas

24


DHT Ejemplo - Pastry Ruteo

Propiedades• log16 N pasos• O(log N) estado

d46a1c

Route(d46a1c)

d462ba

d4213f

d13da3

65a1fc

d467c4

d471f1


DHT Ejemplo - Chord Tabla Finger

(0)

N32

N60

N79

N70

N113

N102

N40

N52

33..33 N40

34..35 N40

36..39 N40

40..47 N40

48..63 N52

64..95 N70

96..31 N102

Nodo n’s i-ésima entrada: primer nodo n + 2i-1

N32’s

Tabla Finger

N80

N85

N=128

Tabla Finger contiene actualmente

ID y dirección IP

25


DHT Ejemplo - Chord Búsqueda

33..33 N40

34..35 N40

36..39 N40

40..47 N40

48..63 N52

64..95 N70

96..31 N102

N32’s

Tabla Finger

Node 32, búsqueda(82): 32 70 79 85.

71..71 N79

72..73 N79

74..77 N79

78..85 N79

86..101 N102

102..5 N102

6..69 N32

N70’s

Tabla Finger (0)

N32

N60N70

N113

N102

N40

N52

N80

N85

N70

N80

N85

80..80 N80

81..82 N85

83..86 N85

87..94 N102

95..110 N102

111..14 N113

15..78 N32

N79’s

Tabla Finger

N79N79


Resumen de Arquitecturas de la Primera y SegundaGeneración de P2PCliente-Servidor Peer-to-Peer

1. El Servidor es la entidad central y el único proveedor del servicio y contenido. La red es manejadapor el servidor

2. El Servidor es el sistema de más alto rendimieno.

3. El Cliente es el sistemad más bajorendimiento

Ejemplo: WWW

1. Los recursos son compartidos entre peers2. Los recursos pueden ser accedidos directamente desde otros peers 3. Concepto de Servent

P2P sin Estructura P2P Estructurado

P2P Centralizado P2P Puro P2P Híbrido Basado en DHT

1. Todas lascaracterísticas de P2P incluidas

2. Una entidad central esnecesaria para proveerel servicio

3. La entidad central esuna especie de Db índice/grupo

Ejemplo: Napster


2. Alguna entidadterminal puede ser removida sin pérdidade funcionalidad

3. Entidades no central es

Ejemplos: Gnutella 0.4, Freenet



3. Enidades centralesdinámicas

Ejemplo: Gnutella 0.6, JXTA



3. Entidades no central es

4. Las conexiones en overlay son “fijas”

Ejemplos: Chord, CAN

1era Gen. 2da Gen.

26


Aplicaciones Posibles

Soporte para diferentes formas de comunicación.

Telefonía.

Streaming.

Sistemas de nombres escalables y flexibles.

Comunicaciones personales (email, IM).

Recursos compartidos intra organizaciones.

GRID sobre P2P.

Spam sobre P2P.

Construcción de Bases de conocimiento/información entre organizaciones.

Ruteo de contexto/contenido.

Juegos multijugador.


Razones en contra P2P

Leyes contra los usuarios.

Patentes de software.

Propiedad intelectual.

Bajo ancho de banda en los nodos terminales.

Los servicios más esforzados son insuficientes para la mayoría de las aplicaciones.

Administración de los derechos digitales.

Comercialización como principio de P2P.

Falta de confianza.

Ideas P2P integradas en otros tópicos.

27


Blockchain

Artículo para leer: An Overview of Blockchain Technology:

Architecture, Consensus, and Future Trends.

https://www.researchgate.net/publication/318131748


Bibliografía:

- Steinmetz, R y Wehrle, K.; “Peer-to-Peer Systems andApplications”. Springer, 2005.

- Coulouris,G.F.; Dollimore, J. y T. Kindberg; “DistributedSystems: Concepts and Design”. 5th Edition Addison Wesley,2011.

- S. Androutsellis-Theotokis, D. Spinellis; A Survey of Peer-to-Peer Content Distribution Technologies. ACM ComputingSurveys, #4, vol 36, dec 2004.

Sistemas Distribuidos Módulo 4 - Departamento de Ciencias ...

Documents

Transcript of Sistemas Distribuidos Módulo 4 - Departamento de Ciencias ...