El futuro de Internet: un nuevo modelo algorítmico que acelera las búsquedas en redes

20 Junio 2014

Un grupo de cuatro investigadores españoles ha desarrollado, entre los que está representado IMDEA Networks Institute, ha presentado un modelo de búsqueda de recursos en red basado en paseos aleatorios modificados para acelerar la obtención de resultados. Los nuevos mecanismos consiguen reducciones de hasta el 90% en la longitud media de las búsquedas realizadas con caminos aleatorios convencionales.

---

Cuando hacemos una búsqueda en Internet casi nunca nos paramos a pensar en el proceso técnico que nos facilita el resultado deseado. Más allá de la aparente sencillez, cada búsqueda que un internauta realiza en la red implica el uso de toda una serie de algoritmos informáticos y matemáticos para guiar la búsqueda. No obstante, la eficacia de estos algoritmos, medibles mediante magnitudes como el tiempo que dura la búsqueda, la longitud de la búsqueda o el ancho de banda utilizado, depende de la cantidad de información proporcionada.

Antonio Fernández Anta (IMDEA Networks Institute), Víctor López Millán, (CEU University of San Pablo), Vicent Cholvi (Universitat Jaume I) y Luis López (Universidad Rey Juan Carlos) han presentado un modelo de búsqueda de recursos, basado en los llamados caminos o paseos aleatorios, random walks, con el que han conseguido diseñar mecanismos eficientes de búsqueda de recursos en una red en la que no se dispone de información centralizada de sus recursos. El rendimiento de dichos mecanismos ha sido evaluado utilizando tanto modelos analíticos como experimentos mediante simulaciones.

Los caminos aleatorios han sido estudiados extensamente en matemáticas, donde se han analizado como cadenas de Markov finitas, y utilizados en una amplia variedad de campos tales como la física estadística, la dinámica de poblaciones, la bioinformática, etc. Aplicados a las redes de comunicaciones, los caminos aleatorios han tenido un profundo impacto en la algoritmia y la teoría de la complejidad pues debido a su la simplicidad, el bajo consumo de recursos de procesamiento y almacenamiento en los nodos, y el hecho de que utilizan sólo información local, evitan la sobrecarga de comunicaciones necesaria en otros mecanismos.

Los investigadores emplearon caminos aleatorios de tipo SAW, self-avoiding walks, en lugar de caminos aleatorios normales, así como caminos parciales precomputados para construir caminos aleatorios más largos de forma eficiente. Lo que se pretendía con esto era mejorar el rendimiento de los caminos aleatorios normales para intentar no revisitar nodos ya recorridos, elevando por lo tanto la probabilidad de localizar el nodo que posee el recurso deseado.

Los SAW consiguen reducciones de la longitud media de las búsquedas con respecto a los caminos aleatorios normales de entre el 50% y el 75% en los experimentos realizados, dependiendo del tipo de red y de su grado medio. Las redes scale-free son las que exhiben reducciones mayores mientras que en redes con replicación de recursos, las reducciones disminuyen a entre el 7% y el 26%, mostrando que los beneficios de intentar no revisitar nodos se ven compensados parcialmente por el conocimiento de los recursos de los vecinos cuando se usan caminos aleatorios normales.

Las búsquedas con caminos aleatorios parciales consiguen reducciones mayores de sus longitudes: la raíz cuadrada de la longitud media de las búsquedas de los caminos aleatorios normales, con una probabilidad de falso positivo en los filtros de Bloom mínima. Esto supone unas reducciones temporales en las búsquedas de entre el 88% y el 98%, sin una dependencia importante del tipo de red. Además, al combinar los caminos parciales con los caminos SAW se obtienen reducciones adicionales de entre un 5% y un 12%.

Cuando se adaptan los mecanismos basados en caminos aleatorios parciales a redes con recursos dinámicos se observan también importantes reducciones de la longitud media de las búsquedas. Los experimentos realizados mostraron que estas reducciones disminuyen al aumentar la dinamicidad de dichos recursos, pero se mantienen en valores significativos incluso para una alta volatilidad.

Este estudio ha demostrado que en mecanismos basados en caminos aleatorios SAW y en caminos aleatorios parciales, y aplicados a redes construidas aleatoriamente y en las que se cumple que cualquier punto de conexión de un nodo puede estar conectado mediante un enlace a cualquier otro punto de conexión de la red con probabilidad uniforme puede obtenerse un rendimiento que supera al de las búsquedas basadas en caminos aleatorios normales.

Estos resultados poseen unas importantes implicaciones prácticas para los internautas que cada día utilizan la Red. Cuando un usuario realiza una búsqueda en Internet, consulta por lo general plataformas como Google o buscadores similares, que se encargan de recorrer la web para almacenar información sobre su contenido en una base de datos. Pero, ¿qué pasa si no contamos con esos buscadores centralizados o no podemos disponer de ellos en algún momento determinado? Es para ese escenario, o para redes P2P que no cuenten con una centralización de enlaces a los contenidos, para el que el modelo propuesto por López Millán tendría utilidad: permitiría escrutar la Red sin necesidad de recurrir a espacios de compartición de ficheros o a los buscadores, con una longitud media de las búsquedas considerablemente menor que si estuvieran basadas sólo en caminos aleatorios.