Routage multicast : gestion des petits groupes et ingénierie de trafic

28/06/2004 Thèse - Ali Boudani - ARMOR 1

Routage multicast : gestion des petits groupes et ingénierie de trafic

Soutenance de Thèse

Ali Boudani

* Institut de recherche en informatique et systèmes aléatoires ** I.R.I.S.A *


Plan

Le routage multicast Le protocole GXcast Le protocole SEM Le protocole MMT Conclusion


•Les types d’arbres multicast•Les protocoles de routage multicast •Les nouveaux services


Unicast et Multicast

G G G G

D1 D2 D4D3

Source (S)

Destinataires D1, D2, D3, D4 membres du groupe G

unicast

G G G G

D1 D2 D4D3

Source (S)

Destinataires D1, D2, D3, D4 membres du groupe G

multicast

Paquet

G Destinataire appartenant à un groupe G

Routeur

Une copie pour chaque destinataire Une copie sur chaque brancheUn arbre est construit


Les types d’arbres multicast

Arbre partagé

Source (S1)

G

G

G

G

Point de rendez-vous

S1,G

Sou

rce

(S2)

S1,GS2,G

Source (S1)

G

G

G

G

*,G

Sou

rce

(S2)

Source (S1)

G

G

G

G

*,G

Sou

rce

(S2)

Arbre basé à la source

Arbre des plus courts chemins inversesArbre des plus courts chemins inverses

Arbre réduitArbre réduit


Les protocoles de routage multicast

IGMP (Internet Group Management Protocol)

Les protocoles de routage Intra-domaine– DVMRP

– MOSPF

– PIM-DM

– PIM-SM

– CBT

Les protocoles de routage Inter-domaine

protocoles à forte densité de membres•Arbre basé à la source•Inondation

protocoles à forte densité de membres•Arbre basé à la source•Inondation

protocoles à membres épars•Arbre partagé•Messages d’adhésion explicites•Point de rendez-vous

protocoles à membres épars•Arbre partagé•Messages d’adhésion explicites•Point de rendez-vous

Problème de résistance au facteur d’échelleProblème de résistance au facteur d’échelle


PIM-SM / MBGP / MSDP– PIM-SM (Protocol Independent Multicast-Sparse Mode)

• Protocole de routage multicast chargé de construire l’arbre multicast entre les domaines

– MBGP (Multi-protocol extensions to BGP4)• Utilisé pour décrire la topologie multicast d’un domaine

– MSDP (Multicast Source Discovery Protocol)• Annonce les sources actives dans les différents réseaux

BGMP / MASC– MASC (Multicast Address Set Claim)

• Allocation d’adresse stricte

– BGMP (Border Gateway Multicast Protocol)• Construction d’un arbre partagé bidirectionnel

Les protocoles de routage Inter-domaine

Protocoles en mode dense ne sont pas adaptés aux groupes ayant des membres épars

Protocoles en mode dense ne sont pas adaptés aux groupes ayant des membres épars

Limitations•Allocation d’adresses•Complexité•Sécurité

Limitations•Allocation d’adresses•Complexité•Sécurité


Les nouveaux services

SSM (Source Specific Multicast)– Notion de canal : <S,G>– Source spécifique

Xcast (Explicit Multicast)– Grand nombre de petits groupes

Un seul protocole ?Un seul protocole ?

Allocation d’adresse simplifiéeAllocation d’adresse simplifiée

Quantité de données à mémoriser par les routeurs paraît coûteuse si les destinataires membres d’un groupe ne sont pas nombreux

Quantité de données à mémoriser par les routeurs paraît coûteuse si les destinataires membres d’un groupe ne sont pas nombreux

Différents types d’applications multicast

Différents types d’applications multicast



Plan

•Le multicast explicite•Les deux protocoles Xcast et Xcast+•Leurs limitations

•Le protocole GXcast


Xcast : multicast explicite

Domaine :

– Un très grand nombre de groupes multicast de petite taille dont les destinataires sont largement dispersés

– Là où le modèle de multicast traditionnel ne convient pas

Objectifs :

– Améliorer la résistance au facteur d’échelle en éliminant les états de routage multicast à sauvegarder dans les routeurs

– Eliminer les messages de contrôle et de maintenance d’arbres– Réduire les problèmes du multicast en problèmes unicast


Le protocole Xcast

Sou

rce

(S)

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6 R7

R8

R9

D3

D4

D1

D2

D5

D6

X2UData

UDP

IP

src=S

dst= D1

Data

UDP

Xcast

D1, D2

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

D3, D4, D5

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

D3, D4, D5, D6

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

D1, D2, D3, D4, D5, D6

IP

src=S

dst= All_Xcast

S,G D1S,G D1, D2, D3, D4, D5, D6


Le protocole Xcast+

Sou

rce

(S)

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6 R7

R8

R9

D3

D4

D1

D2

D5

D6

X2MData

UDP

IP

src=S

dst= G

Data

UDP

Xcast

R4

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R8, R9

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

IP

src=S

dst= G

S,G R4S,G R4, R8, R9

Data

UDP

Xcast

R4, R8, R9

CI=G

IP

src=S

dst= All_Xcast

M2X

Data

UDP

IP

src=S

dst= G

X2M

Data

UDP

IP

src=S

dst= G

X2M

Data

UDP

Xcast

R8

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R9

CI=G

IP

src=S

dst= All_Xcast


Les avantages et les inconvénients de la technique Xcast

IP Xcast

Avantages– Gestion des états de routage et des messages de signalisation– Réaction automatique aux re-routage unicast et ingénierie de trafic simplifiée– Mécanisme simple d’allocation d’adresses multicast

Inconvénients– Baisse de la charge utile !!!

– Traitement complexe de l’en-tête– Changement des en-têtes des paquets à acheminer

Utilisation d’unicast plutôt que de Xcast ?


La fragmentation d’un paquet Xcast

Fragmentation IP

MTU

En-tête IP Dm+1..Dn

En-tête IP

En-tête IP En-tête Xcast D1 ….. Dn

En-tête IP

En-tête IP En-tête Xcast D1..Dm


Sou

rce

(S)

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6R7

R8

R9

D3

D4

D1

D2

D5

D6

X2MData

UDP

IP

src=S

dst= G

Data

UDP

IP

src=S

dst= G

S,G R4S,G R4, R8, R9

Le protocole GXcast (Generalized Xcast) : une généralisation du protocole Xcast

M2X

Data

UDP

Xcast

R4, R8

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R9

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R4

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R8

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R9

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

IP

src=S

dst= G

X2M

Data

UDP

IP

src=S

dst= G

X2M

Data

UDP

Xcast

R8

CI=G

IP

src=S

dst= All_Xcast

Data

UDP

Xcast

R9

CI=G

IP

src=S

dst= All_Xcast

nM : nombre maximum de destinataires autorisées dans

un paquet Xcast

nM : nombre maximum de destinataires autorisées dans

un paquet Xcast


Comportement basique– En-tête IP et Gxcast E= 32 octets, MTU minimale = 576 octets, donc:

nmax = 135

Nombre de paquets générés admet un minimum nmax / 2

Etude du paramètre de GXcast


Evaluation et simulation du protocole GXcast – taux de surcoût engendré par GXcast

Le nombre de paquets générés par GXcast par rapport au multicast, n nM

Le nombre de paquets générés par GXcast par rapport au multicast, n nM

Le nombre de paquets générés par GXcast par rapport au multicast, n > nM

Le nombre de paquets générés par GXcast par rapport au multicast, n > nM


Evaluation et simulation du protocole GXcast – taux de surcoût engendré par GXcast

Taux de surcoût GXcast par rapport à Xcast

Taux de surcoût GXcast par rapport à Xcast

Taux de surcoût unicast par rapport à GXcast

Taux de surcoût unicast par rapport à GXcast


Le simulateur du multicast explicite dans NS

d 80, 130, 250, 1000

Taille de données à transmettre à chaque destinataire

n 80, 90, 100, 110, 120, 130

Nombre de destinataires par groupe

nM70 Nombre de destinataires maximum

dans un paquet GXcast

Le simulateur du multicast explicite http://www.irisa.fr/prive/aboudani/research/xcast/index.htm

Le scénario de simulation– Jeux en réseaux– DIS (Distributed

Interactive Simulation)


lsim

N

iipaq

Nt

lNl

*

)(1

lsim

N

i l

N

jpj

Nt

D

Ll

i

ilpaq

*

)(1

1

)(

Evaluation et simulation du protocole GXcast

La distribution de paquets sur les liens

La distribution de paquets sur les liens

Le surcoût dû aux paquets générés

Le surcoût dû aux paquets générés


Nombre de paquets et volume transmis

- +Destinations

-+Cœur

Proche de celui d’Xcast

+Source

volumeNb paquets

GXcast par rapport à Xcast

+-Destinations

- (12 fois)-Cœur

- (20 fois)-Source

volumeNb paquetsGXcast par rapport à Unicast

GXcast est toujours meilleur en termes de délai (incluant le délai induit par la file d’attente et le temps de traitement)


Le compromis entre GXcast, multicast et unicast

Multicast ExpliciteMulticast ExpliciteMulticastMulticastUnicastUnicast

•Gaspillage de la bande passante

•Gaspillage de la bande passante

•Etats de routage•Maintenance de l’arbre

•Etats de routage•Maintenance de l’arbre

•Temps de traitement•Fragmentation

•Temps de traitement•Fragmentation

GXcast•Avantages en termes de délai et de coût

GXcast•Avantages en termes de délai et de coût

•Le besoin de chercher de nouveaux protocoles•Les nœuds de branchement et l’arbre réduit

•Le besoin de chercher de nouveaux protocoles•Les nœuds de branchement et l’arbre réduit

•Charge utile : le débit est divisé par 2

•Charge utile : le débit est divisé par 2



Plan

•Les nœuds de branchement et l’arbre réduit•Le protocole SEM


Les nœuds de branchement et l’arbre réduit

Source (S)

R1

R2

R3

R4

R5R6

G

S,G

G

•Des études montrent que le pourcentage de nœuds de branchement sur un arbre est petit :(8 %, 13 %)

•Des études montrent que le pourcentage de nœuds de branchement sur un arbre est petit :(8 %, 13 %)

S,G

S,G

S,G

Source (S)

R1

R2

R3

R4

R5R6

G G

S,G


Le protocole HBH

Source

S

H1

R1

MFT : Multicast Forwarding TableMCT: Multicast Control Table

MFT

MCT

H4

H3H2

R2

R3R1

R1

MCT

R1

R2

MCT

R2

R3

R1

MFT

R3

MFT

R3R1R1 R3

R1 R3

H3

H1 R2 Message joinMessage tree

Message fusion

•Utilise l’infrastructure unicast pour la transmission des paquets multicast•Utilise un canal (S, G) pour définir un groupe•Des MFT et des MCT existent encore ?•Trop de messages de contrôle (tree)

•Utilise l’infrastructure unicast pour la transmission des paquets multicast•Utilise un canal (S, G) pour définir un groupe•Des MFT et des MCT existent encore ?•Trop de messages de contrôle (tree)


Message JoinS

ourc

e (S

)

G

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6 R7

R8

R9

S,G R4R4, R8R4, R8, R9

TCM

Le protocole SEM (Simple Explicit Multicast)

TCM: Table de contrôle multicast


S,G R3 --

TRM

Sou

rce

(S)

G

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6 R7

R8

R9

S,G R4, R8, R9

TCM

Message branch et previous_branch

S,G -- R3

TRM

S,G R7

TRM

S,G R7

TRMS,G R3 R8, R9

S,G R3

TRM


Branch

Previous_branch

TRM: Table de routage multicast

S,G S --

TRM

S,G S R4, R7

TRM

S,G S R4

TRM


Paquet de données SEM

Sou

rce

(S)

G

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6 R7

R8

R9

S,G R4, R8, R9

TCM

S,G -- R3

TRM

S,G R7

TRM

S,G R7

TRMS,G R3 R8, R9

TRM

S,G S R4, R7

TRM

S,G R3

TRM



Message Alive

Sou

rce

(S)

G

G

G

G

G

G

G

R1 R2 R3

R4

R5 R6 R7

R8

R9

S,G R4, R8, R9

TCM

S,G -- R3

TRM

S,G R7

TRM

S,G R7

TRMS,G R3 R8, R9

TRM

S,G S R4, R7

TRM

S,G R3

TRM



Evaluation du protocole SEM

Réseau dense40 % de réduction

Réseau dense40 % de réduction

Réseau clairsemé80 % de réduction

Réseau clairsemé80 % de réduction

Taille globale des tables de routageTaille globale des tables de routage


Topologie MCITopologie MCI

Evaluation du protocole SEM

Surcoût de HBH par rapport à SEM (paquets de contrôle)

Surcoût de HBH par rapport à SEM (paquets de contrôle)

Nombre moyen d’états de routageNombre moyen d’états de routage


Par rapport à GXcast :

•Plus de charge utile dans un paquet

•Temps de traitement réduit

Par rapport à GXcast :

•Plus de charge utile dans un paquet

•Temps de traitement réduit

•Les limitations du modèle best effort de l’Internet

•Problématique de qualité de service avec l’ingénierie de trafic

•Les limitations du modèle best effort de l’Internet

•Problématique de qualité de service avec l’ingénierie de trafic

Par rapport à PIM et HBH :

•Diminution en taille des tables de routage

Par rapport à PIM et HBH :

•Diminution en taille des tables de routage

Par rapport à HBH :

•Diminution en nombre de messages de contrôle

Par rapport à HBH :

•Diminution en nombre de messages de contrôle

Résumé



Plan

•L’ingénierie de trafic avec MPLS•La difficulté de servir de l’IP multicast dans un domaine MPLS•Le protocole MMT


R1 Routing TableDestination Next-hop Router192.26.57/24 R2



192.26.57.6

192.26.57.6

192.26.57.6

192.26.57.6R1

R2

R3 R4

R1 Routing TableDestination Port Label192.26.57/24 2 7

R3 Routing TablePort Label Next-hop Router 1 8 R4

MPLS Routing TablePort Label Port Label 1 7 2 8

192.26.57.6

192.26.57.6

192.26.57.6

192.26.57.6

8

7

R1

R2

R3 R4

Routage IP

Routage MPLS

L’ingénierie de trafic avec MPLS

1

2

2 2

1

1

R5

3

Chemin explicite


Les Difficultés de servir de l’IP multicast dans un domaine MPLS

La construction du LSP (Label Switched Path) L’agrégation de trafic Passage du routage de la couche « Liaison de données » au routage

de la couche « Réseau » dans les LSR

•Framework for MPLS and multicast (RFC 3353)•MPLS and PIM-SM (Internet Draft)•Aggregated Multicast (Journal of Networks, Software and Applications)

•arbre agrégé

•Framework for MPLS and multicast (RFC 3353)•MPLS and PIM-SM (Internet Draft)•Aggregated Multicast (Journal of Networks, Software and Applications)

•arbre agrégé


Le protocole MMT (Multicast MPLS Tree)

Le NIMS (Network Information Manager System) collecte les messages d’adhésion et calcule ainsi l’arbre multicast Les messages branch envoyés par le NIMS vers tous les routeurs de branchement Les MPLS LSP entre les routeurs de branchement sont utilisés pour le routage multicast MPLS

S

R4 R5

NIMS

R2

R6

R1R3

G

G

S,G R5, R6

S,G R4


L’entité de gestion (NIMS)

Domaine

Association des arbres aux LSPCalcul de l ’arbre multicast selon les ressources disponibles

IT multicast

Création de nouveaux LSPRe-routage LSPCapacité résiduelleRéservation de ressources

IT unicast

Configuration des routeurs de branchement

Collecte des adhésions aux groupes

Collecte des informations d’états de liens

Configuration des LSP

NIMS


La variante MMT2

S

R4 R5

NIMS

R2

R6

R1R3

G

G

Lg L2, L3

Lg L1

S,G Lg

Cas où un routeur de cœur est un routeur de branchement

Cas où un routeur de cœur est un routeur de branchement

La variante MMT2 et Les arbres agrégés

La variante MMT2 et Les arbres agrégés


Evaluation du protocole MMT

Le simulateur pour le multicast MPLS – MNS (MPLS Network Simulator)– http://www.irisa.fr/prive/aboudani/research/mmt/index.htm

Diminution en taille des tables de routage multicast– 3 réseaux (NSFNET, Abilene, MCI)

Temps de traitement des en-têtes multicast dans les routeurs– (moyen, max, min)

Coût de l ’arbre


Evaluation du protocole MMT

Diminution en taille des tables de routageDiminution en taille des tables de routageDélai global (moyen)Délai global (moyen)Le coût de l ’arbreLe coût de l ’arbre


Conclusion

Gestion de petits groupes– GXcast :

• Aucun état de routage• Pas de messages de signalisation• Permet un nombre élevé de petits groupes

– SEM :• Peu d’états de routage (uniquement dans les nœuds de branchement de l’arbre)• Inter-opérable avec les protocoles de routage multicast traditionnel

Ingénierie de trafic– MMT :

• La combinaison de multicast et de MPLS• Réduit l’IT multicast en une simple IT unicast• Réduction de temps de traitement (avec MPLS)• Arbre du meilleur chemin qui coïncide avec l’arbre des plus courts chemins en l’absence des contraintes d’ingénierie de trafic

Nos résultats montrent que l’IT bénéficie du développement de protocoles spécialisés


Publications Articles de Journaux

– A. Boudani, A. Guitton, B. Cousin. GXcast : une généralisation du protocole Xcast. Informations, Savoirs, Décisions et Médiations (ISDM), special issue on Majecstic (To appear), 2004. Conférences Internationales

– A. Boudani, A. Guitton, B. Cousin. GXcast: Generalized Explicit Multicast Routing Protocols. 9th IEEE Symposium on Computer and Communications (ISCC), Alexandria, Egypt, 2004. – A. Boudani, B. Cousin. SEM : A New Small Group Multicast Routing Protocol. 10th International Conference on Telecommunications (ICT), Tahiti, Papeete, France, 2003. – A. Boudani, B. Cousin. Multicast Routing Simulator over MPLS Networks. 36th Annual Simulation Symposium, Orlando, Florida, USA, 2003. – A. Boudani, B. Cousin, J. Bonnin. MPLS Multicast Traffic Engineering. IEEE ROC&C'2003, Acapulco, Mexique, 2003. – A. Boudani, B. Cousin. A New Approach to Construct Multicast Trees in MPLS Networks. Seventh IEEE Symposium on Computers and Communications (ISCC), Taormina, Italy, Juillet 2002.

Conférences Nationales– A. Boudani, A. Guitton, B. Cousin. GXcast : une généralisation du protocole Xcast. Manifestation des Jeunes Chercheurs STIC (Majecstic), Marseille, France, 2003.

Rapports de recherche– A. Boudani, B. Cousin. Using MPLS for Multicast Traffic Engineering. Rapport de Recherche IRISA, No1548, 2003. – A. Boudani, C. Jawhar, B. Cousin, M. Doughan. A Simulator for Multicast Routing over an MPLS Network. Rapport de Recherche IRISA, No1493, Octobre 2002.

Divers– A. Boudani, A. Guitton, B. Cousin. GXcast: Generalized Explicit Multicast Routing Protocol. draft IETF: draft-boudani-gxcast-00.txt, 2003. – A. Boudani, B. Cousin. The MPLS Multicast Tree (MMT). draft IETF: draft-boudani-mpls-multicast-tree-00.txt, Novembre 2001. – A. Boudani, B. Cousin. Simple Explicit Multicast (SEM). draft IETF: draft-boudani-simple-xcast-00.txt, Juin 2001.


Merci de votre attention

Documents

Routage multicast : gestion des petits groupes et ingénierie de trafic