Université Sétif 1 - Faculté des Sciences - Département d’Informatique

Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.

Chapitre 1 : Optimisation du Routage.

1-Routage multicast :

Dans le « routage unicast », l'acheminement est défini comme le processus d'envoi des paquets
provenant d'un nœud origine à une destination unique. Ceci n'est pas le seul scénario possible.

Un autre scénario de routage se produit lorsque plus de deux nœuds ont besoin d'échanger des
données. Une route qui relie plus de deux nœuds est appelée « route multicast ».

Le routage multicast est applicable à des scénarios où les données ont besoin d’être partagées par un
groupe d'utilisateurs. Ces groupes peuvent varier d’un nombre relativement faible à un grand
nombre de clients.

Utiliser les protocoles de routage unicast pour connecter les éléments d'un groupe est inefficace. Les
ressources du réseau, principalement la bande passante, peut être gaspillée si les paquets sont
envoyés individuellement à chaque nœud du groupe.

Des solutions alternatives qui optimisent l'utilisation des ressources du réseau doivent être
développées.

Notre objectif ici est concentré sur l'optimisation de l'utilisation des ressources dans les réseaux
multicast.

Soit un exemple simple d'application de routage multicast. Une entreprise qui a besoin de mettre à
jour le logiciel utilisé dans plusieurs bureaux situés dans différentes régions d’un pays. L’utilisation du
réseau est payante selon la bande passante consommée. L'objectif de l'entreprise est de réduire la
quantité de bande passante utilisée dans l’opération de mise à jour.

Confrontés à un problème comme celui-ci, l’approche la plus simple peut être d’ouvrir une connexion
différente avec chaque site, et de servir les sites individuellement. L’avantage est la simplicité de la
solution.

Le plus grand inconvénient de cette méthode est le gaspillage de la bande passante, en raison de la
nature répétitive des transmissions qui doivent être accomplies. L’utilisation de la bande passante
pourrait être réduite si on utilise le routage multicast. Dans ce dernier les données sont envoyées
aux nœuds une fois seulement, ces derniers envoient autant de copies que nécessaire jusqu'à ce que
tous les nœuds de destination soient satisfaits.

1.1 Définitions :

Un « groupe multicast » est le nom donné à l'ensemble formé par la source et les nœuds de
destination.

Un groupe multicast peut être « statique » ou « dynamique » en fonction des membres du groupe
qui peuvent être autorisés à changer. Un groupe statique est celui où les membres ne peuvent pas
changer durant toute la vie du groupe. Lorsque les membres sont autorisés à entrer ou quitter le
groupe, de tels groupes multicast sont appelées dynamiques.

Page 1
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

L'un des principaux défis des groupes dynamiques est de maintenir la qualité de l'arbre de routage
sans dépenser trop de temps sur chaque ajout ou suppression d'un nœud.

Les groupes multicast peuvent également être classés en fonction du nombre des membres. Dans les
« groupes espacés », le nombre de participants est faible par rapport au nombre de nœuds dans le
réseau. D'autre part, quand la plupart des nœuds du réseau sont engagés dans la communication
multicast les groupes concernés sont appelés « groupes denses ».

Un « arbre multicast » est un ensemble d'arêtes sans cycle reliant les nœuds dans un
groupe multicast. En général, les arbres multicast sont la meilleure façon de générer des routes,
puisque leur utilisation permet d'éviter la redondance dans la transmission de données.

1.2 Applications

Les applications du routage multicast sont nombreuses et varient des applications commerciales aux
gouvernementales et de divertissement. L'une des premières applications du routage multicast est la
diffusion audio sur Internet.

Un premier exemple d'application de multicast est la fourniture de données financières (la bourse
par exemple), où l'on a un petit nombre de sources de données qui sont demandées par des millions
d'utilisateurs (Investisseurs, chaines de télé, sites web financiers,…).

Les systèmes de distribution multimédia peuvent bénéficier directement de l'amélioration des

technologies multicast. Il ya une énorme quantité de vidéo, de musique et de contenu de
divertissement qui doit être livrée aux utilisateurs à travers le monde.

La livraison de logiciels et la mise à jour est une autre application intéressante du multicast. Le
nombre des logiciels installés dans certaines sociétés est énorme, et va bénéficier grandement d'une
infrastructure de multicast.

1.3 Objectifs d’optimisation

Etant donné un réseau, un nœud source, et un ensemble de destinations, le problème du routage

multicast peut être quantifié en utilisant plusieurs objectifs ou métriques.

1.3.1 Minimisation du délai : un objectif possible est de minimiser le délai des routes utilisées. Dans
une application comme la diffusion vidéo d’une conférence, par exemple, il est important de
minimiser le délai d’acheminement des données. Lorsque le seul objectif est de minimiser le délai, le
problème peut être résolu en temps polynomial. Il suffit ici de calculer le plus court chemin vers
chaque destination individuellement. Le délai du chemin le plus long représente la solution du
problème. Pour résoudre ce problème il suffit donc de trouver l’arbre couvrant de plus court
chemin.

1.3.2 Minimisation d’une métrique autre que le délai : Un autre objectif d’optimisation peut être de
minimiser la somme des poids associés aux liaisons. Ces poids peuvent représenter une distance, un
coût de location, etc. Ici, il s’agit donc de minimiser le coût total de l'arbre multicast. Ce problème
est difficile à résoudre. Dans ce cas, le problème est NP-complet (Une caractéristique importante des
problèmes NP-complets est que nous ne connaissons pas d’algorithmes polynomiaux pour les

Page 2
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

résoudre). Le problème ici revient à trouver l’arbre de Steiner minimal. Un cas particulier se
présente lorsque tous les nœuds du réseau sont des destinations (Broadcast), dans ce cas le
problème revient à trouver l’arbre couvrant minimal (Minimal Spanning Tree, MST) qui est un
problème solvable en temps polynomial.

1.4 Technologies Multicast

L'idée de l'envoi de données à un grand nombre d'utilisateurs est courante dans les systèmes comme
la radio et la télévision. Les réseaux d’ordinateurs ont été initialement conçus pour être utilisé
comme des systèmes de communication de bout en bout semblable au service téléphonique.

La pile de protocoles TCP/IP, qui est la principale technologie sous-jacente de l'Internet,

utilise des protocoles de routage pour la livraison de paquets pour des destinations individuelles. La
plupart de ces protocoles sont basées sur le calcul des plus courts chemins. Un bon exemple de ces
protocoles de routage est OSPF (Open Shortest Path First).

Dans OSPF, chaque routeur dans le réseau est responsable du maintien d'une table de chemins
vers les destinations accessibles. Cette table est créée en utilisant l'algorithme de Dijkstra pour
calculer les plus courts chemins. Ce processus peut être fait en temps polynomial.

Cependant, avec les progrès de l'Internet la nécessité est apparue pour des protocoles capables de
cibler un public plus large. Cette tendance est devenue plus importante en raison du développement
de nouvelles technologies telles que la vidéo à la demande. Cette série de développements a donné
l’idée pour la proposition de protocoles de routage multicast.

Pour gérer les exigences de routage multicast, de nombreuses propositions de technologies multicast
ont été présentées dans la dernière décennie. Quelques exemples de protocoles multicast sont les
suivants: DVMRP – Distance Vector Multicast Routing Protocol et MOSPF - Multicast OSPF.

1.4.1 DVMRP – Distance Vector Multicast Routing Protocol : Le protocole DVMRP a été
développé comme une extension du protocole de routage RIP. Ce dernier est un protocole unicast
utilisé sur Internet. Une version complexe de DVMRP existe. Elle est nommée DVMRP hiérarchique.
Cette dernière divise le réseau en plusieurs domaines. Le problème est alors résolu dans chacun des
domaines, et la solution résultante est combinée pour former un arbre de routage global.

1.4.2 MOSPF - Multicast OSPF : le protocole MOSPF est une extension multicast du protocole unicast
OSPF. Le protocole MOSPF étend l'architecture OSPF en ajoutant la notion des sous-domaines. Il
divise le réseau en plusieurs sous-domaines. Ensuite, l'algorithme calcule un backbone (épine

Page 3
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

dorsale) reliant les sous-domaines, dans le but de réduire la complexité du problème. MOSPF est en
cours de développement.

1.5 Techniques basiques de routage

Dans cette section, nous présentons plus en détail certaines solutions de routage qui ont été
proposées pour faire du routage multicast.

Nous utilisons certains concepts de théorie des graphes et la terminologie présentée ici sera utilisée
dans le reste du cours.

Un graphe est composé d'un ensemble de nœuds et un ensemble d’arêtes. Un graphe est noté par
G=(V, E), où V est l'ensemble des nœuds et E l'ensemble des arêtes. Les nœuds du graphe
représentent des éléments du réseau tels que les routeurs, les machines sources et les destinations.
D'autre part, les arêtes représentent les liaisons entre les éléments du réseau.

Nous considérons des graphes non orientés et sans boucles. Donc il n’y a pas d’arête (i, i) ∈ E pour un
nœud i ∈ V. On note par N(i) l’ensemble des voisins du nœud i ∈ V.

Avec chaque arête (i, j) ∈ E on peut associer des fonctions qui représentent des caractéristiques de la
liaison représenté par l’arête (i, j). Les fonctions les plus utilisées sont le coût w(i, j), et le délai d(i, j).

La fonction de coût est utilisée pour modéliser les coûts de l'utilisation de la liaison. Cela comprend
les frais de location, les frais d'entretien, etc.

Pour la fonction de délai, d(i, j) représente le temps nécessaire pour transmettre les informations
entre les nœuds i, j.

1.5.1 L’inondation

L'algorithme d'inondation peut être utilisé dans le contexte de routage multicast. Ici un paquet reçu
par un nœud est renvoyé à l'ensemble de ses voisins. Par conséquent, toutes les destinations pour un
paquet peuvent être atteintes en utilisant l’algorithme d'inondation.

Bien qu’elle soit simple, la méthode d'inondation a le même inconvénient que dans le cas unicast :
elle utilise trop de ressources. La bande passante est gaspillée. De plus les routeurs doivent stocker
des informations sur les paquets reçus, ce qui augmente la consommation de mémoire et de temps
de traitement. Il est clair que c’est difficile d’utiliser l’inondation dans un réseau de grande taille. Le
passage à l'échelle n’est donc pas possible.

Malgré ces problèmes, plusieurs méthodes ont été proposées pour utiliser l’inondation de manière
efficace. Un exemple de ces méthode est la suivante : pour chaque nœud v et nœud source s dans le
réseau, v détermine le lien (u, v) qui est dans le plus court chemin entre s et v. Ce lien est appelé lien
parent.

Page 4
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

Si, au cours de la phase de routage, un paquet est reçu à partir d'un lien qui n'est pas le lien parent
alors le paquet est éliminé. Sinon, le paquet est envoyé à tous les voisins comme dans l'algorithme
d'inondation.

Le lien parent peut être déterminé de différentes manières. Une manière simple est de choisir le lien
(u, v) comme lient parent si c’est le premier lien sur lequel un paquet originaire de la source s a été
reçu.

D'autres stratégies ont été proposées dans la littérature afin d’optimiser l’inondation pour le routage
multicast.

1.5.2 Routage basé sur un anneau :

C’est une autre méthode intéressante pour la distribution des données dans des groupes multicast.
L'idée principale de cette méthode est d'avoir un anneau reliant les nœuds d’un groupe. La raison de
l'utilisation d'un anneau comme la structure de liaison est de profiter de ses propriétés à améliorer la
fiabilité. Ainsi les arbres peuvent être brisés par la défaillance d'un seul lien alors qu’un anneau n’est
pas brisé par la défaillance d’un lien.

1.5.3 Arbres basés sur le centre du graphe (Center-Based Trees)

Une idée utilisée fréquemment pour le routage multicast est la construction d’un arbre dont la racine
est le nœud source des données. Une autre idée proposée dans la littérature est de construire un
arbre dont la racine est le centre du graphe. Le centre d’un graphe est définit comme le nœud le plus
proche de tout autre nœud du graphe. C’est donc le nœud v qui minimise : « max distance(v, u) »
pour tout nœud u du graphe. (La distance entre deux nœuds dans un graphe est définie par la
longueur du plus court chemin entre ces deux nœuds)

Les chercheurs ont pensé à construire des arbres dont la racine est le centre du graphe car ce dernier
est un meilleur point de départ pour la création d'un arbre de routage. Le centre en raison de sa
position devrait changer moins que d’autre partie de l’arbre. Par conséquent, l’arbre résultat est plus
stable par rapport aux changements qui pourraient se produire dans la composition du groupe
multicast.

Page 5
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

1.6 Algorithmes pour le calcul d’arbres dans les graphes

Puisque le routage multicast est basé essentiellement sur le calcul d’arbres, nous présentons ici
quelques algorithmes de calcul d’arbres dans les graphes.

1.6.1 Algorithme de Kruskal

L'algorithme de Kruskal est un algorithme centralisé de recherche d'arbre couvrant de poids minimal
(minimal spanning tree, MST) dans un graphe connexe pondéré et non-orienté. Un arbre MST est
l’arbre couvrant dont la somme des poids des arêtes est minimale. L’algorithme a été conçu par
Joseph Kruskal. Cet algorithme fonctionne en temps polynomial. Il est à noter que pour utiliser un
algorithme centralisé dans un réseau, il faut que chaque nœud calcule la topologie du réseau avant
d’exécuter l’algorithme centralisé localement.

Etant donné un graphe G (V, E), n le nombre des nœuds et m le nombre des arêtes (n = |V| et
m = |E|) l’algorithme de Kruskal est présenté comme suit :

Exemple 1:

Page 6
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

Exemple 2: appliquer l’algorithme de Kruskal afin de trouver l’arbre MST du graphe suivant :

1.6.2 Algorithme de Prim

L'algorithme de Prim est un algorithme centralisé qui permet de trouver un arbre couvrant de poids
minimal (MST) dans un graphe connexe pondéré et non orienté. Cet algorithme fonctionne en temps
polynomial. Il a été conçu par Robert Prim.

L’algorithme utilise deux variables T et A. T est un ensemble d’arêtes, il est initialement vide et à la
fin il représente l’arbre calculé. A est un ensemble de nœuds, il contient initialement un seul nœud
choisi aléatoirement.

Exemple : appliquer l’algorithme de Prim afin de trouver l’arbre MST du graphe suivant :

Page 7
Université Sétif 1 - Faculté des Sciences - Département d’Informatique
Module : Techniques d’Optimisation des Réseaux - Niveau : Master 2 RSD.
Chapitre 1 : Optimisation du Routage.

Initialisation : T = ∅, A = {L}.

Itération 1 : e = (L, B), T = {(L, B)}, A = {L, B}.

Itération 2 : e = (B, D), T = {(L, B), (B, D)}, A = {L, B, D}.

Itération 3 : e = (B, C), T = {(L, B), (B, D), (B, C)}, A = {L, B, D, C}.

Itération 4 : e = (D, E), T = {(L, B), (B, D), (B, C), (D, E)}, A = {L, B, D, C, E}.

Itération 5 : e = (E, F), T = {(L, B), (B, D), (B, C), (D, E), (E, F)}, A = {L, B, D, C, E, F}.

Itération 6 : e = (E, G), T = {(L, B), (B, D), (B, C), (D, E), (E, F), (E, G)}, A = {L, B, D, C, E, F, G}.

Itération 7 : e = (G, K), T = {(L, B), (B, D), (B, C), (D, E), (E, F), (E, G), (G, K)}, A = {L, B, D, C, E, F, G, K}.

Itération 8 : e = (K, J), T = {(L, B), (B, D), (B, C), (D, E), (E, F), (E, G), (G, K), (K, J)}, A = {L, B, D, C, E, F, G,
K, J}.

Itération 9 : e = (K, H), T = {(L, B), (B, D), (B, C), (D, E), (E, F), (E, G), (G, K), (K, J), (K, H)}, A = {L, B, D, C,
E, F, G, K, J, H}.

Itération 10 : e = (J, I), T = {(L, B), (B, D), (B, C), (D, E), (E, F), (E, G), (G, K), (K, J), (K, H), (J, I)}, A = {L, B,
D, C, E, F, G, K, J, H, I}.

Page 8