Printer Friendly

Solucion Metaheuristica para el Problema de Enrutamiento (RWA) en Redes de Opticas de Multiplexacion por Division de Longitud de Onda (WDM).

Metaheuristic Solution for the Routing and Wavelength Assignment (RWA) Problem in Wavelength-Division Multiplexing (WDM) Optical Networks

INTRODUCCION

Las velocidades de transporte en las redes opticas se han incrementado gracias a la tecnologia WDM (Wavelength Division Multiplexing) donde cada longitud de onda alcanza hasta 2.5 Gbps y multiplicada por esta tecnologia alcanza tantas veces como longitudes de onda se inserten en la misma fibra optica monomodo. Por otro lado, se alcanzan tasas de 10 Gbps, 25 Gbps y otras tasas basadas en transmision coherente. Los problemas asociados a estas redes radican en la obtencion de rutas y la seleccion de la longitud de onda asociada, si se utiliza una misma longitud de onda para cada enlace de la ruta se trata de redes sin conversion de longitud de onda, y si se utilizan longitudes de onda diferentes en cada longitud de onda enlace de la ruta se trata de redes con conversion de longitud de onda, es decir los dispositivos de conmutacion OXC (Optical Cross Connect) deben tener la capacidad de conversion en cada caso.

Las redes actuales inclusive tienen capacidad para conmutar fibras, bandas de longitudes de onda (waveband) y longitudes de onda. Los algoritmos utilizados en estas redes son de tipo heuristico y metaheuristico a diferencia de los dispositivos de enrutamiento electronico donde se desarrollaron una serie de algoritmos tales como: Dikstra, Bellman-Ford, Floyd Warshall, Ford-Fulkerson entre otros, que se pueden denominar convencionales, estos ultimos buscan la optimizacion basada en el vector distancia o sistema de costos. Sin embargo, los algoritmos heuristicos no son capaces de optimizar si el universo de soluciones es de un alto dinamismo y en trafico variable (Rodriguez et al., 2014; Rodriguez et al. 2015). Los escenarios de trafico dinamico no pueden ser resueltos por algoritmos optimizadores debido a que el universo de solucion varia constantemente. Sin embargo, la heuristica permite encontrar soluciones que no son necesariamente optimas pero si son buenas soluciones, y no solo una solucion sino varias en el mismo proceso algoritmico, dandole robustez a estos algoritmos.

Se han estudiado heuristicas y meta heuristicas tales como: Algoritmos geneticos, Simulated Annealing, Tabu Search, Luciernaga, entre otros. Ademas, se han desarrollado diferentes meta heuristicas que modifican o perfeccionan las heuristicas a traves de combinaciones o inclusion de procesos dentro de los algoritmos originales mejorando el tiempo de obtencion de la solucion, mayor cantidad de soluciones o dirigir las soluciones hacia un espacio del universo preestablecido o deseable. En ambito de las redes opticas WDM (Wavelength Division Multiplexing) la tecnologia predominante es el switching que permite conmutar diferentes canales entre longitudes de onda, bandas de longitudes de onda, fibras, canales de tiempo, etc. (Zheng et al., 2016; Sadiq etal., 2016; Gutierrez et al., 2016). Los algoritmos heuristicos responden con mejores resultados para trafico dinamico en este tipo de redes, sin embargo es muy dificil lograr una mejora en la probabilidad de bloqueo y la utilizacion de la red de manera simultanea. En la mayoria de trabajos el trafico es modelado con una distribucion poisson y la carga se da en erlangs, siendo el trafico estatico o dinamico se logra establecer una relacion entre el tipo de trafico y la relacion existente entre el tiempo promedio entre llegadas de solicitudes de servicio y el tiempo promedio de solicitudes de conexion.

La presente investigacion se muestra varias heuristicas y desarrolla la comparacion de simulaciones hasta los 180 Erlangs en la red NSFNET (National Science Foundation Network), mostrando una nueva meta heuristicas basada en el algoritmo Snake One y muestra los resultados para la meta heuristica Snake Three (SNK3), comparada con las heuristicas algoritmo genetico (AG), Simulated Annealing (SA), algoritmo de referencia, Tabu Search (TS), Snake One (SNK1), Snake Two (SNK2) (Zang et al., 2001; Rodriguez et al., 2015; Rodriguez et al., 2018) y otros aplicados a diferentes areas (Alarcon-Aquino et al., 2005; Russo et al., 2011; Piedrahita et al., 2014).

ENCAMINAMIENTO EN REDES OPTICAS

En las redes opticas se presenta el problema RWA (Routing Wavelength Assignment) el mismo se define como la problematica de encontrar una ruta y longitud de onda para cada enlace de la ruta. En las redes opticas se puede distinguir las redes sin conversion de longitud de onda (lambda) donde cada enlace tiene la misma lambda y las redes con conversion de la longitud de onda donde cada enlace puede tener diferente lambda.

La condicion de usar la misma lambda es conocida en la literatura como restriccion de continuidad de longitud de Onda o CCW (Constraint Continuity Wavelength) y para el otro caso se denomina reutilizacion de longitud de onda o WR (Wavelength Reuse). Un camino de luz o Lightpath (LP) es el conjunto de enlaces que conforman la ruta y una longitud onda asociada para el caso CCW. Por ejemplo una ruta del nodo 2 al nodo 5 para un sistema de 8 nodos etiquetados del 0 al 7, con 3 longitudes de onda por enlace ([[lambda].sub.0], [[lambda].sub.1], [[lambda].sub.2]), y se puede observar en la figura 1.

LP = (R, [[lambda].sub.1]) = ([e.sub.21] - [e.sub.13] - [e.sub.36] - [e.sub.65], [[lambda].sub.0]) (1)

LP = ([e.sub.21], [[lambda].sub.1]) - ([e.sub.13] [[lambda].sub.0]) - ([e.sub.36], [[lambda].sub.1]) - ([e.sub.65], [[lambda].sub.2]) (2)

Donde:

[e.sub.ij] = Enlace del nodo i - esimo al nodo j - esimo R = [e.sub.21] - [e.sub.13] - [e.sub.36] - [e.sub.65] = Ruta

La ecuacion 1, muestra el lightpath para el caso CCW y la ecuacion 2 para el caso WR, notese en el ultimo caso que para cada enlace existe una longitud de onda asociada distinta. Las redes WDM-CCW al utilizar la misma longitud de onda en cada enlace tienen una baja latencia en el establecimiento de la conexion, sin embargo el universo de soluciones se agota con rapidez cuando el trafico aumenta generando una alta congestion en la red. Por otro lado, las redes WDM-WR tienen una utilizacion eficiente de los recursos de la red pero tienen una alta latencia en el establecimiento de la conexion. Se han utilizado diferentes estrategias en el campo heuristico y metaheruistico, y se pueden clasificar en dos, aquellas que dividen el problema en dos partes (ESP - Estrategia de Subdivision del Problema) y aquellos que lo solucionan de manera integral (ESI - Estrategia de Solucion Intergral). La ESP tiene la ventaja de disminuir el tiempo de obtencion de la solucion al simplificar el problema utilizando dos procesos algoritmicos, sin embargo al ser utilizado en redes WDM-CCW la asignacion de longitud de onda se convierte en un obstaculo, por lo general mejoran el uso de la red pero aumentan la probabilidad de bloqueo. La ESI utiliza un solo proceso algoritmico para obtener el lightpath balanceando equilibradamente la utilizacion de la red y la probabilidad de bloqueo, sin embargo el tiempo de obtencion de la solucion es significativamente mayor que la ESP. Por otro lado se utilizan criterios de maximizacion o minimizacion de la funcion aptitud (fitness) por ejemplo, el retardo en el enlace, el ruido ASE de los amplificadores en la ruta, cantidad de canales utilizados en el enlace, congestion en el enlace, congestion en el enlace mas utilizado, etc. basados en una metrica denominada costo, que se caracteriza por un numero entero que representa los criterios antes mencionados.

HEURISTICAS Y META HEURISTICAS

Se define una topologia de N conmutadores opticos (OXC) etiquetados de 0 a N-1, con [n.sub.W] longitudes de [[lambda].sub.0] onda por cada enlace de fibra optica tal como ([expresion matematica irreproducible]) donde la solicitud de servicio entrante que llega a los nodos es (Ver ecuacion 3):

[R.sup.j.sub.i] = (D, [n.sub.C], [t.sub.C]) (3)

Donde:

[R.sup.j.sub.i] es la i-esima solicitud del v-esimo nodo; D es el nodo destino de la j-esima solicitud del v-esimo nodo; [n.sub.C] es el numero de conexiones solicitadas; y [t.sub.C] es el tiempo de conexion solicitado--Holding Time.

En la Figura 2, se muestra la red anteriormente descrita, donde el nodo 2 es solicitado con R por una ruta hacia el nodo 5 con un canal por un tiempo de 500 ms. Dicha red utiliza 3 longitudes de onda (N = 8, [n.sub.W] = 3) etiquetadas cada una con numeros del 0 al 7. Por lo tanto se debera buscar una ruta y una longitud de onda que permita satisfacer la demanda en condiciones de CCW, es decir la misma longitud de onda en cada enlace de la ruta.

Las heuristicas encuentran las soluciones a partir de un grupo aleatorio de elementos generado al inicio del algoritmo y despues se realizan procedimientos propios de cada algoritmia, este grupo es denominado poblacion, y esta definida por:

[expresion matematica irreproducible] (4)

Aqui, [P.sub.0] es la poblacion inicial; y [p.sub.ijk]: es el elemento poblacional j-esimo de la i-esima solucion para k-esima longitud de onda.

Por ejemplo, en la matriz poblacional los elementos [p.sub.i02] y [p.sub.i72] corresponden al nodo origen y nodo destino del problema RWA donde i [elemento de] [0,7]. En la ecuacion 5, se muestra la poblacion inicial para la longitud de onda [[lambda].sub.2] (k = 2), donde el nodo 2 recibe la solicitud de servicio hacia el nodo 5.

[expresion matematica irreproducible] (5)

Para el caso de la poblacion de la ecuacion 5, se espera encontrar una ruta del nodo 2 al nodo 5 a traves de la longitud de onda 2. Observando las rutas (filas) estas inicialmente no tienen un costo finito, por ejemplo la fila 0 o primera fila 2 - 0 - 3 - 4 - 2 - 5 - 7 - 5 tiene el costo infinito debido a que tiene enlaces que no existen como 0 - 3 y 7 - 5. Sin embargo realizando procesos con la matriz poblacional segun la heuristica utilizada, estas filas pueden mejorar en aptitud y convirtiendolas en finitas, lo que determina su candidatura como posible solucion, cabe indicar que las nuevas filas solo seran buenas rutas y no necesariamente la optima.

Algoritmos Geneticos (AG)

El AG es uno de los procesos mas estudiados en la literatura su aplicacion data de 1970 a traves de John Henry Holland, se ha aplicado en diferentes areas donde se requiere optimizacion, sin embargo desde la insercion de la fibra optica en las redes de transporte, su utilizacion se ha intensificado a nivel investigativo. El algoritmo se basa en la combinacion genetica para obtener poblaciones con mejores caracteristicas en cada evolucion de la matriz poblacional, de esta forma se obtienen genotipos cada vez mas aptos para la solucion, y por lo general se realiza a traves de una funcion denominada funcion de aptitud o fitness function. Ademas, se incorporan procesos de reproduccion, mortandad y mutacion similares a los producidos en la genetica

De la ecuacion 5 se puede extraer los cromosomas (filas) consecutivas con todos sus elementos (genes), tal como la ecuacion 6:

[expresion matematica irreproducible] (6)

Ambos cromosomas se reproduciran al combinarse tal como se muestra en la ecuacion 7:

[expresion matematica irreproducible] (7)

Esta nuevas filas tienen nuevas aptitudes, es decir una funcion de aptitud diferente a las filas que la generaron, produciendose una nueva poblacion, luego se procede a un ordenamiento descendente por la FF (Fitness Function) y las filas de mayor valor quedaran debajo de la poblacion, y estas podran ser eliminadas (mortandad) y repuestas con nuevas filas aleatorias (natalidad), tambien se puede cambiar un elemento (gen) en particular de manera aleatoria (mutacion), para lograr minimizar la FF hasta que la aptitud sea la deseada. Trabajos como los mostrados en (Rodriguez et al., Cheng et al., 2016; Zahedi et al., 2016; Lefever et al., 2016) entregan resultados que garantizan un excelente funcionamiento bajo trafico dinamico y con alta carga de stress.

Simulated Annealing (SA)

El algoritmo SA, es una heuristica que desarrolla un proceso similar a la tecnica de calentamiento y enfriamiento lento con la finalidad de cambiar las caracteristicas fisicas de los materiales. Existe discusion respecto de quien introdujo el metodo, los autores Scott Kirkpatrick, C. Daniel Gelatt y Mario P. Vecchi en el 1983 mencionan que existe una profunda conexion entre la mecanica estadistica y la optimizacion combinatoria multivariable y Vlado Cerny en 1985, menciona que por analogia con la termodinamica estadistica y utilizando la probabilidad dada por la distribucion de Boltzmann-Gibbs se puede llegar a estar muy cerca de la solucion optima de un problema hasta se puede obtener el optimo verdadero (Kirkpatrick et al., 1983; Cerny et al., 1985). Para este caso la poblacion se trata como un conjunto de moleculas que rotan similarmente a los gases dentro de un volumen de control, donde las paredes son los elementos [p.sub.i02] y [p.sub.i(n-1)2], de tal forma que el resto de elementos rotan por capas a velocidades diferentes siendo mas lenta afuera y rapida dentro y esta velocidad va disminuyendo segun una funcion de enfriamiento tal como se ve en la ecuacion 5:

[v.sub.i] = [v.sub.io] (1 - [varia en proporcion con]T) (8)

En esta ecuacion, [v.sub.i] es la velocidad de la capa i-esima a temperatura T; [v.sub.i0] es la velocidad inicial de la capa i-esima; k [varia en proporcion con] es el coeficiente de enfriamiento; y T es la temperatura.

Existen muchos trabajos de aplicacion del algoritmo en diferentes ambitos, sin embargo en las telecomunicaciones y en especial en las redes opticas los trabajos no han mejorado significativamente los resultados (Rodriguez et al., 2014; Rodriguez et al., 2015).

Tabu Search (TS)

El algoritmo TS fue presentado por primera vez por el Dr. Fred Glover en 1989, pero fue en 1990 cuando este algoritmo fue reconocido como una potente heuristica. Se basa en el intercambio de acciones que mejoran o empeoran la FF, de tal forma que mediante un registro (memoria) de dichas acciones, se premian aquellas que la mejoran y se castigan las que empeoran la FF, de esta forma se busca converger rapidamente hacia el optimo local (Ver figura 4). La principal ventaja del algoritmo es que cuando se localiza una posible solucion esta converge rapidamente. Se basa en la idea que es mayor la informacion que brindan los errores que los aciertos, TS ha establecido records en la busqueda de mejores soluciones a los problemas de planificacion de la produccion y la programacion, asignacion de recursos, diseno de redes, enrutamiento, analisis financiero, las telecomunicaciones, la planificacion de la cartera, gestion de la cadena de suministro, el modelado basado en agentes, el diseno de procesos de negocio, la prevision, el aprendizaje automatico, mineria de datos, etc. Muchos trabajos que utilizan este algoritmo hacen visible la robustez del metodo frente a alta carga de trafico en escenarios dinamicos para redes opticas WDM (Glover 1983; Glover 1989; Ye et al., 2014, Rodriguez et al., 2014).

Snake One (SNK1)

El algoritmo Snake One es un algoritmo que utiliza la matriz de costo denominada matriz Snake (S), donde a traves de desplazamientos horizontales y verticales, dicho algoritmo encuentra la ruta y asignacion de longitud de onda con mucha eficiencia que el resto de heuristicas. Esto incluye saltos para evitar los ciclos cerrados, donde la maxima cantidad de saltos es inferior al numero maximo en los nodos. Dicho algoritmo encuentra la ruta y asignacion de longitud de onda con mucha eficiencia que el resto de heuristicas. La mayor desventaja del algoritmo es que por lo general utiliza nodos del perimetro de la red saturando con rapidez estos recursos, esta caracteristica la coloca en desventaja ante escenarios de stress. En la figura 5, se muestra una red optica de ejemplo con 8 nodos donde se indica que los enlaces inexistentes tienen un costo asociado muy grande (1000), de tal forma que las rutas que utilicen estos enlaces tendran un costo total asociado grande y por lo tanto apareceran al final de la matriz al ser ordenados descendentemente (Ver figura 5). De esta forma se garantiza una ruta de bajo costo pero no necesariamente la optima.

Los resultados mostrados en (Rodriguez et al., 2015) indican que mejora los indicadores de probabilidad de bloqueo pero a una elevada utilizacion de la red. Su comportamiento ante el stress (alto trafico) es bastante mejor que el resto de heuristicas.

Snake Two (SNK2)

El algoritmo Snake Two, es una estrategia que utiliza el algoritmo Snake One para lograr el uso de los enlaces en su punto saturacion, de esta forma dirigir el trafico hacia ciertas zonas, dejando con cierta libertad otras zonas, de esta forma poder atender la demanda entrante. Esto se logra aplicando el algoritmo Snake One desde el origen de la solicitud hasta el enlace seleccionado y desde el enlace hacia el destino de la solicitud. El enlace seleccionado como mas congestionado es obtenido de una matriz ordenada que monitoriza la carga de los enlaces y que periodicamente es ordenada ascendentemente, con la finalidad de tener siempre disponibles los mas congestionados (Ver figura 6).

En la Figura 7, se observa la llegada de la solicitud R al OXC 3 y estando la MEC con el enlace 4-5 disponible se procede a calcular con Snake One la ruta del origen 3 al nodo 4 del enlace congestionado, obteniendose 3-0-4; luego se procede a calcular la ruta del nodo 5 del enlace congestionado al destino 7, obteniendose 5-1-2-7; de esta forma se compone la ruta 3-0-4-5-1-2-7.

Los resultados mostrados indican que mejoran los indicadores promedio de probabilidad de bloqueo y utilizacion de la red (Rodriguez et al., 2015; Rodriguez et al., 2018).

Otras Heuristicas

El algoritmo PSO (Particle Swarm Optimization) fue introducido en 1995 por Reynolds y Heppner para modelar el comportamiento social, por ejemplo el movimiento de los peces las aves, logrando realizar observaciones donde el movimiento de uno o varios predomina sobre el resto (Kennedy et al., 1998; Markovic, 2016). El algoritmo busca la posicion solucion a traves de la variacion de las posiciones de las particulas corregidas en direccion por su velocidad, en cada iteracion las particulas corrigen su posicion con su mejor posicion encontrada y con la mejor posicion evaluada en el enjambre, de esta forma el movimiento total es la composicion de todos las particulas pero con la direccion del lider similarmente como se comportan los enjambres. Se han realizado multiples aplicaciones de este algoritmo en areas como: Antenas, Biomedica, Redes de comunicaciones, Clustering y clasificacion, Optimizacion Combinacional, Control, Diseno, Fallas, Finanzas, robotica y muchas mas. Los resultados mostrados en estos articulos muestran la enorme utilizacion de este algoritmo cuya ventaja es la rapida convergencia en la solucion pero a costos de un alto uso de los recursos y su desventaja es la improbabilidad de encontrar la solucion optima siempre (Poli, 2007; Poli 2008).

El algoritmo Firefly o Luciernaga es introducido por Xin-She Yang en el 2008, basado en los procesos de atraccion de las luciernagas debido a su brillantez. Las condiciones del algoritmo son tres, la primera indica que todas las luciernagas se atraen es decir no hay diferencia de genero, la intensidad de la atraccion es proporcional a la brillantez, si existe ausencia de brillantez las luciernagas se mueven aleatoriamente. Este algoritmo es relativamente joven y en ciertas condiciones es similar al algoritmo PSO, su aplicacion es numerosa y en los mismos ambitos que los mencionados para PSO (Yang, 2010).

El algoritmo murcielago es introducido por Xin-She Yang (2010) y esta basado en la ecolocacion de micro murcielagos (microbats). El comportamiento con indices de pulso variable de emision y amplitud. En terminos practicos, los murcielagos, sales en busca de su presa y segun su ecolocacion emite ondas de diferentes frecuencia y amplitud, siendo estas mas intensas a medida que se acercan a su objetivo, de esta forma el grupo se comunica logrando obtener una o mas presas (soluciones) en un solo proceso. Siendo aun muy joven se han realizado diferentes implementaciones con la finalidad de mejorar su desempeno (Vanegas et al., 2013; Yang, 2010; Yang, 2011; Yang et al., 2012).

Algoritmo Snake Three (SNK3)

El algoritmo Snake Three, es una nueva composicion del algoritmo Snake One con un cambio en la estrategia; en este caso se utiliza el nodo mas congestionado con disponibilidad para atender la solicitud, de esta forma se pretende dirigir el trafico similarmente a Snake Two, pero esta vez hacia zonas de alto trafico para lograr la maxima utilizacion de los recursos, esto es logrado a traves del indicador de congestion nodal (ICN). La ecuacion 9, muestra el indicador de congestion nodal del nodo i que es la suma de los costos de los enlaces adyacentes.

[ICN.sub.i] = [n.suma de (j=0)] [e.sub.ij] [atane a todos] [e.sub.ij] [existente en] (9)

En la Figura 8, se muestra el principio de funcionamiento de SNK3 a traves del nodo mas congestionado que es seleccionado de una matriz ordenada, que monitoriza la carga de los nodos y que periodicamente es ordenada ascendentemente, con la finalidad de tener siempre disponibles los nodos con mayor carga (Ver figura 8), para la seleccion del nodo se utiliza aquel de mayo costo que satisfaga la solicitud de conexion.

En la Figura 9, se observa la ruta obtenida utilizando el algoritmo Snake One para calcular la ruta 3-0-1 hacia el nodo congestionado seleccionado y del nodo congestionado al destino de la solicitud calculando la ruta 1-2-7, de esta forma se compone la ruta 3-0-1-2-7. A diferencia de Snake Two, este algoritmo desarrolla rutas mas cortas pero con el mismo efecto que Snake Two, lo que implica una menor utilizacion de la red.

En la Figura 10, se puede observar el diagrama de flujo de la metaheuristica Snake Three donde se visibiliza el uso de Snake One (SO) y la Matriz de Nodos congestionados (MNC) por cada lambda disponible. Por otro lado, las matrices C, T, y [lambda] son actualizadas con la finalidad de mantener actualizada la MNC. Solo cuando se obtenga la ruta SO y coincida con la longitud de onda disponible se procedera a establecer el Lightpath (LP) en caso contrario se bloqueara la solicitud.

Escenario de Simulacion y demanda de trafico

La red optica mas utilizada para desarrollar simulaciones de redes WDM es la NSFNET o National Science Foundation Network (Ver figura 11), esta red se simulo con 14 nodos y 21 enlaces similarmente a los trabajos mostrados en (Rodriguez et al., 2014; Rodriguez et al., 2015) con la finalidad de realizar la comparacion de los algoritmos heuristicos, a traves de dos indicadores, Probabilidad de Bloqueo y Utilizacion de la Red, variando la carga de trafico de 0 a 180 Erlangs. En la ecuacion 10, se define la solicitud con tres parametros que determinaran el trafico. Donde [S.sup.i.sub.m] determina la m-esima solicitud de servicio del i-esimo nodo, [n.sub.d] determina el nodo destino solicitado, [n.sub.c] determina el numero de conexiones solicitadas y [t.sub.c] determina el tiempo de conexion solicitada.

[S.sup.i.sub.m] = ([n.sub.d], [n.sub.c], [t.sub.c]) (10)

Siendo N el numero de nodos de la red (N=14) el numero de total de solicitudes de simulacion es de [10.sup.8] solicitudes. Los parametros se eligen aleatoriamente segun una distribucion uniforme. El tiempo entre llegadas de solicitudes [t.sub.s] es de distribucion exponencial de tal forma que el numero de solicitudes que llegan al nodo es de distribucion Possion. Los valores medios de estas variables aleatorias son similares a los valores utilizados en los trabajos (Rodriguez et al., 2014; Rodriguez et al., 2015) con fines de comparacion, tales como numero de longitudes de onda [n.sub.w] = 8, el trafico es uniformenle distribuido, el tiempo medio de solicitud de conexion es de 100 ms.

Para establecer el trafico dinamico se utiliza el indice de trafico [I.sub.T] segun la ecuacion 11, si es menor que 1 la demanda es estatica de lo contrario es dinamica, el presente trabajo desarrolla la simulacion para el escenario dinamico y desarrolla una demanda que estresa la red de 0 a 180 Erlangs.

[I.sub.T] = [t.sub.S]/[t.sub.C] (11)

El indicador Probabilidad de Bloqueo ([P.sub.b]) mide la probabilidad de una solicitud entrante de no ser atendida. Al existir la imposibilidad de espera de una solicitud esta es bloqueada al no ser atendida. Por otro lado el indicador Utilizacion de la Red ([U.sub.r]) mide la capacidad utilizada de la red a medida que se incrementa la carga en Erlangs. Esta carga es calculada multiplicando la tasa promedio de solicitudes entrantes con la tasa media de tiempo de conexion solicitado (100 ms).

RESULTADOS

Se utilizaron los indicadores Probabilidad de Bloqueo ([P.sub.b]) Utilizacion de la Red ([U.sub.r]) definidos anteriormente como elementos comparadores del desempeno algoritmico. En la Figura 12, se observa la probabilidad de bloqueo y el comportamiento de los algoritmos para diferentes cargas de simulacion variando de 0 a 180 Erlangs. Se pueden distinguir tres intervalos de carga (Load Range of Blocking Probability--LRBP) que permiten explicar de mejor modo el comportamiento. El primer intervalo (LRBP1: 0-80 Erlangs) el segundo intervalo (LRBP2: 80-120 Erlangs) y el tercer intervalo (LRBP3: 120-180 Erlangs). LRBP1 representa un trafico de baja carga, LRBP2 representa un trafico transitorio y LRBP3 representa un alto trafico o stress. Podemos observar que en LRBP1, SNK2 y SNK3 no ofrecen mayores diferencias comportandose similarmente superando al resto de heuristicas inclusive al algoritmo de referencia, mientras que en LRBP2 los comportamientos empiezan equilibrarse siendo TS, SNK1, SNK2 y SNK3 muy similares. Sin embargo, cuando el trafico alcanza rangos de LRBP3 las heuristicas no responden mejor que el algoritmo de referencia, siendo este ultimo el que mejor se desempena. Es interesante resaltar el comportamiento de AS para altos niveles de trafico siendo bastante parecido al algoritmo de referencia RF.

En la Figura 13, se observa la utilizacion de la red porcentualmente y se pueden distinguir dos intervalos de carga (Load Range of Network Utilization - LRNU) que permiten explicar de mejor modo el comportamiento. El primer intervalo (LRNU1: 0-40 Erlangs) el segundo intervalo (LRNU2: 40-180 Erlangs). Podemos observar que en LRNU1 los algoritmos heuristicos estudiados consumen mas recursos que el algoritmo de referencia y en LRNU2 el uso de los recursos es creciente y constante, como se esperaba SNK3 encuentra rutas mas cortas y consume menor recursos que la red que sus homologos SNK1 y SNK2. Sin embargo no logra ser mejor que GA y SA, siendo el algoritmo de referencia el que menos recursos ocupa, cabe resaltar que el algoritmo de referencia no es heuristico y solo se utiliza con fines comparativos.

CONCLUSIONES

El algoritmo de estudio se comparo con heuristicas que solo encuentran soluciones funcionales es decir, logran el objetivo de transportar sin ser necesariamente el optimo y se utilizo como referencia un algoritmo deterministico (RF). Desde esta perspectiva, los trabajos mostrados y la metaheuristica SNK3 tienen ventaja competitiva cuando observamos la probabilidad de bloqueo, instalandose como mejores respecto del algoritmo de referencia. Sin embargo, cuando observamos el indicador utilizacion de la red, se observa lo contrario, es decir el algoritmo de referencia (deterministico) es mas eficiente.

Por otro lado, una de las ventajas mas importantes de las heuristicas y metaheuristicas es la obtencion de varias soluciones en el mismo proceso algoritmico que entrega robustez a la solucion, mientras que los algoritmos convencionales optimizadores como el de referencia, solo encuentran una solucion en el proceso, esto determina que frente a un sistema que requiera restauracion los algoritmos metaheuristicas tendran mayor oferta de solucion. Esto permite concluir que para bajo rangos de trafico (LRBP1 y LRNU1) las heuristicas responden con una baja probabilidad de bloqueo, pero a un alto consumo de los recursos de la red y este comportamiento empeora cuando el trafico se eleva llegando a consumir mayores recursos que el algoritmo de referencia. Se debera establecer nuevas simulaciones en un escenario de conversion de longitud de onda que permita disminuir las solicitudes bloqueadas sin un alto crecimiento de los recursos de la red.

http://dx.doi.org/10.4067/S0718-07642017000600015

AGRADECIMIENTOS

Especial agradecimiento para el Programa DYCYT de la Universidad de Santiago de Chile- USACH (Project DICYT No. 061572RG), al Proyecto Basal USA1555 MECESUP-USACH y al Grupo de Investigacion en Nuevas Tecnologias (GINT-DTI-USACH) por su importante apoyo al desarrollo de la investigacion.

REFERENCIAS

Alarcon-Aquino, V.; Guerrero-Ojeda L.; Rodriguez-Asomoza J. y Rosas-Romero R., Analisis de Trafico Autosimilar en Redes de Comunicaciones Usando Onditas (Wavelets), https://dx.doi.org/10.4067/S071807642005000200010, Inf. Tecnol., 16(2), 61-66 (2005)

Cerny, V., Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, doi:10.1007/BF00940812, Journal of Optimization Theory and Applications, 45(1), 41-51 (1985)

Chen, Y.; Hao, J. y Glover, F., A hybrid metaheuristic approach for the capacitated arc routing problem, doi:10.1016/j.ejor.2016.02.015, European Journal of Operational Research, 253(1), 25-39 (2016)

Ferrucci, F. y Bock, S., Pro-active real-time routing in applications with multiple request patterns, doi:10.1016/j.eswa.2016.03.005, Expert Systems with Applications, 56(1), 320-334 (2016)

Galan-Jimenez, J. y Gazo-Cervero, A., Using bio-inspired algorithms for energy levels assessment in energy efficient wired communication networks, doi: 10.1016/j.jnca.2013.02.027, Journal of Network and Computer Applications, 37(1), 171-185(2014)

Glover, F., Tabu Search--Part I, ORSA Journal on Computing, 1(3), 190-206 (1989)

Glover, F., Tabu Search--Part II, ORSA Journal on Computing, 2(1), 4-32 (1990)

Gutierrez, F.; Martin, E.; Perry, P.; Ellis, A.; Anandarajah, P. y Barry, L., WDM Orthogonal Subcarrier Multiplexing, doi: 10.1109/jlt.2015.2508418, Journal of Lightwave Technology, 34(8), 1815-1823 (2016)

Kennedy, J. y Eberhart, R., Particle Swarm Optimization, doi:10.1109/icnn.1995.488968, Proceedings of IEEE International Conference on Neural Networks, 4(1), 1942-1948 (1995)

Kirkpatrick, S.; Gelatt, C. y Vecchi, M.P., Optimization by Simulated Annealing, Science, doi:10.1126/science.220.4598.671, PMID 17813860, 220(4598), 671-680 (1983)

Lima, F.; Pereira, D.; Conceicao, S. y Nunez, N., A mixed load capacitated rural school bus routing problem with heterogeneous fleet: Algorithms for the Brazilian context, doi: 10.1016/j.ejor.2016.02.016, European Journal of Operational Research, 253(2), 356-371 (2016)

Lefever, W.; Aghezzaf, E. y Hadj-Hamou, K., A convex optimization approach for solving the single-vehicle cyclic inventory routing problem, doi:10.1016/j.cor.2016.02.010, Computers & Operations Research, 72(1), 97-106 (2016)

Markovic, G., Wavelength Converters Placement in Optical Networks Using Bee Colony Optimization, doi: 10.4316/aece.2016.01001, Advances in Electrical and Computer Engineering, 16(1), 3-10 (2016)

Paraskevopoulos, D.; Bektas, T.; Crainic, T. y Potts, C., A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem, doi: 10.1016/j.ejor.2015.12.051, European Journal of Operational Research, 253(2), 265-279 (2016)

Piedrahita, E.; Hernandez, C.; Pedraza, L. y Salcedo, O., Evaluacion de Protocolos de Senalizacion en Multiprotocolo Generalizado de Conmutacion de Etiquetas (GMPLS) Capaces de Conmutar Paquetes y Longitudes de Ondas, Inf. Tecnol., 25(1), 55-66 (2014)

Poli, R., An analysis of publications on particle swarm optimization applications, In Department of Computer Science, University of Essex, U.K., Technical Report CSM-469 (2007)

Poli, R., Analysis of the publications on the applications of particle swarm optimization, doi:10.1155/2008/685175, Journal of Artificial Evolution and Applications, 1(1), 1-10 (2008)

Rodriguez, A.; Gutierrez, A.; Rivera, L. y Ramirez, L., Comparing Genetic Algorithms and Simulated Annealing for dynamic traffic routing, Advanced Computer and Communication Engineering Technology, 315(1), 3-14 (2014)

Rodriguez, A.; Ramirez, L.; Rivera, L. y Gutierrez, A., Routing wavelength assignement: A solution with tabu search in dynamic traffic, Ingeniare. Rev. Chil. Ing., 22(4), 495-503 (2014)

Rodriguez, A.; Ramirez L. y Travieso, J., New heuristic algorithm for dynamic traffic in WDM optical networks, Revista Ingenieria e Investigacion, 35(3), 100-106 (2015)

Rodriguez, A.; Travieso, J. y Savedra, F., DLE - WDM: Metaheuristica para el Enrutamiento y Asignacion de Longitud de Onda en Trafico Dinamico, Ingeniare, en prensa, 26(1), (2018)

Russo, N.; Noriega, S. y Duchowicz, R., Implementacion de Sistema Optico para Grabado de Redes de Bragg en Fibra Optica, Inf. Tecnol., 22(2), 121-130 (2011)

Sadiq, M.; Zhang, H.; O'Callaghan, J.; Roycroft, B. y otros seis autores, 40 Gb/s WDM Transmission Over 1.15-km HC-PBGF Using an InP-Based Mach-Zehnder Modulator, doi: 10.1109/jlt.2015.2508941, Journal of Lightwave Technology, 34(8), 1706-1711 (2016)

Vanegas, S.; Amaya, I. y Correa, R., Algoritmo del murcielago virtual en el desarrollo de la Integral de Duhamel para sistemas estructurales con un grado de libertad, Revista Ingenieria de Construccion, 28(3), 278-289 (2013)

Yang, X., Nature-inspired meta-heuristic algorithms, 2nd Ed., Luniver Press, Beckington (2010)

Yang, X., New Metaheuristic Bat-Inspired Algorithm, Nature Inspired cooperative Strategies for Optimization, 1(1), 65-74 (2010)

Yang, X., Bat Algorithm for Multiobjective Optimization, International Journal of Bio-Inspired Computation, 3(5), 267-274 (2011)

Yang, X. y Gandomi, A.H., Bat Algorithm: A Novel Approach for Global Engineering Optimization, Engineering Computations, 29(5), 464-483 (2012)

Ye, A.; Zhang, Z.; Zhou, X. y Miao, F., Tabu Assisted Local Search for the Minimum Load Coloring Problem, doi: 10.1166/jctn.2014.3664, J. of Computational and Theoretical Nanoscience, 11(12), 2476-2480 (2014)

Zahedi, Z.; Akbari, R.; Shokouhifar, M.; Safaei, F. y Jalali, A., Swarm intelligence based fuzzy routing protocol for clustered wireless sensor networks, doi:10.1016/j.eswa.2016.02.016, Expert Systems with Applications, 55(1), 313-328 (2016)

Zang, H. y Jue, J., Dynamic Lightpath Establishment in Wavelength-Routed WDM Networks, IEEE Communications Magazine, 39(1), 100-108 (2001)

Zheng, Z.; Zhang F.; Wang D. y otros cuatro autores, Fiber Nonlinearity Mitigation in 32-Gbaud 160AM Nyquist-WDM Systems, doi: 10.1109/jlt.2016.2535408, J. of Lightwave Technology, 34(9), 2182-2187 (2016)

Arturo B. Rodriguez (1), Leonardo J. Ramirez (2) y Felipe R. M. Basile (3)

(1) Universidad Santiago de Chile, Departamento de Tecnologia Industrial, Grupo de Investigacion en Nuevas Tecnologias (GINT), Santiago-Chile. (email: arturo.rodriguez@usach.cl)

(2) Universidad Militar de Nueva Granada, Grupo de Investigacion en Telemedicina (TIGUM), Bogota, Colombia. (email: leonardo.ramirez@unimilitar.edu.co)

(3) Instituto Federal de Educacion, Ciencia y Tecnologia de Sao Paulo, Campus Pirituba, Brasil. (email: felipe.basile@ifsp.edu.br)

Recibido May. 15, 2017; Aceptado Jul. 19, 2017; Version final Ago. 10, 2017, Publicado Dic. 2017

Leyenda: Fig. 1: Red optica de ejemplo

Leyenda: Fig. 2: Red optica mostrando la solicitud de entrada.

Leyenda: Fig. 3: Matriz poblacional en Simulated Annealing.

Leyenda: Fig. 4: Matriz poblacional en Tabu Search.

Leyenda: Fig. 5: Algoritmo Snake One.

Leyenda: Fig. 6: Matriz de enlaces congestionados (MEC).

Leyenda: Fig. 7: Algoritmo Snake Two.

Leyenda: Fig. 8: Matriz de Nodos Congestionados (MNC).

Leyenda: Fig. 9: Algoritmo Snake Three.

Leyenda: Fig. 10: Diagrama de flujo de Snake Three.

Leyenda: Fig. 11: Red NSFNET con 14 nodos y 21 enlaces.

Leyenda: Fig. 12: Comparacion de la Probabilidad de Bloqueo en la NSFNET.

Leyenda: Fig. 13: Comparacion de la utilizacion de red en la NSFNET.
COPYRIGHT 2017 Centro de Informacion Tecnologica
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Rodriguez, Arturo B.; Ramirez, Leonardo J.; Basile, Felipe R.M.
Publication:Informacion Tecnologica
Date:Dec 1, 2017
Words:6247
Previous Article:Antena de Parche Cortocircuitado con Polarizacion Circular y Sentido de Giro Reconfigurable para Aplicaciones en Satelites de Reducido Tamano.
Next Article:Diseno de un Clasificador Difuso para el Establecimiento de los Estados Funcionales de un Sistema de Produccion de Aire Medicinal.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters