Lamiae
Sommaire: Architecture parallèle pour l’accélération de la recherche dans les routeurs IP
Table des matières
LISTE DES FIGURES
LISTE DES TABLEAUX
LISTE DES ABREVIATIONS
Chapitre 1 : Introduction
1.1. Introduction
1.2. Protocole IP et adressage
1.2.1. Protocole IP
1.2.2. Evolution d’adressage IP
1.2.2.1. L’adressage avec classes
1.2.2.1.1. Structure de l’adresse IP
1.2.2.1.2. Classes d’adresses IP
1.2.2.1.3. Adresses IPv4
1.2.2.1.4. Adresses IPv6
1.2.2.1.5. Sous-réseaux
1.2.2.2. Structuration des adresses et agrégation
1.2.2.2.1. Evolution des tailles des tables de routage
1.2.2.2.2. CIDR (Classless Inter-Domain Routing)
1.3. Recherche d’information de routage dans un routeur IP
1.3.1. Routeurs IP
1.3.2. Table de routage
1.3.3. Consultation d’adresses IP (Notre contribution)
1.3.3.1. Consultation d’adresses IP dans le cas d’adressage en classes
1.3.3.2. Consultation d’adresses IP dans le cas d’adressage sans-classes
1.4. Difficulté de recherche des informations de routage
1.5. Contributions
1.6. Plan de la thèse
1.7. Conclusion
Chapitre 2 : Travaux dans le domaine
2.1. Introduction
2.2. Solutions logicielles et structures de données utilisées
2.2.1. Recherche linéaire
2.2.1.1. Recherche linéaire basée sur les longueurs en utilisant les tables de hachage
2.2.2. Algorithmes de recherche binaires basés sur des structures arborescentes
2.2.2.1. Algorithmes de recherche binaires basés sur les bits des préfixes
2.2.2.2. Algorithmes de recherche binaires basés sur les points d’extrémités des plages d’adresses IP (Ranges search)
2.2.2.3. Algorithmes de recherche binaires basés sur les valeurs des préfixes
2.3. Solutions matérielles 1. Mémoire adressable par contenu CAMs et Ternary CAMs
2.3.1.1. Utilisation des CAMs et TCAMs dans les routeurs Internet
2.3.1.2. Architecture des CAMs / TCAMs
2.3.1.3. Recherche dans les CAMs / TCAMs
2.3.1.4. Architectures des CAMs / TCAMs proposées pour l’opération de lookup
2.3.2. Mémoires cache
2.3.3. Architectures multiprocesseurs
2.3.3.1. Manipulation des tables de routage en parallèle
3.4. Conclusion
Chapitre 3 : Parallélisme et architectures parallèles
3.1. Introduction
3.2. Origine du parallélisme
3.3. Sources de parallélisme
3.4. Limites du parallélisme
3.5. Architectures parallèles
3.5.1. Classifications des architectures parallèles
3.5.1.1. Classification de Flynn
3.5.1.1.1. Architecture SISD (Single Instruction stream, Single Data stream)
3.5.1.1.2. Architecture SIMD (Single Instruction stream, Multiple Data stream)
3.5.1.1.3. Architecture MISD (Multiple Instruction stream, Single Data stream)
3.5.1.1.4. Architecture MIMD (Multiple Instructions stream, Multiple Data stream)
3.5.1.2. Classification de Duncan
3.5.2.1. Architectures synchrones
3.5.2.2. Architectures asynchrones
3.5.2.3. Architectures mixtes
3.6. Modèles de programmation parallèle
3.6.1. Parallélisme de données
3.6.2. Parallélisme de contrôle
3.7. Etapes de développement d’une application exécutée sur une architecture parallèle
3.8. Conclusion
Chapitre 4 : L’architecture parallèle « PARIR »
4.1. Introduction
4.2. Conception assisté par ordinateur
4.3. Modèles
4.4. Synthèse et Simulation
4.4.1. Validation et vérification de description HDL
4.4.1.1. Simulation fonctionnelle
4.4.2. Synthèse
4.5. Langages de description de matériel
4.6. Parallélisation des données par la décomposition de la table de routage
4.6.1. Terminologie et définitions
4.6.2. Algorithme de décomposition de la table de routage
4.6.3. Procédure d’expansion des préfixes
4.6.4. Analyse des résultats
4.7. Structure de données et algorithme parallèle
4.7.1. Structure de données
4.7.2. Algorithme parallèle
4.8. L’architecture parallèle « PARIR »
4.8.1. Description de l’architecture « PARIR »
4.8.2. Expérimentations et résultats
4.9. Modélisation de notre système
4.9.1. Décomposition du système en modules
4.9.2. Le langage VHDL
4.9.2.1. Flot de conception basé sur le VHDL
4.9.2.2. Organisation d’un modèle VHDL
4.9.2.2.1. Unités de conception
4.9.2.2.2. Entité de conception
4.9.3. Modélisation et simulations des modules de notre système
4.9.3.1. Le sélecteur
4.9.3.2. Le composant de recherche
4.9.3.3. Le système complet
4.10. Conclusion
Chapitre 5 : Solutions logicielles proposées
5.1. Introduction
5.2. Routeur avec une table de routage cache
5.2.1. Structure de la table de routage
5.2.1.1. Table de routage principale
5.2.1.2. Table de routage cache
5.2.2. Algorithme de remplacement des entrés de la table cache (la moins récemment utilisée)
5.2.3. Ordonnancement de la table cache
5.2.4. Expérimentation
5.3. Algorithme de recherche des informations de routage par arbre binaire à contenu dynamique (ABCD)
5.3.1. Description de l’arbre binaire à contenu dynamique (ABCD)
5.3.1.1. Structure des nœuds de l’arbre ABCD
5.3.1.2. Construction de l’arbre ABCD
5.3.2. Algorithme de recherche du plus long préfixe correspondant dans l’arbre ABCD
5.3.3. Expérimentation et résultats
5.4. Conclusion
Chapitre 6 : Conclusion et perspectives
Bibliographie
Extrait du mémoire Architecture parallèle pour l’accélération de la recherche dans les routeurs IP
Chapitre 1
Introduction
Le routeur prend l’adresse IP de destination d’un paquet et cherche dans sa table de routage les informations de routage, cette opération s’appelle consultation d’adresse IP (address lookup). Dans ce contexte, notre travail s’oriente vers l’accélération de cette opération. Dans ce chapitre nous présentons le contexte de travail qui est la recherche d’information de routage dans les routeurs Internet et nous présentons les motivations, les objectifs et les contributions de cette thèse.
1.1. Introduction
Un réseau peut être vu comme un ensemble de ressources mises en place pour offrir un ensemble de services. Dans l’Internet, la communication entre machines est effectuée en utilisant les paquets d’informations. Une fois que les machines émettent leurs paquets dans le réseau, ce sont les routeurs qui retransmettent ces paquets sur les liaisons des réseaux pour les acheminer vers leurs destinations finales. La croissance du nombre d’utilisateurs d’Internet et l’arrivée de nouveaux services et traitements multimédia ont eu comme conséquence l’augmentation des tailles des tables de routages des routeurs et la complexité de l’opération d’acheminement des paquets de données.
Il y a trois facteurs principaux à être considérés dans les réseaux IP pour maintenir un bon service: Liens avec une grande largeur de bande, commutation de données à grande vitesse et taux élevés de l’expédition de paquets.
Actuellement, les liens optiques de transmission de données et la technologie courante de commutation de données permettent la manipulation facile des deux premiers facteurs. Par conséquent, le déploiement des routeurs de rendement élevé pour expédier les paquets IP est la clef au succès des routeurs IP.
Dans l’Internet, chaque paquet est acheminé indépendamment des autres. Ce mode d’opération est connu comme le mode datagramme. Le mode datagramme permet d’offrir un service robuste, car les routeurs peuvent adapter l’acheminement des paquets lors des changements dans la topologie des réseaux. Cependant, le mode datagramme nécessite que les routeurs aient la capacité suffisante pour traiter tous les paquets arrivant à leurs ports d’entrée.
Ainsi, avec l’accroissement du trafic, il est nécessaire d’optimiser la performance des routeurs lors de l’acheminement des paquets.
………….
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Mémoire Online: Architecture parallèle pour l’accélération de la recherche dans les routeurs IP ( 1.4 MO) (Cours PDF)
