Algoritmos de búsqueda y actualización de información para ruteadores IP - Buendía Gómez, Joel Yazbek (Universidad Autónoma Metropolitana, 2009)
En esta tesis se propone un nuevo algoritmo de búsqueda para encontrar el prefijo de red que coincida con los bits más significativos de la dirección IP de destino y además sea el más largo que exista en la tabla de ruteo. En el esquema del protocolo IP, después de quitar las clases e implementar CIDR, aparece el problema de no tener información acerca de la longitud del prefijo de red. El algoritmo UAM propone que el problema de buscar prefijos de red se cambie por una búsqueda exacta, es decir, convertimos la búsqueda de prefijos aplicando una función que cambia nuestro espacio de búsqueda. La idea principal es que los prefijos de red según su longitud pueden ser representados como ángulos en una circunferencia. Y ahora cuando se busca el prefijo más largo para una dirección IP de destino solamente se debe buscar el ángulo que le corresponde en un arreglo ordenado. La búsqueda de los prefijos y las estructuras de datos para organizar los prefijos son sencillas y de funcionamiento básico. Esta es la bondad de la primera versión del algoritmo UAM. Se utiliza el método de simulación para poder obtener el tiempo que se tarda el algoritmo UAM y compararlo con dos algoritmos clásicos de solución a este problema, pero la facilidad del manejo de las estructuras de datos es lo relevante de nuestra primera propuesta. Por lo tanto el algoritmo UAM es una solución al problema tratado en esta tesis.