Abstract FR:

La tâche principale d'un routeur est d'acheminer des paquets jusqu'à leur destination finale en passant par les différentes réseaux. Comme chaque paquet est traité individuellement, la performance d'un routeur dépend du temps nécessaire pour traiter chaque paquet. Due à la croissance et à la diversité du trafic dans l'Internet, le traitement nécessaire pour acheminer des paquets doit être optimisé. Cette thèse propose des algorithmes pour optimiser la performance du traitement de paquets lors de leur acheminement dans les routeurs best-effort. Pour acheminer (réexpédier) des paquets, un routeur doit tout d'abord rechercher l'information de routage correspondant à chaque paquet. La recherche d'information de routage est basée sur l'adresse destination du paquet et elle s'appelle consultation d'adresse. Nous proposons dans cette thèse deux mécanismes pour la mise à jour incrémentale des table de routage basées sur des tries multibit. Tout d'abord, nous déterminons les conditions nécessaires pour supporter des mises à jour incrémentales dans les tries multibit. À partir de ces conditions, nous proposons des algorithmes et des structures de données pour effectuer ces mises à jour incrémentales. En particulier, nous proposons une structure de données que nous appelons le vecteur de bits PN (pour prefix nesting en anglais). Le vecteur de bits PN code un ensemble de préfixes et leurs relations d'inclusion, car cette information est nécessaire pour supporter des mises à jour incrémentales. Nous évaluons la performance de nos mécanismes implémentés en langage C. Nous présentons les performances de nos mécanismes pour les opérations de recherche, insertion et suppression. Nous présentons également les besoins en termes de mémoire. Une deuxième contribution de cette thèse est l'introduction d'une taxonomie et un cadre de référence pour les algorithmes de consultation rapide d'adresse IP. Notre taxonomie est basée sur l'observation que la difficulté de trouver le plus long préfixe commun avec l'adresse destination est sa double dimension: valeur et longueur. Lorsque nous présentons et classifions les différents mécanismes, l'accent est mis sur le type de transformation que l'on effectue sur l'ensemble de préfixes pour chaque mécanisme. Cette approche unificatrice que nous proposons nous permet de comprendre et de comparer les compromis des différentes mécanismes. Nous comparons les mécanismes en termes de leur complexité en temps et en espace. Nous comparons aussi leur performance en mesurant le temps de l'opération de recherche. Ces mesures sont réalisées sur une même plateforme et en utilisant une vrai table de routage. Une troisième contribution de cette thèse est un mécanisme qui optimise l'usage des buffers dans les routeurs pour offrir un haut dégrée d'isolation entre flux. Tout d'abord, nous étudions la fonctionnalité des buffers dans les routeurs et nous déterminons les caractéristiques souhaitables des buffers dans les routeurs. Ensuite nous proposons MuxQ un mécanisme qui fournit un haut degré d'isolation entre flux. MuxQ est basé sur l'idée de protéger la fonction de multiplexage de la fonction d'absorption de rafales d'un buffer. Nous évaluons MuxQ en utilisant le simulateur ns-2. En particulier, nous étudions la capacité de MuxQ pour isoler différent types de flux. Nous comparons les performances de notre mécanisme avec celles des mécanismes Drop-Tail, CSFQ, FRED et DRR. Nous présentons les résultats de simulations avec des conditions de trafic différentes. MuxQ est un mécanisme simple, deployable et qui fournit un haut degré d'isolation de flux, tout en gardant une quantité limitée d'état.