LES RESEAUX MPLS ET GESTION DE LA QOS

Télécharger le fichier pdf d’un mémoire de fin d’études

La gestion de la QoS

La deuxième évolution concerne la gestion de la QoS. En effet les opérateurs doivent régulièrement mettre à jour leurs infrastructures pour faire face à cet accroissement du trafic sur leurs réseaux et pour assurer un niveau de QoS qui ne cesse d’augmenter avec les nouvelles applications multimédia.
Dans le contexte d’une conjecture économique difficile et très compétitive, les opérateurs ont du trouver une alternative à la solution de surdimensionnement « aveugle » des réseaux. Celle-ci passe nécessairement par le biais de l’optimisation du routage. Cette optimisation permet de mieux utiliser les ressources disponibles dans le réseau. Elle permet aussi d’éviter la dégradation des services en intégrant les indicateurs de QoS dans l’évaluation du routage.
Traditionnellement seul le critère bande passante a suscité l’intérêt des opérateurs. Seulement avec l’avènement des nouvelles applications multimédias sur les réseaux on ne peut plus se contenter de ce seul critère. Il a fallu mettre à jour les modèles en y intégrant des indicateurs de la QoS tels que le délai, la perte ou encore la gigue.
C’est pourquoi nous proposons une modélisation basée sur l’évaluation de ces indicateurs que nous intégrons dans le processus d’optimisation du routage des LSPs.

L’intégration de la gestion de la QoS dans le schéma de routage est basée sur la notion de différenciation de services. En effet DiffServ (Differentiated Services) permet de mettre en place un mécanisme de différentiation des paquets au niveau des files d’attentes. Cela permet de traiter chaque paquet selon la classe de service à laquelle il appartient. Nous nous sommes intéressés, aux différentes politiques de « scheduling » utilisées par les opérateurs de télécommunications. Nous proposons une modélisation très simple basée sur le modélisation par des files d’attentes M/M/1/N. Nous proposons aussi une modélisation plus complexe, mais beaucoup plus fine, basée sur le principe de la combinaison de files prioritaires et de files WFQ (Weighted Fair Queuing). Cette dernière est une émulation de l ‘algorithme LLQ (Low Latency Queuing) proposé par CISCO.

Conception de Topologies

Durant l‘étude du problème de mono-routage des LSPs nous nous sommes rendu compte que la solution dépend étroitement de la topologie du réseau. Pour ainsi dire rien ne sert d’essayer d’améliorer le routage si la topologie sous-jacente est mal conçue.
Nous avons vu précédemment que les réseaux de télécommunications sont devenus des ressources stratégiques pour les institutions tant privées que publiques et leur importance économique ne cesse d’augmenter.
L’augmentation de la connectivité des réseaux et l’intégration de plusieurs services dans un même système de communication (intégration de voix et données, téléphonie mobile, développements de la téléphonie sur plates-formes IP, etc.) a engendré une croissance significative de la complexité du métier de concepteur d’architectures de réseaux.

D’une part, sur des aspects de dimensionnement matériel puisque les structures de communication doivent fédérer un nombre croissant de points de raccordement. D’autre part, la convergence des médias où l’on cherche à faire passer sur un même support physique les données, la voix, la vidéo, entraîne l’ajout de nouveaux équipements.
Le résultat conduit en général à une augmentation de la charge du système de transmission, et pour l’architecte réseau à une préoccupation permanente d’assurer une bonne Qualité de Service (QoS : Quality Of Service) pour les utilisateurs du réseau.
Le premier réflexe de ce dernier pour répondre à cette problématique est d’utiliser des matériels de communication puissants avec beaucoup de mémoire, des processeurs rapides et des lignes à hauts débits. Partant de cet état de fait, l’élaboration d’une topologie optimale nous est apparue, dans ce contexte, un point important à étudier.
Le principal problème étudié consiste à minimiser le coût total du système de communication tout en garantissant sa résilience.
Pour ce faire nous proposons une modélisation qui tient compte du trafic et des coûts d’équipements. Nous élaborons deux approches la première basée sur la programmation linéaire en nombres entiers. La deuxième approche est une heuristique qui combine une technique de « clustering » et une technique de recherche locale.

Plan de la thèse

Le premier chapitre de la thèse présente le contexte des réseaux IP/MPLS et montre la complexité du routage dans de tels réseaux. Nous présentons le routage classique dans les réseaux IP ainsi que le routage par LSPs dans les réseaux MPLS. Nous présentons à la fin de ce chapitre une première formulation du problème de mono-routage des LSPs. Cette formulation permet d’optimiser l’allocation de ressources et d’optimiser la bande passante résiduelle du réseau.
Le deuxième chapitre est dédié à la gestion de QoS dans les réseaux MPLS. Les mécanismes utilisés pour mettre en œuvre cette QoS (IntServ / DiffServ) sont présentés. Nous en discutons les avantages et les inconvénients de ces mécanismes. Nous proposons suite à cela deux modélisations analytiques de la QoS. La première est basée sur les files M/M/1/N et la deuxième est une émulation du protocole LLQ proposé par CISCO. Nous proposons ensuite une extension du problème de mono-routage qui intègre les contraintes de QoS au niveau des LSPs.

Le troisième chapitre traite des méthodes d’optimisation non-linéaires. Nous considérons plusieurs de ces méthodes, parmi les plus connues dans la littérature, afin de déterminer la plus efficace pour notre problème. Le but étant d’approcher la solution du problème de mono-routage à l’aide de la solution multi-routée. Nous présentons dans ce chapitre une nouvelle méthode ILSP (Iterative Loading Shortest Path) pour la génération de chemins candidats. Nous terminons ce chapitre par un comparatif des performances des méthodes étudiés sur des topologies tests.
Le quatrième chapitre traite du problème du mono-routage des LSPs. Nous présentons l’algorithme CISCO Pcalc. Nous présentons par la suite un nouvel algorithme innovant ILSP-OLS-ACO qui combine la qualité des chemins candidats générés par ILSP, la précision de la solution multi-routées par OLS et la qualité de la solution mono-routée par ACO.
Le cinquième chapitre traite de la sécurisation des réseaux IP/MPLS. Nous présentons les différentes techniques de sécurisation disponibles (Backup, Fast Reroute, Multilayer). Nous présentons suite à cela les différentes extensions de l’algorithme ILSP afin de générer des chemins candidats en tenant compte de la contrainte de sécurisation. Nous présentons aussi les algorithmes de calcul des Backup est des Fast Reroute avec ou sans notion de SRLG.

Le sixième chapitre traite de la conception de topologie d’accès. Nous présentons une modélisation du problème qui tient compte du trafic ainsi que des coûts d’équipements. Nous proposons une version décomposée du problème initial basée sur le calcul des configurations « matérielles » optimales au niveau des sites. Nous proposons pour cette modélisation une approche exacte (Branch and Bound amélioré) et une approche heuristique (Lagrangien et formulation duale). Nous proposons aussi une heuristique qui exploite une technique de « clustering » ainsi qu’un algorithme de recherche locale. Nous présentons ensuite les résultats obtenus par les différentes méthodes sur des topologies tests.

Le routage dans les réseaux IP

Le routage IP est un routage de proche en proche. Dans un routeur, une table de routage IP contient la liste des adresses connues localement afin d’associer une interface de sortie à toutes les destinations (next-hop). Lorsqu’un paquet de destination inconnue (non locale) est reçu, le paquet est envoyé vers le routeur de frontière par défaut.
Le routage se compose de deux éléments essentiels :
• Détermination des chemins optimaux de routage,
• Envoi des paquets IP à travers des réseaux.
L’envoi des paquets est somme toute une tâche assez simple. La détermination d’un routage optimal est par contre beaucoup plus complexe.
Les routeurs dans l’Internet sont organisés de manière hiérarchique. Des routeurs sont utilisés pour envoyer les informations dans des groupes de routeurs particuliers sous la même responsabilité administrative. Ces groupes sont appelés des « Autonomous Systems » (AS). Ces routeurs, appelés Interior Gateway Router, utilisent des protocoles de routage appelés Interior Gateway Protocols (IGP). D’autres routeurs permettent à différents Autonomous Systems de communiquer entre eux. Ils utilisent des protocoles de routage appelés Exterior Gateway Protocols (EGP).

En échangeant régulièrement des informations, les routeurs construisent une image de la topologie du réseau ce qui permet de créer les tables de routage. Les tables de routage contiennent en tout nœud, le prochain routeur à utiliser (next hop) pour une destination donnée. Le routage IP spécifie donc bond par bond (hop by hop) comment envoyer des paquets pour une adresse destination donnée.
En fait, la route complète de l’origine jusqu’à la destination n’est pas connue pendant le transit du paquet. Seuls les nœuds intermédiaires sont déterminés un par un parmi les voisins d’un nœud donné. IP opère donc en mode non connecté.
Les principaux objectifs à atteindre par un protocole de routage sont :
– Optimisation (sélectionner le meilleur chemin selon les critères choisis),
– Simplicité (le plus simple possible),
– Robustesse et souplesse (faire face à toutes sortes d’imprévus),
– Convergence rapide (recalculer les routes rapidement pour éviter les boucles, les pannes réseau,…).
Pour la suite, nous allons nous intéresser aux deux protocoles de routage les plus utilisés dans l’Internet : OSPF (Open Shortest Path First) et BGP (Border Gateway Protocol).

Le protocole OSPF

Le protocole OSPF (Open Shortest Path First) est un protocole de routage à état de lien (Link-State) créé par l’IETF [RFC2328]. Il est actuellement l’IGP (Interior Gateway Protocol) le plus répandu.
L’état de lien permet au routeur d’avoir une vision globale du réseau et de sa topologie et l’émission des mises à jour n’est déclenchée qu’en cas de modifications topologiques.
Pour générer la table de routage, le protocole OSPF utilise un arbre du plus court chemin d’abord (SPF Tree : Short Path First Tree) et un algorithme du plus court chemin d’abord (SPF Algorithm) appelée aussi algorithme de Dijkstra, qui détermine le meilleur chemin en terme de coût.
Le coût du chemin dépend de métriques figées par l’opérateur sur chacune des interfaces du réseau. La métrique, est un coût sans dimension aucune valeur n’est imposée. Libre à l’opérateur de choisir la valeur qu’il juge pertinente (CISCO préconise la valeur 108/débit).

Le protocole OSPF est capable de différencier les classes de service, grâce au champ ToS, permettant ainsi un routage différent selon le type de trafic dans le réseau. Les tables de routages pouvant être différentes selon les classes de services, on peut utiliser une métrique différente pour chacune d’elle.
Lorsque plusieurs routes sont équivalentes d’un point de vue métrique (même coût), le partage de charge (Load-Balancing) entre ces routes peut être employé. Le nombre de routes sur lesquelles on peut faire du partage de charge est en général limité (à quatre sur certains routeurs).
Un réseau OSPF peut-être composé d’un ou plusieurs domaines de routage, les aires (Areas), au sein d’un même système autonome : l’aire 0 constitue l’aire de backbone.

Le protocole BGP

Le protocole BGP (Border Gateway Protocol) est un protocole de routage entre AS [RFC1771]. BGP est utilisé pour l’échange d’informations de routage entre AS de l’Internet. Les informations de routage se présentent sous la forme de la suite des numéros d’AS à traverser pour atteindre la destination. C’est BGP qui assure la propagation des routes à l’échelle mondiale.
Quand BGP est utilisé entre AS, le protocole est connu sous le nom de BGP Externe (e-BGP). Si BGP est utilisé à l’intérieur d’un AS pour échanger des routes, alors le protocole est connu sous le nom de BGP interne (i-BGP). Les routeurs de frontière communiquant par i-BGP doivent être complètement maillés (mais pas forcément directement connectés). Avec BGP4, on peut toutefois utiliser les techniques dites de route reflector et de confédérations pour diminuer le nombre d’échanges de messages à l’intérieur d’un grand AS.

BGP est un protocole très robuste et très « scalable » : les tables de routage BGP de l’Internet comprennent plus de 90000 routes. Si BGP a atteint ce niveau de « scalabilité », c’est essentiellement parce qu’il associe aux routes des attributs permettant de définir des politiques de routage entre AS (c’est aussi grâce au sous-adressage).
Les voisins BGP échangent toutes leurs informations de routage au début, lors de l’établissement d’une connexion TCP entre eux. Par la suite, les routeurs BGP n’envoient à leur voisins que des mises à jour des tables de routage lorsqu’un changement de route est détecté ou qu’une nouvelle route est apprise. Ainsi, les routeurs BGP n’envoient pas des mises à jour périodiquement et ne diffusent que le chemin « optimal » vers un réseau destination.

Le concept MPLS

Avec l’augmentation du débit des liens de communication, les routeurs de l’Internet menaçaient de devenir des goulots d’étranglement. L’IETF a ainsi défini le nouveau protocole MPLS [RFC3031], [RFC3032] avec deux objectifs principaux :
• Permettre un acheminement rapide des paquets IP en remplaçant la fonction de routage par une fonction de commutation qui est beaucoup plus rapide, la taille des matrices de commutation étant très petite. La recherche se fait suivant le principe « exact match » au lieu de « best match ».
• Faciliter l’ingénierie réseau en fournissant aux opérateurs la maîtrise de l’acheminement des données, qui étaient très complexes avec des protocoles comme OSPF.

Le protocole MPLS, basé sur le paradigme de changement de label, dérive directement de l’expérience acquise avec l’ATM (étiquettes VPI/VCI). Ce mécanisme est aussi similaire à celui de Frame Relay ou de liaisons PPP. L’idée de MPLS est de rajouter un label de couche 2 aux paquets IP dans les routeurs frontières d’entrée du réseau. Le réseau MPLS va pouvoir créer des LSPs (Label Switching Path), similaires aux PVC d’ATM.
Ces LSPs définissent une route de bout en bout par une concaténation de labels. A l’entrée du réseau MPLS, le label est rajouté à l’entête IP par le routeur frontière LER (Label Edge Routers) puis à la sortie du réseau MPLS le label est retiré par un autre routeur frontière, ce qui permet de retrouver le paquet IP original. Les routeurs du cœur de réseau, appelés LSR (Label Switching Routers), vont router les paquets de proche en proche par commutation de labels, « oubliant » ainsi les adresses IP.
L’entête MPLS se situe entre les entêtes des couches 2 et 3, où l’entête de la couche 2 est celle du protocole de liaison et celle de la couche 3 est l’entête IP. L’entête est composée de quatre champs:
• Le champ Label (20 bits),
• Le champ Exp ou CoS (3 bits) pour la classe de service (Class of Service),
• Un bit Stack pour supporter un label hiérarchique (empilement de labels),
• Et un champ TTL (Time To Live) pour limiter la durée de vie du paquet (8 bits). Ce champ TTL est le même que pour IP.

Distribution des labels

Les LSR se basent sur l’information de label pour commuter les paquets au travers du cœur de réseau MPLS. Chaque routeur, lorsqu’il reçoit un paquet taggué, utilise le label pour déterminer l’interface et le label de sortie. Il est donc nécessaire de propager les informations sur ces labels à tous les LSR. Pour cela, suivant le type d’architecture utilisée, différents protocoles sont employés pour l’échange de labels entre LSR ; en voici quelques exemples :
TDP/LDP (Tag/Label Distribution Protocol) : mapping des adresses IP unicast.
CR-LDP, RSVP-TE : utilisés en Traffic Engineering pour établir des LSP en fonction de critères de ressources et d’utilisation des liens.

MP-BGP (MultiProtocol Border Gateway Protocol) pour l’échange de routes VPN.
Chaque paquet MPLS est susceptible de transporter plusieurs labels, formant ainsi une pile de labels, qui sont empilés et dépilés par les LSR. Cela permet entre autre d’interconnecter plusieurs réseaux, chacun possédant son propre mécanisme de distribution des labels.
Lorsqu’un LSR commute un paquet, seul le premier label est traité. Cette possibilité d’empiler des labels, désignée sous le terme de Label Stacking, est aussi utilisée par le Traffic Engineering et MPLS / VPN.

Le protocole CR-LDP

CR-LDP [RFC3988] est une version étendue de LDP, où CR correspond à la notion de « routage basé sur les contraintes des LSP ». Tout comme LDP, CR-LDP utilise des sessions TCP entre les LSR, au cours desquelles il envoie les messages de distribution des étiquettes. Ceci permet en particulier à CR-LDP d’assurer une distribution fiable des messages de contrôle.
Les échanges d’informations nécessaires à l’établissement des LSP utilisant CR-LDP sont décrits dans la figure suivante :

Le protocole RSVP – TE

Le protocole RSVP utilisait initialement un échange de messages pour réserver les ressources des flux IP à travers un réseau. Une version étendue de ce protocole RSVP-TE [RFC3209], en particulier pour permettre les tunnels de LSP, autorise actuellement RSVP à être utilisé pour distribuer des étiquettes MPLS.
RSVP est un protocole complètement séparé de la couche IP, qui utilise des datagrammes IP ou UDP (User Datagram Protocol) pour communiquer entre LSR. RSVP ne requiert pas la maintenance nécessaire aux connexions TCP, mais doit néanmoins être capable de faire face à la perte de messages de contrôle.
Les échanges d’informations nécessaires à l’établissement de LSP permettant les tunnels de LSP et utilisant RSVP sont décrits dans la figure suivante :

Définition des LSPs suivant les RFC de l’IETF

Le LSP est une succession de routeurs LER et LSR, c’est le chemin que vont suivre les paquets dans le réseau MPLS. Un LSP est défini par les attributs suivants :
• Le LSR d’entrée (Ingress LSR) et de sortie (Egress LSR),
• La (ou les) FEC qu’il transporte,
• La bande passante réservée,
• Mandatory : est activé si le chemin est imposé au LSP,
• Hierarchy : peut être activé lorsque plusieurs chemins sont disponibles,
• Affinity : (ou couleur) permet de marquer les différentes ressources du réseau. On peut alors imposer à un LSP d’utiliser certaines classes de ressources (et donc pas d’autres). Par exemple n’utiliser que des liaisons chiffrées, cryptées ou satellites etc,
• Setup Priority : permet d’affecter une priorité aux LSPs. Cette priorité est tout d’abord utilisée pour déterminer l’ordre dans lequel les LSPs doivent être établis, et donc l’ordre dans lequel ils vont accéder aux ressources du réseau,
• Holding Priority : permet à un LSP de remplacer un autre LSP de son chemin, si cela est nécessaire. Cela est utile si des LSPs de haute priorité doivent être absolument reroutés en cas de panne et remplacer d’autres LSPs moins prioritaires. Cette situation peut arriver en cas de manque de bande passante,
• Fast ReRouting : indique la présence d’un chemin de contournement à utiliser en cas de pannes,
• Explicite Routing : permet de spécifier entièrement (strict) ou partiellement (loose) le chemin du LSP,
• Adaptivity : permet de spécifier si un LSP est réoptimisable (c’est-à-dire si on lui cherche un autre chemin de secours) en cas de problème (panne détectée d’un élément),
• Policing : spécifie les opérations à effectuer en cas de trafics non cohérents avec les contrats,
• AutoBandwidth : permet au LSP d’adapter dynamiquement la bande passante réservée par rapport au trafic présent. On peut spécifier la fréquence avec laquelle on demande la bande passante, spécifier le maximum de bande passante sur le tunnel et la bande passante minimale.
A ces attributs, on peut ajouter les attributs relatifs à l’évaluation de performances tel que le délai, la perte et la gigue maximum tolérés (par classes de services). Plusieurs informations nécessaires au routage des LSPs sont distribuées périodiquement :

• Lorsqu’un changement de la Bande Passante est détecté,
• Lorsqu’une modification de la configuration des liens est détectée,
• Etc.
Ensuite, le calcul du chemin (Path Computation) répondant aux différents critères et contraintes est réalisé. Cette détermination a lieu avant la création réelle (physique) du LSP. Ce calcul de chemin est effectué lors de la demande de création d’un nouveau LSP, lors d’une panne, ou lors d’une demande de réoptimisation.

Rôle du « Traffic Engineering » dans MPLS

Par TE-MPLS « Traffic Engineering MPLS », il faut comprendre, établissement de connexions « à la demande », ingénierie de trafic, gestion des routes, gestion des ressources, gestion de l’écoulement des flux de trafic à travers un réseau IP.
Le TE-MPLS introduit, la possibilité de faire suivre à des paquets IP un chemin à travers le réseau qui ne correspond pas forcément au plus court chemin de niveau 3 (issu du protocole de routage interne du réseau, i.e. RIP, OSPF, IS-IS, EIGRP, etc.), ceci afin de mieux en gérer les ressources. MPLS et ses LSPs constituent dès lors, grâce au TE-MPLS, un outil de gestion et d’optimisation de l’utilisation des ressources d’un réseau IP : les LSP sont placés par l’opérateur selon un chemin que celui-ci peut avoir préalablement choisi et déterminé.

Le TE-MPLS, permet donc de router les LSPs à travers le réseau en tenant compte de la disponibilité des ressources et du trafic courant et attendu. La classe de service et la qualité de service requises pour les données peuvent aussi être prises en compte.
Le TE-MLPS peut être réalisé manuellement ou suivant un processus automatisé, réagissant aux informations relatives à l’état du réseau (charges des liens, pannes, nouveaux trafics).
Grâce à son TE, MPLS permet de gérer des services nécessitant différents niveaux de priorités, tel le transport de voix ou de vidéo sur Internet, sans avoir recours à une politique de surdimensionnement des réseaux physiques.
Le TE-MPLS est donc une seconde valeur ajoutée à la solution MPLS. Il permet en effet à l’opérateur une gestion plus efficace de son réseau grâce à la possibilité de tailler des « LSP » en fonction des classes de services (CoS) et des FEC (Forwarding Equivalent Class).
Cela est en plus combiné à un système de priorités servant à favoriser l’accès aux ressources pour certains trafics. Cette « intelligence » offre au client final un réseau répondant à tous ses critères de QoS, une gestion et une optimisation des ressources pour l’opérateur.

Comment constituer une FEC ?

C’est une fonctionnalité qui permet de spécifier quels paquets vont être aiguillés dans un LSP. La FEC identifie l’ensemble des paquets IP qui seront envoyés sur un LSP. Une FEC est constituée d’un ensemble d’éléments. Chaque élément identifie des paquets qui peuvent utiliser ce LSP.
Les éléments de FEC sont des types suivants (la liste n’est pas exhaustive et on peut donc en avoir autant que désiré) :
• Famille d’adresses,
• Préfixe d’adresse (peut aller jusqu’à l’adresse complète),
• Une adresse complète de machine,
• Etc.
Entre deux LER MPLS, on peut donc regrouper tous les trafics dans une même FEC pour les envoyer dans le même LSP ou séparer certains de ces trafics dans des FEC différentes afin de les placer sur des LSPs différents. Cette dernière décomposition permet d’avoir une granularité très fine qui conduit à une meilleure répartition des trafics dans le cœur de réseau par autant de LSP que nécessaires. Les cas suivants peuvent se présenter :
• Un paquet peut être envoyé sur un LSP dont un élément de FEC indique le routeur Egress si et seulement si aucun autre LSP n’a comme FEC l’adresse de destination du paquet. L’adresse de destination du paquet est donc toujours prioritaire.

• Un paquet peut correspondre à deux FEC de deux LSPs distincts. Le premier contient une FEC ayant même préfixe d’adresse, et le second a une FEC donnant l’adresse complète. Dans ce cas c’est le LSP avec la FEC donnant l’adresse complète qui est choisi.
• Un paquet qui n’a pas la bonne adresse de machine destination (dans le cas où le LSP a une FEC qui positionne une adresse machine), ne peut être envoyé sur ce LSP même si cette adresse identifie un routeur Egress. C’est un cas important à noter car il signifie qu’on ne peut forcer un paquet à sortir par un autre Routeur Egress que celui prévu à priori.
En conséquence, un Ingress LER peut affecter un même label MPLS à des flots n’ayant pas la même destination comme représenté sur la figure ci-dessous.
Les possibilités offertes sont diverses, c’est à l’opérateur de définir son niveau de granularité. Ainsi plus la granularité est grande plus il pourra déployer des services spécifiques à chaque profil client mais plus le nombre de LSPs à gérer dans son réseaux sera contraignant. A l’inverse moins la granularité sera forte moins il aura de LSPs à gérer, par contre il ne pourra plus différencier ses services à souhait.
Le TE-MPLS est un outil qui permet à l’opérateur de trouver le juste milieu entre ces deux extrêmes afin de mieux gérer son réseaux.

MPLS et le Multicast

Avec la croissance des services utilisant la diffusion de données telles que la vidéo, la visioconférence, ou encore la voix sur IP, la consommation en bande passante est devenue un point cruciale de l’ingénierie de réseaux. Le service multicast est apparu comme la solution naturelle et adéquate pour garantir la QoS fournie aux utilisateurs grâce à la bande passante supplémentaire disponible sur le réseau.
Comme présenté précédemment MPLS grâce à son Traffic Engineering permet une gestion efficace de la bande passante du réseau. Il a fallu adapter le service multicast à MPLS [RFC3353] pour tirer profit de la cohabitation de ces deux technologies complémentaires. En effet les arbres multicast utilisés dans des réseaux MPLS permettent de minimiser l’utilisation de la bande passante et MPLS avec son Traffic Engineering permet de redistribuer celle-ci de façon appropriée aux autres utilisateurs.

MPLS peut être employé dans un réseau pour expédier le trafic unicast à l’aide de chemins explicites. De même MPLS peut être employé pour le trafic multicast en utilisant des arbres explicites. Mais le trafic multicast possède des caractéristiques spécifiques dues à la nature du routage multicast [OOM02]. En effet, le routage multicast d’Internet se base sur l’adresse IP multicast et c’est pourquoi il est très difficile d’agréger le trafic multicast puisque les destinataires appartenant au même groupe multicast peuvent être extrêmement dispersés. De plus, la structure arborescente du multicast pourrait nécessiter d’établir des LSP point à multipoint ou même des LSP multipoint à multipoint. Dans les implémentations actuelles de MPLS, les LSP point à point sont privilégiés même si MPLS n’exclut pas d’autres types de LSP.
Afin de construire les arbres multicast plusieurs protocoles ont été proposés. Nous citons parmi ceux ci :
PIM-MPLS [FAR00] qui utilise les messages d’adhésion du protocole multicast PIM-SM [EST98] pour distribuer des labels MPLS et construire ainsi l’arbre multicast MPLS (arbre multicast dont le routage est effectué au niveau de la couche « Liaison de données »). Les messages d’adhésion de PIM-SM sont modifiés pour porter un label MPLS alloué par un LSR en aval.
Aggregated Multicast [CUI03] suppose que plusieurs groupes multicast peuvent partager un même arbre multicast au lieu de construire un arbre multicast pour chaque groupe multicast. Ceci réduit le nombre d’états de routage dans les routeurs du domaine et, également, minimise la gestion de l’arbre. Chaque groupe multicast est associé à un arbre agrégé. Pour la gestion de l’arbre agrégé et l’association entre les groupes multicast et les arbres agrégés, une entité de gestion appelé tree manager est introduite.

MMT [DRAFT05] (MPLS multicast tree) construit un arbre multicast dans un réseau MPLS en considérant seulement les routeurs de branchement de cet arbre. En limitant la présence d’états de routage multicast aux routeurs de branchement, le protocole MMT convertit les flux multicast en multiple flux quasi-unicast. Dans MMT, au lieu de construire un arbre pour chaque canal multicast individuel dans le réseau cœur, on peut avoir plusieurs canaux multicast qui partagent des branches de leurs arbres. Les LSP unicast sont utilisés entre les routeurs de branchement de l’arbre multicast. Cette méthode, permet de réduire la quantité d’informations à mémoriser dans les routeurs et assure la résistance au facteur d’échelle.
Pour traiter le multicast nous avons retenu la solution des LSPs point à point pour la construction d’arbre multicast basée sur le protocole MMT. Nous proposons en outre, deux stratégies d’agrégation pour les arbres multicast.
Celles-ci sont illustrées dans la figure qui suit.

Formulation du problème de mono-routage des LSPs

Introduction

MPLS grâce à son Traffic Engineering permet de définir des chemins de routage explicites dans les réseaux IP (avec RSVP ou CR-LDP). C’est cette possibilité que nous allons exploiter pour fournir une solution au problème de mono-routage des LSPs dans les réseaux MPLS. En effet cette particularité permet de proposer un large panel d’algorithmes de routage dits «hors ligne» .
Dans ce qui suit nous allons illustrer le problème de mono-routage des LSPs sur un petit exemple.

Table des matières

INTRODUCTION GENERALE
A. EVOLUTION DES PROTOCOLES DE ROUTAGE
B. LA GESTION DE LA QOS
C. CONCEPTION DE TOPOLOGIES
D. PLAN DE LA THESE
CHAPITRE 1 – FORMULATION DU PROBLEME DE MONO-ROUTAGE DES LSPS DANS LE CONTEXTE DES RESEAUX IP/MPLS
A. INTRODUCTION
B. QUELQUES ELEMENTS SUR IP
B.1. L’adressage IP
B.2. Le routage dans les réseaux IP
B.2.1. Le protocole OSPF
B.2.2. Le protocole BGP
C. LE CONCEPT MPLS
C.1. Distribution des labels
C.1.1. Le protocole CR-LDP
C.1.2. Le protocole RSVP – TE
C.2. Définition des LSPs suivant les RFC de l’IETF
D. ROLE DU « TRAFFIC ENGINEERING » DANS MPLS
D.1. Comment constituer une FEC ?
E. MPLS ET LE MULTICAST
F. FORMULATION DU PROBLEME DE MONO-ROUTAGE DES LSPS
F.1. Introduction
F.2. Approche basée sur l’aspect bande passante
G. CONCLUSION
CHAPITRE 2 – LES RESEAUX MPLS ET GESTION DE LA QOS
A. INTRODUCTION
B. INTSERV
C. DIFFSERV
C.1. Les composants du modèle DiffServ
D. MPLS ET DIFFSERV
D.1. E-LSP (EXP-InferredPSC LSPs)
D.2. L-LSP (Label-Only-Inferred-PSC LSPs)
E. MODELISATION DE LA QOS DANS LES RESEAUX IP/MPLS
E.1. Introduction du Modèle QoS
E.1.1. Première formulation avec le modèle M/M/1/N
E.2. Les files à priorités
E.3. Les files WFQ
E.4. Deuxième formulation avec le modèle LLQ
E.4.1. Validation du modèle LLQ
F. FORMULATION MATHEMATIQUE
G. CONCLUSION
CHAPITRE 3 – METHODES D’OPTIMISATION NON LINEAIRE
A. INTRODUCTION
B. LA METHODE « DEVIATION DE FLOTS »
C. LA METHODE ILSP (ITERATIVE LOADING SHORTEST PATH)
C.1. Sur la convergence de l’algorithme ILSP
D. LA METHODE DU GRADIENT
E. LA METHODE DU GRADIENT CONJUGUE
F. LA METHODE DE FLETCHER REEVES
G. LA METHODE DE BROYDEN, FLETCHER, GOLDFARB, SHANNO (BFGS)
H. LA METHODE DU GRADIENT PROJETE
I. TESTS ET RESULTATS SUR L’OPTIMISATION NON LINEAIRE
I.1. Introduction
I.2. Comparaison des coûts des solutions
I.3. Comparaison du nombre d’itérations
I.4. Comparaison des temps d’exécution
J. CONCLUSION
CHAPITRE 4 – ETUDE DU ROUTAGE DES LSPS
A. INTRODUCTION
B. LA METHODE CISCO PCALC (PATH CALCULATION)
C. LA METHODE ILSP-OLS-ACO
C.1. ILSP ( Iterative Loading Shortest Path)
C.2. OLS (Optimal Load Sharing)
C.3. ACO (Ant Colony Optimization)
C.3.1. Introduction
C.3.2. Adaptation d’ACO au problème du mono-routage
D. TESTS ET RESULTATS
D.1. Approche bande passante
D.1.1. Comparaison des coûts
D.1.2. Comparaison des bandes passantes résiduelles
D.1.3. Comparaison du nombre de LSPs placés
D.1.4. Comparaison des temps d’exécution
D.2. Approche QoS
E. CONCLUSION
CHAPITRE 5 – SECURISATION DES RESEAUX MPLS
A. INTRODUCTION
B. LES MECANISMES DE PROTECTION
B.1. La protection de Chemin (Backup)
B.2. La protection par reroutage local (Fast-Reroute)
B.2.1. Etapes d’un Fast Reroute de lien
B.2.2. Etapes d’un Fast Reroute de nœud
B.2.3. Intérêts de l’approche Fast Reroute
B.3. La protection multi-niveaux (Multi-Layer)
C. SECURISATION DES LSPS PROTEGES
C.1. Protection par Backup
C.1.1. Approche basée sur l’algorithme de bhandari
C.1.2. Approche basée sur la méthode ILSP-OLS-ACO
C.1.3. Approche mixte
C.2. Protection par Reroutage local ( Fast Reroute)
C.3. Protection multi-niveaux ( Multi-layer)
D. CONCLUSION
CHAPITRE 6 – CONCEPTION DE TOPOLOGIE
A. INTRODUCTION
B. ETAT DE L’ART
C. FORMULATION DU PROBLEME DE CONCEPTION DU RESEAU D’ACCES
C.1. Formulation Mathématique du problème
C.1.1. Coût d’une solution
C.1.1.1. Coût des sites
C.1.1.2. Coût des liens
C.1.1.3. Coût des équipements
C.1.1.4. Coût global d’une solution
C.1.2. Analyse des équipements nécessaires dans un site
C.1.2.1. Notations
C.1.2.2. Contraintes
C.1.2.3. Coût des équipements
D. APPROCHE 1 : LA PROGRAMMATION LINEAIRE
E. DECOMPOSITION DU PROBLEME
E.1. Reformulation du problème
E.2. Résolution des configurations
E.2.1. Position du problème
E.2.2. Problème d’optimisation en nombres entiers
E.2.3. Formulation en programmation dynamique
E.2.4. Etat du système
E.2.5. Commandes
E.2.6. Dynamique du système
E.2.7. Coûts des décisions
E.2.8. Utilisation des configurations précédentes
E.2.9. Borne inférieure
E.2.10. Borne supérieure
E.2.11. Utilisation du principe d’optimalité
E.2.12. Un exemple
F. RELAXATION LAGRANGIENNE
G. APPROCHE 2 : HEURISTIQUE SEARCHCUTEXPLORE
H. APPROCHE EXACTE
H.1. Etat du système
H.2. Commandes
H.3. Dynamique du système
H.4. Coût des décisions
H.5. Principe de résolution : Branch and Cut
H.6. Une borne supérieure
H.7. Une borne inférieure
H.8. Des coupes sur les distances
H.9. Utilisation de la solution de l’heuristique searchCutExplore
I. TESTS ET RESULTATS
I.1. Topologies de tests
I.1.1. Topologie 1
I.1.2. Topologie 2
I.1.3. Topologie 3
I.1.4. Topologie 4
J. CONCLUSION
CONCLUSION GENERALE
BIBLIOGRAPHIE

Télécharger le rapport complet