• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 03/02/2020

Calculez la capacité d’un réseau

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Définissez le problème de flot maximum

Les notions de capacité d’un réseau sont associées à des concepts combinatoires comme le flot et les coupes. Ces notions sont très utiles pour le dimensionnement des réseaux.

Les structures que nous avons considérées jusqu’ici s’intéressaient au trajet d’une information dans un réseau. Lorsqu’on a eu des poids sur les arcs, il s’agissait de longueurs, ou de coût, mais rien sur la capacité d’un lien.

Une question importante est de savoir combien d’informations on peut faire circuler d’un nœud, S, vers un autre, T. C’est le problème du S-T flot maximum.

Chaque arc (u,v) a une capacité qui limite le flot qui circule sur cet arc entre u et v.

Dans chaque nœud en dehors de S et T, aucune information n’est perdue, et aucune n’est créée. Ainsi, tout ce qui rentre, ressort.

Au point de départ, on considère qu’il y a un trafic f qui est injecté. À l’arrivée, ce même trafic est extrait.

Lorsqu’on cherche à maximiser f tout en respectant les contraintes de capacité et de conservation, on obtient la formulation en programmation linéaire du problème de flot maximum.

Des logiciels d’optimisation résolvent très bien ce genre de programme linéaire, mais concernant le flot, il existe aussi des algorithmes plus classiques comme ceux de Ford et Fulkerson ou d’Edmonds-Karp.

Nous n’allons pas rentrer dans les détails de ces algorithmes. Cependant, on peut dire qu’ils fonctionnent sur le principe de chemin améliorant : une solution au problème du flot maximum est obtenue en accumulant des calculs de plus court chemin.

En effet, un flot de S à T peut être vu comme la combinaison linéaire de plusieurs chemins de S à T. La notion de flot permet d’appréhender la notion de capacité d’un réseau. Le flot maximum de S à T donne la quantité maximale d’information pouvant circuler entre ces deux points, et les routes à prendre pour y arriver.

Faites le lien entre le concept théorique de coupe et la capacité d'un réseau

Ce n’est pas la seule manière de considérer la capacité entre deux nœuds, la notion de coupe permet d’en avoir une vision plus structurelle.

En résolvant le problème du flot maximum, on obtient la combinaison de routes et la quantité d’informations maximale qui peut y circuler, notamment entre deux points S et T.

Si une information circule de S à T, elle va nécessairement passer par un des arcs de cette coupe. On appelle capacité de la coupe la somme des capacités des arcs qui la composent.

La capacité d'une coupe est la somme des capacités des arêtes qui la traversent
Capacité d'une coupe

Si un flot f va de S à T, il va nécessairement se répartir sur les liens qui composent la coupe. Et comme le flot respecte la contrainte de capacité vue dans la séquence précédente, on peut faire la somme sur les arcs de la coupe.

Nous obtenons que le flot de S à T est inférieur à la capacité de la coupe. C’est vrai pour tout flot de S à T et pour toute coupe séparant S de T. En particulier, c’est vrai pour le S-T flot maximum et pour la S-T coupe minimum : le flot maximum est inférieur à la coupe minimum.

En fait, la réciproque est vraie, mais trop technique pour la prouver ici. On obtient le célèbre théorème flot max/coupe min : le flot maximum est égal à la coupe minimum et ce, entre toute paire de sommets.

De manière intuitive, la coupe minimum est un goulot d’étranglement qui limite le trafic pouvant circuler. C’est le tunnel de Fourvière à Lyon !

La notion de coupe minimum dans un graphe est très étroitement reliée à celle de flot et donc de capacité de transport d’un réseau. Elle représente en effet les goulots d’étranglement qui limitent le trafic qu’un réseau peut supporter.

Par contre, le problème de la coupe maximum d’un graphe est lui NP-difficile. Il est même très difficile à approximer.

Appréhendez la notion de multiflot

Le problème de flot maximum donne la capacité de transport d’un réseau entre une source et une destination. La notion de multiflot qui l'étend modélise la manière dont plusieurs trafics peuvent se partager le réseau.

Le flot, ou la coupe, permet d’évaluer la capacité de transport d’un réseau entre 2 points, ou d’un point vers tous les autres, c’est équivalent.

Mais les situations où une seule source transmet ou reçoit de l’information sont rares. On s’intéresse alors au multiflot (ou flot multicommodité) qui optimise la combinaison de plusieurs flots sur le même réseau.

Le respect de la capacité de chaque lien doit, lui, être collectif : la somme des flots traversant un arc doit être inférieure à la capacité.

Programme linéaire du multiflot
Programme linéaire du multiflot

Ces équations décrivent tous les multiflots possibles. La fonction objective indique ensuite quel optimum on veut obtenir.

On peut, par exemple, vouloir maximiser la somme des flots transmis. Il peut y avoir alors une inéquité importante entre les flots, certains restant à 0 pour laisser la place à d’autres moins consommateurs de ressources. Une solution rarement satisfaisante dans un réseau de télécommunication.

On peut aussi définir sur les arcs, en plus des capacités, un coût d’utilisation proportionnel à la quantité de flots qui les utilise. Dans ce cas, on peut fixer l’intensité de chaque flot et chercher à obtenir le multiflot de coût minimum.

Il existe beaucoup de variantes possibles pour modéliser un grand nombre de problèmes différents. La solution obtenue donne à la fois une information sur le routage de l’information et sur les politiques de partage d’accès aux ressources qu’il faudra mettre en œuvre dans la couche MAC du réseau.

  • Le multiflot mélange des contraintes individuelles à chaque flot (la conservation) et des contraintes collectives (le respect des capacités). Ces contraintes sont locales.

  • L’objectif d’optimisation est, lui, global, et détermine le partage des ressources entre les flots et le routage de l’information.

En résumé de  la partie 2

Dans cette partie, nous avons vu plusieurs notions de graphes, structurelles et algorithmiques, qui ont des applications importantes dans la conception des infrastructures et protocoles des réseaux. Ces notions servent notamment à modéliser les réseaux et à développer un raisonnement mathématique et algorithmique.

Essayez dans la suite de repérer les concepts de graphes sur lesquels s'appuient les notions qui vous sont présentées.

Exemple de certificat de réussite
Exemple de certificat de réussite