PDF de programación - Dispersión de Tráfico Fractal Mediante Algoritmos Inspirados en Colonias de Hormigas

Dispersión de Tráfico Fractal Mediante

Algoritmos Inspirados en Colonias de Hormigas

Sandra M. Suárez, Student Member, IEEE y Marco A. Alzate, Member, IEEE

1



Resumen—La ingeniería de tráfico permite balancear la carga
entre diferentes rutas, para lo cual tiene en cuenta tanto la
topología de la red como la congestión en los enlaces. En este
trabajo consideramos un parámetro adicional basado en la
variabilidad del tráfico. Proponemos dos algoritmos distintos para
realizar el balance, ambos basados en las propiedades emergentes
de las colonias de hormigas tales como la inteligencia de enjambre,
la adaptabilidad al medio y la auto-organización. Consideramos dos
topologías, una simple con dos enrutadores unidos por dos enlaces y
otra multisalto con siete nodos, diez enlaces y seis posibles rutas. En
todos los casos encontramos que las hormigas no sólo consiguen
dispersar óptimamente el tráfico balanceando las cargas sobre los
enlaces sino que, si se diseñan adecuadamente, logran adaptarse a
los cambios multiescala del
tráfico con gran flexibilidad.
Consideramos que este resultado favorece el nuevo paradigma de la
complejidad en el estudio de redes de comunicaciones,
especialmente a través de novedosas aplicaciones de la inteligencia
computacional.


Palabras Clave—Optimización por Colonia de Hormigas,

Tráfico Fractal, Enrutamiento mediante hormigas.

I. INTRODUCCION

L

a ingeniería de tráfico permite balancear la carga entre los
diferentes enlaces de una red, de manera que ninguno de
ellos permanezca sobrecargado ni subutilizado. MPLS, por
ejemplo, permite dirigir un flujo de paquetes IP por una ruta
determinada, o LSP, para
lo cual se debe compartir
dinámicamente información sobre la topología de la red y el
estado de congestión de los enlaces, usando algún algoritmo de
señalización adecuado (RSVP o LDP). Esto permite hacer un
cálculo "en línea" de las mejores rutas, de acuerdo con la
condiciones dinámicas de la red en cada instante [1]. Esta
capacidad de MPLS para hacer una juiciosa implementación de
ingeniería de tráfico se ve limitada por la falta de un
conocimiento preciso de las características del tráfico que circula
por
la red. Un conocimiento más detallado de dichas
características y de la correspondiente variación dinámica del
estado de la red permitiría tomar mejores y más oportunas
decisiones de ingeniería de tráfico [2]. Sin embargo, en redes
modernas de comunicaciones es de esperarse que la variabilidad
del tráfico obedezca a complejas estructuras de correlación,
incluyendo fractalidad [3], lo cual imposibilita el uso de técnicas
tradicionales de optimización [4].



S. M. Suárez estudia en la Universidad Distrital Francisco José de Caldas.,

Bogotá, Colombia (e-mail: [email protected]).

M. A. Alzate, es profesor de la Universidad Distrital Francisco José de

Caldas., Bogotá, Colombia (e-mail: [email protected]).

(ACO

En efecto, en muchos campos distintos surgen problemas de
optimización cuya complejidad no les permite ser resueltos
dentro de restricciones razonables de tiempo [5]. En estos casos
se recurre a heurísticas que guíen una búsqueda dentro del
espacio de soluciones. Existen algunas heurísticas de
aplicabilidad general tales como los algoritmos genéticos [6], la
búsqueda Taboo [7] o las redes neurales [8]. La optimización
mediante colonia de hormigas
- Ant Colony
Optimization-) es una metaheurística propuesta recientemente
[10], la cual genera repetitivamente nuevas soluciones utilizando
decisiones aleatorias pero influenciadas por la experiencia
obtenida de soluciones anteriores. Los algoritmos ACO hacen
parte de los algoritmos de "inteligencia de enjambre" (SI -Swarm
Intelligence-) [10], la cual emerge de la acción autónoma de
numerosos agentes simples. Los algoritmos SI se inspiran en las
sorprendentes capacidades colectivas de los insectos sociales.
Entre ellos, los algoritmos ACO se basan en el comportamiento
de ciertas especies de hormigas cuando buscan comida para traer
al hormiguero, el cual se puede describir mediante el concepto de
auto-organización (los patrones macroscópicos que se originan
en interacciones microscópicas). En efecto, aunque cada
hormiga actúa autónomamente sin que nadie coordine la labor
colectiva, el efecto es una ordenada organización de la colonia
en su conjunto, en la que el comportamiento colectivo complejo
surge de
interacción entre hormigas simples. Esta
auto-organización le permite a la colonia adaptarse a los cambios
en el ambiente con una gran robustez ante las fallas individuales
de cada hormiga.

la

una

seguir

En el contexto de una colonia de hormigas,

la
auto-organización se da mediante interacciones simples como la
realimentación positiva (estigmergia: las hormigas depositan
rastros de feromonas cuando regresan de una fuente de comida al
hormiguero para que otras hormigas los huelan y tiendan a seguir
el mismo rastro) y el comportamiento aleatorio (cada hormiga
parece
aunque
probabilísticamente influenciada por los rastros de feromonas de
otras hormigas). La evaporación de feromonas es otro
mecanismo importante de interacción. Estos mecanismos son los
que se intentan emular en un algoritmo ACO para resolver
problemas algorítmicamente complejos, tales como aquellos
asociados con manipulación de grafos. El enrutamiento en redes
de comunicaciones es un buen ejemplo de este tipo de
problemas, en los que el nuevo paradigma de los agentes de
software móviles promete soluciones apropiadas [11].

aleatoria,

caminata

Los algoritmos de enrutamiento deben transferir los paquetes
de datos desde la fuente hasta el destino en el menor tiempo
posible, mientras minimizan la pérdida de los mismos. Con este



2

propósito, la red se suele modelar como un grafo en el que los
nodos son los vértices y los enlaces son los arcos. El costo del
uso de los enlaces (retardo, velocidad, tasa de errores,
confiabilidad, etc.) se usa como entrada para determinar cuál es
la mejor ruta entre dos nodos. Desafortunadamente, como vimos,
en las redes modernas de comunicaciones los costos de los
enlaces varían dinámicamente en un amplio rango de escalas de
tiempo con complejas estructuras de correlación, de manera que
la naturaleza estática y determinística de los algoritmos clásicos
de enrutamiento no les permiten adaptarse suficientemente
rápido a dichas variaciones.

Los primeros algoritmos de enrutamiento inspirados en
colonias de hormigas se desarrollaron hacia 1990 como una
aplicación de ACO (Ant Colony Optimization) [12]. AS (Ant
System) [13] fue una de las primeras propuestas, de la que surgió
ACS (Ant Colony System) [14], el cual incorporó mejoras
importantes: Las hormigas se mueven sobre las rutas más
probables, sólo las hormigas con resultados óptimos actualizan
las trazas de feromonas, existe la realimentación negativa
mediante evaporación y se utiliza una lista de información para
guiar las decisiones de enrutamiento. ARS (Ant Routing System)
[15] es otro algoritmo ACO para enrutamiento de redes que
mezcla juiciosamente la exploración aleatoria y la estigmergia
para convergir a buenas soluciones. En [16] se investigó si ARS
podía obtener simultáneamente un aumento de la eficiencia en el
uso de los recursos y una reducción de la pérdida de paquetes,
cuando se utiliza en una red sometida a una alta carga por parte
de los usuarios. Se concluyó que, al combinar realimentaciones
negativa y positiva con heurísticas locales, se puede asegurar un
bajo retardo y una baja pérdida de paquetes simultáneamente.

Los autores de este artículo consideramos que la adaptabilidad
propia de los algoritmos de optimización mediante hormigas los
hacen adecuados para encontrar rutas que varíen dinámicamente
de acuerdo con los cambios temporales del tráfico a diferentes
escalas de tiempo. Como ejemplo, diseñamos dos algoritmos de
dispersión basados en ARS y presentamos distintos resultados
experimentales con los que se verifica que los rastros de
feromonas depositados en
las
variaciones del
tiempo,
alcanzando un balance óptimo de la carga en cada instante.

tráfico en múltiples escalas de

los enlaces responden a

En la sección II presentamos algunos experimentos en los que
se pretende distribuir el tráfico entre dos enlaces paralelos,
encontrando las características de adaptabilidad y optimalidad
deseadas. En la sección III exploramos una topología más
compleja, encontrando los mismos resultados con algoritmos
ligeramente diferentes, lo que sugiere la generalidad de estas dos
propiedades para el enrutamiento mediante hormigas. La sección
IV concluye el artículo.

II. DISPERSIÓN OPTIMA SOBRE DOS ENLACES

Inicialmente nos limitamos a una topología sencilla compuesta
por dos enlaces entre un par de nodos, sobre la cual
determinamos el efecto de los diferentes parámetros en la calidad
de la ruta seleccionada. La red está compuesta por dos
enrutadores, unidos por medio de dos enlaces con capacidades
C1 y C2, como muestra la figura 1. El objetivo es distribuir el
tráfico de entrada λ en dos flujos λ1 y λ2 de manera que se

maximice el caudal y se minimicen los retardos y las pérdidas.

El algoritmo de [16] se basa en el uso adecuado de la
información disponible, combinando las características del
algoritmo Bellman-Ford [17] con las de ARS. Cada paquete que
llega al primer enrutador mira cuál