Optimisation des ressources de réseaux hétérogènes avec coeur de réseau MPLS

Optimisation des ressources de réseaux hétérogènes avec coeur de réseau MPLS

FORMULATION DU PROBLEME DEMONOROUTAGE DES LSPS DANS LE CONTEXTE DES RESEAUX IP/MPLS

Introduction

Un réseau peut être vu comme un ensemble de ressources mises en place pour offrir un ensemble de services. C’est l’évolution des services et des trafics qui en découlent qui a piloté, dans les dernières années, l’évolution technologique qui a permis d’augmenter la capacité et les fonctionnalités des réseaux. Ainsi, par exemple, le succès des services de l’Internet a engendré une explosion de trafics qui a mené les opérateurs à utiliser de nouvelles technologies dans le cœur de réseau tel que l’IP (Internet Protocol) sur ATM (Asynchronous Transfer Mode), le PoS (Packet over Sonet/SDH) , ou encore MPLS (Multi Protocol Label Switching). Dans ce qui suit nous allons nous intéresser à IP et MPLS. Nous commencerons par décrire les réseaux traditionnels fédérés par IP. Nous introduirons par la suite le protocole MPLS et ce qu’il apporte comme avantage par rapport à IP. Nous allons aussi souligner les interactions entre ces deux protocoles ainsi que leur mode de cohabitation. Comme nous l’avons présenté la gestion des ressources d’un réseau est devenue un point crucial dans le processus de planification. A la lumière des nouvelles possibilités offertes par la technologie MPLS nous abordons dans ce chapitre ce problème. Nous proposons une première formulation du problème de mono-routage des LSPs dans les réseaux MPLS. Cette formulation est basée sur l’approche bande passante.

Quelques éléments sur IP

IP est un protocole qui permet l’adressage des machines et le routage des paquets de données [RFC791]. Il correspond à la couche 3 (réseau) de la hiérarchie des couches ISO. Son rôle est d’établir des communications sans connexion de bout en bout entre des réseaux, de délivrer des trames de données (datagram) « au mieux (best effort) », et de réaliser la fragmentation et le ré-assemblage des trames pour supporter des liaisons n’ayant pas la même MTU (Maximum Transmission Unit, c’est-à-dire la taille maximum d’un paquet de donnée).

L’adressage IP

Un des éléments essentiels d’IP est la couverture mondiale qu’assure le protocole. Ceci est fait grâce à une gestion d’adresses uniques. L’adressage IP permet d’identifier de façon unique une interface dans une machine connectée à un réseau. Une machine ayant plusieurs interfaces est communément appelée un routeur. Elle est capable de recevoir et de renvoyer des paquets de données par le biais de différentes interfaces. Elle utilise pour cela une table de routage qui, dans sa version la plus simple, contient un certain nombre d’adresses internet complètes ou sous forme de masques (liste non exhaustive), l’interface à utiliser pour atteindre chacune d’elles, et une ou plusieurs interfaces par défaut vers lesquelles envoyer les paquets d’adresse inconnue. Un paquet IP est composé d’une en-tête et de données. La zone Data (Données) contient les données utiles provenant des applications (couches supérieures) à transférer via le réseau. Les informations principales contenues dans l’entête d’un paquet IP sont : les adresses de la source et de la destination, le type de service (ToS), et la longueur totale du paquet.

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 (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.

Table des matières

REMERCIEMENTS
TABLE DES FIGURES
LISTE DES TABLEAU
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
TABLE DES ABBREVIATIONS
BIBLIOGRAPHIE