jeudi 1 septembre 2016

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, …)

Aucun commentaire:

Enregistrer un commentaire