Optimización Adaptativa basada en Colonias de Hormigas para la Composición de Cadenas de Funciones Virtuales en una Red 5G Dinámica

Actas de las XV Jornadas de Ingeniería Telemática (JITEL 2021), A Coruña (España), 27-29 de octubre de 2021. This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) Optimizaci´ on Adaptativa basada en Colonias de Hormigas para la Composici´ on de Cadenas de Funciones Virtuales en una Red 5G Din´ amica Segundo Moreno, Antonio M. Mora Dto. Teor´ ıa de la Se˜ nal, Telem´ atica y Comunicaciones ETSIIT-CITIC, Universidad de Granada, Espa˜ na [email protected].es, [email protected] Resumen—Las redes 5G dependen en gran medida de la gesti´ on y el procesamiento basados en software. Las redes definidas por software (SDN) y la virtualizaci´ on de funciones de red (NFV) forman parte del n´ ucleo de estas. Los servicios ofrecidos dentro de este entorno se componen de varias funciones de red virtuales (VNF) que deben ejecutarse en un orden (normalmente) estricto. Esto se conoce como Service Function Chaining (SFC) y, dado que esas VNFs podr´ ıan estar ubicadas en diferentes nodos a lo largo de la red, adem´ as de la baja latencia esperada en el procesamiento de los servicios 5G, hace que el SFC sea un problema de optimizaci´ on dif´ ıcil de resolver. En un trabajo anterior, los autores presentaron un algoritmo de Optimizaci´ on de Colonias de Hormigas (ACO) para la minimizaci´ on del coste de enrutamiento de la composici´ on de la cadena de servicios, trat´ andose de una aproximaci´ on preliminar capaz de resolver instancias simples y ’est´ aticas’; es decir, aquellas en las que la topolog´ ıa de la red permanece invariable durante la resoluci´ on. Esto dista mucho de la situaci´ on real de las redes, en las que normalmente los nodos (y los enlaces) aparecen y desaparecen continuamente. As´ ı, en este trabajo describimos una evoluci´ on de nuestra propuesta anterior, que considera un modelo din´ amico del problema, m´ as cercano al escenario real. De manera que, en las instancias, los nodos y enlaces pueden ser eliminados o activados repentinamente. El algoritmo ACO ser´ a capaz de adaptarse a estos cambios y seguir ofreciendo soluciones ´ optimas. Dicho m´ etodo ha sido probado en tres instancias din´ amicas de diferentes tama˜ nos, obteniendo resultados muy prometedores. Palabras Clave—Virtualizaci´ on de Funciones de Red, NFV, Cadena de Funciones Virtuales, Enrutamiento, Routing, Redes 5G, Metaheur´ ısticas, Algoritmos de Optimizaci´ on basada en Colonias de Hormigas, OCH, ACO I. INTRODUCCI ´ ON Las tecnolog´ ıas de red actuales se centran en la enorme demanda que tienen estas, tanto en lo que respecta al n´ umero de dispositivos conectados a ellas como a los exigentes requisitos de baja latencia y gran ancho de banda. Las redes 5G han sido dise˜ nadas para hacer frente a estas nuevas caracter´ ısticas siendo capaces de servir con flexibilidad a las necesidades de los usuarios y servicios. As´ ı, las redes 5G se desplegar´ an sobre nuevas tecnolog´ ıas facilitadoras que permitir´ an la realizaci´ on de una red virtualizada, programable y flexible. Dos de estas tecnolog´ ıas son las redes definidas por software (SDN) y la virtualizaci´ on de las funciones de red (NFV), que a´ un se encuentran en fase de desarrollo y evoluci´ on [1]. Las SDN pretenden separar el reenv´ ıo y el procesamiento del tr´ afico, bas´ andose en la automatizaci´ on de algunas operaciones de gesti´ on de la red. La NFV se basa en la tecnolog´ ıa de virtualizaci´ on para ejecutar funciones de red implementadas por software. Estas dos tecnolog´ ıas se combinan en el llamado composici´ on de cadenas de funciones de red, o Service Function Chaining (SFC), cuyo objetivo es establecer din´ amicamente nuevos servicios de red a trav´ es de un conjunto de funciones virtuales, que deben ejecutarse en un orden espec´ ıfico [2]. Este trabajo aborda la composici´ on ´ optima de estas cadenas de servicios. As´ ı, dado un grafo de red en el que cada nodo puede ejecutar diferentes funciones virtuales; y considerando una cantidad de recursos por nodo, los recursos que requiere una funci´ on, el ancho de banda en los enlaces, y el orden de composici´ on deseado; el objetivo es construir el camino ´ optimo y v´ alido correspondiente a un servicio de red, que minimice el coste de encaminamiento (es decir, el n´ umero de saltos entre nodos). Se trata de un problema de dificultad NP-completo [3], que los autores resolvieron con una primera aproximaci´ on basada en un algoritmo de optimizaci´ on basada en colonias de hormigas (ACO) [4]. Los algoritmos ACO [5] se inspiran en el comportamiento de las hormigas naturales cuando buscan comida y se aplican para resolver problemas de optimizaci´ on combinatoria, por lo que utilizan una colonia de hormigas artificiales, que son agentes computacionales que se comunican entre s´ ı mediante una matriz de feromonas. Estos agentes trabajan sobre problemas formulados en un grafo con pesos en sus arcos. En cada iteraci´ on, cada hormiga construir´ a un 229 Moreno, Mora, 2021. camino completo (soluci´ on) movi´ endose a trav´ es de ´ el. Una vez construido el camino (o durante su construcci´ on), la hormiga depositar´ a un rastro de feromona que, generalmente, estar´ a relacionado con la bondad de la soluci´ on. Por lo tanto, este rastro ser´ a una medida (informativa para otros) de lo deseable que es seguir la misma ruta que la citada hormiga. As´ ı, desarrollamos en [4] una variaci´ on de ACO bautizada como Ant-SFC, inspirada en el modelo de ACO m´ as simple, el Sistema de Hormigas [6]. Sin embargo, los escenarios en los que se prob´ o el algoritmo ten´ ıan una clara desventaja: la ausencia de dinamismo. Las redes son sistemas en continuo cambio, es decir, los nodos (y tambi´ en los enlaces) surgen o desaparecen constantemente. Este comportamiento por ello se incorpora a las instancias para resolver el SFC de manera m´ as fidedigna. Para ello, el presente trabajo mejora tanto la definici´ on y modelizaci´ on del problema -haci´ endolo m´ as cercano a la realidad-, como el algoritmo para abordarlo. De modo que se han considerado instancias din´ amicas, en las que pueden ocurrir algunos eventos, por lo que nodos o enlaces pueden activarse o desactivarse repentinamente. Por tanto, el algoritmo se ha transformado en lo que hemos denominado Dynamic Ant-SFC (DAnt-SFC), capaz de adaptar su comportamiento para encontrar soluciones ´ optimas en estos escenarios cambiantes. Se han definido nuevas instancias del problema para probar el algoritmo propuesto, incluyendo todas ellas los eventos mencionados; tambi´ en se ha considerado un escenario m´ as complejo, teniendo este 52 nodos. En los experimentos se ha analizado la capacidad de adaptaci´ on del algoritmo y su rendimiento en la reconstrucci´ on de soluciones ´ optimas, as´ ı como la habilidad de recuperaci´ on que se ofrece a la red en esos eventos concretos. II. PROBLEMA A RESOLVER: ENRUTAMIENTO DIN ´ AMICO DE COSTE M´ INIMO PARA SFC Este trabajo se centra en la composici´ on de una cadena de funciones de servicio (SFC) en una red. El proceso de composici´ on de la SFC es uno de los principales retos de NFV, ya que en esta tarea intervienen tanto el c´ alculo de la ruta como la direcci´ on del tr´ afico. Adem´ as, debido a las propiedades de SFC, las rutas de flujo se definen como un conjunto ordenado en cadena de funciones de servicio oService Functions (SF) que maneja el tr´ afico de la entrega, el control y la supervisi´ on de un servicio/aplicaci´ on espec´ ıfico [7]. En este entorno y con el fin de mejorar el rendimiento y ahorrar recursos en la red, se requiere una estrategia ´ optima. As´ ı, hemos bautizado este problema como Optimizaci´ on del Enrutamiento para SFC (OR-SFC). En este proceso, ser´ a necesario determinar el camino que deben seguir los datos entre las funciones de red virtuales adyacentes para cada uno de los servicios solicitados. La Figura 1 muestra un ejemplo de instancia de este problema. En ´ el, la petici´ on del usuario se denomina conexi´ on, y est´ a definida por una tupla, C=(origen, destino, valor Fig. 1. Ejemplo de problema de Routing para SFC de la demanda, [funciones a ejecutar]), en la que la conexi´ on tiene como origen el nodo ‘1’ y como destino el nodo ‘6’, con una demanda de tr´ afico de 2 Mbps y las funciones virtuales a ejecutar 3, 5 y 6, en ese preciso orden. Si nos fijamos en la figura, el valor cercano a los enlaces hace referencia al correspondiente ancho de banda disponible en cada uno. En cada nodo se han indicado las funciones de red que puede ejecutar (cubos). Adem´ as, cada uno de los nodos tendr´ a asociados unos recursos inform´ aticos (CPU, Memoria, espacio en disco) agrupados en un ´ unico n´ umero por simplicidad. Del mismo modo, en la definici´ on del problema habr´ a una lista que asocie un coste en recursos a cada funci´ on, como sus requisitos para ser ejecutada. En el ejemplo (Figura 1), una soluci´ on debe servir las funciones 3, 5 y 6 (en este orden estricto). As´ ı, una posible soluci´ on podr´ ıa ser el camino [1→3→1→2→4→ 6], pero tambi´ en [1→3→5→6→4→6]. La elecci´ on de uno u otro afectar´ a al coste del encaminamiento en la red, as´ ı como a su rendimiento global. La ruta tambi´ en debe cumplir algunas restricciones adicionales, como que los enlaces deben tener suficiente ancho de banda para cubrir la demanda, y los nodos deben tener suficientes recursos disponibles para ejecutar las funciones virtuales. Adem´ as de lo descrito anteriormente, se a˜ nade al problema un componente din´ amico. Tratar´ a de simular un comportamiento m´ as realista de la red, manejando posibles cambios o modificaciones durante la resoluci´ on del problema. La forma en que se ha implementado esta parde din´ amica a˜ nade al problema una componente de complejidad, ofreciendo resultados m´ as realistas. Esta posibilidad ofrecer´ a potencialmente una gran flexibilidad a la hora de gestionar esta red dentro de un entorno virtualizado, ya que en la gran mayor´ ıa de los casos podr´ a hacer frente a situaciones imprevistas al no requerir que la red permanezca est´ atica en cuanto a su estructura, llevando el modelo del problema a un enfoque m´ as realista, considerando que las redes reales son completamente din´ amicas. III. ESTADO DEL ARTE SFC es uno de los principales retos en NFV. Este debe ser tratado como un problema de optimizaci´ on NP-completo. Es por ello que ha atra´ ıdo la atenci´ on de la academia, proponiendo diferentes soluciones para resolverlo, que principalmente se centran en soluciones exactas o heur´ ısticas, siendo s´ olo algunas de las propuestas This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 230 Composici´ on de Cadenas de Servicios con OCH las que utilizan m´ etodos de inteligencia computacional avanzada, como las metaheur´ ıstica. En cuanto a las aproximaciones exactas para resolver el problema OR-SFC, la mayor´ ıa de ellas se centran en modelos de optimizaci´ on basados en t´ ecnicas de Programaci´ on Lineal. Por ejemplo, los autores en [2] presentaron un modelo que resuelve el enrutamiento SFC y la asignaci´ on de funciones virtuales para los intervalos de horas pico. Cabe destacar tambi´ en el trabajo desarrollado en [8], en el que los autores formularon un modelo matem´ atico que resuelve el problema utilizando m´ etodos de descomposici´ on. Tambi´ en existen algoritmos heur´ ısticos para resolver este tipo de problemas. Estas heur´ ısticas son ´ utiles para encontrar soluciones factibles y precisas para instancias mayores del problema en un tiempo de c´ alculo reducido. Los algoritmos Greedy son muy utilizados para este fin, como se hace en [9] y [10]. En general, se ha demostrado que las heur´ ısticas producen soluciones aproximadas cercanas al ´ optimo y son apropiadas cuando hay que resolver instancias grandes. En estos casos, la heur´ ıstica proporciona un equilibrio ´ optimo entre la validez de la soluci´ on y el coste de c´ alculo [11]. Por el contrario, las metaheur´ ısticas no se han aplicado demasiado en este ´ ambito. Aunque el problema ORSFC es muy adecuado para la t´ ecnica de Optimizaci´ on basada en Colonias de Hormigas si bien, hasta donde sabemos, s´ olo nuestro trabajo anterior [4] se ha centrado en la resoluci´ on de este problema aplicando ACO. Otros enfoques en la literatura se enfrentan en cambio a la llamada Asignaci´ on de Recursos en NFV, como [12] donde los autores aplican Tabu Search; o [13] en el que los autores abordan la optimizaci´ on de la ubicaci´ on de Funciones Virtuales de Red (VNFs) en los nodos de la red, considerando el consumo de energ´ ıa en los servidores requeridos, aplicando una variaci´ on del Algoritmo Gen´ etico. Dentro de este ´ ambito, algunos trabajos tratan de resolver problemas an´ alogos aplicando un enfoque desde un punto de vista din´ amico, donde la topolog´ ıa de la red puede cambiar. Este es el caso de [14] donde se adoptan diferentes colonias de hormigas simult´ aneamente para favorecer la exploraci´ on en redes din´ amicas, evitando en gran medida el estancamiento. Otro caso se da en [15], donde se utiliza un algoritmo basado en ACO para resolver el enrutamiento din´ amico anycast y la asignaci´ on de longitudes de onda en redes ´ opticas, ofreciendo reducciones de la probabilidad de bloqueo y mejoras sobre otros m´ etodos. Sin embargo, de nuevo, ninguna de las propuestas se centra en la resoluci´ on del problema SFC. IV. ALGORITMO IMPLEMENTADO: ANT-SFC DINAMICO El algoritmo implementado para abordar la versi´ on din´ amica del problema es una ’evoluci´ on’ de nuestro anterior Ant-SFC [4], es decir, una adaptaci´ on del Sistema de Hormigas cl´ asico [6] para resolver el problema SFC est´ andar. As´ ı, cubrir´ a la resoluci´ on de caminos ´ optimos en un modelo de red de telecomunicaciones, cumpliendo con las siguientes restricciones (ver Secci´ on II): •Un camino debe ser definido en el grafo que modela la red para cada resoluci´ on de conexi´ on (solicitud de servicio). Debe pasar por nodos disponibles que puedan servir cada una de las funciones de red requeridas, en el orden dado (indicado por cada servicio). •Cada enlace debe tener suficiente capacidad (ancho de banda disponible) para poder satisfacer la demanda de tr´ afico de cada conexi´ on. ´ Esta disminuir´ a cada vez que una ruta pase por un enlace. •Los nodos, al igual que los enlaces, deben tener suficientes recursos disponibles para la ejecuci´ on de las funciones requeridas. Los recursos de los nodos disminuir´ an seg´ un la demanda de cada funci´ on ejecutada. Estas restricciones deben cumplirse incluso teniendo en cuenta que los nodos o enlaces podr´ ıan activarse o desactivarse repentinamente, ya que las instancias del problema son din´ amicas. Por lo tanto, el algoritmo adaptado se ha denominado Dynamic Ant-SFC o simplemente DAnt-SFC. El dinamismo implementado pretende a˜ nadir un componente a´ un m´ as realista a las redes simuladas. Se conseguir´ a mediante la eliminaci´ on o introducci´ on de nodos y/o enlaces en determinados momentos de la ejecuci´ on, haciendo que el algoritmo sea capaz de recuperarse de eventos de potencial colapso de nodos principales. De este modo, el algoritmo recibir´ a algunas tuplas dentro de un archivo de eventos, como una modelizaci´ on ”controlada” y simplificada de ese dinamismo. El formato de cada tupla es (n´ umero de iteraci´ on, activaci´ on-desactivaci´ on del nodo, nodo, activaci´ ondesactivaci´ on del enlace, nodo origen del enlace, nodo destino del enlace). Por ejemplo, la tupla “(3, 0, 4, 0, 4, 8)” equivaldr´ ıa a decirle al algoritmo que a partir de la iteraci´ on 3, el nodo 4 se desactivar´ a junto con el enlace de 4 a 8, tambi´ en desactivado e inutilizable, a menos que se reactive expl´ ıcitamente de nuevo en un evento posterior. Cada vez que una de estas tuplas sea procesada por la parte de dinamismo, se activar´ a autom´ aticamente una parte del algoritmo para eliminar o a˜ nadir el nodo correspondiente, asegurando as´ ı que las sucesivas soluciones que se calculen considerar´ an una versi´ on actualizada de la red. Adem´ as, al final de cada proceso, se comprueba si existe una soluci´ on potencialmente mejor, teniendo en cuenta el tiempo y la capacidad de los nodos probados. La resoluci´ on de cada conexi´ on (solicitud de servicio) se ha planteado como una b´ usqueda de camino ´ optimo individual, aunque sean dependientes entre s´ ı por el consumo de ancho de banda de los enlaces y de recursos de los nodos. El cuerpo principal de DAnt-SFC se presenta en el Algoritmo 1. La adaptaci´ on del algoritmo se ha centrado en los siguientes aspectos: •Inicializaci´ on del grafo: el grafo tiene que estar inicializado tal y como estaba antes de que la hormiga anterior lo modificara construyendo su soluci´ on antes de que cualquier hormiga comience a construir una soluci´ on. This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 231 Moreno, Mora, 2021. Algorithm 1 DAnt-SFC ( ) Algoritmo principal DAnt-SFC Inicializacion parametros() Leer configuracion red() Leer conexiones() Leer configuracion dinamismo() /* Se buscar´ a una soluci´ on por cada conexi´ on */ for cada conexi´ on c do while criterio finalizacion no terminado do for cada hormiga h do s[h]=Construir Solucion(c,h) end for /* En todos los enlaces del grafo */ Evaporacion Feromona() /* Links usados por la mejor hormiga */ s*=Elegir Mejor Solucion(s[h]) Actualizacion Feromona Global(s*) Actualizar estado dinamismo() /* Comprueba si la mejor soluci´ on es todav´ ıa v´ alida*/ end while /* Ancho de banda de los enlaces y los nodos son actualizados */ Actualizacion Red(c,s*) end for •Heur´ ıstica: se ha considerado asignar una mayor probabilidad de ser elegido a los enlaces con mayor ancho de banda disponible, intentando minimizar el riesgo de agotamiento de los enlaces. Adem´ as, se ha incluido una condici´ on para la selecci´ on del siguiente nodo en la construcci´ on de la soluci´ on: si alguno de los nodos es capaz de servir a la siguiente funci´ on de red que espera ser servida en la cadena, se duplicar´ a la probabilidad de elecci´ on del nodo para guiar a la hormiga hacia ´ el. Obviamente, el enlace debe tener suficiente ancho de banda disponible para cada caso y el nodo seleccionado tiene que tener suficientes recursos para ejecutar la siguiente funci´ on de red en la cadena. •Ruleta de probabilidades: se utilizar´ a una ruleta de probabilidades como pol´ ıtica de decisi´ on para el siguiente estado una vez asignada la probabilidad de pasar a cada nodo desde el real en la construcci´ on de una soluci´ on. Esta ruleta consiste en asignar un espacio proporcional a la probabilidad de cada nodo en una ”ruleta virtual” y su giro aleatorio para obtener el siguiente nodo elegido. •Restricci´ on del ancho de banda de los enlaces: se basa en la construcci´ on de la lista de nodos factibles. •Restricci´ on de recursos de nodos: se basa en la construcci´ on de la lista de nodos factibles. •Actualizaci´ on de enlaces y nodos (construcci´ on de una soluci´ on): el ancho de banda de los enlaces y los recursos de los nodos (en caso de que el nodo cumpla una funci´ on de red) se actualizan cada vez que una hormiga se desplaza hacia un nodo de la red mientras se construye una soluci´ on para resolver una conexi´ on. Ambos valores se actualizan con la demanda de tr´ afico de la conexi´ on y el coste en recursos de la funci´ on de red, respectivamente, evitando la generaci´ on de bucles infinitos. •Actualizaciones de la red (conexiones): la red se actualiza teniendo en cuenta la trayectoria definida por la soluci´ on cada vez que se encuentra una soluci´ on para una determinada cadena. Por lo tanto, los enlaces y nodos utilizados para este camino se actualizan siguiendo el m´ etodo utilizado en el caso anterior. •restricci´ on de trayectoria completa: una soluci´ on s´ olo se considerar´ a v´ alida si comienza y termina en los nodos exactamente dados por la conexi´ on. Tambi´ en tiene que pasar por los nodos que cumplen funciones de red en el orden dado por la propia conexi´ on. Si no es as´ ı, la soluci´ on no se utilizar´ a. •Coste de la ruta (conexi´ on): ser´ a el n´ umero de saltos requerido en el grafo para la composici´ on de la cadena de funciones necesaria para completar una conexi´ on. •Coste de la soluci´ on global: una soluci´ on completa estar´ a formada por unos caminos de coste m´ ınimo para resolver cada una de las conexiones solicitadas para la instancia seleccionada en un determinado intervalo de tiempo. Por lo tanto, el coste de la soluci´ on global ser´ a el n´ umero total de saltos de todas las conexiones solicitadas. •Actualizaci´ on de la feromona: al igual que el correspondiente evaporaci´ on de la feromona realizado en todos los enlaces tras la construcci´ on de todas las soluciones, s´ olo se realizar´ a una actualizaci´ on de la feromona en los enlaces que formen parte de la mejor soluci´ on, que ser´ a directamente proporcional al n´ umero de saltos en esta misma. Cuanto menor sea el n´ umero de saltos, mayor ser´ a la contribuci´ on en los enlaces. V. EXPERIMENTOS Y RESULTADOS Se han considerado tres instancias diferentes para probar el algoritmo propuesto: Instancia de 6 nodos: se utiliza como un enfoque conceptual, donde el algoritmo ha sido evaluado y validado de una manera m´ as intuitiva. Las caracter´ ısticas del gr´ afico se pueden ver en: https://doi.org/10.6084/m9. figshare.14572200.v1 incluyendo las funciones de red disponibles en cada nodo as´ ı como el ancho de banda asociado a cada enlace. En esta instancia se consideran 3 conexiones diferentes a resolver, concretamente (ver formato 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]). Instancia de 19 nodos: es un gr´ afico de 19 nodos que modela un caso m´ as realista, m´ as cercano a los que se resolver´ an en la realidad. La topolog´ ıa de esta instancia se puede consultar desde https://doi.org/10.6084/ m9.figshare.14572224.v1. Las propiedades de los enlaces en esta instancia se pueden ver en https://doi.org/10.6084/ m9.figshare.14572080.v1. Esta instancia est´ a considerando estas 5 conexiones siguientes para resolver: 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]). Instancia de 52 nodos: es un grafo de 52 nodos que modela un caso pr´ oximo a la realidad. Es la instancia m´ as grande utilizada en este trabajo. Su topolog´ ıa se muestra en https://doi.org/10.6084/m9.figshare.14572230.v1, mientras This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 232 Composici´ on de Cadenas de Servicios con OCH Algorithm 2 Construccion Solucion (conexion, ant id) Algoritmo de construccion de una solucion DAnt-SFC Inicializacion hormiga(ant id) Inicializacion red() /* Establece los valores de la red */ Aplicacion dinamismo() /* Comprueba los nodos y enlaces activados/desactivados */ nodo actual = conex.nodo inicial funcion actual = conex.funciones[inicio] L= guardar(nodo actual) /* Lista de estados visitados */ F= guardar(funcion actual) /* Lista de funciones servidas */ while (nodo actual 6=conex(nodo final)) AND (funcion actual 6=conex.funcion[fin]) do /* A: lista nodos alcanzables, P: probabilidad de moverse a cada nodo alcanzable, Ω: restricciones del problema */ P= calcular probabilidades transicion(nodo actual, A,F,L,Ω) siguiente nodo = ruleta probabilidad(P,Ω) /* Actualizaci´ on del ancho de banda de los enlaces */ Actualizacion Enlace(siguiente nodo) L= guardar(siguiente node) nodo actual = siguiente nodo /* Si la funci´ on est´ a disponible ser´ a servida, y los recursos del nodo, actualizados */ if funcion actual in funciones.actuales nodo[] then Actualizar Nodo(funcion actual) F= guardar(funcion actual) funcion actual = conex.siguientes(funciones[]) end if end while que las tablas correspondientes a los enlaces de esta instancia pueden consultarse en https://doi.org/10.6084/m9. figshare.14483592.v2. Hay que resolver 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. Resultados obtenidos Para la ejecuci´ on del algoritmo se ha utilizado un ordenador personal con un procesador Intel Core 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 bits. Las configuraciones del algoritmo consideradas en cada instancia se muestran en la Tabla I. Tabla I PARAMETROS CONSIDERADOS EN LOS EXPERIMENTOS Parametro Instancia 6N Instancia 19N Instancia 52N Iteraciones 6 19 52 Hormigas 12 38 104 α(peso feromona) 1.2 1.2 1.2 β(peso heuristica) 2.0 2.0 2.0 ρ(factor evaporaci´ on) 0.3 0.3 0.3 Los valores dados se han fijado en base a las recomendaciones le´ ıdas en art´ ıculos sobre aplicaci´ on de ACO, como feromona y pesos heur´ ısticos para el c´ alculo de la probabilidad de elecci´ on del siguiente nodo, aunque posteriormente se han ajustado y modificado siguiendo un proceso de experimentaci´ on sistem´ atica. Los n´ umeros de iteraciones y conexiones se han fijado con el fin de obtener buenas soluciones en un tiempo aceptable, aunque se podr´ ıa llevar a cabo una investigaci´ on posterior s´ olo para determinar de forma ´ optima estos valores iniciales, pero no es el objetivo de este trabajo. Dado que se trata de un algoritmo no determinista, para obtener resultados fiables, se han realizado 10 ejecuciones independientes resolviendo la misma instancia del problema (con el mismo n´ umero de conexiones) para cada escenario posible y para cada una de las tres instancias a probar. Como se describe en la secci´ on IV, se ha desarrollado una funci´ on de dinamismo para este algoritmo. ´ Esta permite obtener las mejores soluciones posibles mientras ciertos nodos de la red pueden caer o estar en l´ ınea durante la ejecuci´ on (simulando un escenario real de red de telecomunicaciones) sin modificar el comportamiento b´ asico del c´ odigo ejecutado. Se utiliza para reforzar el ya de por s´ ı buen rendimiento del algoritmo en un mayor n´ umero de situaciones y escenarios diferentes. •Versi´ on elimina nodo: un nodo cr´ ıtico, que forma parte de la mejor soluci´ on, es eliminado de la mejor soluci´ on hasta el momento: con este tipo de variante, el algoritmo se ve obligado a recalcular la mejor ruta obtenida hasta el momento, dado que un nodo cr´ ıtico ser´ a eliminado de la misma, no siendo posible por tanto su utilizaci´ on y teniendo que aplicar las utilidades de la funci´ on de dinamismo para seleccionar la mejor opci´ on posible. •Versi´ on elimina dos nodos: Se eliminan dos nodos cr´ ıticos de la mejor soluci´ on hasta el momento: ser´ a similar al caso anterior, pero con una dificultad a˜ nadida (habr´ a una mayor parte de la matriz de nodos no disponible para ser seleccionada), haciendo que la nueva selecci´ on de rutas sea m´ as desafiante y “realista”. •Versi´ on elimina restaura nodo: Se elimina un nodo cr´ ıtico de la mejor soluci´ on hasta el momento y luego se restaura: para esta situaci´ on, se eliminar´ a un nodo cr´ ıtico seleccionado y, despu´ es de un cierto n´ umero de iteraciones, se restaurar´ a, observando si el algoritmo vuelve a seleccionar la mejor soluci´ on previamente guardada o no (si se ha visto obligado a mejorarla). En la Tabla II, se pueden ver los resultados obtenidos en las simulaciones, tanto en n´ umero de saltos de la mejor This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 233 Moreno, Mora, 2021. soluci´ on y tiempo de ejecuci´ on, como en tiempo, valor medio y desviaci´ on est´ andar. 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. Instancia 6N Versi´ on Ejec. Coste t(s) Media SD elimina nodo 7 13 0.073 13.8 0.707 elimina dos nodos - - - - - elimina restaura nodo 2 12 0.070 12.2 1.41 Instancia 19N Versi´ on Ejec. Coste t(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 restaura nodo 3 17 0.303 17.8 1.41 Instancia 52N Versi´ on Ejec. Coste t(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 restaura nodo 2 37 4.953 38.6 2.121 Cabe destacar que, para la simulaci´ on de la instancia m´ as peque˜ na (6 nodos), al ser utilizada como referencia para replicar el funcionamiento de las dem´ as y debido a su reducido tama˜ no, la versi´ on elimina dos nodos de la prueba (en la que se eliminan dos nodos fundamentales) no puede realizarse como tal, ya que el c´ alculo de ciertas rutas ser´ ıa imposible. Sin embargo, su correcto funcionamiento para este caso puede verificarse en las instancias m´ as grandes. Por este motivo, se han utilizado la versi´ on elimina nodo y la versi´ on elimina restaura nodo, siendo esta ´ ultima igualmente v´ alida como ejemplo de funcionamiento, ya que se elimina un nodo y se reactiva, obligando al algoritmo a recalcular las rutas (como efectivamente hace). Fig. 2. Mejor soluci´ on encontrada para la Versi´ on elimina nodo (un nodo eliminado (C) en la iteraci´ on n´ umero 2) de la instancia de 6 nodos con 3 conexiones. Coste expresado en n´ umero de saltos junto a cada conexi´ on. Figura con mayor resoluci´ on disponible en https://doi.org/10. 6084/m9.figshare.16587497 Los resultados num´ ericos presentados en la Tabla II Se puede observar claramente la diferencia entre las distintas versiones ejecutadas. Para el caso de 6 nodos, en la primera versi´ on, como se ve en la Figura 2, un nodo fundamental (C) bajar´ a en la iteraci´ on n´ umero 2. Cuando Fig. 3. Mejor soluci´ on encontrada para la Versi´ on elimina restaura nodo (un nodo eliminado (C) en la iteraci´ on n´ umero 2, luego reactivado (C) en la iteraci´ on n´ umero 6) de la instancia de 6 nodos con 3 conexiones. Coste expresado en n´ umero de saltos junto a cada conexi´ on. Figura con mayor resoluci´ on disponible en https: //doi.org/10.6084/m9.figshare.16587512 este nodo cae, junto con sus enlaces, no puede ser utilizado en la red para futuros c´ alculos. En esta versi´ on, esto ocurre casi desde el principio (iteraci´ on n´ umero 2), por lo que el algoritmo podr´ ıa utilizar primero este nodo. Sin embargo, tras la correspondiente aplicaci´ on de la funci´ on de dinamismo, este nodo se desactivar´ a y autom´ aticamente, la mejor soluci´ on hasta ahora procesada, en caso de que lo contuviera, ser´ a eliminada y se obtendr´ a otra factible. Se puede observar que para la Versi´ on elimina restaura nodo, que se puede observar en la Figura 3, en la que este mismo nodo se cae pero en sucesivas iteraciones se reactiva de nuevo en la iteraci´ on n´ umero 6, el algoritmo detecta que es la ruta m´ as eficiente y que puede volver a utilizar este nodo, ofreciendo adem´ as un menor coste para servir, por ejemplo, en la primera conexi´ on requerida. De este modo, siempre se obtiene la mejor soluci´ on posible, teniendo en cuenta las capacidades que ofrece la red. Como se ha mencionado anteriormente, con la instancia de 19 nodos se pueden observar gr´ aficamente los cambios realizados en la red. En la primera versi´ on, al poco de comenzar la ejecuci´ on, un nodo se cae de la red (nodo N) en la iteraci´ on n´ umero 4, lo que hace que el algoritmo recalcule las rutas en funci´ on de c´ omo ha quedado la topolog´ ıa. Despu´ es de todas las ejecuciones, el resultado es el que se muestra en la Figura 4. Esto podr´ ıa ser un problema a priori, ya que uno de estos nodos fue utilizado en las rutas ´ optimas de la versi´ on elimina nodo. Sin embargo, la heur´ ıstica acabar´ a encontrando otra ruta ´ optima (de hecho, en este caso incluso mejor que la anterior) para encaminar la conexi´ on seg´ un lo requerido y que se cumplan todos los requisitos. Con respecto a la versi´ on elimina dos nodos, ambos nodos N y M ya no est´ an activos en la red (desconectados en la iteraci´ on 4 y 10 respectivamente), por lo que aparece una marca roja en ellos mismos y en sus enlaces. De nuevo, el algoritmo es capaz de recalcular nuevas rutas que no incluyan esa parte de la red sin mayor dificultad, This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 234 Composici´ on de Cadenas de Servicios con OCH Fig. 4. Mejor soluci´ on encontrada para la Versi´ on elimina nodo (un nodo eliminado (N) en la iteraci´ on n´ umero 4) de la instancia de 19 nodos con 5 conexiones. Coste expresado en n´ umero de saltos junto a cada conexi´ on. Figura con mayor resoluci´ on disponible en: https://doi. org/10.6084/m9.figshare.16587428 Fig. 5. Mejor soluci´ on encontrada para la Versi´ on elimina dos nodos (dos nodos eliminados (M y N) en las iteraciones n´ umero 4 y 10 respectivamente) de la instancia de 19 nodos con 5 conexiones. Coste expresado en n´ umero de saltos junto a cada conexi´ on. Figura con mayor resoluci´ on disponible en: https://doi.org/10.6084/m9.figshare.16587443 Fig. 6. Mejor soluci´ on encontrada para la Versi´ on elimina restaura nodo (dos nodos eliminados (M y N) en las iteraciones 4 y 10 respectivamente, y luego uno reactivado (M) en la iteraci´ on n´ umero 16) de la instancia de 19 nodos con 5 conexiones. Coste expresado en n´ umero de saltos junto a cada conexi´ on. Figura con mayor resoluci´ on disponible en: https://doi.org/10.6084/m9.figshare.16587446 como puede verse en la Figura 5. Por ´ ultimo, los caminos formados en la Versi´ on elimina restaura nodo para esta instancia de 19 nodos se pueden observar en Figura 6. Tras eliminar los nodos N y M en sucesivas iteraciones (iteraci´ on 3 y 9 respectivamente), las soluciones calculadas ahora no pueden incluirlos en las rutas obtenidas. Sin embargo, en la iteraci´ on n´ umero 16 (del total de 19 realizadas), el nodo M vuelve a estar activo, junto con sus correspondientes enlaces. As´ ı, el algoritmo vuelve a incluirlo en sus tablas de nodos activos y lo tiene en cuenta para las nuevas soluciones; tanto es as´ ı que la soluci´ on final para la conexi´ on 4 lo utiliza en sus resultados. En la instancia de 52 nodos, se ha decidido mostrar gr´ aficamente la Versi´ on elimina restaura nodo de los experimentos realizados, mientras que de las versiones elimina nodo y elimina dos nodos se mostrar´ an ´ unicamente los resultados en la Figura 7. En este caso, se muestra c´ omo los nodos V y X se desactivan (en las instancias 4 y 8, respectivamente), y el sistema debe dejar de utilizarlos para el c´ alculo de las soluciones. Sin embargo, el nodo V vuelve a activarse a partir de la instancia 13, por lo que puede volver a utilizarse. De hecho, en la conexi´ on 9, se utiliza para la mejor opci´ on de la misma. Se puede observar la gran complejidad de la red y c´ omo el comportamiento del algoritmo es flexible y robusto ante los cambios, adapt´ andose a ellos en cada situaci´ on (Figura 8). Fig. 7. Resultados de la instancia de 52 nodos con 10 conexiones, Versi´ on elimina nodo y 2. Coste expresado en n´ umero de saltos junto a cada conexi´ on. VI. CONCLUSIONES Y TRABAJO FUTURO Este trabajo presenta una adaptaci´ on de un algoritmo de Optimizaci´ on basada en Colonias de Hormigas o Ant Colony Optimization(ACO) para resolver el problema de enrutamiento en Service Function Chaining (SFC) dentro de una red definida por software (SDN). El problema se ha definido considerando tambi´ en el dinamismo en la topolog´ ıa de la red, ya que los nodos y enlaces pueden ser activados o desactivados en cualquier momento. El algoritmo propuesto se ha aplicado en tres instancias diferentes con distintos tama˜ nos, y varios eventos de activaci´ on/desactivaci´ on predefinidos en algunos de los nodos y enlaces existentes. A la vista de los resultados obtenidos, podemos concluir que DAnt-SFC es capaz de construir soluciones ´ optimas, incluso haciendo frente a cambios dr´ asticos en la topolog´ ıa This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 235 Moreno, Mora, 2021. Fig. 8. Mejor soluci´ on encontrada para la Versi´ on elimina restaura nodo (dos nodos eliminados (V y X) en las iteraciones 4 y 8 respectivamente), y luego uno reactivado (V) en la iteraci´ on 13) de la instancia de 52 nodos con 10 conexiones. Resultados de la Figura 9. Figura con mayor resoluci´ on disponible en https://figshare.com/ s/b48a4c3c9f85ebca721d Fig. 9. Resultados de la instancia de 52 nodos con 10 conexiones, Versi´ on elimina restaura nodo, referida a la Figura 8. Coste expresado en n´ umero de saltos junto a cada conexi´ on. de la red como puede ser la ca´ ıda de nodos cr´ ıticos en las rutas previamente formadas, o la reincorporaci´ on de los mismos, debiendo recalcular las rutas formadas hasta dicho momento. Adem´ as, los tiempos de c´ alculo, siempre muy inferiores a 1 segundo para instancias peque˜ nas y medianas, aunque algo mayores (en torno a 5 segundos para las de mayor tama˜ no) son aceptables para la resoluci´ on de instancias consideradas ejecutadas en tiempo real. En cualquier caso, una de las ventajas de los algoritmos ACO es su capacidad de obtener soluciones v´ alidas desde la primera iteraci´ on, es decir, desde el mismo primer c´ alculo realizado durante una ejecuci´ on, as´ ı como su capacidad de autoadaptar su comportamiento a los cambios en la definici´ on del problema, como sonlos cambios de topolog´ ıa en estas instancias. Como trabajo futuro, probaremos mejores funciones heur´ ısticas para guiar la construcci´ on de soluciones en el algoritmo ACO. Adem´ as, se podr´ ıan implementar algunos enfoques h´ ıbridos, como los m´ etodos de b´ usqueda local. Tambi´ en se probar´ an modelos ACO m´ as sofisticados. AGRADECIMIENTOS Este trabajo ha sido parcialmente financiado por los proyectos RTI2018-102002-A-I00 (Ministerio de Ciencia, Innovaci´ on y Universidades), PID2020-113462RB-I00 (Ministerio de Ciencia e Innovaci´ on), TIN2017-85727-C42-P (Ministerio de Econom´ ıa y Competitividad), B-TIC402-UGR18 (FEDER y Junta de Andaluc´ ıa), y el proyecto P18-RT-4830 (Junta de Andaluc´ ıa). REFERENCIAS [1] I. Afolabi, T. Taleb, K. Samdanis, A. Ksentini, and H. Flinck, “Network slicing and softwarization: A survey on principles, enabling technologies, and solutions,” IEEE Communications Surveys Tutorials, vol. 20, no. 3, pp. 2429–2453, 2018. [2] V. Eramo, E. Miucci, M. Ammar, and F. G. Lavacca, “An approach for service function chain routing and virtual function network instance migration in network function virtualization architectures,” IEEE/ACM Trans. Networking, vol. 25, no. 4, pp. 2008–2025, 2017. [3] T. Lukovszki, M. Rost, and S. Schmid, “It’s a match!: Nearoptimal and incremental middlebox deployment,” SIGCOMM Comput. Commun. Rev., vol. 46, pp. 30–36, Jan. 2016. [4] S. Moreno, A. M. Mora, P. Padilla, J. Carmona-Murillo, and P. A. Castillo, “Applying ant colony optimization for service function chaining in a 5g network,” in Sixth International Conference on Internet of Things: Systems, Management and Security, IOTSMS 2019, Granada, Spain, October 22-25, 2019 (M. A. Alsmirat and Y. Jararweh, eds.), pp. 567–574, IEEE, 2019. [5] M. Dorigo and T. St¨ utzle, “The ant colony optimization metaheuristic: Algorithms, applications, and advances,” in Handbook of Metaheuristics (G. K. F. Glover, ed.), pp. 251–285, Kluwer, 2002. [6] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, vol. 26, no. 1, pp. 29–41, 1996. [7] A. M. Medhat, T. Taleb, A. Elmangoush, G. A. Carella, S. Covaci, and T. Magedanz, “Service function chaining in next generation networks: State of the art and research challenges,” IEEE Communications Magazine, vol. 55, pp. 216–223, February 2017. [8] N. Huin, B. Jaumard, and F. Giroire, “Optimal Network Service Chain Provisioning,” IEEE/ACM Transactions on Networking, vol. 26, pp. 1320–1333, jun 2018. [9] Z. Allybokus, N. Perrot, J. Leguay, L. Maggi, and E. Gourdin, “Virtual function placement for service chaining with partial orders and anti-affinity rules,” Networks, vol. 71, no. 2, pp. 97–106, 2018. [10] L. Qu, M. Khabbaz, and C. Assi, “Reliability-Aware Service Chaining in Carrier-Grade Softwarized Networks,” IEEE Journal Selec. Areas in Communications, vol. 36, no. 3, pp. 558–573, 2018. [11] T.-M. Nguyen, M. Minoux, and S. Fdida, “Optimizing resource utilization in NFV dynamic systems: New exact and heuristic approaches,” Computer Networks, vol. 148, pp. 129–141, jan 2019. [12] J. Gil-Herrera and J. F. Botero, “A scalable metaheuristic for service function chain composition,” in 2017 IEEE 9th Latin-American Conference on Communications, LATINCOM 2017, vol. 2017Janua, pp. 1–6, Institute of Electrical and Electronics Engineers Inc., dec 2017. [13] L. Laaziz, N. Kara, R. Rabipour, C. Edstrom, and Y. Lemieux, “FASTSCALE: A fast and scalable evolutionary algorithm for the joint placement and chaining of virtualized services,” Journal of Network and Computer Applications, vol. 148, p. 102429, dec 2019. [14] K. M. Sim and W. H. Sun, “Multiple ant-colony optimization for network routing,” in First International Symposium on Cyber Worlds, 2002. Proceedings., pp. 277–281, 2002. [15] K. Bhaskaran, J. Triay, and V. M. Vokkarane, “Dynamic anycast routing and wavelength assignment in wdm networks using ant colony optimization (aco),” in 2011 IEEE International Conference on Communications (ICC), pp. 1–6, 2011. This work is licensed under a Creative Commons 4.0 International License (CC BY-NC-ND 4.0) 236