Multidifusión

La multidifusión o difusión múltiple (en inglés: multicast) es el envío de la información en múltiples redes a múltiples destinos simultáneamente.

Antes del envío de la información, deben establecerse una serie de parámetros. Para poder recibirla, es necesario establecer lo que se denomina "grupo multicast". Este grupo multicast tiene asociada una dirección de Internet, de esta forma el emisor del mensaje multicast lo envía a uno o varios grupos y, posteriormente, el mensaje llega a los procesos que están suscritos a dicho grupo, pudiendo estar un proceso suscrito a varios a la vez. La versión actual del protocolo de Internet (Internet Protocol o IP), conocida como IPv4, reserva las direcciones de tipo D para la multidifusión. Las direcciones IP tienen 32 bits, y las de tipo D son aquellas en las cuales los 4 bits más significativos son '1110' (224.0.0.0 a 239.255.255.255).

Multidifusión en Internet

Encaminamiento
Única difusión (unicast)
Alguna difusión (anycast)
Amplia difusión (broadcast)
Múltiple difusión (multicast)
Geodifusión (geocast)
v t e

Algunos ejemplos de multidifusión en internet son:

• IEEE 802.1aq - Shortest Path Bridging (SPB)
• IP Multicast
• Internet Relay Chat (IRC)
• NNTP
• PSYC
• Peercasting usando conexiones punto a punto (peer-to-peer).

Cómo funciona

El direccionamiento grupal antes mencionado es una de las propiedades clave de la multidifusión IP, ya que es fundamental para el funcionamiento de este concepto de comunicación. Además, existe la posibilidad de asignar un direccionamiento estático en el que, por ejemplo, se puede configurar una conexión a un servidor multicast para que este ofrezca el servicio correspondiente.

Fiabilidad

Bormann^[1]​ define el concepto de fiabilidad desde el punto de vista del emisor y del receptor del mensaje. Desde el punto de vista del segundo, se considera que el protocolo es fiable si este puede determinar cuándo está fallando. Por otro lado, desde el punto de vista del emisor, se considera que es fiable si se asegura (con suficiente probabilidad) que todos los mensajes llegan dentro de un tiempo límite a todos los receptores no fallidos. Es decir, el término de fiabilidad está ampliamente relacionado con los mecanismos de recuperación y detección de errores.

En cuanto al concepto de fiabilidad en multicast, se puede dar la siguiente definición: El término fiabilidad en multicast corresponde con la entrega finalmente de todos los datos a todos los miembros del grupo, sin cumplir ningún orden de entrega particular.^[2]​

Se distinguen dos tipos de multidifusión dependiendo del método de recuperación de errores que se utilice: sender-initiated o receiver-initiated.^[3]​

Multidifusión básica

En la multidifusión básica consideramos que la comunicación es fiable uno a uno. En este tipo de multidifusión planteamos un protocolo en el que se usa un método de recuperación de errores del tipo sender-initiated, es decir, aquel en el cual es el emisor el responsable de la recuperación del error, consistiendo en que cada receptor envía un acuse de recibo (ACK) al emisor cuando les llega un mensaje del mismo.

Este método es problemático en entornos donde existen varios grupos multicast ya que llegarán al remitente una gran cantidad de ACK, provocando lo que conocemos como implosión de ACK, en la que se produce una saturación del emisor.

En este tipo de multidifusión el mensaje se entrega al menos una vez, por lo que pueden producirse problemas de duplicación. Además, decimos que es fiable uno a uno ya que no cumple con el concepto de acuerdo o atomicidad: si un proceso recibe un mensaje entonces todo el grupo lo recibe; o todos o ninguno.

 

Estructura de la multidifusión básica.

Multidifusión fiable

La multidifusión se utiliza ampliamente para tráfico multimedia, por lo que la pérdida ocasional de paquetes no es un problema. Sumando esto con que la multidifusión IP es muy fiable y con los problemas mencionados en la multidifusión básica, se utiliza frecuentemente multidifusión IP sobre UDP.

En este tipo se usa el segundo método mencionado anteriormente de recuperación de errores, el receiver-initiated, en el que el responsable de la recuperación del error es el receptor. Es decir, no se envían acuses de recibo (ACK) por separado si no que el emisor los manda adjuntos en otros mensajes que envíe al grupo confirmando la recepción de mensajes anteriores, lo que se conoce como piggiebacked (p. ej. el emisor envía un mensaje X a un proceso p y confirma mediante un ACK adjunto que recibió correctamente un mensaje de p anteriormente). Además, los receptores enviarán acuses de recibo negativos (NACK) por separado cuando se detecte la pérdida de algún mensaje.

En este método también se puede producir una implosión, pero de NACK. Para evitarlo, si un determinado número de receptores no recibe el mensaje actual pero recibe el siguiente, entonces estos comienzan un tiempo de espera aleatorio y el NACK se mandará al emisor solamente una vez por el receptor cuyo tiempo aleatorio termine antes. De este modo se consigue minimizar los NACK duplicados. Este tipo de mecanismos son conocidos como RINA (Receiver-Initiated with NACK Avoidance).^[4]​

En la multidifusión fiable, un proceso emisor entrega un mensaje como mucho una vez y sí que se cumple el concepto de acuerdo.

Funcionamiento de la multidifusión fiable

Planteamos un ejemplo con un grupo formado por 3 procesos {p, q, r}.

 

Envío multicast.

Consideraciones previas:

• Cada proceso p mantiene un número de secuencia ${\displaystyle S_{g}^{p}}$  por cada grupo al que pertenece.
• Cada proceso mantiene un vector de n elementos (siendo n el número de procesos del grupo) donde cada elemento corresponde al número de mensajes recibido por un determinado proceso (p. ej. ${\displaystyle R_{p}}$  en el proceso q es el número de mensajes recibidos de p).

En cuanto al envío del mensaje multicast, el proceso emisor manda dicho mensaje al grupo adjuntando el número de secuencia correspondiente y los acuses de recibo necesarios. Además, se aumenta el número de secuencia (${\displaystyle S_{g}^{p}}$  = ${\displaystyle S_{g}^{p}}$  + 1) cuando el mensaje sea entregado por los procesos receptores.

Por otro lado, en cuanto a la recepción, para explicar el concepto se plantea la siguiente situación: recepción en q de un mensaje de p para el grupo g, con un número de secuencia ${\displaystyle S}$  y acuses de recibo <q, ${\displaystyle R}$ > adjuntos. Tenemos tres escenarios:

 

Recepción multicast.

• Si ${\displaystyle S}$  = ${\displaystyle R_{g}^{p}}$  + 1: el proceso q F-entrega el mensaje y aumenta ${\displaystyle R_{g}^{p}}$  (número de mensajes recibidos de p).

• Si ${\displaystyle S}$  ${\displaystyle \leq }$  ${\displaystyle R_{g}^{p}}$ : el mensaje es un duplicado (ya se había recibido con anterioridad) y por lo tanto es descartado.

• Si ${\displaystyle S}$  ${\displaystyle >}$  ${\displaystyle R_{g}^{p}}$  + 1 o ${\displaystyle R}$  ${\displaystyle >}$  ${\displaystyle R_{g}^{p}}$ : el proceso q manda un acuse de recibo negativo (NACK) a p indicando que ha perdido uno o más mensajes.

Como se ve en la imagen de la derecha, el mensaje actual es entregado por q y por r aunque queden mensajes anteriores por llegar, es decir, los mensajes llegan en distinto orden para los diferentes procesos. Este aspecto se soluciona utilizando otro tipo de multidifusión conocida como multidifusión ordenada.

En el caso de que sea el proceso emisor el que ha perdido mensajes, será notificado por el proceso correspondiente con un NACK.

Multidifusión Ordenada

El algoritmo de multidifusión fiable sobre IP-multicast no garantiza que los mensajes lleguen siempre en el mismo orden y esto puede ser un problema para las aplicaciones que requieren un orden.

Los tipos de ordenación más frecuentes son la ordenación total, causal y la ordenación FIFO.

Tipos de ordenación

• Ordenación FIFO: Si un proceso difunde un mensaje m₁ y luego un mensaje m₂, estos se deberán entregar en el orden en el que fueron enviadas por el emisor, es decir, siempre se entregará m₁ antes que m₂.

• Ordenación causal: Si la difusión de un mensaje m₁ ocurre causalmente antes que la difusión de un mensaje m₂, entonces un proceso correcto entregará m₁ antes que m₂.

• Ordenación total: Si dos procesos correctos P_i y P_j entregan dos mensajes m₁ y m₂, entonces P_i entrega m₁ antes que m₂sí y solo sí P_j entrega m₁ antes que m₂.

Implementación de la ordenación FIFO

Una multidifusión con ordenación FIFO tiene dos operaciones: OF-Multicast y OF-Entrega.

Se utilizarán las siguientes variables en el proceso P:

• S_g^p contador de mensajes que el proceso p ha enviado al grupo g
• R_g^q número de secuencia del último mensaje que p ha recibido del proceso q enviado al grupo g

Cuando se realiza la operación OF-multicast de p para el grupo g

• Adjuntar S_g^p en el mensaje
• Realiza B-multicast del mensaje al grupo g
• Incrementa S_g^p en 1 -> S_g^p = S_g^p + 1

Cuando p recibe un mensaje de q:

• Si S = R_g^q+1 → se comprueba que es el mensaje esperado y p usa OF-entrega fijando R_g^q = S

• Si S > R_g^q+1 → retención del mensaje hasta que los mensajes intermedios hayan sido entregados y se cumpla S = R_g^q+1^[5]​

Implementación de la ordenación causal

Este algoritmo tiene en cuenta la relación “sucedió antes que" y se emplean las operaciones de ordenamiento causal: OC-multicast y OC-entrega, cada proceso p_i tiene su propio vector de marcas temporales.

 

Multidifusión ordenada causal

Variables en el proceso p

V_p^g vector con el no de mensajes recibidos de cada proceso

Para enviar un mensaje mediante OC-multicast al grupo g, el proceso suma 1 a su entrada en el vector de marcas temporales y envía el mensaje mediante B-multicast a g junto con su marca de tiempo.

Cuando un proceso pi B-entrega un mensaje p_j, tiene que colocarlo en la cola de retención antes de realizar la OC-entrega: primero debe asegurarse de haber entregado todos los mensajes que sucedieron antes, esto se comprueba de las siguientes maneras:

• P_j espera hasta que haya entregado todo mensaje enviado por parte de p_j

• P_i espera a que cualquier mensaje que p_j hubiese entregado hasta el instante de tiempo en el que envió el mensaje.

Implementación de la ordenación total

La manera básica de implementar la ordenación total es asignar identificadores totalmente ordenados a los mensajes que se multidifunden de tal forma que todo proceso realice la misma ordenación basada en esos identificadores.

Existen dos métodos para asignar identificadores a los mensajes:

• Secuenciador

El proceso elegido como secuenciador es el encargado de ordenar los mensajes.

Cuando un proceso desea enviar un mensaje m con OT-multicast este se envía al secuenciador.

El secuenciador le asigna un número de secuencia de forma creciente y consecutiva a los mensajes que B-entrega y lo envía a todos los procesos del grupo.

El secuenciador anuncia la secuencia de números mediante B-multicast al grupo g de mensajes con el ordenamiento.

Un mensaje permanecerá retenido en la cola indefinidamente hasta que pueda efectuarse OT-entrega de acuerdo con el correspondiente número de secuencia.

 

Multidifusión ordenada total ISIS

• Implementación total por acuerdo (ISIS)

Fue originariamente desarrollado para la herramientas ISIS (la empresa que comercializaba esta herramienta ya no existe, pero ISIS operó en la bolsa de valores de NY y sigue usándose en el sistema de control de tráfico aéreo francés o en el navío de guerra americano AEGIS[1]. Actualmente, ISIS ha evolucionado hacia una nueva versión más centrada en replicación llamada VSync[2]). Teniendo n procesos, las variables para el proceso qson:

A_g^q: mayor número de secuencia acordado para el grupo g del proceso q

P_g^q: mayor número de secuencia propuesto para el grupo g del proceso q

Implementación

 

Emisión de varios mensajes a la vez a varios procesos

 

Acuerdo entre los mensajes de una multidifusión

 

Envio final en multidifusión ordenada

A la hora de implementar este acuerdo tenemos tres partes (teniendo n procesos):

1. El proceso p realizará un mensaje (m) y lo multidifundirá, es decir: p hace B-multicast<m,i> a g (i identificador único de m)
2. Cada proceso q responde a p con una propuesta P_g^q =máx(A_g^q, P_g^q )+1
   1. Se asigna al mensaje m el no de secuencia Pgq de modo provisional
   2. Se coloca y ordena en la cola de retención según ese no provisional
3. El proceso p decide entre todas las propuestas recibidas el número de secuencia definitivo y lo envía a todos los procesos otra vez, es decir: p recoge todos los números de secuencia propuestos y selecciona el mayor (a) como acuerdo, realizando B-multicast<a,i> a g (siendo "a" el orden acordado)
   1. Cada proceso fija A_g^q = máx(A_g^q, a) y se lo asigna al mensaje i
   2. Reordena la cola si difiere al propuesto
   3. Cuando el mensaje al inicio de la cola tenga no acordado, se entrega

Ejemplo práctico

1. Tenemos 4 procesos, de los cuales P1 y P4 crearán un mensaje y realizarán la multidifusión.
2. Una vez enviado el mensaje, irán recibiendo las propuestas de llegada a cada proceso (el valor del primero al que llega es menor que al último que le llega). Las recogemos en dos grupos, diferenciándolos por el proceso que envió el mensaje.
3. Una vez escogido el número de secuencia se manda a todos los procesos, se reordena el buzón y se procede a realizar el envío del mensaje.
   1. Si el acuerdo que llega a un proceso tiene un valor mayor a los guardados en el buzón, esperaremos a que lleguen los demás acuerdos para ir sacando del buzón y enviado el mensaje del menor al mayor número de secuencia.
   2. Si el acuerdo que llega a un proceso tiene un valor menor que los guardados en el buzón, podemos enviar directamente este mensaje sin necesidad de esperar.

En qué escenario resulta útil

● Si se busca un desempeño optimizado de la red.

● Cuando se desea soporte para aplicaciones distribuidas.

● En caso de querer economizar en recursos.

● Si se quiere hallar facilidad de crecimiento en escala.

Referencias

1. Bormann, C.; Ott, J.; Gehrcke, H.; Seifert, N. (1994). «MTP-2: Towards Achieving the S.E.R.O. Properties for Multicast Transport». Proceedings of ICCCN. 
2. Floyd, S.; Jacobson, V.; Liu, C. -G.; McCanne, S.; Zhang, L. (December 1997). «A reliable multicast framework for light-weight sessions and application level framing». IEEE/ACM Transactions on Networking 5 (6): 784-803. doi:10.1109/90.650139. 
3. Brandt, Joseph J. (26 de mayo de 1998). «Reliable multicast protocols and their application on the Green Bank Telescope». Proc. SPIE 3351, Telescope Control Systems III. 
4. Kostin, A.; Ilushechkina, L. (June 2010). Modeling and Simulation of Distributed Systems. 
5. Coulouris, George F. (2012). Distributed systems : concepts and design. Addison-Wesley / Pearson Education Ltd. ISBN 978-1-4479-3017-4. OCLC 899731054. Consultado el 27 de junio de 2020. 

Bibliografía

• Rodrigo Santamaría. Apuntes Sistemas Distribuidos Universidad de Salamanca. | Tema 5 - Coordinación y acuerdo^[1]​

Enlaces externos

• Sistemas Distribuidos - Coordinación y Acuerdo
• Alberto Lafuente, Mikel Larrea. UPV- EHU Comunicación a grupos

•   Datos: Q899288

1. «Rodrigo Santamaría. Apuntes Sistemas Distribuidos Universidad de Salamanca. | Tema 5 - Coordinación y acuerdo».