El problema de enrutamiento y asignación de longitud de onda ( RWA ) es un problema de red óptica cuyo objetivo es maximizar el número de conexiones ópticas.
El objetivo general del problema RWA es maximizar el número de conexiones establecidas. A cada solicitud de conexión se le debe dar una ruta y una longitud de onda. La longitud de onda debe ser constante en todo el trayecto, a menos que se presuponga el uso de convertidores de longitud de onda. Dos solicitudes de conexión pueden compartir el mismo enlace óptico , siempre que se utilice una longitud de onda diferente.
El problema de RWA se puede definir formalmente en un programa lineal entero (ILP). La formulación ILP que se proporciona aquí está tomada de. [1]
Maximizar:
sujeto a
es el número de pares origen-destino, mientras que es el número de conexiones establecidas para cada par origen-destino. es el número de enlaces y es el número de longitudes de onda. es el conjunto de caminos para enrutar conexiones. es una matriz que muestra qué pares fuente-destino están activos, es una matriz que muestra qué enlaces están activos y es una matriz de asignación de ruta y longitud de onda.
Tenga en cuenta que la formulación anterior supone que las demandas de tráfico se conocen a priori . Este tipo de problema se conoce como Establecimiento estático de Lightpath (SLE). La formulación anterior tampoco considera la calidad de la señal.
Se ha demostrado que el problema SLE RWA es NP-completo . [2] La prueba implica una reducción al problema de colorabilidad del gráfico. En otras palabras, resolver el problema SLE RWA es tan complejo como encontrar el número cromático de una gráfica general. Dado que el RWA dinámico es más complejo que el RWA estático, debe darse el caso de que el RWA dinámico también sea NP-completo.
En [3] se proporciona otra prueba NP-completa. Esta prueba implica una reducción al problema del flujo de múltiples productos .
El problema del RWA se complica aún más por la necesidad de considerar la calidad de la señal. Muchas de las deficiencias ópticas son no lineales, por lo que no se puede utilizar un algoritmo estándar de ruta más corta para resolverlas de manera óptima, incluso si conocemos el estado exacto de la red. Por lo general, esta no es una suposición segura, por lo que las soluciones deben ser eficientes utilizando solo información de red limitada.
Dada la complejidad de RWA, existen dos metodologías generales para resolver el problema:
El enrutamiento de ruta fija es el método más simple para encontrar un camino de luz. Siempre se utiliza la misma ruta fija para un par de origen y destino determinado. Normalmente, esta ruta se calcula con anticipación utilizando un algoritmo de ruta más corta, como el algoritmo de Dijkstra . Si bien este enfoque es muy simple, el rendimiento generalmente no es suficiente. Si los recursos a lo largo de la ruta fija están en uso, las solicitudes de conexión futuras se bloquearán aunque puedan existir otras rutas.
El algoritmo SP-1 (ruta más corta, 1 sonda) es un ejemplo de una solución de enrutamiento de ruta fija. Este algoritmo calcula la ruta más corta utilizando la cantidad de enrutadores ópticos como función de costo. Se utiliza una única sonda para establecer la conexión utilizando el camino más corto. El tiempo de ejecución es el costo del algoritmo de Dijkstra: , donde es el número de aristas y es el número de enrutadores. El tiempo de ejecución es simplemente una constante si se utiliza una ruta predeterminada.
Esta definición de SP-1 utiliza el recuento de saltos como función de costo. El algoritmo SP-1 podría ampliarse para utilizar diferentes funciones de costos, como el número de EDFA.
El enrutamiento alternativo fijo es una extensión del enrutamiento de ruta fija. En lugar de tener una sola ruta fija para un par de origen y destino determinado, se almacenan varias rutas. Las sondas se pueden enviar en serie o en paralelo. Para cada solicitud de conexión, el nodo de origen intenta encontrar una conexión en cada una de las rutas. Si todas las rutas fallan, la conexión se bloquea. Si hay varias rutas disponibles, solo se utilizará una de ellas.
El algoritmo SP- (ruta más corta, sondas ) es un ejemplo de enrutamiento alternativo fijo. Este algoritmo calcula las rutas más cortas utilizando el número de enrutadores ópticos como función de costo. El tiempo de ejecución utilizando el algoritmo de Yen [4] es donde está el número de aristas, es el número de enrutadores y es el número de rutas. El tiempo de ejecución es un factor constante si las rutas se calculan previamente.
El principal problema tanto con el enrutamiento de ruta fija como con el enrutamiento alternativo fijo es que ninguno de los algoritmos tiene en cuenta el estado actual de la red. Si las rutas predeterminadas no están disponibles, la solicitud de conexión se bloqueará aunque puedan existir otras rutas. Tanto el enrutamiento de ruta fija como el enrutamiento alternativo fijo no tienen en cuenta la calidad. Por estas razones, la mayor parte de la investigación en RWA se lleva a cabo actualmente en algoritmos adaptativos. Cinco ejemplos de enrutamiento adaptativo son LORA, PABR, IA-BF, IA-FF y AQoS.
Los algoritmos adaptativos se dividen en dos categorías: tradicionales y físicamente conscientes. Los algoritmos adaptativos tradicionales no consideran la calidad de la señal; sin embargo, los algoritmos adaptativos con conciencia física sí lo hacen.
El algoritmo de enrutamiento lexicográfico (LORA) se propuso en [5] La idea principal detrás de LORA es enrutar las solicitudes de conexión lejos de áreas congestionadas de la red, aumentando la probabilidad de que las solicitudes de conexión sean aceptadas. Esto se logra estableciendo el costo de cada enlace, donde es un parámetro que se puede ajustar dinámicamente según la carga de tráfico y es el número de longitudes de onda en uso en el enlace . Luego se puede utilizar un algoritmo de ruta más corta estándar para encontrar la ruta. Esto requiere que cada conmutador óptico transmita periódicamente información de uso reciente. Tenga en cuenta que LORA no considera ningún impedimento físico.
Cuando es igual a uno, el algoritmo LORA es idéntico al algoritmo SP. Aumentar el valor de aumentará el sesgo hacia rutas menos utilizadas. El valor óptimo de se puede calcular utilizando el conocido algoritmo de escalada de colinas . Los valores óptimos de estaban entre 1,1 y 1,2 en la propuesta.
El algoritmo de reserva hacia atrás con conciencia física (PABR) es una extensión de LORA. PABR puede mejorar el rendimiento de dos maneras: considerando las discapacidades físicas y mejorando la selección de longitud de onda. Mientras PABR busca un camino óptico, se eliminan los caminos con una calidad de señal inaceptable debido a degradaciones lineales. En otras palabras, PABR es LORA con una restricción de calidad adicional.
Tenga en cuenta que PABR sólo puede considerar degradaciones lineales. Por otra parte, las degradaciones no lineales no serían posibles de estimar en un entorno distribuido debido a que requieren conocimientos sobre el tráfico global.
PABR también considera la calidad de la señal al seleccionar la longitud de onda. Lo logra eliminando de consideración todas las longitudes de onda con un nivel de calidad de señal inaceptable. El enfoque se llama Quality First Fit y se analiza en la siguiente sección.
Tanto LORA como PABR se pueden implementar con sondeo único o sondeo múltiple. El número máximo de sondas se indica como LORA- o PABR- . En el caso del sondeo único, al seleccionar la ruta sólo se selecciona una ruta. Con el sondeo múltiple, se intentan múltiples rutas en paralelo, lo que aumenta la probabilidad de éxito de la conexión.
IA-BF : el algoritmo Impairment Aware Best Fit (IA-BF) se propuso en [6] Este algoritmo es un enfoque distribuido que depende de una gran cantidad de comunicación para utilizar información global para elegir siempre la ruta y la longitud de onda más cortas disponibles. . Esto se logra mediante el uso de sondas múltiples en serie. Primero se intenta la ruta y la longitud de onda más cortas disponibles y, en caso de falla, se intenta la segunda ruta y longitud de onda más cortas disponibles. Este proceso continúa hasta que se haya encontrado una ruta y una longitud de onda exitosas o hasta que se hayan intentado todas las longitudes de onda.
El enfoque de sondeo múltiple permitirá que IA-BF supere tanto a PABR-1 como a LORA-1. Sin embargo, a medida que aumenta el número de sondas, el rendimiento de los algoritmos es similar.
IA-FF : Impairment Aware First Fit (IA-FF) es una extensión simple de IA-BF. En lugar de elegir las longitudes de onda en términos de coste mínimo, las longitudes de onda se seleccionan en orden según su índice. IA-BF tiende a superar a IA-FF en la mayoría de los escenarios.
AQoS : calidad de servicio adaptativa (AQoS) se propuso en [7] Este algoritmo es único en un par de formas. Primero, cada nodo mantiene dos contadores: y . El propósito de cada contador es determinar qué problema es un factor más importante en el bloqueo: la disponibilidad de ruta y longitud de onda o los requisitos de calidad. El algoritmo elige rutas de manera diferente según el problema más amplio.
Otra distinción es que AQoS utiliza el factor Q como costo del enlace. El costo del enlace se calcula mediante esta fórmula, donde es el número de caminos de luz en el enlace y son las mediciones del factor de calidad del camino de luz en los nodos de origen y destino del enlace, respectivamente. Las estimaciones repetidas de los factores de calidad son computacionalmente muy costosas.
Este algoritmo es un enfoque de sondeo único. El enfoque de sondeo múltiple, que el artículo denomina ALT-AQoS (AQoS alternativo) es una simple extensión de la misma idea básica.
Dos de los métodos más comunes para la asignación de longitudes de onda son First Fit y Random Fit. First Fit elige la longitud de onda disponible con el índice más bajo. Random Fit determina qué longitudes de onda están disponibles y luego elige aleatoriamente entre ellas. La complejidad de ambos algoritmos es , donde es el número de longitudes de onda. First Fit supera al ajuste aleatorio.
En [5] se propuso una extensión de First Fit y Random Fit para considerar la calidad de la señal. Quality First Fit y Quality Random Fit eliminan de consideración las longitudes de onda que tienen una calidad de señal inaceptable. Sin embargo, la complejidad de estos algoritmos es mayor, ya que se requieren hasta llamadas para estimar el factor Q.
Existen varios otros algoritmos de asignación de longitudes de onda: menos utilizado, más utilizado, producto mínimo, menos cargado, suma máxima [8] y pérdida de capacidad relativa. [9] Más utilizado supera significativamente el uso menos utilizado y supera ligeramente a First Fit. Producto mínimo, menos cargado, suma máxima y pérdida de capacidad relativa intentan elegir una longitud de onda que minimice la probabilidad de que se bloqueen solicitudes futuras.
Una desventaja significativa de estos algoritmos es que requieren una importante sobrecarga de comunicación, lo que hace que su implementación no sea práctica a menos que tenga una estructura de red centralizada.
Un enfoque alternativo para seleccionar una ruta y una longitud de onda por separado es considerarlas conjuntamente. Estos enfoques tienden a ser más teóricos y no tan prácticos. Como se trata de un problema NP completo, probablemente no sea posible una solución exacta. Las técnicas de aproximación tampoco suelen ser muy útiles, ya que requerirán un control centralizado y, normalmente, demandas de tráfico predefinidas. Dos enfoques conjuntos son la formulación ILP y el salto de isla en isla .
La formulación de ILP enumerada anteriormente se puede resolver utilizando un solucionador de ILP tradicional. Por lo general, esto se hace relajando temporalmente las restricciones de números enteros, resolviendo el problema de manera óptima y convirtiendo la solución real en una solución entera. Se pueden agregar restricciones adicionales y repetir el proceso indefinidamente utilizando un enfoque de ramificación y enlace .
En [10] los autores informan sobre el algoritmo que se puede utilizar para resolver de manera eficiente y óptima un problema de RWA restringido. Los autores estudian un problema de enrutamiento restringido y asignación de espectro (RSA), que puede reducirse a un problema de RWA restringido solicitando un segmento. La constricción limita la longitud del camino.
En [11] los autores informan sobre el algoritmo generalizado de Dijkstra, que puede usarse para resolver de manera eficiente y óptima los problemas de RWA, RSA y de enrutamiento, modulación y asignación de espectro (RMSA), sin el límite en la longitud de la ruta.
![{\displaystyle D_{i}={\frac {\sum _ {j=1}^{N_{i}}10\log[Q_{i,j}^{(s)}/Q_{i,j} ^{(d)}]}{N_{i}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dea85789ddde782d1ee68ea48769a686eb727406)
