Alokacja Widma w EON

Metody i algorytmy efektywnej alokacji widma w sieciach elastycznych.

Wyzwanie: Widmo Optyczne jako Cenny Grunt

Wyobraź sobie dostępne widmo optyczne w światłowodzie jako cenny, ograniczony pas niezabudowanej ziemi. Gdy pojawia się żądanie nowego połączenia – jak deweloper chcący zbudować nowy supermarket – operator sieci, działając jako urbanista, musi zdecydować nie tylko, którymi drogami dotrzeć do lokalizacji (to jest Trasowanie, ang. Routing), ale także dokładnie na której działce wzdłuż tej trasy budować. Ta druga, kluczowa decyzja, jest znana jako Alokacja Widma (SA).

W , ten „grunt” jest podzielony na wiele małych, jednolitych działek zwanych szczelinami częstotliwościowymi. Żądanie połączenia (supermarket) wymaga określonej liczby sąsiadujących działek (ciągłego bloku szczelin), na których można się „zbudować”. Zadaniem algorytmu Alokacji Widma jest wydajne przydzielanie tych działek, zapewniając, że żadne dwa supermarkety nie zostaną zbudowane na sobie, a ogólne wykorzystanie gruntu będzie jak najbardziej efektywne dla przyszłego rozwoju.

Główna Przeszkoda: Fragmentacja Widma

Najpoważniejszym wyzwaniem w Alokacji Widma jest Fragmentacja Widma. W dynamicznej sieci połączenia są nieustannie ustanawiane i zrywane. Kiedy połączenie zostaje zakończone, zwalnia swój blok szczelin częstotliwościowych, tworząc lukę dostępnego widma. Z biegiem czasu ten proces alokacji i zwalniania pozostawia po sobie mozaikę małych, rozproszonych i często bezużytecznych wolnych bloków.

Jest to analogiczne do fragmentacji na dysku twardym komputera, gdzie po utworzeniu i usunięciu wielu plików wolne miejsce jest podzielone na wiele małych, nieciągłych fragmentów. W sieciach optycznych oznacza to, że nawet jeśli całkowita ilość wolnego widma na łączu jest duża, obsłużenie nowego żądania połączenia może być niemożliwe, ponieważ żaden pojedynczy blok szczelin nie jest wystarczająco duży.

Konsekwencje Fragmentacji

Źle zarządzana alokacja widma prowadzi do dużej fragmentacji, co z kolei prowadzi do wyższego prawdopodobieństwa blokady. Połączenie jest „blokowane”, jeśli sieć nie może znaleźć odpowiedniej ścieżki i/lub bloku widma, aby je obsłużyć, nawet jeśli sieć nie jest w pełni obciążona. Dla operatora sieci wysokie prawdopodobieństwo blokady przekłada się bezpośrednio na utracone przychody i niezadowolonych klientów.

Heurystyki Alokacji Widma: Proste Reguły dla Złożonego Problemu

Znalezienie absolutnie optymalnej alokacji widma dla każdego możliwego przyszłego żądania jest problemem niezwykle złożonym (). Dlatego kontrolery sieci opierają się na heurystykach – prostych, szybkich algorytmach opartych na regułach, które zapewniają wystarczająco dobre rozwiązanie w krótkim czasie.

Wyobraźmy sobie widmo na łączu światłowodowym jako długą ulicę z ponumerowanymi działkami od 0 do 319. Pojawia się nowe żądanie wymagające 4 sąsiednich działek. Sieć ma kilka wolnych bloków: działki 10-15 (6 działek), 40-43 (4 działki) oraz 90-95 (6 działek). Który blok powinien wybrać algorytm?

Popularne Strategie Alokacji

First-Fit (FF) - Pierwsze Dopasowanie

Reguła: Przeskanuj widmo, zaczynając od najniższej częstotliwości (szczeliny 0) w górę, i przydziel pierwszy dostępny, ciągły blok szczelin, który jest wystarczająco duży, aby obsłużyć żądanie.

W naszym przykładzie: Algorytm przeskanowałby widmo, znalazł wolny blok 10-15, stwierdził, że jest wystarczająco duży $(6 > 4)$ i przydzieliłby szczeliny 10, 11, 12 i 13 do nowego połączenia.

Implikacje: FF jest bardzo prosty i szybki w implementacji. Z czasem ma tendencję do "upakowywania" połączeń w dolnej części widma, pozostawiając większe ciągłe bloki wolne w górnej części, co może być korzystne dla przyszłych żądań o dużej przepustowości. Wiele badań pokazuje, że działa zaskakująco dobrze w redukowaniu ogólnej blokady.

Last-Fit (LF) - Ostatnie Dopasowanie

Reguła: Przeciwieństwo First-Fit. Przeskanuj widmo, zaczynając od najwyższej częstotliwości w dół, i przydziel pierwszy wystarczająco duży blok.

W naszym przykładzie: Algorytm przeskanowałby od góry, znalazł wolny blok 90-95 i przydzielił szczeliny 92, 93, 94 i 95 (lub 90-93).

Implikacje: Ta strategia upakowuje połączenia w górnej części widma, pozostawiając wolne miejsce na dole. Działa podobnie do FF, ale wybór może być podyktowany fizycznymi właściwościami wzmacniaczy optycznych, które czasami mają lepsze profile wzmocnienia na jednym z krańców widma.

Random-Fit (RF) - Losowe Dopasowanie

Reguła: Zidentyfikuj wszystkie dostępne ciągłe bloki, które są wystarczająco duże dla żądania, a następnie wybierz jeden z nich losowo.

W naszym przykładzie: Algorytm zidentyfikowałby bloki $10-15$ , $40-43$ i $90-95$ jako kandydatów i losowo wybrał jeden, aby umieścić w nim 4-szczelinowe połączenie.

Implikacje: Poprzez bardziej równomierne rozpraszanie kanałów po całym widmie, RF może teoretycznie prowadzić do poważniejszej fragmentacji w dłuższej perspektywie, tworząc wiele małych, bezużytecznych luk wszędzie, zamiast konsolidować wolne miejsce. Zazwyczaj działa gorzej niż First-Fit.

Exact-Fit - Dokładne Dopasowanie

Reguła: Poszukaj wolnego bloku, który ma dokładnie taki sam rozmiar jak żądanie. Dopiero jeśli taki idealnie dopasowany blok nie zostanie znaleziony, rozważa się alokację z większego bloku.

W naszym przykładzie: Algorytm najpierw poszukałby bloku 4-szczelinowego. Znalazłby blok $40-43$ i natychmiast by go wybrał, pozostawiając większe bloki $(10-15)$ i $(90-95)$ nietknięte dla potencjalnych większych żądań w przyszłości.

Implikacje: Jest to intuicyjna strategia mająca na celu zachowanie dużych ciągłych bloków. Może być bardzo skuteczna, ale nieco bardziej złożona w implementacji niż prosty First-Fit.

Zaawansowane Aspekty Alokacji

Poza prostymi heurystykami, rzeczywisty system Alokacji Widma musi uwzględniać dodatkowe ograniczenia narzucone przez fizykę optyczną.

Świadomość Formatu Modulacji

Liczba szczelin, jakiej wymaga połączenie, nie jest stała; zależy od wybranego formatu modulacji, co z kolei zależy od długości ścieżki.

Rozważmy żądanie połączenia 100 Gb/s:

Dla krótkiej ścieżki (np. Warszawa - Poznań, ~300 km), możliwe jest użycie modulacji 16-QAM. Wymaga to na przykład 3 szczelin częstotliwościowych.
Dla długiej ścieżki międzymiastowej (np. Warszawa - Paryż, ~1600 km), 16-QAM byłby zbyt podatny na szumy. System musi użyć bardziej odpornego formatu, jak QPSK, który może wymagać 4 lub 5 szczelin, aby dostarczyć te same 100 Gb/s.

Dlatego prawdziwie inteligentny algorytm SA nie może po prostu szukać „jakiegoś wolnego bloku”. Musi najpierw określić wymagany format modulacji na podstawie długości ścieżki, a następnie szukać wolnego bloku, który jest wystarczająco szeroki, aby pomieścić liczbę szczelin wymaganą przez ten konkretny format.

Defragmentacja Widma

Co się dzieje, gdy fragmentacja nieuchronnie staje się problemem? Ostatecznym rozwiązaniem jest defragmentacja widma. Polega ona na aktywnym przestawianiu istniejących połączeń w sieci, przesuwaniu ich do różnych części widma w celu skonsolidowania małych wolnych bloków w większe, bardziej użyteczne. Jest to proces analogiczny do defragmentacji dysku twardego.

Jest to bardzo złożony proces, ponieważ idealnie musi być wykonany bez przerywania działających usług ("defragmentacja bezuderzeniowa"), co wymaga chwilowego przekierowania połączeń lub użycia zaawansowanych technik do przesunięcia częstotliwości kanału bez utraty danych. Pozostaje on aktywnym i trudnym obszarem badań w sieciach optycznych.