Temporally-ordered routing algorithm
Encyclopedia
The Temporally-Ordered Routing Algorithm (TORA) is an algorithm
for routing
data across Wireless Mesh Networks
or Mobile ad-hoc networks.
It was developed by Vincent Park at the 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 product based on Parks algorithm.
using a "flat", non-hierarchical routing algorithm. In its operation the algorithm attempts to suppress, to the greatest extent possible, the generation of far-reaching control message propagation. In order to achieve this, the TORA does not use a shortest path
solution, an approach which is unusual for routing algorithms of this type.
TORA builds and maintains a Directed Acyclic Graph
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:
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
A node which requires a link to a destination because it has no downstream neighbours for it sends a QRY (query) packet and sets its (formerly unset) route-required flag. A QRY packet contains the destination id of the node a route is sought to. The reply to a query is called an update UPD packet. It contains the height quintuple of the neighbour node answering to a query and the destination field which tells for which destination the update was meant for.
A node receiving a QRY packet does one of the following:
A node receiving an update packet updates the height value of its neighbour in the table and takes one of the following actions:
Each node maintains a neighbour table containing the height of the neighbour nodes. Initially the height of all the nodes is NULL. (This is not zero "0" but NULL "-") so their quintuple is (-,-,-,-,i). The height of a destination neighbour is (0,0,0,0,dest).
node C requires a route, so it broadcasts a QRY
The QRY propagates until it hits a node which has a route to the destination, this node then sends an UPD message
The UPD is also propagated, while node E sends a new UPD.
Route Maintenance
Route maintenance in TORA has five different cases according to the flowchart below:
Example
B still has a downstream link to the destination, so no action is needed
partition detection and route erasure
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 refléection 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
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 (->undirected).
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for routing
Routing
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
data across Wireless Mesh Networks
Wireless mesh network
A wireless mesh network is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways.The mesh clients are often laptops, cell phones and other wireless devices while the mesh routers forward traffic...
or Mobile ad-hoc networks.
It was developed by Vincent Park at the University of Maryland
University of Maryland, College Park
The University of Maryland, College Park is a top-ranked public research university located in the city of College Park in Prince George's County, Maryland, just outside Washington, D.C...
and the Naval Research Laboratory. Park has patented his work, and it was licensed by Nova Engineering, who are marketing a wireless
Wireless
Wireless telecommunications is the transfer of information between two or more points that are not physically connected. Distances can be short, such as a few meters for television remote control, or as far as thousands or even millions of kilometers for deep-space radio communications...
router product based on Parks algorithm.
Operation
The TORA attempts to achieve a high degree of scalabilityScalability
In electronics scalability is the ability of a system, network, or process, to handle growing amount of work in a graceful manner or its ability to be enlarged to accommodate that growth...
using a "flat", non-hierarchical routing algorithm. In its operation the algorithm attempts to suppress, to the greatest extent possible, the generation of far-reaching control message propagation. In order to achieve this, the TORA does not use a shortest path
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
solution, an approach which is unusual for routing algorithms of this type.
TORA builds and maintains a Directed Acyclic Graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
rooted at a destination. No two nodes may have the same height.
Information
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...
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:
- Route creation
- Route maintenance
- Route erasure
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
A node which requires a link to a destination because it has no downstream neighbours for it sends a QRY (query) packet and sets its (formerly unset) route-required flag. A QRY packet contains the destination id of the node a route is sought to. The reply to a query is called an update UPD packet. It contains the height quintuple of the neighbour node answering to a query and the destination field which tells for which destination the update was meant for.
A node receiving a QRY packet does one of the following:
- 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 node receiving an update packet updates the height value of its neighbour in the table and takes one of the following actions:
- 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.
Each node maintains a neighbour table containing the height of the neighbour nodes. Initially the height of all the nodes is NULL. (This is not zero "0" but NULL "-") so their quintuple is (-,-,-,-,i). The height of a destination neighbour is (0,0,0,0,dest).
node C requires a route, so it broadcasts a QRY
The QRY propagates until it hits a node which has a route to the destination, this node then sends an UPD message
The UPD is also propagated, while node E sends a new UPD.
Route Maintenance
Route maintenance in TORA has five different cases according to the flowchart below:
Example
B still has a downstream link to the destination, so no action is needed
partition detection and route erasure
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 refléection 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
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 (->undirected).