Abstracto

Mapeo de memoria escalable y eficiente basado en árboles en enrutadores virtuales

Deepika V, Geetha SK y Varunkumarr CV

Muchos algoritmos populares para el reenvío y filtrado rápido de paquetes se basan en la estructura de datos de árbol. Algunos ejemplos son los algoritmos de búsqueda de IP y clasificación de paquetes basados ??en trie. Con el reciente interés en la virtualización en malla, la capacidad de ejecutar múltiples ejemplos de enrutadores virtuales en una plataforma de enrutador personal común es absolutamente vital. Un problema de escalamiento significativo es la cantidad de ejemplos de enrutadores virtuales que se pueden ejecutar en la plataforma. Un factor limitante es la disponibilidad de memoria de alta velocidad y cachés disponibles para almacenar los grupos de datos de reenvío y filtrado de paquetes. Un objetivo ideal es lograr un buen escalamiento mientras se mantiene un aislamiento total entre los enrutadores virtuales. Aunque el aislamiento total requiere mantener estructuras de datos distintas en la memoria de alta velocidad para cada enrutador virtual. En este documento, estudiamos el caso en el que se permite compartir algunos de los grupos de datos de reenvío y filtrado y desarrollamos algoritmos para combinar los intentos utilizados para la búsqueda de IP y la clasificación de paquetes de forma específica. Desarrollamos un método llamado trenzado de trie que nos permite combinar intentos de los grupos de datos de diferentes enrutadores virtuales en un solo trie compacto. Se ofrecen dos algoritmos de trenzado óptimos y un algoritmo heurístico más rápido, y se demuestra su eficacia utilizando conjuntos de hechos y cifras del mundo real.