Les algorithmes distribués dans un contexte Multicast
Boucif AMAR BENSABER
Définitions
Unicast
Envoie de données d’un émetteur à un utilisateur particulier
Exemples : Courriel, Web
Modèle point à point : Any to One
Multipoint
Un mode de fonctionnement d’un service OSI (Open System Interconnection) qui supporte les échanges entre au moins
deux utilisateurs d‘un service OSI
Modèle Multipoint : Any to Some
Modèle émetteur/récepteur
Multicast
Envoie de données en une seule foisd’un émetteur à plusieurs récepteursde plusieurs émetteurs à plusieurs
récepteurs
Multicast = diffusion restreinte
Broadcast
Envoie des données en une seule fois souvent sans que le récepteur n’en fait la demande.
La diffusion peut créer l’inondation du réseau
Broadcast = diffusion générale
Groupe Multicast
Le concept de groupe permet de définir un ensemble d’entités comme une seule entité virtuelle donnant la possibilité d’appeler tous les membres d’un groupe par un seul nom et
de communiquer avec eux avec une seule adresse.
Modification d’un groupe
Un groupe peut être statique ou dynamique.
IP Multicast gère des groupes dynamiques.Les membres du groupe IP Multicast sont
toujours les machines hôtes et non pas les sites ou les sous-réseaux.
Les applications Multicast et Internet
ApplicationMulticast
UDP TCP
IP Multicast
Liaison de données
Physique
Non fiable
Non fiable
Exigences des applications Multicast
Les applications Multicast n’ont pas toutes les mêmes besoins : pour certaines, la notion de temps est la contrainte principale alors que pour d’autres, la livraison des données doit
être fiable et ordonnée.
De Plus, dans le cas des systèmes multimédia interactifs multi-parties, les multiples flux de
données des différentes conversations doivent être synchronisés.
Intégrité du Groupe-ActifL’AGI spécifie des conditions portant sur la composition du groupe actif.
Les conditions d’AGI doivent être vérifiées pour permettre le transfert de données.
Lorsque l’AGI n’est plus vérifiée, l’association de groupe est soit fermée soit suspendue jusqu’à ce que les conditions soient à nouveau satisfaites.
Les conditions suivantes sont des critères possibles d’AGI: Quorum : nombre minimal de participants devant faire partie du groupe-
actif Maximum : nombre maximal de participants pouvant faire partie du
groupe-actif Membres Clefs : un participant devant obligatoirement faire partie du
groupe-actif pour considérer que l’AGI est vérifiée
Topologie d’une association
Participant
Participant
Participant
Participant
Participant
Conversation à Diffusion Unidirectionnelle
Une conversation ou un unique participant appelé C-participant émet vers tous les autres participants de la conversation.
Un seul participant joue le rôle d’émetteur de données en mode diffusion vers tous les autres récepteurs de la conversation.
Tous les autres participants de la conversation sont uniquement récepteurs des données diffusées.
Maître
Conversation à diffusionunidirectionnelle
Conversation à Diffusion Bidirectionnelle
Une conversation ou un unique participant émet vers tous les autres participants de la conversation qui peuvent lui émettre des données.
Un seul participant de la conversation joue le rôle d’émetteur de données en mode diffusion vers tous les autres participants de la conversation. Ce participant joue également le rôle de récepteur de données.
Tous les autres participants sont récepteurs des données diffusées. Ils sont également émetteurs de données, mais uniquement vers l’émetteur en mode diffusion.
Maître
Conversation à Diffusion Multidirectionnelle
Une conversation où tout participant peut émettre des données vers tous les autres participants de la conversation.Chaque participant peut jouer le rôle d’émetteur en mode diffusion vers tous les autres participants de la conversation.Tous les participants sont récepteurs des données diffusées.
IntroductionLes couches transport et réseau sont responsables de la remise des données aux applications avec la qualité de service requise par celles-ci.Nous analysons les fonctionnalités générales des couches réseau et transport : Notre analyse sera orientée communication de groupe, Nous verrons comment les concepts classiques point à
point peuvent s’étendre aux communications de groupe.
Nous étudierons brièvement les aspects liés à l’ordonnancement, la fiabilité, l’atomicité, le contrôle de flux, le routage, la qualité de service et la sécurité.
Communication de Groupe (1)
But : chaque membre d’un groupe doit recevoir une copie de tous les messages adressés au groupe
Accord : sur l’ensemble des messages reçus et leur ordre
Communication de groupe nécessite :
Coordination
On se restreint aux groupes de processus dont leur appartenance est connue (groupes statiques)
Groupes :
Communication de Groupe (2)
Groupe fermé Groupe ouvert
Système : collection de processus pouvant se communiquer d’une façon fiable sur des liens de communication point-à-point
Processus : membres de groupes, peuvent subir une panne totale
Communication de Groupe (3)
multicast(g, m) : envoie le message m à tous les processus du groupe g
Primitives :
sender(m) : identificateur unique qui désigne l’émetteur du message m
group(m) : identificateur unique du groupe auquel est destiné le message m
deliver(m) : livre le message m au processus(le message n’est pas consommé directement par le processus)
Communication de Groupe de Base
But : Garantir qu’un processus non-défaillant livre le message reçu tant que l’émetteur n’est pas en panne
Primitives : B_multicast, B_deliver Implémentation : Utilisation d’une communication point-à-point
fiable
Pour chaque processus p g, send(p, m);
B_multicast(g, m)
B_deliver(m) à p
receive(m) par p
Pas fiable : des accusés de réception peuvent être supprimés (cas du buffer plein et il y a plusieurs processus)
Communicationde Groupe Fiable
Intégrité : un processus correct P livre le message m au plus une fois
Propriétés à satisfaire :
Validité : si un processus correct diffuse un message m, alors il sera éventuellement livré à sa destination
Accord : Si un processus correct livre le message m, alors tous les autres processus corrects dans group(m) livreront éventuellement m
Primitives : R_multicast, R_deliver
Communication de groupe Ordonnée
Si des sources de sorties multiples demandent en parallèle
des mises à jour, il peut être important que ces mises à jour
soient délivrées dans le même ordre à tous les récepteurs.
Exemple : Mise à jour des copies de données distribuées en
utilisant les communications de groupe. Les délais de
propagation différents et les erreurs de transmission, peuvent
donner des copies incohérentes à un instant donné.
But : Tous les destinataires reçoivent les messages, mais
surtout les traitent dans le même ordre.
Problème d’ordonnancement Multicast
Ordonnancement des messages originaires d’une même source Si les messages m1 et m2 sont envoyés par la même source et s’ils sont
adressés au même groupe multicast, alors les processus de destination vont les recevoir dans l’ordre de leur émission (FIFO).
Ordonnancement des messages originaires de sources multiples Si les messages m1 et m2 sont adressés au même groupe multicast,
alors tous les processus de destination vont les recevoir dans le même ordre (même s’ils arrivent de sources différentes). Cet ordre total peut ou non respecter pour chaque source l’ordre FIFO.
Ordonnancement des messages originaires de plusieurs groupes Si les messages m1 et m2 sont délivrés à 2 processus, ils seront
délivrés dans le même ordre relatif (même s’ils arrivent de groupes différents et même s’ils sont adressés à différents groupes multicast).
Processus 1 Processus 2 Processus 3
Ordonnancement FIFO
Si un processus correct exécute multicast(g, m1), puis multicast(g, m2), alors tout processus correct membre de g qui livre m2 livrera m1 avant m2
m1
m3
m2
Te
mps
Ordonnancement FIFO (2)
Primitives : FO_multicast, FO_deliver
: Nombre de messages envoyés par p au groupe gSgp
Implémentation : Utilisation de numéros de séquence
Variables maintenues par chaque processus p :
: Numéro de séquence du dernier message envoyé au groupe g par q et que p a livréRg
q
Algorithme
Ordonnancement FIFO garantie seulement si les groupes ne se chevauchent pas
Ordonnancement Total (1)
Processus 1 Processus 2 Processus 3
Si un processus correct livre un message m2 avant de livrer un message m1, alors tout autre processus correct qui livre m1 livrera m2 avant m1m1
m2
Te
mps
Primitives : TO_multicast, TO_deliver
Ordonnancement Total (2)
Implémentation : Affecter des identificateurs, totalement ordonnés, aux messages transmis
Chaque processus ordonne les messages en se basant sur ces identificateurs
Méthodes d’affectation de ces identificateurs :
Processus séquenceur
Processus s’accordent collectivement sur les numéros de séquence à affecter aux messages
La fiabilité
La fiabilité concerne le degré de robustesse après l’occurrence d’une panne ou d’un problème durant la communication.
La fiabilité
Un réseau est dit fiable, s’il a les propriétés suivantes :Les messages multicast sont délivrés à chaque
station dans le même ordre, sans duplication, ni perte.
Chaque message multicast est accepté par les stations respectives dans un maximum de temps (fini), après quoi il est effacé dans la station source.
Types de fiabilité
Selon le type et la nature de l’application on peut envisager différents degrés de fiabilité Best effortAbsolueStatistique Clé
Best effortEn cas de perte de données ou d’erreurs Les données ne sont pas délivrées Il n’est pas question de récupérer les erreurs (contraintes
temporelles) et les différents récepteurs acceptent les données telles qu’elles sont
Service de diffusion de la télévision et de la radio
Ce type de service ne nécessite aucun contrôle particulier et peut être mis en œuvre sans difficulté avec un grand groupe.
Fiabilité absolue
Assure que les données perdues ou endommagées sont retransmises jusqu’à ce que l’émetteur ait la certitude que tous les récepteurs les ont reçues correctement.Cette technique est très coûteuse Connaissance totale du groupe Gestion individuelles de chacun (adresse individuelle,…) Délai qui peut s’avérer très long pour certaines
applications
Réservée aux groupes très petits ou il est indispensable que chaque récepteur doit avoir l’intégralité (et l’intégrité) des données.
Fiabilité statistique ou k-fiabilité
Suppose qu’un certain pourcentage seulement de récepteurs doit avoir les données correctes (éventuellement après retransmission) pour que l’émetteur continue la diffusion.
Cette technique approche une fiabilité absolue avec moindre coût.
L’émetteur n’a pas besoin de maintenir l’état individuel de tous les récepteurs.
ExempleQuand un émetteur envoie un message en multicast, il le garde dans une mémoire tampon pendant un certain temps T.
Après cette période, l’émetteur détermine s’il doit retransmettre le message.
Sa décision est basée sur l’analyse de l’état des récepteurs accumulé durant T.
La transmission de données multicast est terminée si une proportion donnée d’utilisateurs a reçu les données correctement.
Fiabilité-clé
Avec la fiabilité statistique, on peut définir des conditions (AGI) sur les participants qui ont correctement reçu les données, par exemple qu’il y ait k’ récepteurs parmi les k récepteurs : on parle de fiabilité-clé. Ces récepteurs clés sont à traiter avec une fiabilité absolue.Lors d’une téléconférence le professeur est un
membre clé, par exemple.
Comparaison des fiabilités
La technique de fiabilité absolue a un effet négatif sur le débit de transmission L’émetteur ne peut envoyer un message que si tous les
récepteurs ont reçu les paquets avec succès, ce qui fait que sa mémoire ne se vide lentement
Le débit se dégrade de plus en plus quand le nombre de récepteurs augmente
La fiabilité statistique s’avère très efficace pour les groupes dynamiques de grandes dimensions.
Contrôle d’erreurs
Traditionnellement 2 approches sont utilisées pour la correction des erreursMécanismes de détection et de correction
d’erreur et de retransmission (Automatic Repeat reQuest)
Informations redondantes émises avec le flot de données (Forward Error Correction)
Politiques d’acquittements 1
Acquittement positifChaque unité de données est explicitement
acquittée par chaque récepteur.L’émetteur retransmet si son acquittement n’est
pas reçu.Si taille du groupe est importante, il est
rapidement submergé par les acquittements des membres du groupe.
Politiques d’acquittements 2
Acquittement négatifSi un récepteur détecte la perte d’une unité
de données, il génère un acquittement négatif.
L’émetteur garde en mémoire tampon pendant une période donnée la liste des unités de données transmises pour être en mesure de les restituer ultérieurement.
Politiques de retransmissions 1
La retransmission peut être à destination d’un récepteur identifié ou du groupe entier.
Unicast : l’émetteur doit avoir connaissance individualisée de chacun des membres du groupe et de leur état. La retransmission Unicast nécessite l’ouverture d’une
nouvelle connexion avec le distant, donc il y a gestion de nouveaux paramètres interne au niveau émetteur et récepteur du message
Politiques de retransmissions 2
Multicast : Ce mode de retransmission peut être utilisé dans le cas où un nombre important de récepteurs a perdu la même unité de données. Traitement supplémentaire au niveau du récepteur
qui n’ont pas besoin de retransmission, mais l’opération est simple au niveau de l’émetteur ou de celui qui retransmet le message.
Politiques de retransmissions 3
Saturation : consiste à anticiper les retransmissions en envoyant plusieurs copies de la même unité de données pour augmenter la probabilité de réception. Elle peut générer un grand nombre de messages
redondants et créer une congestion.
Politiques de retransmissions 4
Les retransmissions multicast peuvent être de type continu ou sélectif Continu (Go-Back-N) : l’émetteur revient à la dernière
unité de données non acquittée à défaut de recevoir un acquittement de tous les récepteurs durant une période donnée. Il retransmet alors toutes les unités de données depuis la dernière non acquittée.
Sélectif : l’émetteur retransmet uniquement l’unité de données erronée.
Comparaison
Les mécanismes de détection d’erreurs et de correction par retransmission sont intégrés par la majorité des protocoles, dans la mesure où:
1. Les codes de détection d’erreurs sont traités plus rapidement et nécessitent moins d’informations redondantes que les codes correcteurs.
2. Face à un taux d’erreurs binaires élevé, les codes auto-correcteurs s’avèrent inefficaces pour un multicast totalement fiable. Par ailleurs, ils gaspillent la bande passante si le réseau offre un taux d’erreurs binaires particulièrement faible.
Les stratégies de retransmission sont inadaptées pour les applications temps réel lorsque l’ont veut une communication fiable.
IP Multicast
Le protocole IP Multicast
C’est une extension du protocole réseau IPIl permet la transmission de datagramme IP à un ensemble d’utilisateurs identifié par une adresse IP de classe D avec la fiabilité best effort. Adresse allant de 224.0.0.0 à 239.255.255.255
Pour échanger les informations entre les machines et les routeurs de groupes, les protocoles de couches supérieures utilisent les messages IGMP (Internet Group Management) qui sont mis dans des datagrammes IP.
Le protocole IGMP
Il est employé par un routeur pour savoir si des membres d’un groupe donné sont présents sur le sous-réseau qui lui est directement relié.
Gestion d’un réseau au niveau IP Multicast
MMM
MM
M
M
M
M
IGMP
IGMP
IGMPProtocolede routageMulticast
Protocolede routageMulticast
Protocolede routageMulticast
Engagement dans le groupe
Pour recevoir des datagrammes destinés à un groupe particulier, une machine doit demander à se joindre au groupe sur une interface réseau donnée, elle utilise la commande :JoinHostGroup (Group address, interface)
…Le module IP maintient une liste de groupes associés à chaque interface, auxquels les applications des niveaux supérieurs appartiennent. Au départ, toutes les entrées de la table sont vides ; à
chaque fois qu’un programme d’application rejoint un groupe, IGMP lui alloue une entrée.
Quand une machine rejoint un groupe, elle diffuse un message IGMP pour signaler aux routeurs Multicast voisins son appartenance au groupe JoinHostGroup (Group address, interface). De son côté, le module IP en utilisant la primitive
JoinLocalGroup(Group address) demande au module réseau local de filtrer les trames Multicast et de délivrer les trames destinées au groupe.
Dialogue IGMP
Ethernet
Compatible IBM Compatible IBM
Compatible IBMCompatible IBM
RouteurInternetInternet
Requête IGMP224.0.0.1
Rapport d’appartenanceau groupe
Connaissance du groupe
Pour savoir quel groupe a encore des membres actifs sur le sous-réseau qui lui est directement relié, un routeur Multicast envoie le message IGMP, HostMemberQuery Dans la version IGMP v.1, ce message
HostMemberQuery était adressé à tous les groupes. Dans la version IGMP v.2, le groupe s’adresse à un
groupe spécifique GroupSpecificQuery avec le drapeau TTL=1.
…À la réception d’un message IGMP émis par un routeur Multicast, les machines appartenant à plusieurs groupes calculent un délai aléatoire pour chaque groupe auquel elle appartiennent (afin de ne pas exploser le routeur local). À l’expiration de ce délai, elles émettent leurs réponses (HostMemberReport) pour chaque groupe auquel elle appartiennent, si aucune machine appartenant au groupe n’a pas déjà répondu. Les routeurs n’ont pas besoin de maintenir une liste détaillée de
toutes les machines des différents groupes, mais seulement savoir qu’il reste au moins une machine par groupe.
…
Le logiciel IGMP gère un compteur par groupe qui enregistre les nombre des membres du groupe. Au fur et à mesure que les applications quittent le groupe, Il décrémente le compteur.
Départ d’un groupe
La machine quitte le groupe lorsque le compteur atteint 0, alors elle transmet un message IGMP v.2 (LeaveGroup) à tous les routeurs Multicast sur le sous-réseau (224.0.0.2 : adresse de tous les routeurs Multicast sur le réseau) en indiquant l’adresse du groupe duquel elle se retire.Pour savoir s’il s’agit du dernier membre appartenant à ce groupe sur ce sous-réseau, le routeur transmet le message (GroupSpecificQuery) sur l’interface d’où il a reçu le message. S’il n’a pas de réponse, alors cette partie (sous-réseau) est enlevé de l’arbre de diffusion (d’acheminement) des messages.
Internet
Dialogue IGMP v.2
Ethernet
Compatible IBM Compatible IBM
Compatible IBMCompatible IBM
RouteurInternet
LeaveGroupto 224.0.0.2
GroupSpecificQueryto groupaddress
Si pas de rapportalors quitter le groupeet couper cette partie de l’arbre
Si réceptiondes rapportsalors resterdans le groupe
IGMP v.3Possibilité d’une machine de spécifier la source du trafic Multicast, donc choix d’un groupe ayant comme source d’information telle machineCe contrôle est réalisé grâce aux messages: Inclusion Group-Source Report Message : permet à une
machine de spécifier les adresses IP des sources d’où elle accepte de recevoir.
Exclusion Group-Source report : permet à une machine d’exclure les sources d’où elle ne veut pas recevoir.
Ça permet de ne pas gaspiller la bande passante.Au départ, le message GroupSourceLeave a été ajouté pour permettre à une station de spécifier les adresses IP de chaque paire (Groupe,Source) qu’elle veut quitter.
import java.net.*;import java.io.*;public class MulticastPeer{ public static void main(String args[]){
// args give message contents and destination multicast group (e.g. "228.5.6.7")MulticastSocket s =null;try {InetAddress group = InetAddress.getByName(args[1]);s = new MulticastSocket(6789);s.joinGroup(group);
byte [] m = args[0].getBytes();DatagramPacket messageOut = new DatagramPacket(m, m.length, group, 6789);s.send(messageOut);byte[] buffer = new byte[1000];
for(int i=0; i< 3;i++) { // get messages from others in group DatagramPacket messageIn = new DatagramPacket(buffer, buffer.length); s.receive(messageIn); System.out.println("Received:" + new String(messageIn.getData())); }
s.leaveGroup(group);}catch (SocketException e){System.out.println("Socket: " + e.getMessage());}catch (IOException e){System.out.println("IO: " + e.getMessage());}finally {if(s != null) s.close();}
} }