Diseño de un algoritmo para la transformación de prefijos de una tabla de ruteo IP
2012Profesores: Dr. Miguel Ángel Ruiz Sánchez y Dr. César Jalpa Villanueva
Resumen: Internet es una red mundial de computadoras que intercambian información por medio de paquetes definidos por el protocolo IP. Dichas computadoras pueden ser de 2 tipos. Un primer tipo se caracteriza por ejecutar aplicaciones de propósito general y usan la red para enviar o recibir información; las computadoras que pertenecen a este tipo se les conoce como Hosts. El segundo tipo de computadoras de Internet se caracteriza por estar exclusivamente dedicadas a encaminar los paquetes de información del Host de origen al Host destino final; estas computadoras se conocen con el nombre de ruteadores. Es un hecho que el número de usuarios y de aplicaciones de Internet no ha dejado de crecer. Esto ha provocado un rápido crecimiento del tráfico de paquetes que circula por los enlaces y ruteadores de Internet. Afortunadamente, la capacidad de los enlaces ha mantenido un crecimiento suficiente para poder lidiar con este crecimiento del tráfico de paquetes. Así, hoy en día se cuenta con enlaces con capacidades de varias decenas de gigabit por segundo. Desafortunadamente, no podemos decir lo mismo de la capacidad de proceso de paquetes por parte de los ruteadores. En los ruteadores, el cuello de botella principal es la búsqueda de información en sus tablas de ruteo; proceso que tienen que realizar con cada uno de los paquetes que reciben. Más específicamente, cuando un ruteador recibe un paquete, el ruteador debe decidir el próximo destino intermedio o final en el camino del Host origen al Host destino. Esta decisión toma en cuenta, por un lado la dirección destino final que lleva el propio paquete, y por otro lado la información contenida en la tabla de ruteo del ruteador en cuestión. A este proceso que efectúan los ruteadores se le conoce como proceso de reexpedición de paquetes. Hay que hacer notar que este proceso de reexpedición de paquetes no contempla la recopilación de la información de la tabla de ruteo; dicha recopilación la realiza el ruteador pero por medio de otro proceso que se conoce como el proceso de ruteo. Una de las operaciones críticas en el proceso de reexpedición de paquetes es la búsqueda en la tabla de ruteo. Una tabla de ruteo contiene esencialmente en cada entrada un prefijo de direcciones y su correspondiente información de ruteo. La búsqueda en una tabla de ruteo es complicada, por un lado por el gran número de entradas que tiene dicha tabla (del orden de 400 000 en los grandes ruteadores), y por otro lado por el hecho de que se necesita una búsqueda del prefijo más largo y no una búsqueda exacta. Un factor importante a tomar en cuenta es que es necesario que esta búsqueda sea cada vez más rápida a medida que Internet crece y la tasa de paquetes por unidad de tiempo que recibe un ruteador aumenta. En la literatura se han propuesto varios algoritmos y estructuras de datos para optimizar en tiempo y en espacio esta búsqueda en tablas de ruteo. Un gran número de estas propuestas necesitan como un paso inicial la transformación del conjunto de prefijos de la tabla de ruteo original en otro conjunto equivalente; es decir, en otro conjunto con la misma información de ruteo pero con características que permiten mejorar los tiempos de busqueda. En esta propuesta de trabajo de investigación, nosotros estamos interesados en un tipo de transformación específica. Esta transformación consiste en obtener un conjunto de prefijos disjuntos, a partir del conjunto original de prefijos. En la literatura, este paso previo de transformación se da por hecho y no se especifica la manera en que realmente se efectúa. Además de que no se toma en cuenta el impacto que tiene este paso de transformación de prefijos en el desempeño del esquema total.
En esta propuesta de trabajo de investigación, se diseñará un algoritmo para realizar la transformación del conjunto de prefijos de una tabla de ruteo en otro conjunto de prefijos disjuntos pero que preserve la información de ruteo original. Además, se estudiará el impacto de este paso en por lo menos uno de los esquemas propuestos en la literatura que usan este paso previo. También se estudiará la escalabilidad del algoritmo de transformación propuesto con respecto a la longitud de los prefijos IP; más específicamente con los prefijos en IPv6 cuyo arribo es cada vez más cercano.
Objetivo general
- Diseñar un algoritmo para obtener un conjunto de prefijos disjuntos a partir del conjunto de prefijos originales de una tabla de ruteo IP
Objetivos específicos
- Diseñar e implementar un algoritmo para obtener un conjunto de prefijos disjuntos de una tabla de ruteo IP
- Estudiar el impacto que este paso de transformación provoca en por lo menos uno de los esquemas propuestos en la literatura que usan este paso previo
Ultima actualización 14/08/2022 por pcyti