Multicast - Algorithme gossip ou épidémique

Le multicast est l'une des briques des systèmes distribués. Cet article tente d'apporter une réponse à cette problématique et entre dans le cadre de sa spécialisation Cloud Computing sur coursera.

Dans un premier temps nous analyserons ce qu'est le multicast en en proposant des résolutions simple. Dans un second temps, nous étudieront les algorithmes épidémiques ou gossip pour proposer une solution plus élégante.

reseaumonde

Multicast

Le multicast consiste à envoyer un message à un sous-ensemble de nœuds. Une telle fonctionnalité se doit

  • d'être résistent aux fautes
  • de pouvoir passer à l'échelle

Une implémentation simple de cet algorithme serait de parcourir l'ensemble des nœuds destinataires et leur envoyer le message. Cette approche souffre de plusieurs lacunes :

  • Si le nœud émetteur s'arrête au milieu de sa boucle d'envoi, seulement la moitié des destinataires auront une chance de recevoir le message
  • Si le nombre de destinataires est très grand, ce sera très long d'envoyer tous les messages.

Pour palier à ces soucis, il est possible de structurer les nœuds sous forme d'arbre équilibré, avec pour racine le nœud émetteur. L'émetteur envoie le message à ses fils qui transmettent à leur tour à leurs fils. Cette approche souffre de nouveau d'un problème de tolérance aux fautes : tous les nœuds qui descendent d'un nœud qui crash ne recevront pas le message.

Il existe des algorithmes qui réparent un arbre brisé par l'utilisation de ACKs (acquittement à la réception d'un message) ou de NACKs (envoi d'un acquittement si aucun message n'est reçu sur une longue période de temps). Cela peut par contre conduire à une inondation d'ACK ou de NACK.

Algorithme Gossip ou épidémique

Pour palier à ce problème d'explosion de messages d'acquittement, il est possible d'utiliser des algorithmes épidémiques ou gossip.

Le principe du gossip est d'envoyer à intervalle régulière un message gossip vers un nombre (en général 2) de nœuds aléatoires.

A la réception d'un message gossip, chaque nœud continue à transmettre à plusieurs nœuds aléatoires.

L'overhead d'un tel algorithme n'est pas très important. A terme, tous les nœuds sont infectés par le message gossip.

On distingue ensuite plusieurs approche pour transmettre l'information :

  • en Push où les messages gossip contiennent les messages à multicaster (ou un sous ensemble aléatoire de ces messages)
  • en Pull où les messages gossip servent à demander une mise à jour des message multicastés. Le nœud renvoie alors les informations demandées.
  • en Push-Pull ou cette approche hybride demande des mise à jour tout en transmettant les informations à diffuser.

L'analyse de cet algorithme se basent sur les travaux fait en épidémiologie (Bailey, 1975). On en déduit :

  • une faible latence
  • tous les nœuds reçoivent à terme le message
  • algorithme très léger : chaque nœud n'envoie que peu de messages
  • En cas de perte de message ou de crash d'un nœud, le système global n'est pas affecté
  • La version en pull est plus rapide.

Selon la typologie réseau, les routeurs peuvent se retrouver submergés par les messages. Pour réduire ce problème, il est possible de réduire le soucis en réduisant la probabilité d'envoyer des messages vers un autre réseau.

Il existe plusieurs implémentation d'algorithmes gossip sur le marché :

  • Les transaction email ou de base de données
  • refDBMS
  • Amazon EC2 et S3
  • Membership dans Cassandra
  • NNTP (protocole de news)

Post a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*