Ac as de las XV Jo nadas
de Ingenie ía Telemá ica
(JITEL 2021),
A Co uña (España),
27-29 de oc ub e de 2021.
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
Op imizaci´
on Adap a i a basada en Colonias de
Ho migas pa a la Composici´
on de Cadenas de
Funciones Vi uales en una Red 5G Din´
amica
Segundo Mo eno, An onio M. Mo a
D o. Teo ´
ıa de la Se˜
nal, Telem´
a ica y Comunicaciones
ETSIIT-CITIC, Uni e sidad de G anada, Espa˜
na
[email p o ec ed].es, amo ag@ug .es
Resumen—Las edes 5G dependen en g an medida de la
ges i´
on y el p ocesamien o basados en so wa e. Las edes
de inidas po so wa e (SDN) y la i ualizaci´
on de unciones
de ed (NFV) o man pa e del n´
ucleo de es as. Los se icios
o ecidos den o de es e en o no se componen de a ias
unciones de ed i uales (VNF) que deben ejecu a se en un
o den (no malmen e) es ic o. Es o se conoce como Se ice
Func ion Chaining (SFC) y, dado que esas VNFs pod ´
ıan
es a ubicadas en di e en es nodos a lo la go de la ed,
adem´
as de la baja la encia espe ada en el p ocesamien o
de los se icios 5G, hace que el SFC sea un p oblema
de op imizaci´
on di ´
ıcil de esol e . En un abajo an e io ,
los au o es p esen a on un algo i mo de Op imizaci´
on de
Colonias de Ho migas (ACO) pa a la minimizaci´
on del cos e
de en u amien o de la composici´
on de la cadena de se icios,
a ´
andose de una ap oximaci´
on p elimina capaz de esol e
ins ancias simples y ’es ´
a icas’; es deci , aquellas en las
que la opolog´
ıa de la ed pe manece in a iable du an e
la esoluci´
on. Es o dis a mucho de la si uaci´
on eal de las
edes, en las que no malmen e los nodos (y los enlaces)
apa ecen y desapa ecen con inuamen e. As´
ı, en es e abajo
desc ibimos una e oluci´
on de nues a p opues a an e io , que
conside a un modelo din´
amico del p oblema, m´
as ce cano al
escena io eal. De mane a que, en las ins ancias, los nodos
y enlaces pueden se eliminados o ac i ados epen inamen e.
El algo i mo ACO se ´
a capaz de adap a se a es os cambios y
segui o eciendo soluciones ´
op imas. Dicho m´
e odo ha sido
p obado en es ins ancias din´
amicas de di e en es ama˜
nos,
ob eniendo esul ados muy p ome edo es.
Palab as Cla e—Vi ualizaci´
on de Funciones de Red, NFV,
Cadena de Funciones Vi uales, En u amien o, Rou ing, Re-
des 5G, Me aheu ´
ıs icas, Algo i mos de Op imizaci´
on basada
en Colonias de Ho migas, OCH, ACO
I. INTRODUCCI ´
ON
Las ecnolog´
ıas de ed ac uales se cen an en la eno me
demanda que ienen es as, an o en lo que espec a al
n´
ume o de disposi i os conec ados a ellas como a los
exigen es equisi os de baja la encia y g an ancho de
banda. Las edes 5G han sido dise˜
nadas pa a hace en e
a es as nue as ca ac e ´
ıs icas siendo capaces de se i con
lexibilidad a las necesidades de los usua ios y se icios.
As´
ı, las edes 5G se desplega ´
an sob e nue as ec-
nolog´
ıas acili ado as que pe mi i ´
an la ealizaci´
on de una
ed i ualizada, p og amable y lexible. Dos de es as
ecnolog´
ıas son las edes de inidas po so wa e (SDN)
y la i ualizaci´
on de las unciones de ed (NFV), que
a´
un se encuen an en ase de desa ollo y e oluci´
on [1].
Las SDN p e enden sepa a el een ´
ıo y el p ocesamien o
del ´
a ico, bas´
andose en la au oma izaci´
on de algunas
ope aciones de ges i´
on de la ed. La NFV se basa en
la ecnolog´
ıa de i ualizaci´
on pa a ejecu a unciones de
ed implemen adas po so wa e. Es as dos ecnolog´
ıas se
combinan en el llamado composici´
on de cadenas de un-
ciones de ed, o Se ice Func ion Chaining (SFC), cuyo
obje i o es es ablece din´
amicamen e nue os se icios de
ed a a ´
es de un conjun o de unciones i uales, que
deben ejecu a se en un o den espec´
ı ico [2].
Es e abajo abo da la composici´
on ´
op ima de es as
cadenas de se icios. As´
ı, dado un g a o de ed en el que
cada nodo puede ejecu a di e en es unciones i uales; y
conside ando una can idad de ecu sos po nodo, los e-
cu sos que equie e una unci´
on, el ancho de banda en los
enlaces, y el o den de composici´
on deseado; el obje i o es
cons ui el camino ´
op imo y ´
alido co espondien e a un
se icio de ed, que minimice el cos e de encaminamien o
(es deci , el n´
ume o de sal os en e nodos).
Se a a de un p oblema de di icul ad NP-comple o
[3], que los au o es esol ie on con una p ime a ap o-
ximaci´
on basada en un algo i mo de op imizaci´
on basada
en colonias de ho migas (ACO) [4]. Los algo i mos ACO
[5] se inspi an en el compo amien o de las ho migas
na u ales cuando buscan comida y se aplican pa a e-
sol e p oblemas de op imizaci´
on combina o ia, po lo
que u ilizan una colonia de ho migas a i iciales, que
son agen es compu acionales que se comunican en e s´
ı
median e una ma iz de e omonas. Es os agen es abajan
sob e p oblemas o mulados en un g a o con pesos en
sus a cos. En cada i e aci´
on, cada ho miga cons ui ´
a un
229
Mo eno, Mo a, 2021.
camino comple o (soluci´
on) mo i´
endose a a ´
es de ´
el.
Una ez cons uido el camino (o du an e su cons ucci´
on),
la ho miga deposi a ´
a un as o de e omona que, gene al-
men e, es a ´
a elacionado con la bondad de la soluci´
on.
Po lo an o, es e as o se ´
a una medida (in o ma i a pa a
o os) de lo deseable que es segui la misma u a que la
ci ada ho miga.
As´
ı, desa ollamos en [4] una a iaci´
on de ACO bau-
izada como An -SFC, inspi ada en el modelo de ACO
m´
as simple, el Sis ema de Ho migas [6]. Sin emba go,
los escena ios en los que se p ob´
o el algo i mo en´
ıan
una cla a des en aja: la ausencia de dinamismo. Las edes
son sis emas en con inuo cambio, es deci , los nodos (y
ambi´
en los enlaces) su gen o desapa ecen cons an emen e.
Es e compo amien o po ello se inco po a a las ins ancias
pa a esol e el SFC de mane a m´
as idedigna.
Pa a ello, el p esen e abajo mejo a an o la de inici´
on
y modelizaci´
on del p oblema -haci´
endolo m´
as ce cano
a la ealidad-, como el algo i mo pa a abo da lo. De
modo que se han conside ado ins ancias din´
amicas, en las
que pueden ocu i algunos e en os, po lo que nodos o
enlaces pueden ac i a se o desac i a se epen inamen e.
Po an o, el algo i mo se ha ans o mado en lo que
hemos denominado Dynamic An -SFC (DAn -SFC), capaz
de adap a su compo amien o pa a encon a soluciones
´
op imas en es os escena ios cambian es.
Se han de inido nue as ins ancias del p oblema pa a
p oba el algo i mo p opues o, incluyendo odas ellas
los e en os mencionados; ambi´
en se ha conside ado un
escena io m´
as complejo, eniendo es e 52 nodos. En los
expe imen os se ha analizado la capacidad de adap aci´
on
del algo i mo y su endimien o en la econs ucci´
on de
soluciones ´
op imas, as´
ı como la habilidad de ecupe aci´
on
que se o ece a la ed en esos e en os conc e os.
II. PROBLEMA A RESOLVER: ENRUTAMIENTO
DIN ´
AMICO DE COSTE M´
INIMO PARA SFC
Es e abajo se cen a en la composici´
on de una cadena
de unciones de se icio (SFC) en una ed. El p oceso de
composici´
on de la SFC es uno de los p incipales e os de
NFV, ya que en es a a ea in e ienen an o el c´
alculo de la
u a como la di ecci´
on del ´
a ico. Adem´
as, debido a las
p opiedades de SFC, las u as de lujo se de inen como
un conjun o o denado en cadena de unciones de se icio
oSe ice Func ions (SF) que maneja el ´
a ico de la en-
ega, el con ol y la supe isi´
on de un se icio/aplicaci´
on
espec´
ı ico [7].
En es e en o no y con el in de mejo a el endimien o
y aho a ecu sos en la ed, se equie e una es a e-
gia ´
op ima. As´
ı, hemos bau izado es e p oblema como
Op imizaci´
on del En u amien o pa a SFC (OR-SFC). En
es e p oceso, se ´
a necesa io de e mina el camino que
deben segui los da os en e las unciones de ed i uales
adyacen es pa a cada uno de los se icios solici ados.
La Figu a 1 mues a un ejemplo de ins ancia de es e
p oblema.
En ´
el, la pe ici´
on del usua io se denomina conexi´
on,
y es ´
a de inida po una upla, C=(o igen, des ino, alo
Fig. 1. Ejemplo de p oblema de Rou ing pa a SFC
de la demanda, [ unciones a ejecu a ]), en la que la
conexi´
on iene como o igen el nodo ‘1’ y como des ino
el nodo ‘6’, con una demanda de ´
a ico de 2 Mbps y
las unciones i uales a ejecu a 3, 5 y 6, en ese p eciso
o den. Si nos ijamos en la igu a, el alo ce cano a los
enlaces hace e e encia al co espondien e ancho de banda
disponible en cada uno. En cada nodo se han indicado
las unciones de ed que puede ejecu a (cubos). Adem´
as,
cada uno de los nodos end ´
a asociados unos ecu sos
in o m´
a icos (CPU, Memo ia, espacio en disco) ag upados
en un ´
unico n´
ume o po simplicidad. Del mismo modo, en
la de inici´
on del p oblema hab ´
a una lis a que asocie un
cos e en ecu sos a cada unci´
on, como sus equisi os pa a
se ejecu ada.
En el ejemplo (Figu a 1), una soluci´
on debe se i las
unciones 3, 5 y 6 (en es e o den es ic o). As´
ı, una posible
soluci´
on pod ´
ıa se el camino [1→3→1→2→4→
6], pe o ambi´
en [1→3→5→6→4→6]. La elecci´
on
de uno u o o a ec a ´
a al cos e del encaminamien o en la
ed, as´
ı como a su endimien o global. La u a ambi´
en
debe cumpli algunas es icciones adicionales, como que
los enlaces deben ene su icien e ancho de banda pa a
cub i la demanda, y los nodos deben ene su icien es
ecu sos disponibles pa a ejecu a las unciones i uales.
Adem´
as de lo desc i o an e io men e, se a˜
nade al p o-
blema un componen e din´
amico. T a a ´
a de simula un
compo amien o m´
as ealis a de la ed, manejando posi-
bles cambios o modi icaciones du an e la esoluci´
on del
p oblema.
La o ma en que se ha implemen ado es a pa de
din´
amica a˜
nade al p oblema una componen e de comple-
jidad, o eciendo esul ados m´
as ealis as. Es a posibilidad
o ece ´
a po encialmen e una g an lexibilidad a la ho a de
ges iona es a ed den o de un en o no i ualizado, ya que
en la g an mayo ´
ıa de los casos pod ´
a hace en e a si ua-
ciones imp e is as al no eque i que la ed pe manezca
es ´
a ica en cuan o a su es uc u a, lle ando el modelo del
p oblema a un en oque m´
as ealis a, conside ando que las
edes eales son comple amen e din´
amicas.
III. ESTADO DEL ARTE
SFC es uno de los p incipales e os en NFV. Es e
debe se a ado como un p oblema de op imizaci´
on
NP-comple o. Es po ello que ha a a´
ıdo la a enci´
on
de la academia, p oponiendo di e en es soluciones pa a
esol e lo, que p incipalmen e se cen an en soluciones
exac as o heu ´
ıs icas, siendo s´
olo algunas de las p opues as
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
230
Composici´
on de Cadenas de Se icios con OCH
las que u ilizan m´
e odos de in eligencia compu acional
a anzada, como las me aheu ´
ıs ica.
En cuan o a las ap oximaciones exac as pa a esol e
el p oblema OR-SFC, la mayo ´
ıa de ellas se cen an en
modelos de op imizaci´
on basados en ´
ecnicas de P og a-
maci´
on Lineal. Po ejemplo, los au o es en [2] p esen-
a on un modelo que esuel e el en u amien o SFC y la
asignaci´
on de unciones i uales pa a los in e alos de
ho as pico. Cabe des aca ambi´
en el abajo desa ollado
en [8], en el que los au o es o mula on un modelo
ma em´
a ico que esuel e el p oblema u ilizando m´
e odos
de descomposici´
on.
Tambi´
en exis en algo i mos heu ´
ıs icos pa a esol e
es e ipo de p oblemas. Es as heu ´
ıs icas son ´
u iles pa a
encon a soluciones ac ibles y p ecisas pa a ins ancias
mayo es del p oblema en un iempo de c´
alculo educido.
Los algo i mos G eedy son muy u ilizados pa a es e in,
como se hace en [9] y [10]. En gene al, se ha demos ado
que las heu ´
ıs icas p oducen soluciones ap oximadas ce -
canas al ´
op imo y son ap opiadas cuando hay que esol e
ins ancias g andes. En es os casos, la heu ´
ıs ica p opo -
ciona un equilib io ´
op imo en e la alidez de la soluci´
on
y el cos e de c´
alculo [11].
Po el con a io, las me aheu ´
ıs icas no se han aplicado
demasiado en es e ´
ambi o. Aunque el p oblema OR-
SFC es muy adecuado pa a la ´
ecnica de Op imizaci´
on
basada en Colonias de Ho migas si bien, has a donde
sabemos, s´
olo nues o abajo an e io [4] se ha cen ado
en la esoluci´
on de es e p oblema aplicando ACO. O os
en oques en la li e a u a se en en an en cambio a la
llamada Asignaci´
on de Recu sos en NFV, como [12]
donde los au o es aplican Tabu Sea ch; o [13] en el que
los au o es abo dan la op imizaci´
on de la ubicaci´
on de
Funciones Vi uales de Red (VNFs) en los nodos de la ed,
conside ando el consumo de ene g´
ıa en los se ido es e-
que idos, aplicando una a iaci´
on del Algo i mo Gen´
e ico.
Den o de es e ´
ambi o, algunos abajos a an de e-
sol e p oblemas an´
alogos aplicando un en oque desde
un pun o de is a din´
amico, donde la opolog´
ıa de la
ed puede cambia . Es e es el caso de [14] donde se
adop an di e en es colonias de ho migas simul ´
aneamen e
pa a a o ece la explo aci´
on en edes din´
amicas, e i ando
en g an medida el es ancamien o. O o caso se da en [15],
donde se u iliza un algo i mo basado en ACO pa a esol e
el en u amien o din´
amico anycas y la asignaci´
on de longi-
udes de onda en edes ´
op icas, o eciendo educciones de
la p obabilidad de bloqueo y mejo as sob e o os m´
e odos.
Sin emba go, de nue o, ninguna de las p opues as se cen a
en la esoluci´
on del p oblema SFC.
IV. ALGORITMO IMPLEMENTADO: ANT-SFC
DINAMICO
El algo i mo implemen ado pa a abo da la e si´
on
din´
amica del p oblema es una ’e oluci´
on’ de nues o
an e io An -SFC [4], es deci , una adap aci´
on del Sis ema
de Ho migas cl´
asico [6] pa a esol e el p oblema SFC
es ´
anda . As´
ı, cub i ´
a la esoluci´
on de caminos ´
op imos
en un modelo de ed de elecomunicaciones, cumpliendo
con las siguien es es icciones ( e Secci´
on II):
•Un camino debe se de inido en el g a o que modela
la ed pa a cada esoluci´
on de conexi´
on (solici ud
de se icio). Debe pasa po nodos disponibles que
puedan se i cada una de las unciones de ed
eque idas, en el o den dado (indicado po cada
se icio).
•Cada enlace debe ene su icien e capacidad (ancho
de banda disponible) pa a pode sa is ace la demanda
de ´
a ico de cada conexi´
on. ´
Es a disminui ´
a cada ez
que una u a pase po un enlace.
•Los nodos, al igual que los enlaces, deben ene
su icien es ecu sos disponibles pa a la ejecuci´
on de
las unciones eque idas. Los ecu sos de los nodos
disminui ´
an seg´
un la demanda de cada unci´
on eje-
cu ada.
Es as es icciones deben cumpli se incluso eniendo en
cuen a que los nodos o enlaces pod ´
ıan ac i a se o desac-
i a se epen inamen e, ya que las ins ancias del p oblema
son din´
amicas. Po lo an o, el algo i mo adap ado se ha
denominado Dynamic An -SFC o simplemen e DAn -SFC.
El dinamismo implemen ado p e ende a˜
nadi un com-
ponen e a´
un m´
as ealis a a las edes simuladas. Se con-
segui ´
a median e la eliminaci´
on o in oducci´
on de nodos
y/o enlaces en de e minados momen os de la ejecuci´
on,
haciendo que el algo i mo sea capaz de ecupe a se de
e en os de po encial colapso de nodos p incipales. De es e
modo, el algo i mo ecibi ´
a algunas uplas den o de un
a chi o de e en os, como una modelizaci´
on ”con olada”
y simpli icada de ese dinamismo.
El o ma o de cada upla es (n´
ume o de i e aci´
on,
ac i aci´
on-desac i aci´
on del nodo, nodo, ac i aci´
on-
desac i aci´
on del enlace, nodo o igen del enlace, nodo
des ino del enlace). Po ejemplo, la upla “(3, 0, 4, 0, 4,
8)” equi ald ´
ıa a deci le al algo i mo que a pa i de la
i e aci´
on 3, el nodo 4 se desac i a ´
a jun o con el enlace
de 4 a 8, ambi´
en desac i ado e inu ilizable, a menos que
se eac i e expl´
ıci amen e de nue o en un e en o pos e io .
Cada ez que una de es as uplas sea p ocesada po la
pa e de dinamismo, se ac i a ´
a au om´
a icamen e una pa e
del algo i mo pa a elimina o a˜
nadi el nodo co espon-
dien e, asegu ando as´
ı que las sucesi as soluciones que se
calculen conside a ´
an una e si´
on ac ualizada de la ed.
Adem´
as, al inal de cada p oceso, se comp ueba si exis e
una soluci´
on po encialmen e mejo , eniendo en cuen a el
iempo y la capacidad de los nodos p obados.
La esoluci´
on de cada conexi´
on (solici ud de se icio)
se ha plan eado como una b´
usqueda de camino ´
op imo
indi idual, aunque sean dependien es en e s´
ı po el con-
sumo de ancho de banda de los enlaces y de ecu sos de
los nodos. El cue po p incipal de DAn -SFC se p esen a
en el Algo i mo 1.
La adap aci´
on del algo i mo se ha cen ado en los
siguien es aspec os:
•Inicializaci´
on del g a o: el g a o iene que es a
inicializado al y como es aba an es de que la ho miga
an e io lo modi ica a cons uyendo su soluci´
on an es
de que cualquie ho miga comience a cons ui una
soluci´
on.
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
231
Mo eno, Mo a, 2021.
Algo i hm 1 DAn -SFC ( )
Algo i mo p incipal DAn -SFC
Inicializacion pa ame os()
Lee con igu acion ed()
Lee conexiones()
Lee con igu acion dinamismo()
/* Se busca ´
a una soluci´
on po cada conexi´
on */
o cada conexi´
on c do
while c i e io inalizacion no e minado do
o cada ho miga h do
s[h]=Cons ui Solucion(c,h)
end o
/* En odos los enlaces del g a o */
E apo acion Fe omona()
/* Links usados po la mejo ho miga */
s*=Elegi Mejo Solucion(s[h])
Ac ualizacion Fe omona Global(s*)
Ac ualiza es ado dinamismo() /* Comp ueba si la mejo soluci´
on es
oda ´
ıa ´
alida*/
end while
/* Ancho de banda de los enlaces y los nodos son ac ualizados */
Ac ualizacion Red(c,s*)
end o
•Heu ´
ıs ica: se ha conside ado asigna una mayo
p obabilidad de se elegido a los enlaces con mayo
ancho de banda disponible, in en ando minimiza el
iesgo de ago amien o de los enlaces. Adem´
as, se ha
incluido una condici´
on pa a la selecci´
on del siguien e
nodo en la cons ucci´
on de la soluci´
on: si alguno de
los nodos es capaz de se i a la siguien e unci´
on de
ed que espe a se se ida en la cadena, se duplica ´
a
la p obabilidad de elecci´
on del nodo pa a guia a la
ho miga hacia ´
el.
Ob iamen e, el enlace debe ene su icien e ancho
de banda disponible pa a cada caso y el nodo se-
leccionado iene que ene su icien es ecu sos pa a
ejecu a la siguien e unci´
on de ed en la cadena.
•Rule a de p obabilidades: se u iliza ´
a una ule a de
p obabilidades como pol´
ı ica de decisi´
on pa a el
siguien e es ado una ez asignada la p obabilidad de
pasa a cada nodo desde el eal en la cons ucci´
on
de una soluci´
on. Es a ule a consis e en asigna un
espacio p opo cional a la p obabilidad de cada nodo
en una ” ule a i ual” y su gi o alea o io pa a ob ene
el siguien e nodo elegido.
•Res icci´
on del ancho de banda de los enlaces: se
basa en la cons ucci´
on de la lis a de nodos ac ibles.
•Res icci´
on de ecu sos de nodos: se basa en la
cons ucci´
on de la lis a de nodos ac ibles.
•Ac ualizaci´
on de enlaces y nodos (cons ucci´
on de
una soluci´
on): el ancho de banda de los enlaces
y los ecu sos de los nodos (en caso de que el
nodo cumpla una unci´
on de ed) se ac ualizan cada
ez que una ho miga se desplaza hacia un nodo
de la ed mien as se cons uye una soluci´
on pa a
esol e una conexi´
on. Ambos alo es se ac ualizan
con la demanda de ´
a ico de la conexi´
on y el cos e
en ecu sos de la unci´
on de ed, espec i amen e,
e i ando la gene aci´
on de bucles in ini os.
•Ac ualizaciones de la ed (conexiones): la ed se ac-
ualiza eniendo en cuen a la ayec o ia de inida po
la soluci´
on cada ez que se encuen a una soluci´
on
pa a una de e minada cadena. Po lo an o, los enlaces
y nodos u ilizados pa a es e camino se ac ualizan
siguiendo el m´
e odo u ilizado en el caso an e io .
• es icci´
on de ayec o ia comple a: una soluci´
on s´
olo
se conside a ´
a ´
alida si comienza y e mina en los
nodos exac amen e dados po la conexi´
on. Tambi´
en
iene que pasa po los nodos que cumplen unciones
de ed en el o den dado po la p opia conexi´
on. Si
no es as´
ı, la soluci´
on no se u iliza ´
a.
•Cos e de la u a (conexi´
on): se ´
a el n´
ume o de sal os
eque ido en el g a o pa a la composici´
on de la
cadena de unciones necesa ia pa a comple a una
conexi´
on.
•Cos e de la soluci´
on global: una soluci´
on comple a
es a ´
a o mada po unos caminos de cos e m´
ınimo
pa a esol e cada una de las conexiones solici adas
pa a la ins ancia seleccionada en un de e minado
in e alo de iempo. Po lo an o, el cos e de la
soluci´
on global se ´
a el n´
ume o o al de sal os de odas
las conexiones solici adas.
•Ac ualizaci´
on de la e omona: al igual que el co es-
pondien e e apo aci´
on de la e omona ealizado en
odos los enlaces as la cons ucci´
on de odas las
soluciones, s´
olo se ealiza ´
a una ac ualizaci´
on de
la e omona en los enlaces que o men pa e de la
mejo soluci´
on, que se ´
a di ec amen e p opo cional
al n´
ume o de sal os en es a misma. Cuan o meno
sea el n´
ume o de sal os, mayo se ´
a la con ibuci´
on
en los enlaces.
V. EXPERIMENTOS Y RESULTADOS
Se han conside ado es ins ancias di e en es pa a p oba
el algo i mo p opues o:
Ins ancia de 6 nodos: se u iliza como un en oque
concep ual, donde el algo i mo ha sido e aluado y a-
lidado de una mane a m´
as in ui i a. Las ca ac e ´
ıs icas
del g ´
a ico se pueden e en: h ps://doi.o g/10.6084/m9.
igsha e.14572200. 1 incluyendo las unciones de ed
disponibles en cada nodo as´
ı como el ancho de banda
asociado a cada enlace. En es a ins ancia se conside an
3 conexiones di e en es a esol e , conc e amen e ( e
o ma o en la secci´
on II): Conexi´
on 1: (A, F, 2, [3,5,6]),
Conexi´
on 2: (A, E, 8, [1,2,4]), y Conexi´
on 3: (A, D, 5,
[2,4,5]).
Ins ancia de 19 nodos: es un g ´
a ico de 19 nodos
que modela un caso m´
as ealis a, m´
as ce cano a los
que se esol e ´
an en la ealidad. La opolog´
ıa de es a
ins ancia se puede consul a desde h ps://doi.o g/10.6084/
m9. igsha e.14572224. 1. Las p opiedades de los enlaces
en es a ins ancia se pueden e en h ps://doi.o g/10.6084/
m9. igsha e.14572080. 1. Es a ins ancia es ´
a conside ando
es as 5 conexiones siguien es pa a esol e : Conexi´
on 1:
(H, J, 8, [5,1,2]), Conexi´
on 2: (B, D, 8, [4,3,1]), Conexi´
on
3: (Q, B, 1, [2,3,1]), Conexi´
on 4: (R, J, 3, [5,2,3]),
Conexi´
on 5: (J, S, 8, [4,1,3]).
Ins ancia de 52 nodos: es un g a o de 52 nodos que
modela un caso p ´
oximo a la ealidad. Es la ins ancia m´
as
g ande u ilizada en es e abajo. Su opolog´
ıa se mues a en
h ps://doi.o g/10.6084/m9. igsha e.14572230. 1, mien as
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
232
Composici´
on de Cadenas de Se icios con OCH
Algo i hm 2 Cons uccion Solucion (conexion, an id)
Algo i mo de cons uccion de una solucion DAn -SFC
Inicializacion ho miga(an id)
Inicializacion ed() /* Es ablece los alo es de la ed */
Aplicacion dinamismo() /* Comp ueba los nodos y enlaces ac i ados/desac i ados */
nodo ac ual = conex.nodo inicial
uncion ac ual = conex. unciones[inicio]
L= gua da (nodo ac ual) /* Lis a de es ados isi ados */
F= gua da ( uncion ac ual) /* Lis a de unciones se idas */
while (nodo ac ual 6=conex(nodo inal)) AND ( uncion ac ual 6=conex. uncion[ in]) do
/* A: lis a nodos alcanzables, P: p obabilidad de mo e se a cada nodo alcanzable, Ω: es icciones del p oblema */
P= calcula p obabilidades ansicion(nodo ac ual, A,F,L,Ω)
siguien e nodo = ule a p obabilidad(P,Ω)
/* Ac ualizaci´
on del ancho de banda de los enlaces */
Ac ualizacion Enlace(siguien e nodo)
L= gua da (siguien e node)
nodo ac ual = siguien e nodo
/* Si la unci´
on es ´
a disponible se ´
a se ida, y los ecu sos del nodo, ac ualizados */
i uncion ac ual in unciones.ac uales nodo[] hen
Ac ualiza Nodo( uncion ac ual)
F= gua da ( uncion ac ual)
uncion ac ual = conex.siguien es( unciones[])
end i
end while
que las ablas co espondien es a los enlaces de es a ins-
ancia pueden consul a se en h ps://doi.o g/10.6084/m9.
igsha e.14483592. 2. Hay que esol e 10 conexiones:
Conexi´
on 1: (AP, K, 16, [3,1,2]), Conexi´
on 2: (P, O, 6,
[2,3,1]), Conexi´
on 3: (R, AU, 11, [4,1,2]), Conexi´
on 4:
(AT, E, 5, [3,2,1]), Conexi´
on 5: (AF, AE, 5, [1,3,2]),
Conexi´
on 6: (AA, AD, 14, [4,3,1]), Conexi´
on 7: (S, I,
11, [4,2,1]), Conexi´
on 8: (X, AD, 10, [3,2,1]), Conexi´
on
9: (K, R, 7, [1,3,2]), Conexi´
on 10: (AG, AX, 18, [3,1,2]).
A. Resul ados ob enidos
Pa a la ejecuci´
on del algo i mo se ha u ilizado un o de-
nado pe sonal con un p ocesado In el Co e i5-1135G7 de
4 n´
ucleos y 8 hilos a 2,40GHz, con 8GB de RAM DDR-4
y Windows 10 O.S. de 64 bi s.
Las con igu aciones del algo i mo conside adas en cada
ins ancia se mues an en la Tabla I.
Tabla I
PARAMETROS CONSIDERADOS EN LOS EXPERIMENTOS
Pa ame o Ins ancia 6N Ins ancia 19N Ins ancia 52N
I e aciones 6 19 52
Ho migas 12 38 104
α(peso e omona) 1.2 1.2 1.2
β(peso heu is ica) 2.0 2.0 2.0
ρ( ac o e apo aci´
on) 0.3 0.3 0.3
Los alo es dados se han ijado en base a las ecomen-
daciones le´
ıdas en a ´
ıculos sob e aplicaci´
on de ACO,
como e omona y pesos heu ´
ıs icos pa a el c´
alculo de
la p obabilidad de elecci´
on del siguien e nodo, aunque
pos e io men e se han ajus ado y modi icado siguiendo
un p oceso de expe imen aci´
on sis em´
a ica. Los n´
ume os
de i e aciones y conexiones se han ijado con el in de
ob ene buenas soluciones en un iempo acep able, aunque
se pod ´
ıa lle a a cabo una in es igaci´
on pos e io s´
olo
pa a de e mina de o ma ´
op ima es os alo es iniciales,
pe o no es el obje i o de es e abajo.
Dado que se a a de un algo i mo no de e minis a, pa a
ob ene esul ados iables, se han ealizado 10 ejecuciones
independien es esol iendo la misma ins ancia del p o-
blema (con el mismo n´
ume o de conexiones) pa a cada
escena io posible y pa a cada una de las es ins ancias a
p oba .
Como se desc ibe en la secci´
on IV, se ha desa ollado
una unci´
on de dinamismo pa a es e algo i mo. ´
Es a
pe mi e ob ene las mejo es soluciones posibles mien as
cie os nodos de la ed pueden cae o es a en l´
ınea
du an e la ejecuci´
on (simulando un escena io eal de ed
de elecomunicaciones) sin modi ica el compo amien o
b´
asico del c´
odigo ejecu ado. Se u iliza pa a e o za el ya
de po s´
ı buen endimien o del algo i mo en un mayo
n´
ume o de si uaciones y escena ios di e en es.
•Ve si´
on elimina nodo: un nodo c ´
ı ico, que o ma
pa e de la mejo soluci´
on, es eliminado de la mejo
soluci´
on has a el momen o: con es e ipo de a ian e,
el algo i mo se e obligado a ecalcula la mejo u a
ob enida has a el momen o, dado que un nodo c ´
ı ico
se ´
a eliminado de la misma, no siendo posible po
an o su u ilizaci´
on y eniendo que aplica las u ili-
dades de la unci´
on de dinamismo pa a selecciona
la mejo opci´
on posible.
•Ve si´
on elimina dos nodos: Se eliminan dos nodos
c ´
ı icos de la mejo soluci´
on has a el momen o:
se ´
a simila al caso an e io , pe o con una di icul ad
a˜
nadida (hab ´
a una mayo pa e de la ma iz de nodos
no disponible pa a se seleccionada), haciendo que
la nue a selecci´
on de u as sea m´
as desa ian e y
“ ealis a”.
•Ve si´
on elimina es au a nodo: Se elimina un nodo
c ´
ı ico de la mejo soluci´
on has a el momen o y
luego se es au a: pa a es a si uaci´
on, se elimina ´
a
un nodo c ´
ı ico seleccionado y, despu´
es de un cie o
n´
ume o de i e aciones, se es au a ´
a, obse ando si
el algo i mo uel e a selecciona la mejo soluci´
on
p e iamen e gua dada o no (si se ha is o obligado a
mejo a la).
En la Tabla II, se pueden e los esul ados ob enidos en
las simulaciones, an o en n´
ume o de sal os de la mejo
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
233
Mo eno, Mo a, 2021.
soluci´
on y iempo de ejecuci´
on, como en iempo, alo
medio y des iaci´
on es ´
anda .
Tabla II
RESULTADOS DEL ALGORITMO DANT-SFC PARA LAS INSTANCIAS DE
6, 19 Y52 NODOS. SE ESPECIFICA:MEJOR EJECUCI ´
ON,COSTE,
TIEMPO,VALOR MEDIO Y DESVIACI ´
ON EST ´
ANDAR O STANDARD
DEVIATION (SD), OBTENIDOS PARA 10 EJECUCIONES EN CADA
VERSI ´
ON DIN ´
AMICA.
Ins ancia 6N
Ve si´
on Ejec. Cos e (s) Media SD
elimina nodo 7 13 0.073 13.8 0.707
elimina dos nodos - - - - -
elimina es au a nodo 2 12 0.070 12.2 1.41
Ins ancia 19N
Ve si´
on Ejec. Cos e (s) Media SD
elimina nodo 2 17 0.283 17.4 0.707
elimina dos nodos 8 16 0.258 16.2 0.707
elimina es au a nodo 3 17 0.303 17.8 1.41
Ins ancia 52N
Ve si´
on Ejec. Cos e (s) Media SD
elimina nodo 5 35 4.906 35.5 1.414
elimina dos nodos 7 35 4.796 35.4 1.414
elimina es au a nodo 2 37 4.953 38.6 2.121
Cabe des aca que, pa a la simulaci´
on de la ins ancia
m´
as peque˜
na (6 nodos), al se u ilizada como e e encia
pa a eplica el uncionamien o de las dem´
as y debido
a su educido ama˜
no, la e si´
on elimina dos nodos de
la p ueba (en la que se eliminan dos nodos undamen-
ales) no puede ealiza se como al, ya que el c´
alculo de
cie as u as se ´
ıa imposible. Sin emba go, su co ec o
uncionamien o pa a es e caso puede e i ica se en las
ins ancias m´
as g andes. Po es e mo i o, se han u ilizado la
e si´
on elimina nodo y la e si´
on elimina es au a nodo,
siendo es a ´
ul ima igualmen e ´
alida como ejemplo de
uncionamien o, ya que se elimina un nodo y se eac i a,
obligando al algo i mo a ecalcula las u as (como e ec-
i amen e hace).
Fig. 2. Mejo soluci´
on encon ada pa a la Ve si´
on elimina nodo (un
nodo eliminado (C) en la i e aci´
on n´
ume o 2) de la ins ancia de 6 nodos
con 3 conexiones. Cos e exp esado en n´
ume o de sal os jun o a cada
conexi´
on. Figu a con mayo esoluci´
on disponible en h ps://doi.o g/10.
6084/m9. igsha e.16587497
Los esul ados num´
e icos p esen ados en la Tabla II Se
puede obse a cla amen e la di e encia en e las dis in as
e siones ejecu adas. Pa a el caso de 6 nodos, en la
p ime a e si´
on, como se e en la Figu a 2, un nodo
undamen al (C) baja ´
a en la i e aci´
on n´
ume o 2. Cuando
Fig. 3. Mejo soluci´
on encon ada pa a la Ve si´
on elim-
ina es au a nodo (un nodo eliminado (C) en la i e aci´
on n´
ume o 2,
luego eac i ado (C) en la i e aci´
on n´
ume o 6) de la ins ancia de 6
nodos con 3 conexiones. Cos e exp esado en n´
ume o de sal os jun o
a cada conexi´
on. Figu a con mayo esoluci´
on disponible en h ps:
//doi.o g/10.6084/m9. igsha e.16587512
es e nodo cae, jun o con sus enlaces, no puede se u ilizado
en la ed pa a u u os c´
alculos. En es a e si´
on, es o ocu e
casi desde el p incipio (i e aci´
on n´
ume o 2), po lo que
el algo i mo pod ´
ıa u iliza p ime o es e nodo. Sin em-
ba go, as la co espondien e aplicaci´
on de la unci´
on de
dinamismo, es e nodo se desac i a ´
a y au om´
a icamen e,
la mejo soluci´
on has a aho a p ocesada, en caso de que
lo con u ie a, se ´
a eliminada y se ob end ´
a o a ac ible.
Se puede obse a que pa a la Ve si´
on elim-
ina es au a nodo, que se puede obse a en la Figu a
3, en la que es e mismo nodo se cae pe o en sucesi as
i e aciones se eac i a de nue o en la i e aci´
on n´
ume o
6, el algo i mo de ec a que es la u a m´
as e icien e y
que puede ol e a u iliza es e nodo, o eciendo adem´
as
un meno cos e pa a se i , po ejemplo, en la p ime a
conexi´
on eque ida. De es e modo, siemp e se ob iene la
mejo soluci´
on posible, eniendo en cuen a las capacidades
que o ece la ed.
Como se ha mencionado an e io men e, con la ins ancia
de 19 nodos se pueden obse a g ´
a icamen e los cambios
ealizados en la ed. En la p ime a e si´
on, al poco de
comenza la ejecuci´
on, un nodo se cae de la ed (nodo N)
en la i e aci´
on n´
ume o 4, lo que hace que el algo i mo
ecalcule las u as en unci´
on de c´
omo ha quedado la
opolog´
ıa. Despu´
es de odas las ejecuciones, el esul ado
es el que se mues a en la Figu a 4. Es o pod ´
ıa se
un p oblema a p io i, ya que uno de es os nodos ue
u ilizado en las u as ´
op imas de la e si´
on elimina nodo.
Sin emba go, la heu ´
ıs ica acaba ´
a encon ando o a u a
´
op ima (de hecho, en es e caso incluso mejo que la
an e io ) pa a encamina la conexi´
on seg´
un lo eque ido y
que se cumplan odos los equisi os.
Con espec o a la e si´
on elimina dos nodos, ambos
nodos N y M ya no es ´
an ac i os en la ed (desconec ados
en la i e aci´
on 4 y 10 espec i amen e), po lo que apa ece
una ma ca oja en ellos mismos y en sus enlaces. De
nue o, el algo i mo es capaz de ecalcula nue as u as
que no incluyan esa pa e de la ed sin mayo di icul ad,
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
234
Composici´
on de Cadenas de Se icios con OCH
Fig. 4. Mejo soluci´
on encon ada pa a la Ve si´
on elimina nodo (un
nodo eliminado (N) en la i e aci´
on n´
ume o 4) de la ins ancia de 19
nodos con 5 conexiones. Cos e exp esado en n´
ume o de sal os jun o a
cada conexi´
on. Figu a con mayo esoluci´
on disponible en: h ps://doi.
o g/10.6084/m9. igsha e.16587428
Fig. 5. Mejo soluci´
on encon ada pa a la Ve si´
on elimina dos nodos
(dos nodos eliminados (M y N) en las i e aciones n´
ume o 4 y 10
espec i amen e) de la ins ancia de 19 nodos con 5 conexiones. Cos e
exp esado en n´
ume o de sal os jun o a cada conexi´
on. Figu a con mayo
esoluci´
on disponible en: h ps://doi.o g/10.6084/m9. igsha e.16587443
Fig. 6. Mejo soluci´
on encon ada pa a la Ve si´
on elim-
ina es au a nodo (dos nodos eliminados (M y N) en las i e aciones 4 y
10 espec i amen e, y luego uno eac i ado (M) en la i e aci´
on n´
ume o
16) de la ins ancia de 19 nodos con 5 conexiones. Cos e exp esado en
n´
ume o de sal os jun o a cada conexi´
on. Figu a con mayo esoluci´
on
disponible en: h ps://doi.o g/10.6084/m9. igsha e.16587446
como puede e se en la Figu a 5.
Po ´
ul imo, los caminos o mados en la Ve si´
on elim-
ina es au a nodo pa a es a ins ancia de 19 nodos se
pueden obse a en Figu a 6. T as elimina los nodos N
y M en sucesi as i e aciones (i e aci´
on 3 y 9 espec i-
amen e), las soluciones calculadas aho a no pueden in-
clui los en las u as ob enidas. Sin emba go, en la i e aci´
on
n´
ume o 16 (del o al de 19 ealizadas), el nodo M uel e a
es a ac i o, jun o con sus co espondien es enlaces. As´
ı, el
algo i mo uel e a inclui lo en sus ablas de nodos ac i os
y lo iene en cuen a pa a las nue as soluciones; an o es
as´
ı que la soluci´
on inal pa a la conexi´
on 4 lo u iliza en
sus esul ados.
En la ins ancia de 52 nodos, se ha decidido mos a
g ´
a icamen e la Ve si´
on elimina es au a nodo de los ex-
pe imen os ealizados, mien as que de las e siones elim-
ina nodo y elimina dos nodos se mos a ´
an ´
unicamen e
los esul ados en la Figu a 7. En es e caso, se mues a
c´
omo los nodos V y X se desac i an (en las ins ancias 4 y
8, espec i amen e), y el sis ema debe deja de u iliza los
pa a el c´
alculo de las soluciones. Sin emba go, el nodo
V uel e a ac i a se a pa i de la ins ancia 13, po lo
que puede ol e a u iliza se. De hecho, en la conexi´
on
9, se u iliza pa a la mejo opci´
on de la misma. Se puede
obse a la g an complejidad de la ed y c´
omo el com-
po amien o del algo i mo es lexible y obus o an e los
cambios, adap ´
andose a ellos en cada si uaci´
on (Figu a
8).
Fig. 7. Resul ados de la ins ancia de 52 nodos con 10 conexiones,
Ve si´
on elimina nodo y 2. Cos e exp esado en n´
ume o de sal os jun o a
cada conexi´
on.
VI. CONCLUSIONES Y TRABAJO FUTURO
Es e abajo p esen a una adap aci´
on de un algo i mo
de Op imizaci´
on basada en Colonias de Ho migas o An
Colony Op imiza ion(ACO) pa a esol e el p oblema de
en u amien o en Se ice Func ion Chaining (SFC) den o
de una ed de inida po so wa e (SDN). El p oblema
se ha de inido conside ando ambi´
en el dinamismo en la
opolog´
ıa de la ed, ya que los nodos y enlaces pueden se
ac i ados o desac i ados en cualquie momen o.
El algo i mo p opues o se ha aplicado en es ins ancias
di e en es con dis in os ama˜
nos, y a ios e en os de
ac i aci´
on/desac i aci´
on p ede inidos en algunos de los
nodos y enlaces exis en es.
A la is a de los esul ados ob enidos, podemos conclui
que DAn -SFC es capaz de cons ui soluciones ´
op imas,
incluso haciendo en e a cambios d ´
as icos en la opolog´
ıa
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
235
Mo eno, Mo a, 2021.
Fig. 8. Mejo soluci´
on encon ada pa a la Ve si´
on elim-
ina es au a nodo (dos nodos eliminados (V y X) en las i e aciones
4 y 8 espec i amen e), y luego uno eac i ado (V) en la i e aci´
on
13) de la ins ancia de 52 nodos con 10 conexiones. Resul ados de la
Figu a 9. Figu a con mayo esoluci´
on disponible en h ps:// igsha e.com/
s/b48a4c3c9 85ebca721d
Fig. 9. Resul ados de la ins ancia de 52 nodos con 10 conexiones,
Ve si´
on elimina es au a nodo, e e ida a la Figu a 8. Cos e exp esado
en n´
ume o de sal os jun o a cada conexi´
on.
de la ed como puede se la ca´
ıda de nodos c ´
ı icos en
las u as p e iamen e o madas, o la einco po aci´
on de
los mismos, debiendo ecalcula las u as o madas has a
dicho momen o. Adem´
as, los iempos de c´
alculo, siemp e
muy in e io es a 1 segundo pa a ins ancias peque˜
nas y me-
dianas, aunque algo mayo es (en o no a 5 segundos pa a
las de mayo ama˜
no) son acep ables pa a la esoluci´
on de
ins ancias conside adas ejecu adas en iempo eal.
En cualquie caso, una de las en ajas de los algo i mos
ACO es su capacidad de ob ene soluciones ´
alidas desde
la p ime a i e aci´
on, es deci , desde el mismo p ime
c´
alculo ealizado du an e una ejecuci´
on, as´
ı como su ca-
pacidad de au oadap a su compo amien o a los cambios
en la de inici´
on del p oblema, como sonlos cambios de
opolog´
ıa en es as ins ancias.
Como abajo u u o, p oba emos mejo es unciones
heu ´
ıs icas pa a guia la cons ucci´
on de soluciones en el
algo i mo ACO. Adem´
as, se pod ´
ıan implemen a algunos
en oques h´
ıb idos, como los m´
e odos de b´
usqueda local.
Tambi´
en se p oba ´
an modelos ACO m´
as so is icados.
AGRADECIMIENTOS
Es e abajo ha sido pa cialmen e inanciado po los
p oyec os RTI2018-102002-A-I00 (Minis e io de Cien-
cia, Inno aci´
on y Uni e sidades), PID2020-113462RB-I00
(Minis e io de Ciencia e Inno aci´
on), TIN2017-85727-C4-
2-P (Minis e io de Econom´
ıa y Compe i i idad), B-TIC-
402-UGR18 (FEDER y Jun a de Andaluc´
ıa), y el p oyec o
P18-RT-4830 (Jun a de Andaluc´
ıa).
REFERENCIAS
[1] I. A olabi, T. Taleb, K. Samdanis, A. Ksen ini, and H. Flinck,
“Ne wo k slicing and so wa iza ion: A su ey on p inciples, en-
abling echnologies, and solu ions,” IEEE Communica ions Su eys
Tu o ials, ol. 20, no. 3, pp. 2429–2453, 2018.
[2] V. E amo, E. Miucci, M. Amma , and F. G. La acca, “An app oach
o se ice unc ion chain ou ing and i ual unc ion ne wo k
ins ance mig a ion in ne wo k unc ion i ualiza ion a chi ec u es,”
IEEE/ACM T ans. Ne wo king, ol. 25, no. 4, pp. 2008–2025, 2017.
[3] T. Luko szki, M. Ros , and S. Schmid, “I ’s a ma ch!: Nea -
op imal and inc emen al middlebox deploymen ,” SIGCOMM Com-
pu . Commun. Re ., ol. 46, pp. 30–36, Jan. 2016.
[4] S. Mo eno, A. M. Mo a, P. Padilla, J. Ca mona-Mu illo, and P. A.
Cas illo, “Applying an colony op imiza ion o se ice unc ion
chaining in a 5g ne wo k,” in Six h In e na ional Con e ence on
In e ne o Things: Sys ems, Managemen and Secu i y, IOTSMS
2019, G anada, Spain, Oc obe 22-25, 2019 (M. A. Alsmi a and
Y. Ja a weh, eds.), pp. 567–574, IEEE, 2019.
[5] M. Do igo and T. S ¨
u zle, “The an colony op imiza ion me a-
heu is ic: Algo i hms, applica ions, and ad ances,” in Handbook o
Me aheu is ics (G. K. F. Glo e , ed.), pp. 251–285, Kluwe , 2002.
[6] M. Do igo, V. Maniezzo, and A. Colo ni, “The an sys em: Op i-
miza ion by a colony o coope a ing agen s,” IEEE T ansac ions on
Sys ems, Man, and Cybe ne ics Pa B: Cybe ne ics, ol. 26, no. 1,
pp. 29–41, 1996.
[7] A. M. Medha , T. Taleb, A. Elmangoush, G. A. Ca ella, S. Co aci,
and T. Magedanz, “Se ice unc ion chaining in nex gene a ion
ne wo ks: S a e o he a and esea ch challenges,” IEEE Commu-
nica ions Magazine, ol. 55, pp. 216–223, Feb ua y 2017.
[8] N. Huin, B. Jauma d, and F. Gi oi e, “Op imal Ne wo k Se -
ice Chain P o isioning,” IEEE/ACM T ansac ions on Ne wo king,
ol. 26, pp. 1320–1333, jun 2018.
[9] Z. Allybokus, N. Pe o , J. Leguay, L. Maggi, and E. Gou din,
“Vi ual unc ion placemen o se ice chaining wi h pa ial o de s
and an i-a ini y ules,” Ne wo ks, ol. 71, no. 2, pp. 97–106, 2018.
[10] L. Qu, M. Khabbaz, and C. Assi, “Reliabili y-Awa e Se ice
Chaining in Ca ie -G ade So wa ized Ne wo ks,” IEEE Jou nal
Selec. A eas in Communica ions, ol. 36, no. 3, pp. 558–573, 2018.
[11] T.-M. Nguyen, M. Minoux, and S. Fdida, “Op imizing esou ce
u iliza ion in NFV dynamic sys ems: New exac and heu is ic
app oaches,” Compu e Ne wo ks, ol. 148, pp. 129–141, jan 2019.
[12] J. Gil-He e a and J. F. Bo e o, “A scalable me aheu is ic o se ice
unc ion chain composi ion,” in 2017 IEEE 9 h La in-Ame ican
Con e ence on Communica ions, LATINCOM 2017, ol. 2017-
Janua, pp. 1–6, Ins i u e o Elec ical and Elec onics Enginee s
Inc., dec 2017.
[13] L. Laaziz, N. Ka a, R. Rabipou , C. Eds om, and Y. Lemieux,
“FASTSCALE: A as and scalable e olu iona y algo i hm o he
join placemen and chaining o i ualized se ices,” Jou nal o
Ne wo k and Compu e Applica ions, ol. 148, p. 102429, dec 2019.
[14] K. M. Sim and W. H. Sun, “Mul iple an -colony op imiza ion
o ne wo k ou ing,” in Fi s In e na ional Symposium on Cybe
Wo lds, 2002. P oceedings., pp. 277–281, 2002.
[15] K. Bhaska an, J. T iay, and V. M. Vokka ane, “Dynamic anycas
ou ing and wa eleng h assignmen in wdm ne wo ks using an
colony op imiza ion (aco),” in 2011 IEEE In e na ional Con e ence
on Communica ions (ICC), pp. 1–6, 2011.
This wo k is licensed unde a C ea i e Commons 4.0 In e na ional License (CC BY-NC-ND 4.0)
236
