Trasowanie z ograniczeniami skrętu
Algorytm routingu decyduje o ścieżce, którą podąża pakiet od routerów źródłowych do docelowych w sieci . Ważnym aspektem, który należy wziąć pod uwagę podczas projektowania algorytmu routingu, jest unikanie impasu . Routing z ograniczeniami skrętu to algorytm trasowania dla rodziny topologii typu mesh , który pozwala uniknąć zakleszczeń poprzez ograniczenie typów skrętów dozwolonych w algorytmie podczas określania trasy od węzła źródłowego do węzła docelowego w sieci.
Przyczyna impasu
Zakleszczenie (pokazane na rys. 1) to sytuacja, w której dalszy transport pakietów nie może mieć miejsca z powodu nasycenia zasobów sieciowych, takich jak bufory czy łącza . Główną przyczyną impasu jest cykliczne pozyskiwanie kanałów w sieci. Załóżmy na przykład, że w sieci są cztery kanały. Cztery pakiety zapełniły bufory wejściowe tych czterech kanałów i muszą zostać przesłane do następnego kanału. Załóżmy teraz, że bufory wyjściowe wszystkich tych kanałów są również wypełnione pakietami, które należy przesłać do następnego kanału. Jeśli te cztery kanały tworzą cykl, dalsze przesyłanie pakietów jest niemożliwe, ponieważ bufory wyjściowe i bufory wejściowe wszystkich kanałów są już zapełnione. Nazywa się to cykliczną akwizycją kanałów i powoduje zakleszczenie.
Rozwiązanie impasu
Zakleszczenia można wykryć , przerwać lub całkowicie uniknąć . Wykrywanie i usuwanie zakleszczeń w sieci jest kosztowne pod względem opóźnień i zasobów. Tak więc łatwym i niedrogim rozwiązaniem jest unikanie zakleszczeń poprzez wybór technik routingu, które zapobiegają cyklicznemu pozyskiwaniu kanałów.
Logika wyznaczania ograniczeń skrętu
Logika wyznaczania tras z ograniczeniami skrętu wywodzi się z kluczowej obserwacji. Cykliczna akwizycja kanałów może mieć miejsce tylko wtedy, gdy wystąpiły wszystkie cztery możliwe obroty zgodnie z ruchem wskazówek zegara (lub przeciwnie do ruchu wskazówek zegara). Oznacza to, że można uniknąć impasu, zabraniając co najmniej jednego obrotu zgodnie z ruchem wskazówek zegara i jednego obrotu w kierunku przeciwnym do ruchu wskazówek zegara. Wszystkie obroty w kierunku zgodnym z ruchem wskazówek zegara i przeciwnym do ruchu wskazówek zegara, które są możliwe w nieograniczonym algorytmie trasowania, pokazano na rys. 2.
Przykłady wyznaczania tras z ograniczeniami skrętu
Trasowanie z ograniczeniem skrętu można uzyskać, zabraniając co najmniej jednego z czterech możliwych skrętów zgodnie z ruchem wskazówek zegara i co najmniej jednego z czterech możliwych skrętów w kierunku przeciwnym do ruchu wskazówek zegara w algorytmie wyznaczania trasy. Oznacza to, że istnieje co najmniej 16 (4x4) możliwych technik ograniczania skrętu, ponieważ masz do wyboru 4 skręty zgodnie z ruchem wskazówek zegara i 4 skręty przeciwnie do ruchu wskazówek zegara. Niektóre z tych technik zostały wymienione poniżej.
Routing uporządkowany według wymiarów (XY).
Trasowanie uporządkowane według wymiarów (XY) (pokazane na rys. 3) ogranicza wszystkie zakręty z wymiaru y do wymiaru x. Zabrania to dwóch obrotów w kierunku przeciwnym do ruchu wskazówek zegara i dwóch obrotów w prawo, co jest więcej niż faktycznie wymagane. Nawet wtedy, ponieważ ogranicza liczbę dozwolonych tur, możemy powiedzieć, że jest to przykład trasowania z ograniczeniem skrętu.
Pierwsza trasa na zachód
Pierwsza trasa na zachód (pokazana na rys. 4) ogranicza wszystkie skręty w kierunku zachodnim. Oznacza to, że w razie potrzeby na proponowanej trasie należy najpierw obrać kierunek zachodni.
Ostatnia trasa na północ
Ostatnia trasa na północ (pokazana na rys. 5) ogranicza skręcanie w dowolnym innym kierunku, jeśli aktualnym kierunkiem jest północ. Oznacza to, że w razie potrzeby kierunek północny należy obrać jako ostatni na proponowanej trasie.
Negatywny pierwszy routing
Ujemna pierwsza trasa (pokazana na rys. 6) ogranicza skręcanie do kierunku ujemnego, podczas gdy obecny kierunek jest dodatni. Zachód jest uważany za kierunek ujemny w wymiarze X, a południe jest uważany za kierunek ujemny w wymiarze Y. Oznacza to, że każdy skok w jednym z ujemnych kierunków powinien zostać wykonany przed wykonaniem jakiegokolwiek innego skrętu.
Zalety wyznaczania tras z ograniczeniami skrętu
- Unikanie zakleszczeń jest tańsze w implementacji niż techniki wykrywania i łamania zakleszczeń.
- Ograniczenia skrętu zapewniają alternatywne ścieżki o minimalnej długości , jak również ścieżki o nieminimalnej długości z jednego węzła do drugiego, co umożliwia wyznaczanie tras wokół przeciążonych lub uszkodzonych łączy.
Weźmy na przykład rysunek 7 poniżej. Załóżmy, że istnieje wiele routerów, F1, F2 itd., które dostarczają pakiety do przeciążonego, ale taniego łącza z routera źródłowego S do routera docelowego D. Implementacja routingu z ograniczeniem skrętu oznacza, że niektóre skręty z dowolnego routera zasilającego do przeciążony router S może być teraz ograniczony. Te routery zasilające mogą być zmuszone do korzystania z dłuższej ścieżki, aby dostać się do miejsca docelowego D, odciążając w ten sposób łącze z S do D do pewnego stopnia.
