Soutenance mémoire
Modélisation standard des couches de protocoles
Les protocoles de communications utilisés peuvent être groupés suivant leur fonctionnalités et leur niveau de fonctionnement. On utilise pour cela des modèles représentatifs des différentes couches réseau. L’indépendance des couches y est assurée : un élément appartenant à une couche donnée ne doit pas intervenir sur une autre couche, et ne peut communiquer qu’avec un élément de même niveau. Les couches sont traversées successivement. Lorsqu’un message est émis par une application, les données sont transmises de la couche la plus haute vers la couche la plus basse, en traversant l’intégralité des couches intermédiaires.
Le modèle OSI est un modèle purement théorique normalisé par l’Organisation internationale de normalisation (ISO) en 1977. Il prend en compte l’hétérogénéité des équipements et définit comment ces derniers devraient communiquer. Le modèle TCP/IP est calqué sur l’implémentation réelle des protocoles TCP et IP . Ce modèle est maintenu par l’organisation de standardisation nommée Internet Engineering Task Force (IETF). Il s’est progressivement imposé comme modèle de référence en lieu et place du modèle OSI. Il agrège certaines couches du modèle OSI , pour n’en conserver que 4 :
1. Accès réseau : regroupe les couches 1 et 2 du modèle OSI. Elle permet de transmettre un paquet IP sur le réseau.
2. Internet : cette couche gère l’acheminement des paquets dans les réseaux (potentiellement hétérogènes). Elle repose sur le protocole IP. Elle correspond à la couche 3 du modèle OSI.
3. Transport : correspondant à la couche 4 du modèle OSI, elle permet d’assurer la communication des données entre deux entités. TCP et UDP sont les deux principaux protocoles que l’on retrouve sur cette couche.
4. Application : regroupe les couches 5, 6 et 7 du modèle OSI. Ce regroupement s’explique par le fait que les couches 5 et 6 du modèle OSI sont en pratique très peu différenciées de la couche 7.
Protocole IP et routage
IP est un protocole permettant l’adressage et le routage des paquets. L’adresse IP permet d’identifier de manière unique une interface dans une machine connectée sur un réseau. Les paquets IP sont composés d’une entête, comportant principalement les adresses IP source et destination, et d’une zone réservée au transport des données de l’utilisateur.
Certaines machines, que l’on nomme routeurs, sont dotées de plusieurs interfaces réseaux, et sont chargées de transmettre et de router les paquets qu’elles reçoivent. Ces composants sont des points d’aiguillage qui forment l’architecture du réseau. À cet effet, chaque routeur dispose d’une table de routage lui permettant de définir sur quelle interface il devra transmettre le paquet qu’il a reçu, pour qu’il atteigne sa destination. Chaque paquet est alors routé de proche en proche, jusqu’à atteindre sa destination. Les échanges d’informations entre routeurs sont codifiées par les protocoles de routage qu’utilise le réseau. Ces échanges permettent aux routeurs de construire une image du réseau, et donc une table de routage. Les réseaux IP composant l’Internet sont composés de groupes distincts de routeurs, que l’on nomme Système Autonome (AS). Chaque AS regroupe des routeurs placés sous la même autorité administrative, et est géré indépendamment. Le nombre d’AS ne cesse de croître, et en début 2015, le nombre d’AS présents sur Internet est d’environ 50000 [112].
La construction de la table de routage utilisée par le routeur pour transmettre les paquets s’effectue différemment à l’intérieur d’un AS (on parle de routage intra-domaine) et entre les différents AS (routage inter-domaine).
Routage intra-domaine avec IGP
Le routage à l’intérieur même d’un AS, aussi appelé routage intra-domaine, s’effectue à l’aide de protocoles dédiés, que l’on nomme Interior Gateway Protocol (IGP). On peut alors citer les protocoles Open Shortest Path First (OSPF) [78], Intermediate System to Intermediate System (IS-IS) [86] et dans un moindre mesure Routing Information Protocol (RIP) [71]. Nous présentons ici le protocole OSPF . Son fonctionnement est très similaire à celui du protocole IS-IS. OSPF est un protocole de routage à état de lien, qui fut originellement crée par l’IETF pour remplacer le protocole RIP. Les routeurs utilisant OSPF s’échangent l’état des liens qui leur sont rattachés. Cette communication permet à chaque routeur de construire une image du réseau, qui n’est mise à jour qu’en cas de modification de topologie (comme la suppression et l’ajout de liens ou de nœuds). OSPF procède malgré tout à un envoi périodique de l’intégralité des informations d’états des liens (toutes les 30 minutes par défaut).
Comme le nom du protocole l’indique, les paquets sont routés sur des plus courts chemins. La table de routage de chaque routeur est donc déterminée à partir d’un algorithme de plus courts chemins (e.g. algorithme de Dijkstra [37]). La longueur d’un chemin est définie comme la somme des longueurs des liens parcourus, tandis que la longueur d’un lien (que l’on nomme également métrique ou poids OSPF) peut-être fixée arbitrairement par le gestionnaire du réseau (à la seule condition d’être un nombre entier positif). Les poids OSPF sont souvent fixés à une valeur égale à 1 (la longueur d’un chemin représente alors le nombre de sauts), mais certains opérateurs comme CISCO, proposent d’utiliser un poids tenant compte de la capacité du lien (poids = 10⁸ / capacité). Ces poids influencent la longueur des chemins, donc les plus courts chemins et le routage qui en résulte. Lorsque plusieurs routes de même longueur sont disponibles, un partage de charge équitable entre les chemins est employé : s’il existe n chemins d’égales longueurs reliant le routeur courant s à une destination t, alors chaque flux passant par s à destination de t avec une demande d sera routé sur les n chemins, chacun faisant alors transiter une demande égale à d/n.
Routage inter-domaine avec EGP
Le routage entre AS est assuré par un Exterior Gateway Protocol (EGP), dont le plus communément utilisé est Border Gateway Protocol (BGP). Il s’agit d’un protocole dont la scalabilité est reconnue, BGP étant en effet responsable de la propagation des routes Internet à l’échelle mondiale. Il ne tient pas compte de la structure interne des AS (cette partie étant dévolue aux IGP). Les voisins BGP échangent toutes leurs informations dès leur première connexion en utilisant le protocole TCP . Ensuite, seules les éventuelles informations de mise à jour sont transmises, si une route est modifiée ou ajoutée. Contrairement à OSPF, le protocole BGP ne procède pas à un envoi périodique des informations. La propagation des routes de bout en bout s’effectue plus exactement grâce à deux protocoles distincts : BGP externe (e-BGP) pour la communication de routes directement entre routeurs de frontière d’AS différents, et BGP interne (i-BGP) pour l’échange de routes passant à l’intérieur des AS.
|
Table des matières
1 Introduction
1.1 Plan de la thèse
2 Quelques éléments sur les réseaux de communications IP
2.1 Introduction
2.2 Modélisation standard des couches de protocoles
2.3 Protocole IP et routage
2.3.1 Routage intra-domaine avec IGP
2.3.2 Routage inter-domaine avec EGP
2.4 La technologie MPLS
2.5 Protocoles de la couche transport
2.5.1 UDP
2.5.2 TCP
2.6 Métriques de qualité de service dans les réseaux
2.6.1 Latence
2.6.2 Taux de perte
2.6.3 Bande passante disponible
2.7 Quelques techniques de mesure de bande passante utilisables coté client
2.7.1 Techniques d’estimation passives pour le protocole TCP
2.7.2 Techniques de mesure actives
2.8 Conclusion
3 Techniques d’optimisation
3.1 Introduction
3.2 Optimisation linéaire
3.2.1 Programmation linéaire
3.2.2 Programmation linéaire en nombre entiers
3.3 Optimisation non-linéaire
3.3.1 Méthode du gradient
3.3.2 Méthode du gradient conjugué
3.3.3 Méthode du gradient projeté
3.4 Méthodes heuristiques et métaheuristiques
3.4.1 Algorithme glouton
3.4.2 Recherche locale
3.4.3 Optimisation par colonie de fourmis
4 Optimisation dynamique des réseaux OSPF
4.1 Introduction
4.2 Définition du problème
4.3 Algorithme en ligne
4.3.1 Estimation de la matrice de trafic
4.3.2 Optimisation robuste des poids des liens
4.3.2.1 Incrément minimal de poids ∆`
4.3.2.2 Évaluation de la charge des liens au pire cas
4.3.3 Réduction du nombre de changement de poids
4.4 Résultats
4.4.1 Trafics simulés
4.4.1.1 Moyenne temporelle du taux de congestion réseau
4.4.1.2 Évolution temporelle des taux de congestion réseau
4.4.1.3 Temps d’exécution
4.4.2 Trafics réels
4.4.3 Panne de liens
4.5 Conclusion
5 Optimisation du placement des LSP dans les réseaux MPLS
6 Conclusion
