Wielkie Wyzwanie: Optyczne Planowanie Przestrzenne

Wyobraź sobie, że jesteś urbanistą w futurystycznej metropolii, gdzie ruch odbywa się za pomocą wiązek światła. Korporacja chce zbudować nowe, wysokoprzepustowe łącze danych między swoją siedzibą a nowym centrum danych. Twoim zadaniem jest nie tylko zaplanowanie trasy dla tej nowej autostrady światła przez istniejącą siatkę światłowodową, ale także przydzielenie konkretnego, ciągłego "gruntu" widmowego wzdłuż całej tej trasy pod budowę. Ta złożona, dwuczęściowa łamigłówka to sedno problemu Trasowania i Alokacji Widma (RSA).

RSA jest centralnym wyzwaniem optymalizacyjnym w Elastycznych Sieciach Optycznych (EON). To „mózg”, który sprawia, że sieć jest naprawdę elastyczna. Żądanie nowego połączenia jest definiowane przez trzy rzeczy: węzeł źródłowy, węzeł docelowy i wymaganą przepływność (np. 400 Gb/s). Algorytm RSA musi następnie znaleźć rozwiązanie, które nie tylko łączy te dwa punkty, ale robi to w sposób efektywnie wykorzystujący ograniczone zasoby widmowe sieci. Nie jest to proste zadanie; wybory dokonane dla jednego połączenia bezpośrednio wpływają na zasoby dostępne dla wszystkich przyszłych połączeń.

Trzy Złote Reguły: Ograniczenia Problemu RSA

Każde poprawne rozwiązanie problemu RSA musi przestrzegać trzech fundamentalnych zasad podyktowanych fizyką i technologią sieci optycznych. Ograniczenia te definiują „zasady ruchu drogowego” dla światła podróżującego przez sieć.

• 1

  Warunek Ciągłości Widma (w obrębie łącza)

  Szczeliny częstotliwościowe przydzielone jednemu połączeniu na dowolnym pojedynczym łączu światłowodowym muszą tworzyć jeden, spójny, nieprzerwany blok. Jeśli połączenie 100 Gb/s wymaga 4 szczelin częstotliwościowych, należy przydzielić szczeliny 50, 51, 52 i 53. Nie można przydzielić szczelin 50, 51, 54 i 55, pozostawiając luki. Dzieje się tak, ponieważ sprzęt do przełączania optycznego jest zaprojektowany do obsługi ciągłych fragmentów widma, a nie rozproszonych fragmentów. Pomyśl o tym jak o pociągu – wszystkie wagony muszą być ze sobą połączone.

• 2

  Warunek Ciągłości Widma (na całej ścieżce)

  To najbardziej restrykcyjna i wymagająca reguła. Gdy połączenie optyczne przebiega przez wiele łącz światłowodowych w sieci, musi ono zajmować dokładnie ten sam blok szczelin częstotliwościowych na każdym pojedynczym łączu wzdłuż całej ścieżki. Na przykład, jeśli połączenie z Warszawy do Berlina używa szczelin od 100 do 105 na łączu wychodzącym z Warszawy, musi używać szczelin od 100 do 105 na każdym kolejnym łączu aż do samego Berlina. Nie może w połowie drogi zmienić pasa widmowego. Zasada ta istnieje, ponieważ większość sieci nie posiada przystępnych cenowo, w pełni optycznych konwerterów długości fali, które mogłyby płynnie zmieniać „kolor” sygnału.

• 3

  Warunek Nienakładania się Widm

  Dwa różne połączenia, które współdzielą to samo fizyczne łącze światłowodowe, nie mogą używać tych samych szczelin częstotliwościowych. To najbardziej intuicyjna zasada – nie można zbudować dwóch supermarketów na tej samej działce. Zapobiega to interferencjom między sygnałami. Dla bezpieczeństwa często pozostawia się małe Pasmo Ochronne (kilka pustych szczelin) między sąsiednimi połączeniami.

Czwarty Ograniczenie: Fizyka Dystansu

Poza trzema „Złotymi Regułami”, istnieje czwarte ograniczenie, które nierozerwalnie łączy problemy trasowania i alokacji widma: kompromis między formatem modulacji a zasięgiem. Im dalej sygnał musi podróżować, tym więcej szumu gromadzi. Złożone formaty modulacji są bardzo wrażliwe na szum.

Dlatego fizyczna długość wybranej trasy bezpośrednio determinuje maksymalną złożoność formatu modulacji, jaki można zastosować. To z kolei determinuje liczbę szczelin częstotliwościowych wymaganą dla danej przepływności.

Przykład współzależności:

• Pojawia się żądanie połączenia 200 Gb/s.
• Algorytm trasowania 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.
• Na podstawie tabeli zasięg-modulacja, krótka ścieżka pozwala na użycie modulacji 16-QAM. Aby osiągnąć 200 Gb/s, może to wymagać 4 szczelin częstotliwościowych. Algorytm alokacji widma musi teraz znaleźć blok 4 szczelin, który jest ciągły i dostępny na całej 500-kilometrowej trasie.
• Długa ścieżka jest zbyt odległa dla 16-QAM. Wymaga bardziej odpornego formatu, jak QPSK. Aby osiągnąć te same 200 Gb/s przy użyciu QPSK, może to wymagać 8 szczelin częstotliwościowych. Algorytm musi teraz szukać znacznie szerszego bloku 8 szczelin na dłuższej trasie.

Optymalne rozwiązanie nie zawsze jest najkrótszą ścieżką. Nieco dłuższa fizycznie trasa, która pozwala na użycie bardziej wydajnej modulacji (wymagającej mniejszego bloku widmowego), może być łatwiejsza do zrealizowania w zatłoczonej sieci, zapobiegając w ten sposób blokadzie połączenia.

Sformułowanie Matematyczne: Język Optymalizacji

Aby polecić komputerowi optymalne rozwiązanie problemu RSA, musimy przełożyć to wyzwanie na precyzyjny język matematyczny. Standardowym narzędziem do tego jest Programowanie Liniowe Całkowitoliczbowe (ILP). Model ILP ma trzy główne komponenty: zmienne decyzyjne (pytania, na które szukamy odpowiedzi), funkcję celu (co chcemy zminimalizować lub zmaksymalizować) i ograniczenia (reguły).

Zmienne Decyzyjne (Niewiadome)

Zmienne te reprezentują wybory, których algorytm musi dokonać.

• $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. Reprezentują one indeks pierwszej ($f_a$) i ostatniej ($f_b$) szczeliny częstotliwościowej w bloku przydzielonym do połączenia. Te zmienne definiują 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 (Cel)

Definiuje to, co chcemy osiągnąć. Powszechnym celem jest minimalizacja całkowitej długości wybranej ścieżki w celu oszczędzania zasobów:

Ten wzór sumuje fizyczną odległość ($d_{ij}$) wszystkich łącz światłowodowych w sieci ($E$), ale człon $x_{ij}$ działa jak przełącznik, zapewniając, że sumujemy tylko odległości tych łącz, które faktycznie są częścią wybranej ścieżki ($x_{ij}=1$).

Ograniczenia (Reguły Gry)

Są to równania matematyczne, które wymuszają wszystkie zasady.

• Warunki Zachowania Przepływu: Równania te zapewniają, że wybrane łącza tworzą poprawną, ciągłą ścieżkę od źródła ($s$) do celu ($d$). Dla każdego węzła pośredniego liczba wchodzących łącz użytych w ścieżce musi być równa liczbie wychodzących łącz.
  $\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}$
• Ograniczenie Liczby Szczelin: To równanie oblicza, ile szczelin jest potrzebnych w oparciu o żądaną pojemność $C$ i wybrany format modulacji $m$.
  $f_b - f_a + 1 = \lceil \frac{C}{C_{szczeliny}(m)} \rceil + G$
  Tutaj $C_{szczeliny}(m)$ to pojemność pojedynczej szczeliny dla formatu modulacji $m$, a $G$ to pasmo ochronne.
• Warunki Ciągłości: Seria złożonych równań zapewnia, że ten sam blok ($f_a, f_b$) jest używany na wszystkich łączach ścieżki ($x_{ij}=1$) i że ten blok jest rzeczywiście ciągły.