TP Réseau : Routage en diffusion sur Internet Exercice Réseau Routage en Diffusion

Routage en diffusion sur Internet

 

Dans ce problème on étudie la diffusion sur groupe (multicast) dans l’Internet. La figure suivante représente
un site émetteur (une source de messages S) et des sites destinataires (D1, D2, D3, D4). 

On a représenté le réseau avec des hôtes, des routeurs, des liens qui sont utilisés dans une diffusion sur groupes (traits gras) et d’autres liens et routeurs inutilisés.

1) Le principe fondamental d’un routage en diffusion sur groupe consiste à construire un arbre couvrant à coût minimum enraciné au site source et dont les feuilles sont les sites destinataires. Sur l’arbre, pour diffuser aux destinataires, on ne transmet qu’une copie du message par liaison utilisée. On cherche à comparer la solution en point à point à la solution en diffusion sur une arbre, en utilisant la métrique Internet du nombre de sauts.

1.1) Pour le réseau de la figure précédente, si l’on réalise quatre communications en point à point pour al ler de S aux quatre destinataires combien de sauts doit-on effectuer ?

1.2) Si l’on utilise l’arbre couvrant en diffusion, combien de saut doit-on effectuer ? 

1.3) Supposons qu’un routage en diffusion utilise un arbre binaire pour atteindre 2**N destinataires, combien de sauts doit-on effectuer en mode point à point ?

1.4) Sur un arbre binaire permettant d’atteindre 2**N destinataires, combien de sauts doit-on effectuer en mode diffusion sur l’arbre ? 

1.5) Que conclure quant aux performances relatives des deux solutions ? 


2) Adresses IP de diffusion.

2.1) L’adressage IPV4 utilise dans sa version de base différentes classes d'adresses. Quelle est le nom de la classe qui est prévue pour la diffusion à des groupes de destinataires (le multicast Quelles sont les adresses utilisables pour définir des groupes de diffusion? 


2.2) De combien d’adresses différentes peut-on ainsi disposer pour adresser des groupes en Ipv4?

 2.3) Les adresses multicast IP peuvent servir à délivrer des messages en diffusion au moyen de réseaux locaux type Ethernet. Ethernet dispose également d'un adressage multicast.

Pour établir automatiquement une correspondance entre adresse IP multicast et adresses Ethernet multicast une technique normalisée consiste à copier 23 bits de poids faible de l'adresse IP multicast pour fabriquer 23 bits de l'adresse multicast Ethernet qui lui correspond. Sur le schéma suivant on représente une adresse Ethernet multicast avec le préfixe constant caractéristique de la conversion IP multicast vers Ethernet multicast et un bit à 0 qui ramène à 23 le nombre de bits significatifs dans les 24 bits de la partie droite.

Cette présentation correspond au codage des adresses Ethernet lorsqu’elles circulent sur les fils (le bit 0 est envoyé en premier en codage grand boutiste). Pourquoi le premier bit est-il obligatoirement à 1 ? 

2.4) La représentation officielle des adresses Ethernet est telle que les 6 octets sont numérotés de la gauche vers la droite (grand boutiste) mais les bits à l’intérieur des octets sont numérotés de la droite vers la gauche (petit boutiste). Lorsque l’on édite une adresse Ethernet, dans la représentation officielle (dite en mémoire), les adresses multicast Ethernet sont donc notées en inversant l’ordre des bits dans les octets. L’adresse Ethernet multicast avec le préfixe constant caractéristique de la conversion IP multicast vers Ethernet multicast devient donc : 

  Le domaine d’adressage est donc défini dans les normes par l’intervalle  01:00:5e:00:00:00 à 01:00:5e:7f:ff:ff 

  Soient les adresses multicast IP 224.144.8.5 et 225.144.8.5 (en hexadécimal e0.90.08.05 et e1.90.08.05). Donner les adresses multicast Ethernet correspondantes sachant que l’on recopie purement  et simplement les 23 bits de la partie droite de l’adresse IP multicast dans l’adresse Ethernet multicast (pour répondre, en cas de doute on  peut éventuellement représenter sous forme binaire les adresses) ? Comment résoudre le problème posé par l'utilisation simultanée de ces deux adresses dans le même réseau.


3) Gestion des abonnements

3.1) Quel est le protocole de la suite Internet qui prend en charge la gestion des groupes en IP V4?

3.2) Quelles sont ses principales fonctions?

4) Routage en diffusion. 

4.1) Le problème du routage en diffusion consiste à atteindre à partir d'une source un groupe de destinataires. L'un des protocoles de routage en diffusion sur l'internet s'appelle DVMRP ("Distance Vector Multicast Routing Protocol"). Le protocole DVMRP est donc un routage à vecteur de distance qui utilise un principe voisin du protocole RIP ("Routing Information Protocol"). Rappelez les principes des protocoles à vecteur de distance pour entretenir une table des chemins à coût minimum dans un réseau?

4.2) En DVMRP, pour construire l'arbre de diffusion, périodiquement un routeur source (un routeur de rattachement d'un hôte source) émet vers ses routeurs voisins un message indiquant qu'il a un flot de messages en diffusion à transmettre. Les différents routeurs atteints réémettent à leur tour ce message vers leurs voisins. Comment appelle t'on une telle stratégie de circulation des messages d'indication de flot ?

4.3) En fait chaque routeur du réseau n'accepte un message d'indication de flot de diffusion et ne le réémet vers ses voisins que s'il provient du routeur voisin qui se trouve sur le chemin à coût minimum vers la source. Les messages provenant des autres voisins sont ignorés. Pourquoi est-ce que cette stratégie évite l'explosion combinatoire du nombre des messages? 

Pour construire l'arbre couvrant à coût minimum, DVMRP fonctionne en deux phases. Dans la première phase, DVMRP construit un arbre couvrant à coût minimum du routeur source vers tous les routeurs ("minimum spanning tree"). 
  Dans la seconde phase DVMRP procède à l'élagage de l'arbre couvrant. Lorsqu'un routeur est une feuille de l'arbre couvrant (il ne relaie pas de messages vers un autre routeur) et qu'il n'est pas destinataire (il n'y a pas d'abonné connecté à ce routeur à qui les messages d'un flot de diffusion doivent être délivrés) alors ce routeur n'a pas à recevoir le flot de diffusion. Il peut être retiré de l'arbre de diffusion. Ce routeur émet un message à son père dans l'arbre qui est appelé message d'élagage.  De proche en proche l'élagage se poursuit jusqu'à obtenir un arbre utilisable.


4.4) Sur le réseau suivant qui comporte 8 routeurs notés A,B,C,D,E,F,G,H, on a mentionné les coûts des arêtes. Quelle est la circulation des messages dans la première phase? On présente la réponse sous la forme d'un ensemble de lignes (X , Y) ou X est l'émetteur et Y le destinataire d'un message. On ajoute pour chaque message l'indication Y retransmet le message ou Y ne retransmet pas. Par exemple la première ligne de la réponse est: (A , B)    B retransmet le message.

4.5) Quel est l'arbre couvrant obtenu après circulation des messages d'indication de flot ?

4.6) Quelle est la circulation des messages d'élagage? 

4.7) Quel est l'arbre de diffusion finalement construit après circulation des messages d'élagage?