Enrutamiento y asignación de longitud de onda

El enrutamiento de ruta fija es el método más sencillo para encontrar una ruta óptica. Siempre se utiliza la misma ruta fija para un par de origen y destino dados. Normalmente, esta ruta se calcula con antelación mediante un algoritmo de ruta más corta, como el algoritmo de Dijkstra . Si bien este método es muy simple, su rendimiento suele ser insuficiente. Si los recursos a lo largo de la ruta fija están en uso, las futuras solicitudes de conexión se bloquearán, incluso si existen otras rutas.

El algoritmo SP-1 (Shortest Path, 1 Probe) es un ejemplo de solución de enrutamiento de ruta fija. Este algoritmo calcula la ruta más corta utilizando el número de enrutadores ópticos como función de coste. Se utiliza una sola sonda para establecer la conexión mediante la ruta más corta. El tiempo de ejecución es el coste del algoritmo de Dijkstra.${\displaystyle O(m+n\log n)}$, dónde${\displaystyle m}$es el número de aristas y${\displaystyle n}$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 número de saltos como función de coste. El algoritmo SP-1 podría ampliarse para utilizar diferentes funciones de coste, como el número de EDFA.

El enrutamiento alternativo fijo es una extensión del enrutamiento de ruta fija. En lugar de tener una única ruta fija para un par de origen y destino, 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 SP-${\displaystyle p}$(Camino más corto,${\displaystyle p}$Sondas,${\displaystyle p>1}$El algoritmo ) es un ejemplo de enrutamiento alternativo fijo. Este algoritmo calcula el${\displaystyle p}$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${\displaystyle O(pn(m+n\log n))}$dónde${\displaystyle m}$es el número de aristas,${\displaystyle n}$es el número de enrutadores y${\displaystyle p}$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 del enrutamiento de ruta fija como del enrutamiento alternativo fijo es que ninguno de los dos 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 existan otras rutas. Ni el enrutamiento de ruta fija ni el enrutamiento alternativo fijo consideran la calidad. Por estas razones, la mayor parte de la investigación en RWA se centra 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 con conciencia física. Los algoritmos adaptativos tradicionales no consideran la calidad de la señal, mientras que los algoritmos adaptativos con conciencia física sí.

El algoritmo de enrutamiento lexicográfico (LORA) fue propuesto en ^{[ 5 ]} . La idea principal detrás de LORA es enrutar las solicitudes de conexión lejos de las á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 en${\displaystyle costo(l)=\beta ^{uso(l)}}$dónde${\displaystyle \beta }$es un parámetro que se puede ajustar dinámicamente según la carga de tráfico y${\displaystyle usage(l)}$es el número de longitudes de onda en uso en el enlace${\displaystyle l}$Posteriormente, se puede utilizar un algoritmo estándar de ruta más corta para encontrar el camino. Esto requiere que cada conmutador óptico transmita periódicamente información sobre su uso reciente. Cabe destacar que LORA no tiene en cuenta ninguna limitación física.

Cuando${\displaystyle \beta }$es igual a uno, el algoritmo LORA es idéntico al algoritmo SP. Aumentar el valor de${\displaystyle \beta }$aumentará el sesgo hacia las rutas menos utilizadas. El valor óptimo de${\displaystyle \beta }$se puede calcular utilizando el conocido algoritmo de ascenso de colinas . Los valores óptimos de${\displaystyle \beta }$En la propuesta, los valores oscilaban entre 1,1 y 1,2.

El algoritmo de reserva hacia atrás con conciencia física (PABR) es una extensión de LORA. PABR mejora el rendimiento de dos maneras: considerando las limitaciones físicas y optimizando la selección de longitud de onda. Al buscar una trayectoria óptica , PABR descarta aquellas con una calidad de señal inaceptable debido a limitaciones lineales. En otras palabras, PABR es LORA con una restricción de calidad adicional.

Cabe señalar que PABR solo puede considerar deterioros lineales. Por otro lado, no sería posible estimar los deterioros no lineales en un entorno distribuido debido a que requieren conocimiento del tráfico global.

PABR también considera la calidad de la señal al seleccionar la longitud de onda. Para ello, descarta todas las longitudes de onda con un nivel de calidad de señal inaceptable. Este método se denomina "Calidad Primero Ajuste" y se describe en la siguiente sección.

Tanto LORA como PABR pueden implementarse con sondas simples o múltiples. El número máximo de sondas${\displaystyle p}$se denota como LORA-${\displaystyle p}$o PABR-${\displaystyle p}$Con el sondeo único, la selección de ruta selecciona solo un camino. Con el sondeo múltiple, se intentan varios caminos en paralelo, lo que aumenta la probabilidad de éxito de la conexión.

IA-BF - El algoritmo de Ajuste Óptimo con Conciencia de las Discapacidades (IA-BF) fue propuesto en ^{[ 6 ]} . Este algoritmo es un enfoque distribuido que depende de una gran cantidad de comunicación para utilizar información global y seleccionar siempre la ruta y longitud de onda más cortas disponibles. Esto se logra mediante el uso de sondeo múltiple en serie. Primero se intenta la ruta y longitud de onda más cortas disponibles y, en caso de fallo, se intenta la segunda ruta y longitud de onda más cortas disponibles. Este proceso continúa hasta que se encuentra una ruta y longitud de onda exitosas o se han intentado todas las longitudes de onda.

El método de sondeo múltiple permitirá que IA-BF supere a PABR-1 y LORA-1. Sin embargo, a medida que aumenta el número de sondas, el rendimiento de los algoritmos es similar.

IA-FF (Imparment Aware First Fit) es una extensión sencilla de IA-BF. En lugar de seleccionar las longitudes de onda en función del coste mínimo, se seleccionan en orden según su índice. IA-BF suele ofrecer mejores resultados que IA-FF en la mayoría de los casos.

AQoS - Calidad de Servicio Adaptativa (AQoS) fue propuesto en ^{[ 7 ]} . Este algoritmo es único en un par de aspectos. Primero, cada nodo mantiene dos contadores:${\displaystyle N_{BER}}$y${\displaystyle N_{wave}}$El objetivo de cada contador es determinar qué factor influye más en el bloqueo: la disponibilidad de la ruta y la longitud de onda o los requisitos de calidad. El algoritmo elige las rutas de forma diferente según el factor predominante.

Otra distinción es que AQoS utiliza el factor Q como coste del enlace. El coste del${\displaystyle i_{th}}$El enlace se calcula mediante esta fórmula.${\displaystyle D_{i}={\frac {\sum _{j=1}^{N_{i}}10\log[Q_{i,j}^{(s)}/Q_{i,j}^{(d)}]}{N_{i}}}}$dónde${\displaystyle N_{i}}$es el número de trayectorias de luz en el${\displaystyle i_{th}}$enlace,${\displaystyle Q_{i,j}^{(s)}}$y${\displaystyle Q_{i,j}^{(d)}}$son las mediciones del factor de calidad de la${\displaystyle j_{th}}$trayectoria de la luz en los nodos de origen y destino del${\displaystyle i_{th}}$enlace, respectivamente. Las estimaciones repetidas del factor de calidad son computacionalmente muy costosas.

Este algoritmo utiliza un enfoque de sondeo único. El enfoque de sondeo múltiple, que el artículo denomina ALT-AQoS (AQoS alternativo), es una extensión sencilla de la misma idea básica.