Optimización de tráfico en redes multiservicios aplicando técnicas heurísticas

Título:

Optimización de tráfico en redes multiservicios aplicando técnicas heurísticas

Autor:

Carletto, Javier Alejandro

Otros autores / Colaboradores:

 Hernández, José Luis; [ Director/a]  Díaz, Francisco Javier; [ Director/a] 

Temas:

OPTIMIZACIÓN; MÉTODOS HEURÍSTICOS; 

URL:

https://doi.org/10.35537/10915/147414,

Palabras clave:

conmutación de etiquetas multiprotocolo, 

Nota de tesis:

Tesis (Maestría en Redes de Datos) - Universidad Nacional de La Plata. Facultad de Informática, 2022.

Extensión:

1 archivo (3,2 MB) : il. col.

Resumen:

El abrupto crecimiento del tráfico presente en las redes convergentes actuales, trae como consecuencia la implementación de nuevas tecnologías que permiten ofrecer a los usuarios mayores anchos de banda para lo cual es necesario realizar una distribución óptima del tráfico, tomando algún criterio de desempeño y teniendo en cuenta la elasticidad del flujo que involucra atender tráficos tan disímiles como voz, video, sonido, datos, entre otros. Optimizar la distribución de distintos requerimientos considerando estos aspectos en redes multiservicios permite garantizar la disponibilidad de la red para los requerimientos de tráfico, cuando las demandas modernas ponen en riesgo de congestión a las redes que utilizan las técnicas tradicionales de conmutación. MPLS (conmutación de etiquetas multiprotocolo) se ha convertido en una tecnología eficaz en la solución a estos inconvenientes, aunque el problema de la selección de la mejor ruta y de la distribución de tráfico no solo sigue existiendo, sino que exige nuevas propuestas de optimización del enrutamiento. En muchos casos, la planificación óptima de distribución de tráfico en redes MPLS, conlleva la necesidad de resolver un problema de optimización combinatorio de características tales que, para instancias medias o grandes del problema, los métodos determinísticos no son adecuados desde el punto de vista del tiempo de ejecución necesario para obtener el óptimo. En este punto las heurísticas, constituyen una alternativa válida para proporcionar buenas soluciones en tiempos aceptables. En esta tesis se presenta una taxonomía de estrategias heurísticas y metaheurísticas con el objetivo de distribuir los requerimientos en los enlaces disponibles de una red minimizando el costo de enrutamiento, al tiempo que se satisfacen restricciones en cuanto a demanda y capacidad de cada enlace. Se presenta el desarrollo, descripción y modelado del problema, se diseñan diferentes algoritmos bio-inspirados en el comportamiento de enjambres que brindan una solución de configuración fuera de línea, a este problema tradicional de la ingeniería de tráfico en redes con alta interconectividad. Se implementan cinco algoritmos inspirados en bandadas de pájaros, colonias de hormigas y el comportamiento de quirópteros, que permiten determinar una solución óptima explorando el espacio de búsqueda desde diferentes estrategias. Se ejecutan los algoritmos sobre cuatro redes de ensayo de diferentes tamaños, con lo que se determina la aplicabilidad de los algoritmos, y los parámetros óptimos de funcionamiento en cada caso, se presenta el análisis comparativo de los resultados obtenidos y se dejan planteadas distintas opciones de trabajos e investigaciones a futuro.

Puede solicitar más fácilmente el ejemplar con: TES 22/21

Agradecimientos 
Resumen 
Índice de Tablas
Índice de Figuras 
Índice de Algoritmos (pseudocódigos) Acrónimos 

Referencias matemáticas y algorítmicas 
  Relacionado al modelado 
  Relacionado a PSO / Algoritmo PSO
  Relacionado a PSO / Algoritmo PSO 
  Relacionado a ACO / Algoritmo ACO 1 / Algoritmo ACO 2 / Algoritmo BPA 
  Relacionado a BA / Algoritmo BA / Algoritmo BPA 
Terminología propia  

Capítulo 1 - Introducción  
 1.1 Introducción 
1.2 Objetivos:
1.3 Motivación - Estado del Arte 
1.4 Temas de Investigación: 
1.5. Alcances y límites
1.6 Estructura del documento

Capítulo 2 - Multiprotocol Label Switching (MPLS)  
2.1 Introducción 
2.2 MPLS: su historia, presente y futuro 
2.2.1 Sus predecesores 

2.2.2 La evolución de MPLS 
2.2.3 Perspectiva actual de MPLS 
2.3 Características básicas de las redes MPLS 
2.3.1 Concepto funcional, términos y dispositivos de una red MPLS 
2.3.2 MPLS, Modelo OSI y Etiquetas 
2.3.3 Asignación y distribución de etiquetas 
2.4 Operación de MPLS 
2.5 Aplicaciones de MPLS
2.6 Ventajas y desventajas de MPLS
2.7 Conclusiones del capítulo

Capítulo 3 - Definición del problema y modelado de la red  
3.1 Introducción .
 3.2 Definición del problema
3.3 Representación de una red MPLS
3.4 Modelado matemático 
3.5 Representación de una solución 
3.6 Dimensión del espacio de soluciones
3.7 Conclusiones del capítulo

Capítulo 4 - Metaheurísticas 
4.1 Introducción
4.2 Optimización por enjambre de partículas (PSO – Particle Swarm Optimization) 
4.2.1 Introducción a PSO
4.2.2 Movimiento de las Partículas 
4.2.3 Formulación matemática
4.2.4 Diseño del Algoritmo 
4.3 Optimización por colonia de hormigas (ACO – Ant Colony Optimization) 
4.3.1 Introducción 
4.3.2 Formulación Matemática
4.3.3 Diseño del Algoritmo 
4.3.3.1 Algoritmo ACO 1 – Distribución de flujos basado en ACO
4.3.3.2 Algoritmo ACO 2 – Redistribución de flujos basado en ACO
4.4 Optimización por Algoritmo de Murciélagos (BA – Bat Algorithm) 
4.4.1 Introducción 
4.2.2 Reglas del movimiento de los murciélagos virtuales
4.2.3 Formulación matemática
4.2.4 Diseño del Algoritmo 
4.5 Algoritmo híbrido murciélago - hormiga (BPA – BA post-optimizado con ACO) 
4.5.1 Introducción
4.5.2 Diseño del algoritmo 
4.6 Conclusiones del capítulo 

Capítulo 5 - Experimentación y Resultados  
5.1 Introducción 
5.2 Experimentación con CASO 1 – Red de 4 nodos.
5.2.1 Ensayos del algoritmo PSO (Caso 1) 
5.2.2 Ensayos del algoritmo ACO 1 – Distribución de flujos (Caso 1)
5.2.3 Ensayos del algoritmo ACO 2 – Redistribución de flujos (Caso 1) 
5.2.4 Ensayos del algoritmo de murciélagos (BA) (Caso 1) 
5.2.5 Comparación del desempeño de los algoritmos para el Caso 1
5.3 Experimentación con CASO 2 – Red de 6 nodos
5.3.1 Ensayos del algoritmo PSO (Caso 2) 
5.3.2 Ensayos del algoritmo ACO 1 – Distribución de flujos (Caso 2) 
5.3.3 Ensayos del algoritmo ACO 2 – Redistribución de flujos (Caso 2) 
5.3.4 Ensayos del algoritmo de murciélagos (BA) (Caso 2) 
5.3.5 Comparación del desempeño los algoritmos para el Caso 2 
5.4 Experimentación con CASO 3 – Red de 8 nodos
5.4.1 Ensayos del algoritmo PSO (Caso 3) 
5.4.2 Ensayos del algoritmo ACO 2 – Redistribución de flujos (Caso 3) 
5.4.3 Ensayos del algoritmo de murciélagos (BA) (Caso 3) 
5.4.4 Ensayos del algoritmo híbrido murciélago - hormiga (BPA) (Caso 3) 
5.4.5 Comparación del desempeño de los algoritmos para el Caso 3
5.5 Experimentación con CASO 4 – Red de 10 nodos
5.5.1 Ensayos del algoritmo de murciélagos (BA) (Caso 4)
5.5.2 Ensayos del algoritmo híbrido murciélago - hormiga (BPA) (Caso 4)
5.5.3 Comparación del desempeño de los algoritmos para el Caso 4
5.6 Conclusiones del capítulo

Capítulo 6 - Conclusiones  
6.1 Conclusiones 
6.2 Trabajos a Futuro