Download Introducción

ENCAMINAMIENTO GENÉTICO EN REDES DE COMUNICACIONES DE DATOS
ARTURO ELÍAS RAMÍREZ.
Tutor Dr. Felipe Padilla Díaz
INTRODUCCIÓN
El problema fundamental para los dispositivos de
encaminamiento (routers) en las redes de
conmutación de paquetes es crear las tablas de
enrutamiento. Las prácticas actuales emplean
protocolos de enrutamiento de estado de enlace y
computo de la ruta más corta, empleando el
conocimiento que se tiene de la topología de la red
empleada.
Este enfoque tiene inconvenientes.
Primeramente involucra una configuración manual
de las métricas de los enlaces lo cual requiere
entrenamiento, habilidades y hasta cierto punto algo
de suerte. Como las redes están en continuo
crecimiento y cambio es importante automatizar en
todo lo posible todos estos procesos. Los primeros
experimentos demostraron que estos esfuerzos no
son triviales pero si de alto riesgo [1]. Un segundo
problema que involucran las prácticas actuales es la
dificultad que se encuentra para distribuir la carga de
tráfico a través de enlaces múltiples. En una red de
gran tamaño, a menudo los enlaces llegan a
sobresaturarse, pero rara vez la mayoría de ellos se
encuentran saturados al mismo tiempo.
La forma actual de trabajar no tienen ningún soporte
para realizar auque sea pequeños cambios en las
métricas fijadas por el operador de la red, pudiendo
de esta forma cambiar el tráfico a los enlaces menos
utilizados de aquellos que están sobresaturados.
Cuando las métricas se ajustan manualmente para
aliviar la sobresaturación, esta ya se ha resuelto en
otra parte.
En esta investigación se propone mostrar las
implicaciones alrededor del problema anterior, pero
empleando heurísticas con bases en la computación
evolutiva. En contraste, a las propuestas donde hay
paquetes especialmente dedicados al intercambio de
información de enrutamiento [2], la propuesta
empleada tiene el potencial de agregar información a
los paquetes de datos para deducir una topología de
enrutamiento. Esta propuesta tiene el riesgo de crear
una mayor saturación sobre las rutas más empleadas.
Sin embargo, sí el resultado final es un mejor uso del
enlace y la eliminación de muchas de las tareas de
configuración manual, lo anterior se puede justificar.
Construir una tabla de enrutamiento basándose por
completo en el comportamiento de los paquetes en la
red, representa un salto significativo desde el punto
de vista de los enfoques de enrutamiento empleados
por Internet. Un paso evolutivo que quizá por si
mismo permita explorar una nueva porción de los
protocolos de enrutamiento.
OBJETIVO
Se propone establecer que es posible evolucionar
para alcanzar rutas cercanas a las óptimas, sin la
necesidad de configurar manualmente las métricas
de los enlaces de una red de comunicación de datos.
METODOLOGÍA
Los métodos genéticos se consideran adecuados
para descubrir y seleccionar problemas de
enrutamiento [3].
Las complejidades de los problemas de
optimización por sí mismas, los descalifican para
ser resueltos aún con toda la información
disponible. Cuando se aplican las técnicas
genéticas, mucha de esa complejidad se puede
ignorar. La tarea primaria consiste en identificar un
significado por el cual las rutas seleccionadas se
puedan comparar unas con otras. En el contexto del
problema general de optimización para el
enrutamiento, un método necesita comparar las
rutas basándose en la probabilidad de la perdida y
el retardo de paquetes.
RESULTADOS
La heurística propuesta simula la evolución,
siguiendo los operadores familiares de la naturaleza
como lo son la reproducción, mutación y selección,
en donde dentro de un entorno cambiante en la red,
el sistema evoluciona con el entorno.
Para los casos estudiados al momento la heurística
se comporta estable, ha convergido y no exhibe un
comportamiento oscilatorio. Además de ser simple
en su concepto y su implementación.
CONCLUSIONES
La heurística propuesta tiene bastantes fortalezas.
Entre otras es no mínima y distribuye el tráfico
uniformemente cuando así lo requiere, es capaz de
adaptarse sin un conocimiento explicito de la
topología o el tráfico, aunque es susceptible a
topologías en las cuales se puede desempeñar
pobremente, al menos es un intento de demostrar la
importancia que tiene el encontrar nuevas formas
factibles y eficientes al problema de enrutamiento
en redes de conmutación de paquetes.
REFERENCIAS
[1] IETF. MPLS - defnition of the working group.
http://www.ietf.org/, 1997.
[2] Basam Halabi. Internet Routing Architectures.
Cisco Press, 1998.
[3]Computación Evolutiva
http://bayes.escet.urjc.es/~Ejmuruzabal/