Routing i przydział długości fali

routingu i przypisania długości fali ( RWA ) to problem sieci optycznej , którego celem jest maksymalizacja liczby połączeń optycznych.

Definicja

Ogólnym celem problemu RWA jest maksymalizacja liczby zestawionych połączeń. Każdemu żądaniu połączenia należy podać trasę i długość fali. Długość fali musi być spójna na całej ścieżce, chyba że zakłada się użycie konwerterów długości fali. Dwa żądania połączeń mogą współdzielić to samo łącze optyczne , pod warunkiem, że używana jest inna długość fali.

Problem RWA można formalnie zdefiniować w programie liniowym liczb całkowitych (ILP). Podany tutaj preparat ILP pochodzi z.

Wyolbrzymiać:

${\ Displaystyle C_ {0} (\ rho, q) = \ suma _ {i = 1} ^ {N_ {sd}} m_ {i}}$

z zastrzeżeniem

${\ Displaystyle m_ {i} \ geq 0, liczba całkowita, i = 1,2, ..., N_ {sd}}$

$\ Displaystyle c_ {ij} \ w {0,1}, i = 1,2, ..., P, j = 1,2,..., W}$

$}}$

${ \ Displaystyle C ^ {T} B \ równoważnik l_ {W \ razy$

${\ Displaystyle m \ równoważnik 1_ {W} C ^ {T} A}$

${\ Displaystyle m_ {i} \ równoważnik q_ {i} \ rho, i = 1,2, ..., N_ {sd}}$

${\ Displaystyle N_ {sd}}$ to liczba par źródło-miejsce docelowe, podczas gdy $połączeń$ ustanowionych dla każdej pary źródło-miejsce docelowe. $L}$$displaystyle$ to liczba linków, a liczba długości fal. ${\ displaystyle P}$ to zbiór ścieżek do trasowania połączeń. ${\ Displaystyle A: P \ razy N_ {sd}}$ jest macierzą, która pokazuje, które pary źródło-miejsce docelowe są aktywne, $P \times W}$$macierzą$ , która pokazuje, które linki są aktywne, i do to macierz przypisania trasy i długości fali.

Należy zauważyć, że powyższe sformułowanie zakłada, że ​​wymagania dotyczące ruchu są znane a priori . Ten typ problemu jest znany jako Static Lightpath Establishment (SLE). Powyższe sformułowanie nie uwzględnia również jakości sygnału.

Wykazano, że problem SLE RWA jest NP-zupełny w. Dowód obejmuje redukcję do problemu kolorowania wykresu ${\ displaystyle n}$ . Innymi słowy, rozwiązanie problemu SLE RWA jest tak złożone, jak znalezienie liczby chromatycznej ogólnego wykresu. Biorąc pod uwagę, że dynamiczne RWA są bardziej złożone niż statyczne RWA, musi być tak, że dynamiczne RWA są również NP-zupełne.

Podano inny dowód NP-zupełny. Dowód ten obejmuje redukcję do problemu przepływu wielu towarów .

Problem RWA dodatkowo komplikuje konieczność uwzględnienia jakości sygnału. Wiele upośledzeń optycznych ma charakter nieliniowy, więc nie można zastosować standardowego algorytmu najkrótszej ścieżki do ich optymalnego rozwiązania, nawet jeśli znamy dokładny stan sieci. Zwykle nie jest to bezpieczne założenie, dlatego rozwiązania muszą być wydajne przy użyciu tylko ograniczonych informacji o sieci.

Metodologia

Biorąc pod uwagę złożoność RWA, istnieją dwie ogólne metodologie rozwiązania problemu:

• Pierwsza metoda polega na rozwiązaniu najpierw części trasowania, a następnie przypisaniu długości fali. Istnieją trzy typy wyboru trasy: wyznaczona trasa, wyznaczona trasa alternatywna i trasa adaptacyjna.
• Drugie podejście polega na łącznym rozważeniu zarówno wyboru trasy, jak i przypisania długości fali.

Najpierw routing, potem przydział długości fali

Algorytmy trasowania

Stałe wyznaczanie tras

Trasowanie po stałej ścieżce to najprostsze podejście do znajdowania ścieżki świetlnej. Zawsze używana jest ta sama ustalona trasa dla danej pary źródłowej i docelowej. Zazwyczaj ta ścieżka jest obliczana z wyprzedzeniem przy użyciu algorytmu najkrótszej ścieżki, takiego jak Algorytm Dijkstry . Chociaż to podejście jest bardzo proste, wydajność zwykle nie jest wystarczająca. Jeśli używane są zasoby wzdłuż ustalonej ścieżki, przyszłe żądania połączeń będą blokowane, nawet jeśli mogą istnieć inne ścieżki.

Algorytm SP-1 (najkrótsza ścieżka, 1 sonda) jest przykładem rozwiązania wyznaczania stałej ścieżki. Algorytm ten oblicza najkrótszą ścieżkę na podstawie liczby routerów optycznych jako funkcji kosztu. Pojedyncza sonda służy do nawiązania połączenia najkrótszą drogą. Czas działania to koszt algorytmu Dijkstry: ${\ Displaystyle O (m + n \ log n)}$ , gdzie ${\ displaystyle m}$ to liczba krawędzi i ${\ displaystyle N}$ to liczba routerów. Czas działania jest po prostu stałą, jeśli używana jest z góry określona ścieżka.

Ta definicja SP-1 wykorzystuje liczbę przeskoków jako funkcję kosztu. Algorytm SP-1 można rozszerzyć, aby wykorzystywał różne funkcje kosztów, takie jak liczba EDFA.

Naprawiono trasę alternatywną

Stały routing alternatywny jest rozszerzeniem routingu o stałej ścieżce. Zamiast jednej ustalonej trasy dla danej pary źródłowej i docelowej, przechowywanych jest kilka tras. Sondy mogą być przesyłane szeregowo lub równolegle. Dla każdego żądania połączenia węzeł źródłowy próbuje znaleźć połączenie na każdej ze ścieżek. Jeśli wszystkie ścieżki zawiodą, połączenie zostanie zablokowane. Jeśli dostępnych jest wiele ścieżek, wykorzystana zostanie tylko jedna z nich.

SP- (najkrótsza ścieżka, $sondy$ , $displaystyle$$p> 1}$ przykładem ustalonej trasy alternatywnej. Algorytm ten oblicza $ścieżki$ na podstawie liczby routerów optycznych jako funkcji kosztu. Czas działania przy użyciu algorytmu Yena wynosi gdzie jest liczbą krawędzi, $n$$n$$}$ to liczba routerów, a $p}$ liczba ścieżek. Czas działania jest stałym czynnikiem, jeśli ścieżki są wstępnie obliczone.

Routing adaptacyjny

Głównym problemem związanym zarówno z routingiem ze stałą trasą, jak iz trasowaniem alternatywnym, jest to, że żaden algorytm nie bierze pod uwagę bieżącego stanu sieci. Jeśli z góry określone ścieżki nie są dostępne, żądanie połączenia zostanie zablokowane, mimo że mogą istnieć inne ścieżki. Routing o ustalonej ścieżce i o ustalonej trasie alternatywnej nie są świadome jakości. Z tych powodów większość badań w RWA odbywa się obecnie w algorytmach adaptacyjnych. Pięć przykładów routingu adaptacyjnego to LORA, PABR, IA-BF, IA-FF i AQoS.

Algorytmy adaptacyjne dzielą się na dwie kategorie: tradycyjne i świadome fizycznie. Tradycyjne algorytmy adaptacyjne nie biorą pod uwagę jakości sygnału, jednak algorytmy adaptacyjne świadome fizycznie tak.

Tradycyjne adaptacyjne RWA

leksykograficzny routingu (LORA) został zaproponowany w . Główną ideą LORA jest kierowanie żądań połączenia z dala od przeciążonych obszarów sieci, zwiększając prawdopodobieństwo, że żądania połączenia zostaną zaakceptowane. Osiąga się to poprzez ustawienie kosztu każdego łącza na do o $Displaystyle cost (l) = \ beta ^ {usage (l)}}$ gdzie ${ \displaystyle\beta}$$,$ można dynamicznie regulować w zależności od obciążenia fal używanych $.$ Do znalezienia ścieżki można następnie użyć standardowego algorytmu najkrótszej ścieżki. Wymaga to okresowego wysyłania przez każdy przełącznik optyczny informacji o ostatnim użyciu. Należy pamiętać, że LORA nie bierze pod uwagę żadnych upośledzeń fizycznych.

Kiedy $się$ jeden, algorytm LORA jest identyczny z algorytmem SP. $.$ wartości zwiększy odchylenie w kierunku rzadziej używanych tras Optymalną wartość $wzniesień$ obliczyć za pomocą dobrze znanego algorytmu pokonywania . We wniosku optymalne wartości $1,2 .$

Fizycznie świadomy adaptacyjny RWA

Fizycznie świadomy algorytm rezerwacji wstecznej (PABR) jest rozszerzeniem LORA. PABR jest w stanie poprawić wydajność na dwa sposoby: biorąc pod uwagę upośledzenia fizyczne i ulepszony dobór długości fali. Gdy PABR szuka ścieżki optycznej, ścieżki o niedopuszczalnej jakości sygnału z powodu upośledzeń liniowych są przycinane. Innymi słowy, PABR to LORA z dodatkowym ograniczeniem jakości.

Należy zauważyć, że PABR może uwzględniać tylko upośledzenia liniowe. Z drugiej strony, nieliniowe upośledzenia nie byłyby możliwe do oszacowania w środowisku rozproszonym ze względu na wymóg globalnej wiedzy o ruchu drogowym.

PABR bierze również pod uwagę jakość sygnału przy wyborze długości fali. Osiąga to poprzez usunięcie z rozważań wszystkich długości fal o niedopuszczalnym poziomie jakości sygnału. Podejście to nosi nazwę Quality First Fit i zostało omówione w następnej sekcji.

Zarówno LORA, jak i PABR można wdrożyć za pomocą pojedynczego lub wielokrotnego sondowania. Maksymalna liczba sond jest oznaczona jako LORA- $\ displaystyle p}$$lub$ PABR- ${\ displaystyle p}$ . W przypadku pojedynczego sondowania podczas wyboru trasy wybierana jest tylko jedna ścieżka. W przypadku wielokrotnego sondowania próbuje się połączyć wiele ścieżek równolegle, co zwiększa prawdopodobieństwo pomyślnego nawiązania połączenia.

Inne podejścia do routingu

IA-BF — algorytm uwzględniający utratę wartości (IA-BF) został zaproponowany w . Algorytm ten jest podejściem rozproszonym, które jest zależne od dużej ilości komunikacji w celu wykorzystania globalnych informacji w celu wybrania zawsze najkrótszej dostępnej ścieżki i długości fali. Osiąga się to poprzez zastosowanie szeregowego wielokrotnego sondowania. Najpierw próbuje się wybrać najkrótszą dostępną ścieżkę i długość fali, aw przypadku niepowodzenia próbuje się wybrać drugą najkrótszą dostępną ścieżkę i długość fali. Proces ten trwa do momentu znalezienia udanej ścieżki i długości fali lub próby wykorzystania wszystkich długości fal.

Podejście z wieloma sondami pozwoli IA-BF przewyższyć zarówno PABR-1, jak i LORA-1. Jednak wraz ze wzrostem liczby sond wydajność algorytmów jest podobna.

IA-FF - Impairment Aware First Fit (IA-FF) jest prostym rozszerzeniem IA-BF. Zamiast wybierania długości fal pod kątem minimalnego kosztu, długości fal są wybierane w kolejności według ich indeksu. IA-BF ma tendencję do przewyższania IA-FF w większości scenariuszy.

AQoS — adaptacyjna jakość usług (AQoS) została zaproponowana w r. Algorytm ten jest wyjątkowy na kilka sposobów. Po pierwsze, każdy węzeł utrzymuje dwa liczniki: ${\ displaystyle N_ {BER}}$ i ${\ displaystyle N_ {wave}}$ . Celem każdego licznika jest określenie, który problem ma większy wpływ na blokowanie: dostępność ścieżki i długości fali lub wymagania dotyczące jakości. Algorytm wybiera trasy inaczej w zależności od większego problemu.

Inną różnicą jest to, że AQoS wykorzystuje współczynnik Q jako koszt łącza. Koszt ${\ displaystyle i_ {th}}$ oblicza się według tego wzoru ${\ Displaystyle D_ {i} = {\ Frac {\ suma _ {j = 1} ^ {N_ {i}} 10 \ log [Q_ {i, j} ^ {(s)} / Q_ {i, j} ^ {(d)}]} {$$łączu$${i}}}}$ gdzie jest liczbą ścieżek świetlnych na ${\ Displaystyle Q_ {i, j} ^ {(s)}}$ ja , $\ displaystyle i_ {th$ i ${\ Displaystyle Q_ {i, j} ^ {(d)}}$ to pomiary współczynnika jakości j ${\ displaystyle j_ {th}}$${\ displaystyle i_ {th}}$ świetlna odpowiednio w węzłach źródłowych i docelowych łącza ja . Powtarzane oszacowania współczynnika jakości są bardzo kosztowne obliczeniowo.

Algorytm ten jest podejściem z pojedynczym sondowaniem. Podejście z wieloma sondami, które artykuł nazywa ALT-AQoS (alternatywny AQoS), jest prostym rozszerzeniem tej samej podstawowej idei.

Przypisanie długości fali

Dwie najpopularniejsze metody przydzielania długości fali to First Fit i Random Fit. First Fit wybiera dostępną długość fali o najniższym indeksie. Random Fit określa, które długości fal są dostępne, a następnie wybiera losowo spośród nich. Złożoność obu $algorytmów$$gdzie$ jest długości Pierwsze dopasowanie przewyższa losowe dopasowanie.

Zaproponowano rozszerzenie First Fit i Random Fit w celu rozważenia jakości sygnału. Quality First Fit i Quality Random Fit eliminują z rozważań długości fal, które mają niedopuszczalną jakość sygnału. Złożoność tych algorytmów jest jednak większa, ponieważ do oszacowania współczynnika Q wymagane są maksymalnie $.$

Istnieje kilka innych algorytmów przypisania długości fali: Najrzadziej używane, Najczęściej używane, Minimalny produkt, Najmniej obciążone, Maksymalna suma i Względna utrata pojemności. Najwięcej używanych znacznie przewyższa użycie Najrzadziej używane i nieznacznie przewyższa pierwsze dopasowanie. Min Product, Least Loaded, Max Sum i Relative Capacity Loss próbują wybrać długość fali, która minimalizuje prawdopodobieństwo zablokowania przyszłych żądań.

Znaczącą wadą tych algorytmów jest to, że wymagają one znacznych narzutów komunikacyjnych, co czyni je niepraktycznymi do wdrożenia, chyba że masz scentralizowaną strukturę sieci.

Wspólne trasowanie i przydział długości fali

Alternatywnym podejściem do oddzielnego wybierania trasy i długości fali jest rozważenie ich łącznie. Podejścia te wydają się być bardziej teoretyczne, a nie praktyczne. Ponieważ jest to problem NP-zupełny, żadne dokładne rozwiązanie prawdopodobnie nie będzie możliwe. Techniki aproksymacji również zwykle nie są zbyt przydatne, ponieważ będą wymagały scentralizowanej kontroli i zwykle predefiniowanych wymagań dotyczących ruchu. Dwa wspólne podejścia to formułowanie ILP i przeskakiwanie na wyspę .

Formułę ILP wymienioną powyżej można rozwiązać przy użyciu tradycyjnego solwera ILP. Zwykle odbywa się to poprzez tymczasowe złagodzenie ograniczeń całkowitych, optymalne rozwiązanie problemu i przekształcenie rzeczywistego rozwiązania w rozwiązanie całkowite. Można dodać dodatkowe ograniczenia i proces powtarzać w nieskończoność, stosując rozgałęzione i powiązane .

W artykule autorzy podają algorytm, który można wykorzystać do efektywnego i optymalnego rozwiązania problemu RWA z ograniczeniami. Autorzy badają problem ograniczonego trasowania i przydziału widma (RSA), który można zredukować do problemu ograniczonego RWA, żądając jednego wycinka. Zwężenie ogranicza długość ścieżki.

W artykule autorzy przedstawiają uogólniony algorytm Dijkstry, który może być wykorzystany do wydajnego i optymalnego rozwiązywania problemów RWA, RSA oraz routingu, modulacji i przydziału widma (RMSA) bez ograniczeń długości ścieżek.