Construcción y navegación de redes de pequeño mundo

Resumen

Uno de los problemas fundamentales en las redes de ordenadores, por ejemplo Internet, es la localización eficiente de recursos. Una de las formas de abordar el problema es la utilización de redes superpuestas. En esta tesis usamos redes superpuestas en las que los nodos se conectan con una geometría que permita una localización más rápida de los recursos en la red. En la construcción de estas redes superpuestas se hace uso un conjunto de paradigmas habitualmente utilizados en los sistemas entre pares (peer-to-peer) en Internet. El primer paradigma es la computación epidémica que permite obtener, de forma eficiente, en cada nodo de una red grande el resultado de un cálculo agregado utilizando valores almacenados en todos los nodos de la red. Un segundo paradigma es la asignación de posiciones a los nodos de Internet. Para ello se asignan posiciones a los nodos en un determinado espacio métrico. Las posiciones asignadas a los nodos junto con el concepto de distancia van a permitir la construcción de redes superpuestas y el diseño de algoritmos de encaminamiento geográfico eficientes, ya que la distancia entre dos nodos es una buena estimación de la latencia real entre los mismos. Un tercer paradigma que usado en nuestras redes es la propiedad de “Pequeño Mundo”, que combinada con la utilización de algoritmos de encaminamiento geográfico ávidos permitirá localizar un nodo eficientemente. Un cuarto paradigma es la utilización de algoritmos no deterministas que, en ciertos tipos de redes, no necesiten de la posición de los nodos para localizar un recurso de forma rápida y eficiente. El muestreo (selección) de nodos de una red es la piedra angular para la construcción de redes superpuestas. Se han diseñado y evaluado dos nuevos algoritmos distribuidos de muestreo, BS y RCW. BS permite seleccionar nodos con cualquier distribución de probabilidad utilizando únicamente información local a los nodos. RCW es un paseo aleatorio que proporciona un muestreo exacto con la distribución de probabilidad deseada. En su funcionamiento siempre se aleja de la fuente que lo originó, lo que hace que la longitud del paseo esté acotado por el diámetro de la red. En la tesis también se ha propuesto un nuevo modelo de red que permite construir redes sin escala, además de dos algoritmos que aprovechan la topología de la red para obtener un encaminamiento eficiente. Las redes superpuestas propuestas en esta tesis podrán ser utilizadas en varios ámbitos, como por ejemplo para mejorar los sistemas de “streaming” o facilitar el funcionamiento de las redes que se adaptan a la carga.