Optimization of Packet Forwarding in Best-effort Routers

Optimisation de la réexpédition de paquets dans les routeurs best-effort

Miguel Ángel Ruiz Sánchez (1)

1 PLANETE - Protocols and applications for the Internet

The main task of a router is to forward packets through the networks to deliver them to their final destination. Since each packet must be treated individually, the performance of a router depends on the time to process each packet. To keep pace with increasing traffic and wide spectrum of traffic requirements, the packet forwarding capacity of routers need to be optimized. This thesis proposes several algorithms to optimize the performance of the packet forwarding process in best effort routers.
To forward packets, routers must make a forwarding decision. The operation of determining the forwarding information is based on the packet's destination address and it is called address lookup. We propose in this thesis two incremental update mechanisms for address lookup schemes based on the multibit-trie data structure. First, we determine the requirements to support incremental updates in multibit-tries based forwarding databases.Then, we propose algorithms and data structures to support incremental updates. In particular, we propose a data structure called Prefix Nesting bit vector, or PN bit vector for short. The PN bit vector encodes a set of prefixes and their nesting structure, for this information is necessary to support incremental updates. We present performance results of a C-language implementation of our scheme. Performance results are shown in terms of time for the search, insert and delete operations. Memory requirements are also shown.
A second contribution of this thesis is the introduction of a taxonomy and a framework of reference of existing fast address lookup schemes. Our taxonomy is based on the observation that the difficulty of the best prefix matching problem resides in its double dimension: value and length. In our analysis, we emphasize that to improve the performance of the address lookup operation, the different methods make a transformation of the original set of prefixes of the forwarding database. We state the different tradeoffs of the different transformation methods in terms of time and space and we compare the performance of the different schemes. While the most important aspect is the search operation, we also analyze the potential capabilities of the schemes to support incremental updates. We state that to support incremental updates, a mechanism must have additional data structures to keep track of the prefix transformation process.
A third contribution of this thesis is a mechanism to optimize the use of the buffer in routers to provide fiow isolation. First, we study the buffering functionality of IP routers. We find the desired properties of a router buffer system, then we design a mechanism based on these characteristics. We emphasize that buffers in routers have two functions: a multiplexing function and a burst absorbing function. Our mechanism, which we call MuxQ, is based on the idea of protecting the multiplexing function from the burst absorbing function by progressively and dynamically controlling the allocation of buffer space in a FIFO queue. MuxQ is a new queue management mechanism that provides fiow isolation by using a very simple algorithm and without using per-fiow queuing. We compare the performance of the MuxQ scheme to that of classical Drop-Tail and to that of other proposed schemes, including CSFQ and DRR which provides nearly perfect isolation by using per-fiow queuing. By keeping only limited fiow-state, our mechanism performs very much better than Drop-Tail. MuxQ achieves performance similar to that of CSFQ but MuxQ does not need modifications to the IP packet header as it is the case for CSFQ. Since MuxQ does not need modifications of the IP packet header and does not expect a special behavior from other routers, MuxQ can be deployed incrementally. We believe that MuxQ is an interesting approach to achieve a high degree of fiow isolation with respect to Drop-Tail by using a very simple algorithm

La tâche principale d'un routeur est d'acheminer des paquets jusqu'à leur destination finale en passant par les différents 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 tables 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érents 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 degré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, déployable et qui fournit un haut degré d'isolation de flux, tout en gardant une quantité limitée d'état.

Mots clés: Non disponible

Domaines: Réseaux et télécommunications [cs.NI]

Miguel Ángel Ruiz Sánchez. Optimization of Packet Forwarding in Best-effort Routers. Networking and Internet Architecture [cs.NI]. Université de Nice Sophia Antipolis, 2003. English. ⟨NNT : ⟩. ⟨tel-00408685⟩