Temporally-Ordered Routing Algorithm

The Temporally Ordered Routing algorithm presented by Park and Corson in Park1997 belongs to the family of link reversal routing algorithms. It is based on the ideas of the GB and LMR algorithms. It uses Query and Reply packets as in LMR but combines this with the notion of height as in the GB partial reversal algorithm. The main enhancement comes from the introduction of a time value which stores the time since a link failure.

TORA also maintains a DAG by means of an ordered quintuple with the following information:

• t time of a link failure
• oid originator id
• r reflection bit indicates 0=original level 1=reflected level
• d integer to order nodes relative to reference level
• i the nodes id

The triplet (t,oid,r) is called the reference level. And the tuple (d,i) is said to be an offset within that reference level.

As with the GB algorithms the heights of the nodes for a given destination to each other determine the direction of the edges of the directed acyclic graph. The DAG is destination oriented (routed at the destination) when the quintuples which represent the heights are maintained in lexicographical order, the destination having the smallest height, traffic always flowing downstreams. Heights are however not needed for route discovery, instead a mechanism as in LMR is used. Also nodes which do not currently need to maintain a route for themselves or for others won't change a height value. Each node has a Route-required flag for that purpose, additionnally the time since the las UPD (update-) packet was sent is recorded.

Each node maintains a neigbour 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).

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 seeked 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 destinationm, 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.
• if a node has at least one downstream neighbour and the height for that link is null it sets its height to the minimum of the heights of the neighbour nodes, increments its d value by one and broadcasts an UPD packet.
• if the node has a downstream link and its height is non-NULL it discards the QRY packet if an UPD packet was being issued since the link became active (rr-Flag set). Otherewise it sends an UPD packet.

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.

This is best shown by an example from the original paper. Park1997

Circles in the pictures below signify that the RR flag is set

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:

• 1 Generate: The node has lost its last downstream link due to a failure. The node defines a new "reference level", so it sets oid (originator id) to its node id and t to the time of the failure. This is done only if the node has upstream neighbours. If not it sets its height to NULL.
• 2 Propagate: The node has no more downstream link due to a link reversal following the receipt of an update packet and the reference levels (t,oid,r) of its neighbours are not equal. The node then propagates the references level of its highest neighbour and sets the offset to a value which is lower (-1) than the offset of all its neighbours with the maximum level.
• 3 Reflect: The node has lost its downstream links due to a link reversal following the receipt of an update packet and the reference heights of the neighbours of the node are equal with the reflection bit not set. The node then reflects back the refence height by setting the reflection bit. It's d value is set to 0.
• 4 Detect: The node has lost its downstream links due to a link reversal following the receipt of an update packet and the reference heights of the neighbours of the node are equal with the reflection bit set. This means that the node has detected a partition and begins the route erasure procedure. The height values are set to NULL.
• 5 Generate: The node has lost its last downstream link due to a link reversal following the receipt of an update packet and the reference haights of all the neighbours are equal with the reflection bit set and the oid of the neighbours heights isn't the node's id. The node then sets t to the time of the link failure and sets oid to its own id. The d value is set to 0. This means that the link failure required no reaction. The node experienced a link failure between the time it propagated a higher reference (from someone else) and the time this level got reflected from a place further away in the network. Because the node didn't define the new reference level itself this is not necessarily an indication of a partitioning of the network. So the node simply defines a new higher reference level with the time of the link failure.

Example

The link between B and E fails

B still has a downstream link to the destination, so no action is needed

The link between D and H fails

Node D defines a new reference level. It sets the originator id to his own id since it was node D that defined the new level. The logical time of the link failure is also recorded (t=1). The new reference level is now higher than that of the neighbours, so the update message has as effect the reversal of the links to A and B. This is case 1 of the decision tree.

Node B has lost its downstream not because of a link failure, but because of a link reversal. It propagates the reference level that was defined by D. Because the node must have a lower height than the upstream node D it has to set it's subheight (offset) lower than that of D, so d=-1. This is case 2 of the decision tree.

Node A has now also has lost its last downstream due to an update and propagates the reference level and sets its d to the lowest of its neighbours -1. (also Case 2)


partition detection and route erasure

(the graphics below where copied from a presentation of TORA by Jeff Dobbelaere, Wireless & Mobile Systems Working Group at the College of William and Mary, Williamsburg VA, USA http://www.cs.wm.edu/~kearns/swg97/tora.pdf)


Here the link F to G fails, partitioning G from the rest of the network

F defines a new reference level and sends an update message with oid=F and the time of the link failure

The 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.

Now node B reflects the reference level, because all of its neighbours have the same reference height and their reflection bits are not set. The offset (d) is set to 0 to make node B now be higher than its neighbours and the reflection bit is set.

The links are now reversed in the opposite direction, but the reflection bit is set.



when node D propagates the reference level the reference heights of the neighbours of F are equal, but the reflection bit is set. F has detected a partition and sets its height to NULL indicating that the route to the destination no longer exists. The route erase protocol is triggered.

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).

Conclusion

Partioning of the network is detected in 2 passes of the algorithm for the affected nodes. Route erasure takes three passes. Compared with LMR which takes an uncertain amount of time for erasing invalid routes due to false replies, TORA converges in exactly three passes of the affected nodes. TORA is thus a rather reliable algorithm for mobile networks. If the network gets big and the mobility is high, the message overhead for the link reversals having to be propagated through the network can get rather important. TORA assumes that there is a synchronised clock for all the nodes to record the time of link failures. Such a source could be obtained for example by a GPS receiver. It is however not mandatory that such a clock must exist if nodes have a local clock and they adjust it to be always at least higher or equal than the neighbours time they discover when a link failure occurs. At the worst case the result of a link failure would be that there will only be a partial reversal of the links at the moment of the link failure, but the algorithm would work despite of this with some more messages that has to be exchanged.