Optimización multiobjetivo de enrutamiento multicast y ubicación de VNF con protección dedicada a fallas simples de enlace en redes SDN/NFV

Escenarios experimentales

David Verón · Nicholas Jara · Ingeniería en Informática, FP-UNA

Tutor: D.Sc. Ing. Diego P. Pinto-Roa · reunión 23 · 07/09/2026

1Decisiones

DecisiónValorPor qué
Topologíasnobel-us (14/21), janos-us (26/42), janos-us-ca (39/61), de SNDlib [SNDlib 2010]Reales, citables y con coordenadas publicadas. Las anteriores se habían transcrito a mano de una figura y no existen como archivo.
Costo de enlace5 por unidad de ancho de bandaEl costo de un enlace es proporcional al ancho de banda que transporta, no a su longitud. Xu et al. 2021; EVNFP 2015; SFCaaS 2022; CPVNF 2018.
Retardo de enlaceLa distancia en kilómetros entre los extremos de cada enlace, utilizando la fórmula de haversineEl retardo se toma como la distancia entre los nodos: SNDlib publica las coordenadas, pero no el retardo. [Sinnott 1984]
Costo de VNFActivación constante 20 y uso proporcional al ancho de banda (comprime 7, neutro 10, amplifica 13)La activación se cobra una sola vez por nodo, no por sesión [Cohen et al. 2015; Malandrino et al. 2019; Kiji et al. 2020; Ren et al. 2020; Ma et al. 2020; Guo et al. 2022], y el uso depende del ancho de banda del flujo [Xu et al. 2021; Cai et al. 2022].
Peticionesuna por nodo, destinos aleatorios entre el 5–20 % de los nodos, ancho de banda 20 por sesión. Una petición por nodo da 14 / 26 / 39 sesiones en cada dataset respectivamenteEl rango de destinos sigue a [Xu et al. 2019; Ren et al. 2020]. El ancho de banda va en las mismas unidades que la capacidad de enlace, así que cada sesión ocupa 20/C de cada enlace que usa. Una petición por nodo hereda el criterio de [García 2025].
Tipos de VNFtres tipos en tercios exactos, según lo que la función le hace al tráfico: comprime (el ancho de banda baja de 20 a 14), neutro (sigue en 20) o amplifica (sube a 26)Al pasar por el VNF el ancho de banda cambia, así que los enlaces entre el origen y el VNF transportan una tasa y los enlaces entre el VNF y los destinos transportan otra, y el costo de reservar capacidad para el respaldo depende de dónde queda el VNF. Los factores 0.7, 1.0 y 1.3 vienen de [Moré 2025], y Ma et al. [Ma 2019] midieron 0.8 en un compresor zlib y 1.3 en un codificador BCH.
Conjunto de peticiones30 conjuntos de destinos por escenarioSe generan 30 conjuntos de destinos al azar (mismos orígenes, misma topología y misma carga), en vez de quedarse con un único caso, para medir la variabilidad de la instancia. Los mismos 30 conjuntos se usan para los 3 algoritmos [Alhussein 2020; Ma et al. 2020].
Cargacuartos de C100: 100, 75, 50 y 25 %  (C100 = nobel-us 240, janos-us 480, janos-us-ca 700)Pasos iguales de 25 puntos. Los cuatro niveles caen en cuatro regímenes distintos de bloqueo, mientras que una grilla de mitades desperdicia el último (red saturada).
Comparación con/sin protecciónmisma instancia y misma capacidad, cambia solo el modoLo que se quiere medir es el costo de proteger. Si entre los dos modos cambiara cualquier otra cosa, la diferencia dejaría de ser atribuible a la protección. Con topología, peticiones y capacidad idénticas, toda la brecha en bloqueo y en costo es el precio del respaldo.

2Datasets

candidato VNF nodo común diámetro de nodo proporcional al grado
 

Figura 1: topologías sobre sus coordenadas reales. El tamaño de cada nodo es su grado, o sea cuántos enlaces salen de él. En azul, los nodos que pueden alojar una VNF, que son el 25 % del total de nodos de la red, elegidos por ser los de mayor grado.

RedNodosEnlacesGrado mín Grado mediokm mín–máxSesiones
nobel-us142123.00262–283714
janos-us264223.23149–114526
janos-us-ca396123.13132–120239

3Cuatro niveles de carga

El nivel de carga se controla exclusivamente con la capacidad de los enlaces C. Las peticiones quedan fijas y los cuatro niveles son cuartos de la capacidad holgada C100 de cada red. Con y sin protección se corre sobre la misma capacidad, que es lo que hace comparables los dos modos.

C100 es la capacidad más baja en la que la red todavía admite una solución sin ninguna sesión bloqueada, con y sin protección. Se estima evaluando 300 soluciones al azar por capacidad, más la de todos los VNF activos, y la capacidad pasa si alguna llega a cero bloqueo. Al ser un muestreo el valor es una cota superior, porque el algoritmo evolutivo busca de forma dirigida y llega más abajo. Las 300 muestras quedan fijas para que el número sea reproducible.

sin protección con protección
 

Figura 2: sesiones bloqueadas en cada nivel de carga, tomando el mínimo sobre los individuos evaluados. En naranja sin protección, en azul con protección. La franja donde solo bloquea la azul es el costo de capacidad de proteger. La tabla de abajo da los mismos números, con C la capacidad de enlace de cada nivel.

Nivelnobel-usjanos-usjanos-us-ca
Csin prot.con prot.Csin prot.con prot.Csin prot.con prot.
100 %240004800070000
75 %180023600652507
50 %12006240012350017
25 %6051012010191751228

4Cómo se generaron las instancias

Se parte del archivo nativo de SNDlib. Se pliegan los arcos dirigidos a enlaces no dirigidos, el retardo de cada enlace es la distancia en km entre sus extremos y el costo es 5 por unidad de ancho de banda (proporcional al flujo). Sobre esa base, el generador crea una petición por nodo, cada nodo es la fuente de la suya. Para cada una elige al azar la cantidad de destinos (5–20 % de los nodos, mínimo 2) y cuáles son, más el tipo de VNF que le toca. Los candidatos a VNF son el 25 % de nodos de mayor grado.

Para no depender de un único sorteo, se generan 30 conjuntos de destinos por escenario: en cada uno se eligen al azar los destinos (mismos orígenes, misma topología y misma carga). Los mismos 30 conjuntos se usan para los 3 algoritmos y para las 4 capacidades, y sobre ellos se reportan media, desvío y diagramas de caja por métrica.

5Referencias

  1. S. Orlowski, M. Pióro, A. Tomaszewski, R. Wessäly, "SNDlib 1.0: Survivable Network Design Library," Networks, vol. 55, no. 3, pp. 276–286, 2010. doi:10.1002/net.20371
  2. F. Lezama, A. F. Martínez-Herrera, G. Castañón, C. Del-Valle-Soto, A. M. Sarmiento, E. Muñoz de Cote, "Solving routing and spectrum allocation problems in flex-grid optical networks using pre-computing strategies," Photonic Network Communications, vol. 41, pp. 17–35, 2020. doi:10.1007/s11107-020-00918-4
  3. G. García Villalba, Algoritmo Genético aplicado al Problema de Ubicación de VNF en Sesiones Multicast en redes NFV-SDN, tesis de grado, FP-UNA, 2025, §9.2.
  4. C. Cañete Pérez, C. Medina Leiva, Ubicación de Funciones de Red Virtuales en Sesiones Multicast: un enfoque basado en algoritmos evolutivos multiobjetivo, tesis de grado, FP-UNA, 2025, §9.3–9.4.
  5. R. W. Sinnott, "Virtues of the Haversine," Sky and Telescope, vol. 68, no. 2, pp. 158–159, 1984. Verificado contra el geodésico de Vincenty sobre WGS-84, donde la aproximación esférica (R = 6371 km) se desvía 0.14–0.31 % en nuestros enlaces, un orden de magnitud menos que la precisión de minuto de arco con que SNDlib publica las coordenadas.
  6. M. Médard, S. G. Finn, R. A. Barry, R. G. Gallager, "Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs," IEEE/ACM Transactions on Networking, vol. 7, no. 5, pp. 641–652, 1999.
  7. M. Doherty, R. Matzner, R. Sadeghi, P. Bayvel, A. Beghelli, "Reinforcement learning for dynamic resource allocation in optical networks: hype or hope?," arXiv:2502.12804, 2025.
  8. R. Matzner et al., "Topology Bench: systematic graph based benchmarking for core optical networks," arXiv:2411.04160, 2024.
  9. L. G. Moré, C. Cañete, C. Medina, J. Colbes, D. P. Pinto-Roa, "Evolutionary multi-objective multicast virtual network function placement in NFV-SDN networks," CLEI Electronic Journal, vol. 28, no. 5, 2025.
  10. W. Ma, J. Beltran, Z. Pan, D. Pan, N. Pissinou, "Placing traffic-changing and partially-ordered NFV middleboxes via SDN," IEEE Trans. Netw. Service Manag., vol. 16, no. 4, pp. 1303–1317, 2019.
  11. Z. Xu, H. Ren, W. Liang, Q. Xia, W. Zhou, G. Wu, P. Zhou, "Near optimal and dynamic mechanisms towards a stable NFV market in multi-tier cloud networks," in Proc. IEEE INFOCOM, 2021.
  12. M. Ghaznavi, A. Khan, N. Shahriar, K. Alsubhi, R. Ahmed, R. Boutaba, "Elastic virtual network function placement (EVNFP)," in Proc. IEEE CloudNet, 2015.
  13. H. Moufakir, M. F. Zhani, A. Gherbi, M. Aloqaily, N. Ghrada, "SFCaaS: service function chains as a service in NFV environments," arXiv:2203.01098, 2022.
  14. P.-W. Chi et al., "CPVNF: cost-efficient proactive VNF placement and chaining," arXiv:1803.06025, 2018.
  15. R. Cohen, L. Lewin-Eytan, J. Naor, D. Raz, "Near optimal placement of virtual network functions," in Proc. IEEE INFOCOM, 2015.
  16. F. Malandrino, C. F. Chiasserini, G. Einziger, G. Scalosub, "Reducing service deployment cost through VNF sharing," arXiv:1910.03611, 2019.
  17. Y. Cai, F. Llorca, A. Tulino, A. F. Molisch, "Optimal multicast service chain control: packet processing, routing, and duplication," arXiv:2205.15557, 2022.
  18. O. Alhussein et al., "A virtual network customization framework for multicast services in NFV-enabled core networks," IEEE J. Sel. Areas Commun., vol. 38, no. 6, pp. 1025–1039, 2020.
  19. N. Kiji, T. Sato, R. Shinkuma, E. Oki, "Virtual network function placement and routing for multicast service chaining using merged paths," Optical Switching and Networking, vol. 36, art. 100554, 2020.
  20. H. Ren, Z. Xu, W. Liang, Q. Xia, P. Zhou, O. F. Rana, A. Galis, G. Wu, "Efficient algorithms for delay-aware NFV-enabled multicasting in mobile edge clouds with resource sharing," IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 9, pp. 2050–2066, 2020.
  21. Y. Ma, W. Liang, J. Wu, Z. Xu, "Throughput maximization of NFV-enabled multicasting in mobile edge cloud networks," IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 2, pp. 393–407, 2020.
  22. D. Guo, B. Ren, G. Tang, L. Luo, T. Chen, X. Fu, "Optimal embedding of aggregated service function tree," IEEE Trans. Parallel Distrib. Syst., vol. 33, no. 10, 2022.

Cadena completa: scripts/sndlib_to_base.py → scripts/generate_instance.py → scripts/select_instance_reu22.py → scripts/calibrate_reu22.py. Puntajes y curvas en docs/reu22/seleccion_*.json y calib_*.json.