{"id":2944,"date":"2022-08-14T06:15:07","date_gmt":"2022-08-14T06:15:07","guid":{"rendered":"https:\/\/pcyti.izt.uam.mx\/?p=2944"},"modified":"2022-08-14T06:15:07","modified_gmt":"2022-08-14T06:15:07","slug":"diseno-de-un-algoritmo-para-la-transformacion-de-prefijos-de-una-tabla-de-ruteo-ip","status":"publish","type":"post","link":"https:\/\/pcyti.izt.uam.mx\/?p=2944","title":{"rendered":"Dise\u00f1o de un algoritmo para la transformaci\u00f3n de prefijos de una tabla de ruteo IP"},"content":{"rendered":"\n

 Descargar versi\u00f3n PDF<\/a><\/p>\n\n\n\n

Profesores<\/strong>: Dr. Miguel \u00c1ngel Ruiz S\u00e1nchez<\/a> y Dr. C\u00e9sar Jalpa Villanueva<\/a><\/p>\n\n\n\n

Resumen<\/strong>: Internet es una red mundial de computadoras que intercambian informaci\u00f3n 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\u00f3sito general y usan la red para enviar o recibir informaci\u00f3n; 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\u00f3n del Host de origen al Host destino final; estas computadoras se conocen con el nombre de ruteadores. Es un hecho que el n\u00famero de usuarios y de aplicaciones de Internet no ha dejado de crecer. Esto ha provocado un r\u00e1pido crecimiento del tr\u00e1fico 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\u00e1fico de paquetes. As\u00ed, hoy en d\u00eda 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\u00fasqueda de informaci\u00f3n en sus tablas de ruteo; proceso que tienen que realizar con cada uno de los paquetes que reciben. M\u00e1s espec\u00edficamente, cuando un ruteador recibe un paquete, el ruteador debe decidir el pr\u00f3ximo destino intermedio o final en el camino del Host origen al Host destino. Esta decisi\u00f3n toma en cuenta, por un lado la direcci\u00f3n destino final que lleva el propio paquete, y por otro lado la informaci\u00f3n contenida en la tabla de ruteo del ruteador en cuesti\u00f3n. A este proceso que efect\u00faan los ruteadores se le conoce como proceso de reexpedici\u00f3n de paquetes. Hay que hacer notar que este proceso de reexpedici\u00f3n de paquetes no contempla la recopilaci\u00f3n de la informaci\u00f3n de la tabla de ruteo; dicha recopilaci\u00f3n la realiza el ruteador pero por medio de otro proceso que se conoce como el proceso de ruteo. Una de las operaciones cr\u00edticas en el proceso de reexpedici\u00f3n de paquetes es la b\u00fasqueda en la tabla de ruteo. Una tabla de ruteo contiene esencialmente en cada entrada un prefijo de direcciones y su correspondiente informaci\u00f3n de ruteo. La b\u00fasqueda en una tabla de ruteo es complicada, por un lado por el gran n\u00famero 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\u00fasqueda del prefijo m\u00e1s largo y no una b\u00fasqueda exacta. Un factor importante a tomar en cuenta es que es necesario que esta b\u00fasqueda sea cada vez m\u00e1s r\u00e1pida 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\u00fasqueda en tablas de ruteo. Un gran n\u00famero de estas propuestas necesitan como un paso inicial la transformaci\u00f3n del conjunto de prefijos de la tabla de ruteo original en otro conjunto equivalente; es decir, en otro conjunto con la misma informaci\u00f3n de ruteo pero con caracter\u00edsticas que permiten mejorar los tiempos de busqueda. En esta propuesta de trabajo de investigaci\u00f3n, nosotros estamos interesados en un tipo de transformaci\u00f3n espec\u00edfica. Esta transformaci\u00f3n consiste en obtener un conjunto de prefijos disjuntos, a partir del conjunto original de prefijos. En la literatura, este paso previo de transformaci\u00f3n se da por hecho y no se especifica la manera en que realmente se efect\u00faa. Adem\u00e1s de que no se toma en cuenta el impacto que tiene este paso de transformaci\u00f3n de prefijos en el desempe\u00f1o del esquema total.<\/p>\n\n\n\n

En esta propuesta de trabajo de investigaci\u00f3n, se dise\u00f1ar\u00e1 un algoritmo para realizar la transformaci\u00f3n del conjunto de prefijos de una tabla de ruteo en otro conjunto de prefijos disjuntos pero que preserve la informaci\u00f3n de ruteo original. Adem\u00e1s, se estudiar\u00e1 el impacto de este paso en por lo menos uno de los esquemas propuestos en la literatura que usan este paso previo. Tambi\u00e9n se estudiar\u00e1 la escalabilidad del algoritmo de transformaci\u00f3n propuesto con respecto a la longitud de los prefijos IP; m\u00e1s espec\u00edficamente con los prefijos en IPv6 cuyo arribo es cada vez m\u00e1s cercano.<\/p>\n\n\n\n

Objetivo general<\/strong><\/p>\n\n\n\n