Problem Trasowania i Alokacji Widma (RSA)

Problem RSA w elastycznej sieci optycznej

Żądanie ustanowienia kanału optycznego obejmuje parę węzłów oraz wymaganą przepływność. Przykładowo operator może zestawiać wysokoprzepływne łącze między siedzibą firmy a centrum danych przez istniejącą siatkę światłowodową. Algorytm musi wybrać trasę w grafie włókien i przydzielić na niej blok szczelin częstotliwościowych o szerokości wynikającej z przepływności, formatu modulacji i narzutu kodowania korekcyjnego. Te dwie decyzje tworzą problem Trasowania i Alokacji Widma (RSA).

RSA jest centralnym wyzwaniem optymalizacyjnym w Elastycznych Sieciach Optycznych (EON). Żądanie określa węzeł źródłowy, docelowy oraz przepływność, na przykład 400 Gb/s. Elastyczna siatka pozwala dopasować szerokość kanału do zapotrzebowania zamiast rezerwować jeden stały kanał WDM dla każdego połączenia. Algorytm szuka ścieżki i wolnego bloku spełniającego warunki przyległości, ciągłości oraz rozłączności przydziałów. Przydział jednego połączenia wpływa na fragmentację widma dostępnego dla kolejnych żądań, dlatego wybór trasy i widma trzeba rozpatrywać razem. Żądania mogą napływać dynamicznie, dlatego przydział musi być wykonalny w chwili decyzji, z uwzględnieniem bieżącego stanu całej sieci. Model kontroluje również dostępność szczelin na każdym łączu oraz zgodność transpondera z wybranym formatem. Formalnie wolna szczelina nie wystarcza, jeśli parametry transmisji przekraczają budżet jakości. Jeżeli na wszystkich łączach nie ma wspólnego ciągłego bloku, żądanie zostaje zablokowane, nawet gdy suma wolnych szczelin jest duża.

Ograniczenia problemu RSA

Model RSA obejmuje trzy warunki zasobowe. Obejmują one przyległość szczelin w kanale, ciągłość zakresu na trasie oraz brak nakładania przydziałów na tym samym łączu.

• 1

  Przyległość szczelin w kanale

  Szczeliny przydzielone jednemu kanałowi muszą tworzyć jeden nieprzerwany blok. Jeśli potrzebne są cztery szczeliny, przydział 50, 51, 52 i 53 spełnia ten warunek, a zestaw 50, 51, 54 i 55 pozostawia niedozwoloną lukę. Przełączniki optyczne pracują na ciągłych fragmentach widma, więc rozproszone szczeliny nie tworzą jednego kanału. Szerokość bloku wynika z wymaganej przepływności oraz parametrów transpondera.

• 2

  Ciągłość szczelin na trasie

  W transparentnym kanale przydział widma musi zachować zgodny zakres na każdym łączu wybranej trasy. Jeżeli połączenie między Warszawą a Berlinem otrzyma szczeliny od 100 do 105 na pierwszym łączu, ten sam blok musi pozostać dostępny na kolejnych łączach. Najprostszy wariant utrzymuje tę samą częstotliwość środkową i szerokość szczeliny na całej ścieżce. Sieć z konwerterem widma może zmienić położenie zakresu między przeskokami przy zachowaniu wymaganej szerokości. Bez takiej funkcji zakresu nie można przesuwać w środku trasy. Ograniczenie ciągłości wynika więc z możliwości węzłów oraz z właściwości wybranej trasy.

• 3

  Brak nakładania szczelin

  Dwa różne połączenia korzystające z tego samego fizycznego łącza nie mogą współdzielić tych samych szczelin. Ich bloki muszą być rozłączne, aby ograniczyć interferencję między sygnałami i uniknąć nakładania kanałów. Operator może dodać małe Pasmo Ochronne między sąsiednimi połączeniami. W praktyce pasmo ochronne obejmuje jedną lub kilka pustych szczelin, a jego szerokość zależy od urządzeń i profilu transmisji.

Wpływ zasięgu i modulacji na RSA

Wybór trasy łączy alokację widma z budżetem transmisyjnym. Dłuższa trasa zwiększa tłumienie i kumuluje szum, dlatego profile modulacji o większej gęstości bitowej mają zwykle krótszy zasięg. Złożone formaty są bardziej wrażliwe na szum. O wykonalności kanału decydują także wymagania dotyczące OSNR i dyspersji chromatycznej.

W modelu RSA wybór formatu modulacji wpływa na liczbę wymaganych szczelin dla danej przepływności. Trasa musi jednocześnie spełniać limit zasięgu przypisany do wybranego profilu.

Przykład zależności dla przyjętej tabeli zasięg-modulacja:

Liczba szczelin zależy od ich szerokości, szybkości symbolowej, kodowania FEC i parametrów transpondera. Poniższe wartości przyjęto wyłącznie dla tej tabeli.

• Pojawia się żądanie połączenia o przepływności 200 Gb/s.
• Algorytm znajduje dwie możliwe ścieżki: krótką, bezpośrednią o długości 500 km oraz dłuższą, zapasową o długości 1500 km. Dla każdej sprawdza długość i ograniczenia jakości transmisji, w tym OSNR oraz dyspersję chromatyczną.
• Krótka ścieżka pozwala w przyjętej tabeli na modulację 16-QAM. Dla 200 Gb/s może ona wymagać 4 szczelin częstotliwościowych, które muszą być dostępne na całej trasie 500 km.
• Dłuższa ścieżka jest poza zasięgiem 16-QAM, więc wymaga odporniejszego formatu, takiego jak QPSK. Ta sama przepływność może wtedy wymagać 8 szczelin częstotliwościowych, a algorytm musi znaleźć szerszy blok na trasie 1500 km.

Najkrótsza trasa nie musi minimalizować zajętego widma. Wynik zależy od dostępnych bloków, jakości transmisji i funkcji celu przyjętej przez operatora.

Model matematyczny problemu RSA

Jedną z metod opisu problemu RSA jest Programowanie Liniowe Całkowitoliczbowe (ILP). Model zawiera zmienne decyzyjne, funkcję celu oraz ograniczenia wymuszające poprawną trasę i przydział widma. Wszystkie zależności pozostają liniowe, a zmienne opisujące użycie łączy i granice bloku mają wartości całkowite albo binarne.

Zmienne decyzyjne

Zmienne opisują trasę oraz położenie przydzielonego bloku szczelin.

• $x_{ij}$: Zmienna binarna. $x_{ij} = 1$ jeśli ścieżka połączenia używa łącza światłowodowego od węzła $i$ do węzła $j$. W przeciwnym razie $x_{ij} = 0$. Ta zmienna definiuje trasę.
• $f_a, f_b$: Zmienne całkowitoliczbowe wskazujące indeks pierwszej ($f_a$) i ostatniej ($f_b$) szczeliny w bloku przydzielonym do połączenia. Określają alokację widma.
• Dodatkowe zmienne pomocnicze, jak $x'_{ij,l}$ (wybór konkretnego wolnego bloku $l$ na łączu $ij$) i $c^k_{ij}$ (wskazanie, czy szczelina $k$ na łączu $ij$ jest używana) są również potrzebne do pełnego modelu.

Funkcja celu

Przykładowa funkcja celu minimalizuje całkowitą długość wybranej ścieżki:

Suma obejmuje odległości łącz ($d_{ij}$) należących do grafu sieci ($E$). Zmienna $x_{ij}$ włącza do wyniku tylko łącza należące do wybranej ścieżki ($x_{ij}=1$).

Długość ścieżki jest jednym z możliwych kryteriów wyboru. W zatłoczonej sieci krótsza trasa może mieć mniej wolnych bloków, dlatego funkcja celu może również uwzględniać zajęte widmo, fragmentację albo prawdopodobieństwo blokady.

Ograniczenia modelu

Ograniczenia wymuszają poprawną trasę oraz zgodny przydział widma.

• Zachowanie przepływu: Równania zapewniają, że wybrane łącza tworzą ścieżkę od źródła ($s$) do celu ($d$). Dla węzła pośredniego liczba użytych łączy wchodzących równa się liczbie użytych łączy wychodzących.
  $\sum_i x_{ij} - \sum_k x_{jk} = \begin{cases} -1, & \text{dla } j=s \\ 1, & \text{dla } j=d \\ 0, & \text{w p.p.} \end{cases}$
• Liczba szczelin: Liczba szczelin wynika z żądanej pojemności $C$ i przepływności pojedynczej szczeliny dla formatu modulacji $m$.
  $f_b - f_a + 1 = \lceil \frac{C}{C_{szczeliny}(m)} \rceil + G$
  Tutaj $C_{szczeliny}(m)$ oznacza przepływność pojedynczej szczeliny dla formatu modulacji $m$, a $G$ oznacza pasmo ochronne. Ograniczenie rozłączności pilnuje, aby przydziały różnych połączeń nie zajmowały tych samych szczelin na jednym łączu.
• Ciągłość i przyległość: Ograniczenia zapewniają, że zgodny blok ($f_a, f_b$) jest używany na łączach ścieżki ($x_{ij}=1$) oraz że jego szczeliny sąsiadują ze sobą.