Routage Multicast IP -trèèèèèèès intéressant ( formation animée pour le compte des ingénieurs d'Ooredoo)

Objectifs : 
– communications point à multipoint
• exemples
    – diffusion d’un canal vidéo/audio
    – visioconférences ( N sources, interactif)
    – jeux en réseau
    – diffusion de logiciels/données/…

– utilisation efficace du réseau
    • 1 seule copie des données sur un lien
    • => réalisé par le réseau au niveau IP
    • extensible (Nb récepteurs, de sources, de groupes, interdomaine)

Hypothèses:

•Réseau de type IP
• Envoyer le même paquet à plusieurs destinations en minimisant le trafic et les délais
• Le paquet IP parcourt (au moins) un arbre dont la racine est la source et les feuilles les récepteurs

Multicast de niveau 2 

• Dans un réseau à diffusion comme ethernet
– tout le monde reçoit (diffusion) puis sélection par les récepteurs
• Interconnexion de réseaux à diffusion au niveau 2 (pont, switch ethernet)
– construction d’un arbre de recouvrement (spanning tree) pour supprimer les boucles
– diffusion comme dans un réseau unique

– Multicast consomme des ressources
     • problème du filtrage (802.1 GARP) : GMRP ?
– Partiellement résolu en partitionnant le domaine de broadcast
– => utilisation des VLAN
    • Broadcast/multicast limité au VLAN de l’émetteur

Modèle de Deering (1991) 
• Multicast non défini dans IP d’origine
• Travaux de Deering :
    – Paquets IP multicast même format que unicast
    – Adresse multicast identifie un ensemble de récepteurs (classe D IPv4 : 224.0.0.0-239.255.255.255 = 224.0.0.0/4)
    – Groupe = adresse multicast – récepteurs se déclarent au routeur voisin (IGMP) – Pas de connaissance exhaustive des membres du groupe
• Les sources ne se déclarent pas
    – Emission spontanée, sources « bursty »
    – Difficulté du contrôle
• Multipoint à multipoint si les sources sont aussi réceptrices
    – possibilité d’un seul arbre pour N sources
    – possible grâce au mode datagramme (# ATM)
 • Séparation des signalisations IGMP, routage

Adhésion aux groupes

• Protocole spécifique (IGMP) au dessus d’IPv4
        – inclus dans ICMPv6 pour IPv6 (MLD)
• Objectif : connaître les groupes qui ont des récepteurs sur une interface de routeur donnée
    – pas de connaissance exhaustive des récepteurs
• Principe
    – routeur interroge cycliquement IGMP-Query (défaut 125s)
    – récepteurs de G répondent IGMP-Reply (G)

• Mécanismes
   – éviter les réponses multiples :
      • réponses retardées un temps aléatoires
      • supprimées si redondantes
              – idéal = 1 réponse par groupe qui a des récepteurs)
      • => Report IGMP envoyé en multicast
           – à l’adresse du groupe considéré
    – « soft state » : pas de réponse pour G = supprimer info

  – Retrait d’un groupe
       • sur délai (IGMPv1, RFC 1112)
       • retrait explicite : IGMP-leave (IGMPv2, RFC 2236)
  – IGMP protocole datagramme (non fiable)
       • mécanismes de robustesse
       • routeur envoie Plusieurs Query Spécifiques (G) à G
       • avant de supprimer groupe
– traite pertes IGMP, autres récepteurs du groupe

– Choisir les sources d’un groupes
     • une source vidéo dans visioconférence
     • filtrer source indésirable
 – Possible avec IGMPv3, RFC 3376, (2002)
    • mode INCLUDE = liste des sources voulues
    • mode EXCLUDE = liste des sources non voulues
    • synthèse (conservatrice) par le routeur
– Les reports ne sont plus envoyés au groupe mais à
      • 224.0.0.22 = all IGMPv3 capable routeurs
– un report pour plusieurs groupes
– tous les récepteurs répondent
      • permet host tracking facultatif

Listes de sources 

– Ex synthèse de deux Reports,
    même groupe
    listes de sources L1 et L2
    include(L1) et include(L2) => include(L1 ∪ L2)
    include(L1) et exclude (L2) => exclude (L2 \ L1)
    exclude(L1) et exclude (L2) => exclude(L1 ∩ L2)
– IGMPv3 complexe
    messages toIN, toEX, isIN, isEX
    compatibilité avec versions 1 et 2

Quelques adresses prédéfinies 

• 224.0.0.0 Base Address (Reserved)
• 224.0.0.1 All Systems on this Subnet [RFC1112]
• 224.0.0.2 All Routers on this Subnet
• 224.0.0.4 DVMRP Routers [RFC1075]
 • 224.0.0.11 Mobile-Agents
• 224.0.0.12 DHCP Server / Relay Agent [RFC1884]
• 224.0.0.13 All PIM Routers
• 224.0.0.22 All IGMPv3 Routers [RFC 3376]

Lien avec le niveau liaison (1) 

• Lien point-à-point : pas de problème
• Lien à diffusion (ex : ethernet)
– encapsuler paquet IP multicast dans trame ethernet multicast
– mise en correspondance d’adresses
    • 23 derniers bits @ IP => 23 derniers bits @ 802
    • 25 premiers bits 01-00-5E-00-00-00 224.1.2.3 => 01-00-5E-01-02-03
    • collision d’@ possible : filtrage en réception 225.129.2.3 => 01-00-5E-01-02-03
    • en IPv6 : 33.33. Suivi des 4 derniers octets @ IPV6

IP multicast et bridging 

• Dans un réseau avec ponts
    – par défaut multicast = broadcast
    – risque de saturation du réseau
• VLAN = découpage domaine broadcast
• Solutions de niveau 2 type GARP/GMRP
   – en pratique peu ou pas implémentées
• Solutions de niveau 2+3
   – IGMP snooping

IGMP snooping 

• Principe : – les ponts espionnent (snooping) 

• paquets IGMP (et routage multicast) 

• déterminent où sont les récepteurs 

   – IGMP report et routeurs multicast 

• Problèmes 

– éviter la suppression de Report IGMP 

        • filtrer IGMP vers autres membres 

– départ implicite => timeout – calculs switchs (examiner entêtes MAC + IP + IGMP) 

– changer logiciels switch si changements IGMP/MLD

Routage multicast

 • Permettre l’acheminement d’un paquet multicast de la source vers les récepteurs 

 • Arbre construit par signalisation entre les routeurs 

     – semi-explicite (inondation/élagage) 

     – explicite (adhésion/retrait) 

 • Distinction entre 

     – mode dense ou épars 

     – intra ou inter domaine

Routage en mode dense 

• Inondation du réseau (flood) et élimination des branches inutiles (prune) 

    – DVMRP (sur routage unicast spécifique à la RIP) RFC 1075

    – PIM-DM (sur routage unicast « quelconque ») 

• Un arbre par source (pas scalable) 

     – O(S*G) entrées par routeur 

         • une entrée par couple S,G même si hors de l’arbre 

• Repose sur le RPF check

     – utilise le chemin vers la source « chemin inverse »

RPF Check

• B accepte un paquet multicast venant de A s’il arrive par la route unicast (interface) de B vers A

   – permet d’éviter les boucles 

   – la route unicast de B vers A est connue de B 

   – problème en cas de routes asymétriques 

 • Inondation/Elagage périodique (soft state)

Inondation/élagage 

• Reverse Path Flooding ou Broadcasting (RPF check)  

      – problème : les données encombrent tout le réseau 

• Truncated RPB – supprimer les réseaux feuilles inutiles (IGMP) 

• Reverse Path Multicasting – élagage (initial et périodique)

MOSPF 

• Extension de OSPF (RFC 1584) 

     – spécifique à OSPF 

• chaque routeur connaît les liens du réseau(routage par état des liens) 

    – nécessite de connaître l’existence des membres de chaque groupe sur chaque lien 

            • = nouvel attribut de l’état du lien, diffusé

 – calcul des arbres multicast à la volée (coûteux) 

      • calcul de l’arbre de S vers tous les membres (Dijkstra) 

      • suis-je sur cet arbre et avec quels successeurs ? 

      • Résultat mis en cache

 – chemins calculés dans le « bon sens »

Mode dense: conclusion 

• Adapté dans un petit domaine si la majorité des réseaux contiennent des membres 

• coûteux en signalisation (PRUNE) si groupe épars 

• coûteux en états dans TOUS les routeurs du domaine : proportionnel au nombre de couples sources*groupes (DVMRP)

Protocoles en mode épars 

• Un arbre partagé par toutes les sources 

• Construit autour d’un point central (RP) 

• Signalisation explicite (join) des récepteurs vers le centre 

• Arbre en général construit à l’envers « chemin inverse » 

• Localisation du centre ? Panne du centre ? 

• un protocole normalisé et utilisé : PIM-SM

Construction de l’arbre PIM-SM 

RFC 4601 (Standard Track, août 2006) 

• Le routeur d’attachement du nouveau récepteur 

    – à réception d’un Report IGMP – calcule l’adresse du RP 

    – transmet le join au routeur voisin vers le RP 

• Le join remonte vers le RP jusqu’à rencontrer un routeur sur l’arbre 

• messages de retrait (prune) analogues

PIM-SM mécanismes 

• Table de routage PIM-SM : types d’entrées 

      – (S,G) si arbre par source 

      – (*,G) si arbre centré vers un RP 

      – (*,*,RP) pour tous les G partageant un RP (interdomaine)

      – choix de l’entrée (interface d’arrivée, …)

 • informations par entrée de la table : 

      – iif : une interface d’entrée (déterminée par RPF) 

      – oif : n interfaces de sorties ( n >0) – des indicateurs, timers, …

• Adhésion 

– nouveau groupe présent (IGMP Report) sur interface oi 

– si entrée (*,G) existe • ajouter oi à oifs – sinon • calculer interface ii vers le RP de G 

• créer entrée (*,G) avec oif = {oi} et iif = ii 

• envoyer PIM join/prune vers RP par ii

– à réception Pim-Join(G) 

     • si (*,G) existe ajouter interface de sortie 

     • sinon : similaire à adhésion locale : 

                – créer entrée

                – propager PIM-Join 

– le PIM-join est propagé de proche en proche 

        • jusqu’à un routeur « on tree » ou éventuellement le RP

Retrait 

– quand le dernier membre de G sur un LAN 

      • quitte explicitement (IGMP-done) ou implicitement 

      • le routeur supprime l’interface de la liste oif 

– si oif devient vide 

       • envoyer PIM-prune vers RP et supprimer entrée

 – le PIM prune remonte de proche en proche 

       • jusqu’au premier routeur à plusieurs fils ou le RP

• Message périodique PIM-Hello (30s) 

• connectivité entre routeurs voisins 

     – indépendant des arbres 

• Maintenance de l’arbre 

    – message PIM-join périodique fils -> père (60s) 

            • rafraîchissement de l’arbre 

            • suppression des entrées (sur le père) sur timeout 

    – Remarque : pas de message « downstream »

Passage à un arbre (ou branche) par source

 – décidé 

      • par un routeur feuille (débit) 

      • ou par le RP pour la branche source => RP 

• envoi d’un message PIM-join(S,G) vers S 

• création d’une entrée (S,G) en plus de l’entrée (*,G) et avec les mêmes oif

– à réception de données par la branche spécifique = élagage par le côté RP
– pas de repassage explicite à l’arbre partagé
– sur DR timeout sur (S,G) : pas de données => (*,G)
• Plusieurs routeurs sur le même LAN
– mécanisme Assert (si réception de données par oif)
– élection du routeur qui propage sur le LAN
• métrique + identificateur

PIM-SM : choix du centre

• Algorithme du bootstrap

– bootstrap router (BSR) élu parmi les candidats BSR

    • chaque candidat diffuse son identité à tous les routeurs PIM

    • tant qu’il n’en connaît pas un meilleur

– un candidat RP envoie au BSR élu

    • liste des plages adresses multicast et priorité

– le BSR élu

    • choisit parmi candidats

    • diffuse une liste de points de rendez-vous (RP) valides

– sur chaque routeur

    • une fonction de hachage associe adresse de groupe => RP

Commentaires

• Nombre d’entrées en O(g) où g = nombre de

groupes « On tree », plus arbres (S,G)

• mécanisme de sélection du RP n’est pas scalable:

    – la liste de tous les RP doit être connue de tous les

routeurs (diffusion de cette liste)

    – placement non optimal dans un grand réseau

• a priori devrait dépendre de la topologie (variable) des

membres

    – panne du RP = reconstruction de tout l’arbre

Déploiement actuel

• Implémentations de DVMRP, PIM

• Multicast utilisé en interne

     – entreprises : visioconférence, cours bourse

     – FAI : exemple canaux TV chez Free

• Beaucoup d’opérateurs ne routent pas le multicast

     – encore peu de solutions viables à grande échelle

     – disponible chez quelques opérateurs : Sprint, …

• Réseau expérimental Mbone (FMBone)

     – tunnels entre routeurs multicast à travers routeurs non multicast

     – allocation d’adresse manuelle (ou GLOP)

Problèmes de l’inter-domaine

• Extensibilité

       – en nombre de groupes

            • potentiels, existants, existants à un endroit

       – taille des groupes

       – état à mémoriser, signalisation

• Allocation des adresses

       – unicité à l’échelle d’Internet

       – dynamicité

                • si nombreux groupes transitoires

                • espace d’adressage limité (en IPv4)

• Interaction protocoles de routage intra/inter

       – en unicast : protocoles différents

• Respect des politiques de routage

       – contrôle des flux multicast en transit

       – minimiser la « third party dependency »

• Accounting

       – essentiel si applications multicast commerciales

• diffusion vidéo, diffusion d’infos,...

• Fiabilité du routage

      – liée à la taille

      – importance si applications commerciales

Adressage multicast IPv4

• Choix manuel + annonce -> risque de collision

• allocation hiérarchique (architecture MASC, liée au routage)

• allocation par AS : GLOP (RFC 2770)

      – préfixe 233.0.0.0/8, ASN, groupID (8 bits)

• locale à la source (SSM) préfixe 232/8

• Scope (étendue)

     – avec le TTL ( 1 = lien, …)

     – préfixe

          • 239.255.0.0/16 (local)

          • 239.192.0.0/14 (site)

Adressage multicast IPv6

• FF, flags (4 bits), scope (4bits), réservé (80 bits), GroupeID (32 bits)

• flag 0000 = permanent 0001 = transitoire

• scope IPv6

       – 1 = node-local, 2 = link-local, 5 = site-local,

       – 8 = organization-local, E = global

        • ex : FF02:0:0:0:0:0:0:D All PIM Routers (perm., link)

        • FF05:0:0:0:0:0:1:3 All-dhcp-servers (perm., site)

L’architecture BGMP/MASC (Thaler et al, ietf)

• Un protocole d’allocation d’adresses multicast inter- domaine (MASC), + protocoles intra

domaine (AAP, MDHCP)

• Un protocole d’annonce des blocs d’adresses multicast et des politiques multicast (BGP4+)

• Un protocole de construction d’arbre multicast inter-domaine (BGMP)

• Un modèle d’interaction aux frontières

• Des protocoles de routage multicast intra-domaine

BGP4+ (MBGP)

• Extensions de BGP4 (routage interdomaine), RFC 2283

• Introduit de nouveaux attributs

     – Adresse multicast (pour BGMP)

     – Adresse unicast

• Si topologies unicast et multicast différentes

     – Permet le RPF check

     – MSDP, PIM-SSM

MASC (Multicast Address Set Claim)

• Domaines organisés en une hiérarchie

• Allocation unique, dynamique et temporaire

• Chaque domaine

     – demande une (ou plusieurs) plages d’adresses dans une plage affectée à son domaine père

     – résolution de conflit

• Les plages d’adresses utilisées par un domaine sont annoncées à l’extérieur via BGP

– association plage d’adresse <-------> Root Domain

– pas (encore ?) implémenté

MSDP ( Multicast Source Discovery Protocol)

– Solution provisoire en attendant une vraie solution inter-domaine

– RFC 3618 (2003)

– existe seulement pour IPv4

– Implémentée (cisco, ….) et utilisée

– But : relier des domaines PIM-SM entre eux

• Les domaines PIM-SM sont interconnectés

    – Chaque RP (domaine) participant

• a au moins une connexion avec un autre RP (domaine) participant

• graphe de domaine

     – Connexions TCP (fiable)

     – Installées manuellement

     – Servent à transmettre les annonces de sources

• SA(RP-annonçant, Source, Groupe)

• Quand un RP apprend une nouvelle source locale à son domaine

      – Via un PIM-Register

      – Construit un SA

– L’envoie à tout ses voisins MSDP (flooding)

• A réception d’un SA, un RP

      – Propage le SA, en faisant un RPF check (flood)

• SA ré-émis cycliquement (soft state)

• Traitement du SA(RP, S, G)

     – Si entrée (*,G) dans sa table de routage

• Groupe G actif

• Envoyer un join(S,G) vers S

• Construction d’une branche (S,G) inter-domaine

• S’arrête au premier routeur ayant une entrée (S,G)

    – Arbre (S,G) inter-domaine

    – construction utilise MBGP

Le modèle SSM

• Issu de l’architecture Express

• canal identifié par couple (source, ident)

• ident utilisée comme IP destination

    – adresse de groupe

    – unicité de l’ident simple à garantir (par source)

• construction d’arbres par source (S,G), unidirectionnels

• Insertion dans Pim-SM

    – utilise le mécanisme d’arbre par source de SM

    – ne nécessite plus de mécanisme de RP

    – => forte simplification si SSM uniquement

    – traitement SM (modèle ASM) ou SSM suivant plage d’adresse

    – IPv4 SSM = 232.0.0.0/8

    – nécessite l’utilisation d’IGMPv3 mode INCLUDE : abonnement à un couple source, groupe

             • G, include(S)

• Avantages

   – simple, déjà implémenté (PIM-SM)

   – allocation d’adresse triviale (inter-domaine)

   – Permet de faire de l’inter-domaine

• Inconvénients

   – pas de multipoint à multipoint direct

   – contrôle des récepteurs ?

Routage multicast et IPv6

• adresses IPv6 multicast

champs :FF, Flags, Portée, réservés, Group-ID

bits :       8     4           4          80           32

Portée : 1(noeud), 2(lien), 5(site), E(globale)

Flags xyzt :

t (0 = permanente, 1 = transitoire)

z (1 = adresse basée sur préfixe unicast)

               réservés(80) = 0(8), plen(8), prefix(64)

adresse « appartient » au préfixe prefix/plen

y (1 = RPembedded)

réservés = 0(4), RPad(4), plen(8), prefix(64)

adresse du RP = prefix/plen::Rpad

exemples adresses IPv6

• FF02:0::D : permanente locale au lien (tous les routeurs PIM)

• FF05:0::1:3 : permanente locale au site (tous les serveurs dhcp)

• FF1E::7777 : transitoire globale (groupe transitoire 7777)

• FF3E:40:2001:660:220:102::7777 : globale transitoire basée sur le préfixe 2001:660:220:102 (de longueur 64 = 0x40)

• cas particulier SSM : basée sur un préfixe unicast de longueur nulle

• FF3E:0::7777 : canal SSM global 7777

• FF7E:540:2001:660:220:102::7777 : adresse RP_embedded adresse du RP : 2001:660:220:102::5

multicast V6

• PIM étendu à IPv6

• MLDv1 (Multicast Listener discovery)

     – correspond à IGMPv2

     – MLDv2 correspond à IGMPv3

• Possibilité SSM comme en V4

• Pour ASM :

    – MSDP non disponible (mais non extensible)

    – possibilité de RP-Embedded

          • a priori extensible inter-domaine

          • gestion des RP, allocation des adresses ?

          • panne RP ?

Etat des lieux

• En IPv4,

– pas de bonne solution pour ASM interdomaine

        • MSDP, allocation d’adresses

– SSM OK (pour applis type canal TV)

        • mais IGMPv3 pas encore universel (Mac :-((

• En IPv6

– solution RP embedded pour ASM interdomaine

– SSM

– mais IPv6/MLDv2 pas encore universels

Au dessus d’IP multicast

• Transport UDP (TCP point à point)

• Non-fiable

• Fiabilité : problème difficile à grande échelle (PGM, …)

– codes correcteurs de pertes (Flute, …)

• Contrôle

– RTP/RTCP pour flux temps réel

– Contrôle de session (SAP, SIP, …)