El problema de enrutamiento y asignación de longitud de onda ( RWA ) es un problema de red óptica cuyo objetivo es maximizar la cantidad de conexiones ópticas.
El objetivo general del problema RWA es maximizar la cantidad de conexiones establecidas. A cada solicitud de conexión se le debe asignar una ruta y una longitud de onda. La longitud de onda debe ser consistente para toda la ruta, a menos que se suponga 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 RWA se puede definir formalmente en un programa lineal entero (ILP). La formulación de ILP que se presenta aquí se tomó 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 rutas para enrutar conexiones. es una matriz que muestra qué pares origen-destino están activos, es una matriz que muestra qué enlaces están activos, y es una matriz de asignación de rutas y longitudes 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 de trayectoria de luz estática (SLE). La formulación anterior tampoco tiene en cuenta la calidad de la señal.
Se ha demostrado que el problema de RWA de SLE es NP-completo en [2] . La prueba implica una reducción al problema de colorabilidad de grafos. En otras palabras, resolver el problema de RWA de SLE es tan complejo como encontrar el número cromático de un grafo general. Dado que el RWA dinámico es más complejo que el RWA estático, debe ser el caso de que el RWA dinámico también sea NP-completo.
En [3] se da otra prueba NP-completa. Esta prueba implica una reducción al problema del flujo de múltiples productos .
El problema de 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. Esta no suele ser una suposición segura, por lo que las soluciones deben ser eficientes utilizando solo información limitada de la red.
Dada la complejidad de RWA, existen dos metodologías generales para resolver el problema:
El enrutamiento por ruta fija es el método más simple para encontrar una ruta 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 método es muy simple, el rendimiento generalmente no es suficiente. Si se utilizan recursos a lo largo de la ruta fija, las futuras solicitudes de conexión se bloquearán aunque puedan existir otras rutas.
El algoritmo SP-1 (Shortest Path, 1 Probe) 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 sola sonda para establecer la conexión utilizando la ruta más corta. El tiempo de ejecución es el costo del algoritmo de Dijkstra: , donde es la cantidad de aristas y es la cantidad 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 número de saltos como función de costo. El algoritmo SP-1 se podría ampliar para utilizar distintas funciones de costo, como la cantidad de EDFA.
El enrutamiento alternativo fijo es una extensión del enrutamiento de ruta fija. En lugar de tener solo una ruta fija para un par de origen y destino determinado, se almacenan varias rutas. Las sondas se pueden enviar de forma serial o paralela. 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 (Shortest Path, Probes, ) es un ejemplo de enrutamiento alternativo fijo. Este algoritmo calcula los caminos más cortos utilizando la cantidad de enrutadores ópticos como función de costo. El tiempo de ejecución utilizando el algoritmo de Yen [4] es donde es la cantidad de aristas, es la cantidad de enrutadores y es la cantidad de caminos. El tiempo de ejecución es un factor constante si los caminos se calculan previamente.
El principal problema con el enrutamiento de ruta fija y 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. El enrutamiento de ruta fija y el enrutamiento alternativo fijo no tienen en cuenta la calidad. Por estos motivos, la mayor parte de la investigación en RWA se está llevando 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 conscientes de la física. Los algoritmos adaptativos tradicionales no tienen en cuenta la calidad de la señal, mientras que los algoritmos adaptativos conscientes de la 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 las áreas congestionadas de la red, lo que aumenta la probabilidad de que se acepten las solicitudes de conexión. Esto se logra estableciendo el costo de cada enlace en donde es un parámetro que se puede ajustar dinámicamente de acuerdo con la carga de tráfico y es la cantidad de longitudes de onda en uso en el enlace . Luego se puede usar un algoritmo de ruta más corta estándar para encontrar la ruta. Esto requiere que cada conmutador óptico transmita información de uso reciente periódicamente. Tenga en cuenta que LORA no considera ninguna discapacidad física.
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 reconocimiento físico (PABR) es una extensión de LORA. PABR puede mejorar el rendimiento de dos maneras: considerando las deficiencias físicas y mejorando la selección de longitudes de onda. A medida que PABR busca una ruta óptica, se eliminan las rutas con una calidad de señal inaceptable debido a deficiencias lineales. En otras palabras, PABR es LORA con una restricción de calidad adicional.
Tenga en cuenta que PABR solo puede considerar deficiencias lineales. Por otro lado, no sería posible estimar deficiencias no lineales en un entorno distribuido debido a que requieren conocimiento del tráfico global.
PABR también tiene en cuenta la calidad de la señal al seleccionar la longitud de onda. Para ello, elimina de la consideración todas las longitudes de onda con un nivel de calidad de señal inaceptable. Este enfoque se denomina "ajuste de calidad primero" y se analiza en la siguiente sección.
Tanto LORA como PABR se pueden implementar con sondeo único o con sondeo múltiple. La cantidad máxima de sondeos se indica como LORA- o PABR- . Con el sondeo único, solo se selecciona una ruta mediante la selección de ruta. Con el sondeo múltiple, se intentan varias rutas en paralelo, lo que aumenta la probabilidad de éxito de la conexión.
IA-BF : el algoritmo de mejor ajuste consciente de la discapacidad (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 múltiples sondeos 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 se hayan intentado todas las longitudes de onda.
El enfoque de múltiples sondas 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 del costo 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 : Adaptive Quality of Service (AQoS) se propuso en [7] . Este algoritmo es único en un par de aspectos. 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: disponibilidad de ruta y longitud de onda o requisitos de calidad. El algoritmo elige rutas de manera diferente según el problema más importante.
Otra distinción es que AQoS utiliza el factor Q como el 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 del factor de calidad son computacionalmente muy costosas.
Este algoritmo es un método de sondeo único. El método de sondeo múltiple, que el artículo denomina ALT-AQoS (AQoS alternativo), es una extensión simple 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 a Random Fit.
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 la 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 otros algoritmos de asignación de longitud de onda: Least Used, Most Used, Min Product, Least Loaded, Max Sum, [8] y Relative Capacity Loss. [9] Most Used supera significativamente a Least Used y supera ligeramente a First Fit. Min Product, Least Loaded, Max Sum y Relative Capacity Loss intentan elegir una longitud de onda que minimice la probabilidad de que se bloqueen futuras solicitudes.
Una desventaja importante de estos algoritmos es que requieren una sobrecarga de comunicación significativa, lo que hace que su implementación sea poco práctica a menos que se cuente con una estructura de red centralizada.
Un enfoque alternativo para seleccionar una ruta y una longitud de onda por separado es considerarlas en conjunto. Estos enfoques tienden a ser más teóricos y no tan prácticos. Como se trata de un problema NP-completo, es probable que no sea posible encontrar una solución exacta. Las técnicas de aproximación tampoco suelen ser muy útiles, ya que requerirán un control centralizado y, por lo general, demandas de tráfico predefinidas. Dos enfoques conjuntos son la formulación ILP y el salto de isla en isla .
La formulación ILP mencionada anteriormente se puede resolver utilizando un solucionador ILP tradicional. Esto se hace generalmente relajando temporalmente las restricciones enteras, 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 acotación .
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 asignación de espectro y enrutamiento (RSA) restringido, que se puede reducir a un problema de RWA restringido solicitando una porción. La restricción limita la longitud de la ruta.
En [11] los autores informan sobre el algoritmo Dijkstra generalizado, que se puede utilizar 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)
