Content deleted Content added
m missing punct. |
Link suggestions feature: 2 links added. Tags: Visual edit Mobile edit Mobile web edit Newcomer task Suggested: add links |
||
| (17 intermediate revisions by 13 users not shown) | |||
Line 1:
{{Short description|Routing algorithm}}
{{
The '''Temporally Ordered Routing Algorithm''' ('''TORA''') is an [[algorithm]] for [[routing]] data across [[Wireless mesh network|Wireless Mesh Networks]] or [[Mobile ad hoc network]]s.<ref name="I.2012">{{cite book|author=Lakhtaria, Kamaljit I.|title=Technological Advancements and Applications in Mobile Ad-Hoc Networks: Research Trends: Research Trends|url=https://books.google.com/books?id=6aGeBQAAQBAJ&q=%22Temporally+ordered+routing+algorithm%22|date=31 March 2012|publisher=IGI Global|isbn=978-1-4666-0322-6}}</ref>
It was developed by [[Vincent Park]] and Scott Corson at the [[University of Maryland, College Park|University of Maryland]] and the [[Naval Research Laboratory]]. Park has patented his work, and it was licensed by [[Nova Engineering]], who are marketing a [[wireless]] [[Router (computing)|router]] product based on Park's algorithm.
Line 9 ⟶ 10:
TORA builds and maintains a [[Directed acyclic graph|Directed Acyclic Graph]] (DAG) rooted at a destination. No two nodes may have the same height.
[[Information]] may flow from nodes with higher heights to nodes with lower heights. Information can therefore be thought of as a fluid that may only flow downhill. By maintaining a set of totally ordered heights at all times, TORA achieves loop-free [[multipath routing]], as information cannot 'flow uphill' and so cross back on itself.
The key design concepts of TORA is localization of control messages to a very small set of nodes near the occurrence of a topological change. To accomplish this, nodes need to maintain the routing information about adjacent (one hop) nodes. The protocol performs three basic functions:
Line 17 ⟶ 18:
During the route creation and maintenance phases, nodes use a height metric to establish a directed acyclic graph (DAG) rooted at destination. Thereafter links are assigned based on the relative height metric of neighboring nodes. During the times of mobility the DAG is broken and the route maintenance unit comes into picture to reestablish a DAG routed at the destination.
Timing is an important factor for TORA because the height metric is dependent on the logical time of the link failure. TORA's route erasure phase is essentially involving flooding a broadcast clear packet (CLR) throughout the network to erase invalid routes.
===Route creation===
Line 26 ⟶ 25:
* If its route required flag is set, this means that it doesn't have to forward the QRY, because it has itself already issued a QRY for the destination, but better discard it to prevent message overhead.
* If the node has no downstream links and the route-required flag was not set, it sets its route-required flag and rebroadcasts the QRY message.
A
* If the reflection bit of the neighbours height is not set and its route required flag is set it sets its height for the destination to that of its neighbours but increments d by one. It then deletes the RR flag and sends an UPD message to the neighbours, so they may route through it.
* If the neighbours route is not valid (which is indicated by the reflection bit) or the RR flag was unset, the node only updates the entry of the neighbours node in its table.
Line 38 ⟶ 37:
===Route Maintenance===
Route maintenance in TORA has five different cases according to the [[flowchart]] below as an example:
''Partition Detection and Route Erasure''
# The links between Nodes D-F and E-F reverse.
# Node E
# Node A propagates the reference level.
▲he links D-F and E-F reverse. Node D propagates the reference level.
▲Node E now "reflects" the reference level. The reference heights of the neighbours are equal with the reflection bit not set. E sets the reflection bit to indicate the reflection and sets its offset to 0. Node C just propagates the new reference level.
▲Node A now propagates the reference level.
===Route Erasure===
Line 58 ⟶ 51:
When a node has detected a partition it sets its height and the heights of all its neighbours for the destination in its table to NULL and it issues a CLR (Clear) packet. The CLR packet consists of the reflected reference level (t,oid,1) and the destination id.
If a node receives a CLR packet and the reference level matches its own reference level it sets all heights of the neighbours and its own for the destination to NULL and broadcasts the CLR packet. If the reference level doesn't match its own it just sets the heights of the neighbours its table matching the reflected reference level to NULL and updates their link status
==References==
{{Reflist}}
==External links==
*[
*[https://archive.today/20130416233218/http://modis.ispras.ru/wikipedia/pic/Ad_hoc_routing_protocol_list.html MODIS Group Management of Data and Information Systems]
[[Category:Routing algorithms]]
| |||