Tablas de ruteo IP dinámicas basadas en árboles Multibit Public Deposited
Debido al crecimiento exponencial de internet, el tamaño de las tablas de ruteo también se ha incrementado. Un enrutador típico del backbone de internet en el año 2014 llega a almacenar alrededor de 500 000 prefijos de red (1). Este crecimiento propicia que los enrutadores se tornen lentos al realizar la reexpedición de paquetes, ya que les toma más tiempo decidir por cuál de sus interfaces deberá ser reenviada la información. Para reducir estos tiempos, se ha optado por almacenar los prefijos de red dentro de estructuras que permitan realizar actualizaciones y búsquedas de información. El tiempo de búsqueda dependerá de la complejidad de la estructura. La solución clásica a este problema es utilizar árboles binarios, ya que esta estructura nos permite almacenar prefijos de red de distintas longitudes, por otra parte, tanto el proceso de búsqueda como el proceso de actualización tienen una complejidad lineal (2) (3). Sin embargo, debido a que las longitudes de los prefijos pueden ser grandes (de 32 bits en el peor de los casos para IPV4) las búsquedas pueden tornarse lentas ya que en esta técnica se compara solamente un bit del prefijo a la vez. En este trabajo se propone una estructura de almacenamiento que se basa en árboles Multibit los cuales, a diferencia de los árboles binarios, pueden comparar varios bits a la vez, mejorando los tiempos de búsqueda (al número de bits comparados se le conoce como stride). Los árboles Multibit o Tries-Multibit ofrecen la ventaja de que las operaciones de búsqueda son más rápidas que en el algoritmo clásico que utiliza árboles binarios, sin embargo, para las estructuras Trie-Multibit en su forma simple no existen operaciones de actualización, es decir no existen operaciones de inserción y borrado (que no impliquen la reconstrucción de todo el árbol) que garanticen la integridad de los datos almacenados, por lo que se pueden perder elementos en el proceso de actualización del árbol, esta problemática será abordada con más detalle en el capítulo 3.1. La estructura propuesta en este documento permite a los árboles Multibit realizar operaciones de actualización garantizando que no exista pérdida de información en el proceso, para esto, se propone y se evalúa la estructura Trie-Multibit con respaldo. Dicha estructura es implementada en lenguaje C y son evaluados los algoritmos de inserción, borrado y búsqueda. Después de analizar los resultados experimentales, podemos concluir que el almacenamiento en la estructura Trie-Multibit con respaldo es más conveniente que el almacenamiento en árboles binarios, ya que las operaciones de búsqueda son más rápidas y que a pesar de que las operaciones de actualización son más lentas, éstas pueden ser toleradas debido a que ocurren con menor frecuencia.
Relationships
| In Administrative Set: |
|---|
Descriptions
| Attribute Name | Values |
|---|---|
| Creador | |
| Contributors | |
| Tema | |
| Editor | |
| Idioma | |
| Identificador | |
| Keyword | |
| Año de publicación |
|
| Tipo de Recurso | |
| Derechos | |
| División académica | |
| Línea académica | |
| Licencia |
