El arte del hormigueo

Tener que leer e informarte sobre nuevas tendencias en comunicaciones, técnicas inspiradas en la biología y nanotecnología sin duda te lleva por caminos sorprendentes que quizás no te hubieras planteado.

Y es que es tendencia, ya no tan reciente, la de fijarse en la naturaleza y la biología para mejorar los sistemas que rigen nuestras comunicaciones y proponer nuevas y eficientes vías para resolver distintos problemas. Os remito a un survey paper que resume dicha tendencia exponiendo ejemplos como usar principios de nuestro sistema immunitario para mejorar la seguridad en redes, o lo que conocemos de la epidemiología para la distribución de información (sí, además de virus).

Pero en concreto a mí me hacía gracia hablar de cómo el comportamiento social de una colonia de hormigas se ha usado E IMPLANTADO (en mayúsculas, que de idear a implantar hay un camino muuuuy largo) en protocolos de enrutamiento en redes, principalmente en redes dinámicas, donde temas como la mobilidad de los usuarios o la intermitencia de disponibilidad son cruciales.

¿Qué tiene que ver el enrutado de paquetes en Internet con la típica fila de hormigas que se produce cuando os dejáis comida suelta en vuestro (supuesto) jardín? Si os interesa o queréis intentar aclararos, seguid leyendo, seguid...

El enrutamiento o encaminamiento es básicamente buscar un camino de entre todos los posibles en una red. Cuando tú, desde tu casa, envías un archivo a otra persona, tu router (sí, el cacharro de Telefónica o Vodafone con lucecitas és un enrutador) tiene que saber la dirección del siguiente router que, al final, le permitirá llegar al destinatario. Es como una gimcana pero sin pruebas. Tú sólo sabes cuál es tu siguiente paso; y cuando llegas a él, preguntas cuál será el siguiente, sucesivamente hasta llegar a tu destino.

Clásicamente, Internet está formado por equipos fijos, por tanto los routers tienen tablas donde consultar "el siguiente paso" da normalmente siempre el mismo resultado para el mismo origen y destino. Pero el problema de enrutar datos en redes de sensores o móviles reside en que el siguiente paso, será otro sensor o móvil, y que puede haberse ido, quedarse sin batería, etc. Así, las probabilidades de no llegar al destino con rutas fijas es muy alto.

Necesitamos un conjunto de reglas (o protocolo) que permita realizar enrutamientos dinámicos, de manera que se encuentre la mejor ruta a medida que la red cambia, pero sin sobrecargar el sistema. Pues se descubrió hace unos años que la clave para conseguirlo de una manera eficiente es imitar el comportamiento de las hormigas al determinar el camino a seguir cuando descubren una fuente de comida.


COMPORTAMIENTO OBSERVADO
Supongamos que varias hormigas salen a explorar en busca de una fuente de comida. Al hacer tal, van dejando cierta concentración de feromonas en su camino, las cuales se dispersan en el ambiente cuando pasa un tiempo. Por lo cual, si una hormiga no encuentra nada, se pierde y muere, su rastro acabará muriendo con ella.

Cuando una de ellas encuentra comida, retrocede sobre sus pasos, reforzando el rastro de feromonas que había dejado. El resto de colegas que salgan del hormiguero en busca de comida se verán afectadas por las feromonas de la siguiente manera: al encontrarse con bifurcaciones, obstáculos o lo que sea, la hormiga escogerá con más probabilidad según el nivel de feromonas que detecte. Recalco lo de "con más probabilidad" para dejar claro que no es una decisión cerrada... Simplemente cuantas más feromonas, más probable es que se siga ese camino.

Con esta configuración, las hormigas irán tomando diferentes caminos para llegar a la fuente de comida, y volviendo después sobre sus pasos. Lo que está claro, es que si hay dos caminos diferentes y uno es larguísimo, el rastro de feromonas se difuminará más rápido y las hormigas por probabilidad escogerán el camino corto. Así, el camino corto acabará viéndose reforzado por la asiduidad y rapidez que las hormigas toman tal decisión.

Las amigas van del hormiguero (N) a la comida (F). En las bifurcaciones, tomarán decisiones aleatorias al principio y cada vez más sesgadas debido al rastro de feromonas. El rastro se hace fuerte en el camino más directo hasta que (casi) todas las hormigas acaban formando fila. 

Fuente: Wikipedia

BENEFICIOS OBTENIDOS

Puede verse claramente que el sistema ha conseguido encontrar la ruta más favorable sin tener una visión general del mismo, simplemente sensando los alrededores en ciertos momentos. Esta propiedad es excepcional: en una red tan cambiante como las redes móviles, tener un mapa con la posición y conexión de todos los nodos es casi imposible. Así pues, está bien tener una manera de encontrar rutas generales cortas sólo teniendo conocimiento de nuestro alrededor más inmediato.

Otra de las gracias de esto es que las decisiones siempre son PROBABILÍSTICAS (o como a algunos les gusta llamar, estocásticas). Dejadme que dé un ejemplo: si dos caminos son casi igual de buenos, el rastro de feromonas será parecido en los dos, y más o menos la mitad de hormigas irá por un lado y la otra mitad por el otro. ¿Qué importancia tiene esto? Pues que si algo ocurre en uno de los caminos, no habrá necesidad de volver a ponerse a explorar para encontrar el otro camino que es igual de bueno. En el caso de las redes, si una ruta se cae porque un ordenador falla, tendremos una ruta ya establecida que servirá de vía de escape. Además, podemos ver como el tráfico de hormigas/mensajes se repartirá entre los caminos, una manera excelente de evitar congestión en las redes.

EL RESULTADO
Hay decenas de protocolos para diferentes tipos de redes que usan estos principios para conseguir una red equilibrada, a prueba de fallos y que consigue encontrar rutas en entornos muy dinámicos.

---

Y aquí acaba esta pequeña explicación de un tema que me ha sorprendido gratamente y que me hace ver que quizás no vayamos tan desencaminados en buscar respuestas en la biología. ¡Hasta la próxima!