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 · 04/09/2026

1Decisiones

Decisión	Valor	Por qué
Topologías	nobel-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 enlace	50, homogéneo	Misma convención que EON y USA [García 2025, Cañete y Medina 2025]. SNDlib no publica costo de ruteo.
Retardo de enlace	distancia en km (haversine [Sinnott 1984] sobre las coordenadas)	SNDlib no publica retardo, y las coordenadas son la única fuente.
Costo de VNF	30 por nodo y por sesión = activación 20 + uso 10	Valores heredados de las dos tesis anteriores del grupo [García 2025, Cañete y Medina 2025]. Lo que decide el modelo es la relación con el costo del salto. Como un salto cuesta 50 y un nodo VNF 30, sale más barato un árbol que usa un nodo VNF de más que uno que se desvía un salto. Ninguno de los dos valores está justificado en la fuente, y el costo de activación se cobra por sesión, así que no premia concentrar sesiones en pocos nodos.
Peticiones	una por nodo, destinos 10–20 % de los nodos, ancho de banda 20 por sesión. Una petición por nodo da 14 / 26 / 39 sesiones en cada dataset respectivamente	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. Hereda el criterio de [García 2025] y de NADT [Raposo 2016]. Para generar el grupo de destinos se re-sortea hasta que la sesión admita primario y respaldo disjuntos.
Tipos de VNF	tres 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 peticiones	elegido entre varias instancias candidatas, no por un sorteo único	Un solo sorteo de destinos puede dar una red que nunca bloquea, o que salta de cero a saturada, o nodos sin tráfico. Se generan varios conjuntos y se elige el de bloqueo gradual, con diferencia clara entre los dos modos y todos los nodos como destino [Doherty 2025].
Carga	cuartos de C₁₀₀: 100, 75, 50 y 25 % (C₁₀₀ = 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ón	misma instancia y misma capacidad, cambia solo el modo	Lo 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.

Red	Nodos	Enlaces	Grado mín	Grado medio	km mín–máx	Sesiones
`nobel-us`	14	21	2	3.00	262–2837	14
`janos-us`	26	42	2	3.23	149–1145	26
`janos-us-ca`	39	61	2	3.13	132–1202	39

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 C₁₀₀ de cada red. Con y sin protección se corre sobre la misma capacidad, que es lo que hace comparables los dos modos.

C₁₀₀ 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.

Nivel	nobel-us			janos-us			janos-us-ca
	C	sin prot.	con prot.	C	sin prot.	con prot.	C	sin prot.	con prot.
100 %	240	0	0	480	0	0	700	0	0
75 %	180	0	2	360	0	6	525	0	7
50 %	120	0	6	240	0	12	350	0	17
25 %	60	5	10	120	10	19	175	12	28

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 50. Sobre esa base, el generador crea una petición por nodo, cada nodo es la fuente de la suya. Para cada una sortea la cantidad de destinos (10–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.

Cada grupo de destinos sorteado se acepta solo si la heurística logra construir para esa sesión un árbol primario y uno de respaldo sin enlaces en común, con capacidad infinita y todos los VNF activos. Si no, se descarta y se vuelve a sortear. janos-us-ca necesitó 43 re-sorteos para sus 39 sesiones, contra 3 en las otras dos.

El conjunto de peticiones no sale de un sorteo único. Se generan 60 instancias candidatas y se puntúa cada una por separación entre los dos modos, monotonía del bloqueo, cobertura pareja de los nodos como destino, riqueza del frente y cantidad de re-sorteos. Gana la de mayor puntaje.

5Referencias

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
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
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.
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.
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.
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.
L. Raposo, T. Gomes, L. Martins, C. K. Constantinou, G. Ellinas, "A new arc-disjoint-trees scheme for survivable multicasting in mixed-graph sparse-splitting optical networks," in Proc. RNDM, 2016, pp. 158–165. doi:10.1109/rndm.2016.7608282
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.
R. Matzner et al., "Topology Bench: systematic graph based benchmarking for core optical networks," arXiv:2411.04160, 2024.
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.
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.

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.