Solució de la PAC3 PDF

Preview

Summary

Warning: TT: undefined function: 32Sistemas DistribuidosPEC 31. Ejercicio 1Enunciado: Explain what temporal and spatial coupling mean. Compare time and space coupling/uncoupling in MPI, JMS, IP Multicast, Whatsapp and mailbox.Solución:En el contexto de sistemas distribuidos, se habla de comunicación...

Description

Sistemas Distribuidos

PEC3

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

1. Ejercicio 1 Enunciado: Explain what temporal and spatial coupling mean. Compare time and space coupling/uncoupling in MPI, JMS, IP Multicast, Whatsapp and mailbox. Solución: En el contexto de sistemas distribuidos, se habla de comunicación directa cuando emisor y receptor intercambian mensajes directamente sin ningún intermediario, siendo necesario que los dos estén acoplados tanto temporal (los dos procesos deben existir y estar activos en un mismo espacio de tiempo) como espacialmente (el emisor debe conocer la identidad del receptor para poder comunicarse). En el mismo contexto, se habla de comunicación indirecta como la que se da entre entidades a través de un intermediario entre emisor y receptor, lo que permite que pueda haber un desacoplamiento temporal (cuando emisor y receptor no están activos o no existan simultáneamente) y/o espacial (cuando emisor y receptor desconozcan o no necesiten conocer sus identidades) entre ellos. La siguiente tabla recoge los cuatro diferentes acoplamientos/desacoplamientos temporal/espacial:

Acopla lamien miento tempo poral Acop la mien to tem po ral Acopla lamien miento espacia aciall Acop la mien to esp acia

Desaco acoplam plamie iento tempo poral Des aco plam ie nto tem po ral

Comunicación dirigida hacia Comunicación dirigida hacia un

receptor

o

receptores un

receptor

dados. Los receptores deben dados. existir en ese momento.

Desaco acoplam plamien iento espacia aciall Des aco plam ien to esp acia

o

Emisor

receptores y

receptor

pueden no existir a la vez.

Los emisores no necesitan Los emisores no necesitan conocer

la

identidad

del conocer

la

identidad

del

receptor o receptores. Emisor receptor o receptores. Emisor y receptor deben existir a la y receptor pueden no existir a la vez.

vez.

Con respecto a los sistemas de comunicación objeto de la comparativa, MPI (Message Passing Interface) es un estándar de interfaz de paso de mensajes. El proceso que envía, el que recibe y el mensaje, son los principales elementos que intervienen en el paso de mensajes.

1

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

Es un modelo de comunicación directa (no existen intermediarios en la comunicación) y el paso de mensajes se realiza de forma síncrona o asíncrona. Cuando se envía el mensaje este se almacena en una cola de mensajes en el equipo local que ha recibido el mensaje y de ahí ira recuperando los mensajes para irlos procesando. Cuando se realiza de forma síncrona se bloquearían los dos procesos tanto el que envía el mensaje como el que recibe el mensaje. De forma asíncrona el proceso que envía los mensajes puede seguir enviando mensajes tan pronto como se haya copiado el mensaje al buffer local y la transmisión de los mensajes se realiza en paralelo con el envío de mensajes. En todos los casos, existe acoplamiento temporal y espacial. En contraposición, JMS (Java Mesage Service) es una especificación para estandarizar la comunicación indirecta entre programas java en un entorno distribuido que utiliza dos modelos, el modelo de publicación y subscripción y el modelo de cola de mensajes. Es un modelo de comunicación indirecta entre el proceso productor de mensajes y el proceso consumidor de mensajes. En una comunicación JMS los productores envían los mensajes a un servidor JMS, en el cual se encolan los mensajes en una cola FIFO que actúa como buffer externo para los procesos. Y a continuación, a partir de la cola de mensajes son enviados a consumidores JMS. Está desacoplado espacialmente (no es necesario que el productor JMS conozca la localización del consumidor JMS) y desacoplado temporalmente (el mensaje estará almacenado en el buffer del servidor JMS hasta que el consumidor JMS pueda recibirlo no siendo necesario que los dos procesos estén activos al mismo tiempo). Multidifusión IP (IP multicast) es un sistema para transmitir datagramas IP a un grupo de receptores interesados. Cuando el emisor quiere enviar un mensaje, envía un único datagrama (desde la dirección unicast del emisor) a la dirección multidifusión (una dirección multidifusión está asociada con un grupo de receptores interesados). Los mensajes enviados por IP multicast a un determinado grupo serán entregados a todos los miembros del grupo que se encuentren disponibles en el momento de la entrega. Por lo tanto, hay desacoplamiento espacial pero no temporal (los receptores deben estar existir en el momento en que se envía la multidifusión o se perderá). Whatsapp es un sistema de mensajería instantánea, donde un emisor envía mensajes a uno o varios receptores. Dichos mensajes se reciben y procesan en los servidores intermedios proveedores del servicio, que los reenvían al receptor en un formato ligero basado en XMPP y lo reciben en su terminal. Es, por tanto, un tipo de comunicación 2

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

indirecta que puede ser síncrona (intercambio de mensajes en tiempo real y llamadas de voz) o asíncrona (es habitual utilizarlo para enviar mensajes al destinatario sin que éste este online ni esperar respuesta inmediata). Existe por tanto un desacoplamiento temporal (el mensaje se almacena en una base de datos Mnesia mientras el receptor no puede recibirlo), y existe un acoplamiento espacial ya que el emisor debe conocer la identidad del receptor. Buzón de correo (mailbox) hace referencia a aquellos sistemas de almacenamiento de correo electrónico que se intercambian entre usuarios. Los mensajes intercambiados se envían/reciben por los servidores smtp y se mantienen mientras los clientes de correo no accedan a sus buzones. El acceso de los clientes a dichos buzones se puede realizar por diferentes protocolos (POP, IMAP, ActiveSync,…) y no es necesario que estén activos en el momento del intercambio del mensaje, existiendo por tanto desacoplamiento temporal, si bien sí existe acoplamiento espacial, ya que el emisor conoce de antemano la identidad del receptor para poder enviar el mensaje.

3

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

2. Ejercicio 2 Enunciado: Explain the differences between the four models of indirect communication: group communication, publish/subscribe, message queues and shared memory systems. Give real examples of each model. Solución: En el contexto de los sistemas distribuidos, la comunicación indirecta se define como la comunicación entre entidades a través de un intermediario sin acoplamiento directo entre emisor y receptor. Ejemplos específicos de la comunicación indirecta son la comunicación grupal (group communication), los sistemas de publicación-suscripción (publish/subscribe), colas de mensajes (message queues) y los enfoques basados en abstracciones de memoria compartida (shared memory systems). Group communication: Este tipo de modelo de comunicación indirecta envía un mensaje a un grupo de usuarios que es entregado sin conocer ni esperar la identidad del grupo de usuarios. Envía los mensajes multicast a todos los miembros del grupo de comunicación. Estos grupos tienes las siguientes características: Un sistema de difusión de Información confiable para que lleguen los mensajes a un gran número de clientes. Soportan aplicaciones de colaboración, como pueden ser los juegos dónde los eventos nuevos deben ser difundidos a todos los usuarios, dando una vista común a todos ellos. Tolerancia a fallos, en la que también se actualice de manera constante todos los datos replicados. Apoyo a sistemas de gestión para poder supervisar el sistema. Por ejemplo, sistemas de gestión que ayuden a balancear la carga. Se pueden distinguir grupos de comunicación abiertos (aquellos que pueden recibir mensajes desde otros sitios de fuera del grupo) y cerrados (no pueden recibir mensajes de otros miembros que no sean del grupo). Como ejemplos de este sistema podemos citar los sistemas de streaming de video, IRC (Internet Relay Chat) o los JGroups, un conjunto de herramientas para comunicación grupal confiable escrita en Java. Publish/subscribe: Este modelo está basado en un sistema de publicación de eventos al que están subscritos determinados equipos. Cuando se realiza la subscripción al 4

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

publicador, estos equipos comunican cuales son los eventos a los que ellos quieren subscribirse en particular. Cuando el publicador publica un nuevo evento, este envía una notificación a los equipos que están subscritos a ese evento. Así pues, los equipos que están subscritos reciben la notificación y actualizan los datos que tienen del evento que se acaba de publicar. Un publicador no necesita saber quién utiliza la publicación que proporciona, y un subscriptor no necesita saber quién proporciona la información que recibe como resultado de una subscripción (desacoplamiento espacial). Por otro lado, no es necesario que trabajen en la misma línea de tiempo (desacoplamiento temporal). Tiene las siguientes características: Es heterogéneo, ya que permite la comunicación de componentes que no fueron diseñados para comunicarse entre sí. Es asíncrono, se envían las notificaciones a todos los suscriptores que han mostrado interés sin necesidad de una respuesta sincronizada en el subscriptor. Puede ser utilizado en arquitecturas centralizadas y distribuidas. En el primero habrá un publicador que será el encargado de realizar la notificación al resto de subscriptores (puede contribuir a formar cuellos de botella y es poco tolerante a fallos). En el segundo utilizamos sistemas peer-to-peer dónde un mismo equipo puede realizar las tareas de publicador y de subscripción (solventará que se formen cuellos de botella y mejorará la tolerancia a fallos). Como ejemplos de este tipo podemos ver los sistemas de subscripción RSS, Amazon Simple Notification Service (SNS), algunos sistemas de actualización de software, o la difusión de eventos relacionados con anuncios publicitarios. Message queues: Es un modelo de comunicación indirecta uno a uno, punto a punto, a diferencia de los anteriores que eran uno a muchos. Este modelo utiliza las colas de mensaje como forma indirecta de envío de mensajes. El emisor envía mensajes a la cola de mensajes donde se quedan a la espera, hasta que son recogidos por los procesos receptores (desacoplamiento temporal) y a continuación eliminados de la cola. Los mensajes son persistentes, es decir, la cola de mensajes almacena mensajes hasta que son consumidos. Las colas de mensaje garantizan que los mensajes sean enviados y además que sean enviados una única vez, pero no pueden garantizar el tiempo del envío. No es necesario conocer la localización de los receptores (desacoplamiento espacial). La mayoría de los sistemas que utilizan la cola de mensajes como modelo de comunicación utilizan el orden FIFO para ordenar la entrada y salida de mensajes, no 5

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

obstante, se pueden utilizar otros sistemas de ordenación que corresponda mejor con lógica de la aplicación. Algunos ejemplos pueden ser IBM WebSphere MQ (un middleware de mensajería que simplifica y agiliza la integración de diversas aplicaciones y datos de negocio en varias plataformas), JMS (Java Messaging Service) o Amazon Simple Queue Service (SQS). Shared memory systems: utiliza los espacios de memoria de sistemas distribuidos virtuales para poder comunicarse con el resto de los equipos que no comparten la misma memoria física. Utilizando los espacios de memoria compartidos para que los programas o los programadores puedan tener accesos de lectura o escritura a espacios de memoria compartidos. Los espacios de memoria se dividen en tuplas, en filas en los cuales cada proceso puede leer o escribir dependiendo del caso. Las propiedades generales que poseen las tuplas, es que tienen un espacio desacoplado y que el tiempo también esta desacoplado, por lo tanto, una tupla puede tener varios procesos que están enviando datos y varios procesos que están recibiendo esta información. La tupla permanecerá en ese espacio hasta que sea eliminada por lo que tanto el receptor como el emisor no tendrán problemas por solaparse en el tiempo. Un ejemplo que se puede encontrar es JavaSpaces, que es un DSM basado en espacios de tuplas para simplificar el desarrollo de aplicaciones en ambientes distribuidos.

6

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

3. Ejercicio 3 Enunciado: Briefly describe the components of the BitTorrent architecture and argue which of them may limit the scalability. How does BitTorrent incentive the cooperation? Solución: BitTorrent es un protocolo diseñado para el intercambio de archivos punto a punto (P2P, peer-to-peer) en Internet, siendo uno de los protocolos más comunes para la transferencia de archivos grandes por haber demostrado ser efectivo, escalable y robusto. En este modelo, la red peer-to-peer combina el recurso entre todos y hacia todos los peers, a diferencia del modelo cliente-servidor tradicional. Las interacciones ocurren principalmente entre los peers y, ocasionalmente, con un servidor para localizar nuevos peers. En lugar de descargar el archivo de una sola fuente, el protocolo BitTorrent organiza a sus peers (que funcionarán como clientes y/o servidores) en una red “Torrent” para descargar y subir el mismo archivo, trozo a trozo (chunks) de forma simultánea. Cuando un nuevo fichero se comparte en BitTorrent el sistema crea un fichero .torrent que contiene, entre otros el nombre y longitud del fichero, la localización del tracker y un checksum asociado con cada trozo del fichero (chunk). Con tracker nos estamos refiriendo estrictamente a un servidor, aunque no de ficheros, que se encarga de conocer a un subconjunto de los peers que están compartiendo un recurso (fichero o conjuntos de ficheros). El tracker sirve de nodo de acceso inicial a la red de compartición y gestiona las descargas. El tracker se encarga de buscar los usuarios, que conforma el swarm (enjambre). Cuando ya ha terminado de descargarse el recurso o cuando él es la fuente inicial de recurso, el peer suele llamarse seed (semilla) y siempre tiene una copia completa del recurso. En cambio, suele denotarse como leecher a un peer que contiene sólo algunas partes del fichero, generalmente porque lo están descargando en ese momento. La siguiente imagen ilustra las cinco tareas básicas de un proceso de compartición de ficheros con BitTorrent:

7

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

1. Para descargar un archivo, el peer A primero descarga el archivo .torrent correspondiente, desde un servidor web. 2. A continuación, el peer A contacta al tracker para obtener una lista de los peers activos que participan en el Torrent. 3. El tracker devuelve una lista de peers que están involucrados en el torrent. 4. Después, el peer A agrega a todos los peers conectados de la lista como sus vecinos, y envía el archivo solicitud de piezas entre sí. 5. Finalmente, una vez que se acepta la solicitud, el peer A puede intercambiar el archivo con los vecinos. En cuanto a la escalabilidad, BitTorrent es un sistema P2P con buena escalabilidad, debido a que la demanda de cada peer es independiente del número de peers vecinos. Nada está centralizado, por lo que el sistema puede expandirse indefinidamente sin ningún otro recurso que no sean los propios pares. El rendimiento será mayor cuanto mayor sea el número de peers. La literatura define establece varios modelos analíticos que miden el rendimiento de la red BitTorrent en base a diferentes parámetros. Algunos de estos modelos, mantienen estados en una cadena para los peers de forma que cuantos más peers se unen a la red, más estados habría que mantener en la cadena y limitaría la escalabilidad. Otras limitaciones de BitTorrent es que es relativamente vulnerable a ataques, bien de denegación de servicio, de ataque a seeds o de “subida corrupta”. Además, es poco eficiente en transferencias de archivos pequeños. Otro punto débil es el tracker, siendo un cuello de botella que consume el 1 por mil del tráfico total de la red. En cuanto a incentivar la colaboración, BitTorrent incorpora mecanismos de selección de peers que consiguen mejorar la experiencia de los peers que contribuyen al sistema y 8

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

penaliza a los usuarios libres, que sólo descargan de otros peers, pero nunca suben. Mecanismos como tit-for-tat (TFT, “yo te doy, si tú me das), refuerzan el intercambio justo y determina la preferencia por los peers de los que también recibimos datos. Ahora bien, debe aplicarse de forma controlada por mecanismos de desbloqueo de conflictos, que solucionen problemas como que nuevos participantes que aun no comparten datos, no sean penalizados (mecanismo “optimistic unchoking”), mediante el cual el cliente se reserva determinada fracción de su ancho de banda y la asigna a participantes al azar, con la esperanza de poder identificar buenos vecinos y haciendo también posible que los nuevos llegados se ganen un lugar en la red BitTorrent.

9

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

4. Ejercicio 4 Enunciado: Give the routing tables of a Chord overlay with nodes N1, N8, N12, N14, N50, N52. Describe the process of looking up for key 51 from N1. What is the complexity of a lookup? What happens when the nodes are not uniformly distributed? Solución: Chord es una Tabla Hash Distribuida utilizada para la implementación de redes peer-topeer estructuradas. Chord especifica la información que cada nodo de la red debe almacenar, referente a otros nodos, así como, la información referente a los ficheros que es compartida entre nodos. Además, regula la comunicación y el intercambio de mensajes entre estos. En este ejercicio, para no exceder demasiado el contenido máximo, se omite la explicación teórica de la asignación de claves a nodos y se ciñe sólo al caso práctico de las tablas de rutas para los nodos dados, que serían las siguientes: Para el nodo N1:

Índice Cálculo búsque queda Índi ce Cálc ulo bús que da

Nodo ucesor No do ssuce uce sor

1

1 + 20 = 2

N8

2

1 + 21 = 3

N8

3

1 + 22 = 5

N8

4

1 + 23 = 9

N12

5

1 + 2 4 = 17

N50

6

1 + 2 5 = 33

N50

Para el nodo N8:

Índice Cálculo búsque queda Índi ce Cálc ulo bús que da

Nodo ucesor No do ssuce uce sor

1

8 + 20 = 9

N12

2

8 + 2 1 = 10

N12

3

8 + 2 2 = 12

N12

4

8 + 2 3 = 16

N50

5

8 + 2 4 = 24

N50

6

8 + 2 5 = 40

N50

10

75.589 – Sistemas Distribuidos – PEC3 – 2018-19-Sem. 2

Para el nodo N12:

Índice Cálculo búsque queda Índi ce Cálc ulo bús que da

Nodo ucesor No do ssuce uce sor

1

12 + 20 = 13

N14

2

12 + 21 = 14

N14

3

12 + 22 = 16

N50

4

12 + 23 = 20

N50

5

12 + 24 = 28

N50

6

12 + 25 = 44

N50

Para el nodo N14:

Índice Cálculo búsque queda Índi ce Cálc ulo bús que da

Nodo ucesor No do ssuce uce sor

1

14 + 20 = 15

N50

2

14+ 2 1 = 16

N50

3

14 + 22 = 18

N50

...