Algorytm routingu uporządkowany czasowo
Temporally Ordered Routing Algorithm ( TORA ) jest algorytmem trasowania danych w bezprzewodowych sieciach kratowych lub mobilnych sieciach ad hoc .
Został opracowany przez Vincenta Parka i Scotta Corsona z University of Maryland i Naval Research Laboratory . Park opatentował swoją pracę i uzyskał licencję od Nova Engineering, która sprzedaje router bezprzewodowy oparty na algorytmie Parka.
Operacja
TORA próbuje osiągnąć wysoki stopień skalowalności przy użyciu „płaskiego”, niehierarchicznego algorytmu routingu. Algorytm w swoim działaniu stara się w jak największym stopniu stłumić generowanie dalekosiężnej propagacji komunikatu sterującego. Aby to osiągnąć, TORA nie stosuje najkrótszej ścieżki , co jest podejściem nietypowym dla algorytmów trasowania tego typu.
TORA buduje i utrzymuje skierowany graf acykliczny (DAG) zakorzeniony w miejscu docelowym. Żadne dwa węzły nie mogą mieć tej samej wysokości.
Informacje mogą przepływać z węzłów o wyższych wysokościach do węzłów o niższych wysokościach. Informacje można zatem traktować jako płyn, który może płynąć tylko w dół. Utrzymując zestaw całkowicie uporządkowanych wysokości przez cały czas, TORA osiąga bezpętlowe trasowanie wielościeżkowe, ponieważ informacje nie mogą „płynąć pod górę”, a więc wracać do siebie.
Kluczową koncepcją projektową TORA jest lokalizacja komunikatów sterujących w bardzo małym zestawie węzłów w pobliżu wystąpienia zmiany topologicznej. Aby to osiągnąć, węzły muszą przechowywać informacje o routingu dotyczące sąsiednich (jeden przeskok) węzłów. Protokół spełnia trzy podstawowe funkcje:
- Tworzenie tras
- Utrzymanie trasy
- Wymazanie trasy
Podczas faz tworzenia i utrzymywania tras węzły używają metryki wysokości do ustanowienia ukierunkowanego grafu acyklicznego (DAG) zakorzenionego w miejscu docelowym. Następnie łącza są przypisywane na podstawie metryki względnej wysokości sąsiednich węzłów. W okresach mobilności DAG jest zepsuty, a jednostka obsługi trasy pojawia się, aby przywrócić trasę DAG do miejsca docelowego.
Czas jest ważnym czynnikiem dla TORA, ponieważ metryka wysokości zależy od logicznego czasu awarii łącza.
Faza wymazywania tras TORA polega zasadniczo na rozsyłaniu przez sieć pakietu Clear Broadcast (CLR) w celu wymazania nieprawidłowych tras
Tworzenie tras
Węzeł, który wymaga łącza do miejsca docelowego, ponieważ nie ma sąsiadów w dół, wysyła pakiet QRY (zapytanie) i ustawia swoją (wcześniej nieustawioną) flagę wymaganej trasy. Pakiet QRY zawiera identyfikator miejsca docelowego węzła, do którego poszukiwana jest trasa. Odpowiedź na zapytanie jest nazywana aktualizacją pakietu UPD. Zawiera pięciokrotność wysokości sąsiedniego węzła odpowiadającego na zapytanie oraz pole docelowe, które mówi, dla którego miejsca docelowego była przeznaczona aktualizacja. Węzeł odbierający pakiet QRY wykonuje jedną z następujących czynności:
- Jeśli jego flaga wymaganej trasy jest ustawiona, oznacza to, że nie musi przekazywać QRY, ponieważ sam już wystawił QRY dla miejsca docelowego, ale lepiej go odrzucić, aby uniknąć narzutu wiadomości.
- Jeśli węzeł nie ma łączy downstream, a flaga wymaganej trasy nie została ustawiona, ustawia swoją flagę wymaganej trasy i retransmituje komunikat QRY.
Węzeł otrzymujący pakiet aktualizacyjny aktualizuje w tabeli wartość wysokości swojego sąsiada i wykonuje jedną z następujących akcji:
- Jeśli bit odbicia wysokości sąsiadów nie jest ustawiony, a jego flaga wymaganej trasy jest ustawiona, ustawia swoją wysokość dla miejsca docelowego na wysokość swoich sąsiadów, ale zwiększa d o jeden. Następnie usuwa flagę RR i wysyła wiadomość UPD do sąsiadów, aby mogli przez nią przejść.
- Jeśli trasa sąsiadów jest nieprawidłowa (co wskazuje bit odbicia) lub flaga RR nie była ustawiona, węzeł aktualizuje tylko wpis węzła sąsiadów w swojej tablicy.
Każdy węzeł utrzymuje tablicę sąsiadów zawierającą wysokość sąsiednich węzłów. Początkowo wysokość wszystkich węzłów wynosi NULL. (To nie jest zero „0”, ale NULL „-”), więc ich pięciokrotność to (-,-,-,-,i). Wysokość docelowego sąsiada to (0,0,0,0,dest).
Węzeł C wymaga trasy, więc rozgłasza QRY.
QRY propaguje się, dopóki nie trafi w węzeł, który ma trasę do miejsca docelowego, następnie ten węzeł wysyła komunikat UPD.
UPD jest również propagowane, podczas gdy węzeł E wysyła nowy UPD.
Utrzymanie Trasy
Utrzymanie trasy w TORA ma pięć różnych przypadków zgodnie z poniższym schematem blokowym:
Przykład
B nadal ma łącze podrzędne do miejsca docelowego, więc nie jest wymagane żadne działanie
wykrywanie partycji i usuwanie tras
łączy DF i EF na odwrót. Węzeł D propaguje poziom odniesienia.
Węzeł E „odzwierciedla” teraz poziom odniesienia. Wysokości odniesienia sąsiadów są równe nieustawionemu bitowi odbicia. E ustawia bit odbicia, aby wskazać odbicie i ustawia jego przesunięcie na 0. Węzeł C po prostu propaguje nowy poziom odniesienia.
Węzeł A propaguje teraz poziom odniesienia.
Wymazywanie trasy
Gdy węzeł wykryje partycję, ustawia swoją wysokość i wysokości wszystkich swoich sąsiadów dla miejsca docelowego w swojej tablicy na NULL i wysyła pakiet CLR (Clear). Pakiet CLR składa się z odbitego poziomu odniesienia (t,oid,1) i identyfikatora miejsca docelowego.
Jeśli węzeł odbierze pakiet CLR, a poziom odniesienia odpowiada jego własnemu poziomowi odniesienia, ustawia wszystkie wysokości sąsiadów i swój własny dla miejsca docelowego na NULL i rozgłasza pakiet CLR. Jeśli poziom odniesienia nie pasuje do własnego, po prostu ustawia wysokości sąsiadów, jego tabelę pasującą do odbitego poziomu odniesienia na NULL i aktualizuje stan ich łącza