Temporally-Ordered Routing Algorithm - Essay Example

Temporally-Ordered Routing Algorithm (TORA) The Temporally-Ordered Routing Algorithm (TORA) is an algorithm for routing data across Wireless Mesh Networks or Mobile ad-hoc networks (MANET). It was developed by Vincent Park at the University of Maryland, College Park and the Naval Research Laboratory. Park has patented his work, and owns Nova Engineering, who are marketing a wireless router product based on Parks algorithm. (Wikipedia, 2005, para.1-2) Park and Corson (1997, p.1) name the TORA protocol as one of a family of protocols which they term "link reversal" algorithms. The protocol's reaction is structured as a temporally-ordered sequence of diffusing computations; each computation consisting of a sequence of directed link reversals. The protocol is highly adaptive, efficient and scalable; being best-suited for use in large, dense, mobile networks. In these networks, the protocol's reaction to link failures typically involves only a localized "single pass" of the distributed algorithm. This capability is unique among protocols which are stable in the face of network partitions, and results in the protocol's high degree of adaptivity . This desirable behavior is achieved through the novel use of a "physical or logical clock" to establish the "temporal order" of topological change events which is used to structure (or order) the algorithm's reaction to topological changes. (Park and Corson, 1997, p.1) Introduction The basic, underlying algorithm is neither distance-vector nor link-state; it is a member of a class referred to as link-reversal algorithms. The protocol builds a loop-free, multipath routing structure that is used as the basis for forwarding traffic to a given destination. The protocol can simultaneously support both source-initiated, on-demand routing for some destinations and destination-initiated, proactive routing for other destinations. (Lundberg, 2002) Park and Corson (1997, p.2) think that a routing algorithm is well-suited for operation in dynamical environment when it possess the following properties: Executes distributedly Provides loop-free routes Provides multiple routes (to alleviate congestion) Establishes routes quickly (so they may be used before the topology changes) Minimizes communication overhead by localizing algorithmic reaction to topological changes when possible (to conserve available bandwidth and increase scalability) Routing optimality (i.e. determination of the shortest path) is less important for the TORA algorithm. Also it is assumed that it's not necessary (nor desirable) to maintain routes between every source/destination pair at all times. The overhead expended to establish a route between a given source/destination pair will be wasted if the source does not require the route prior to its invalidation due to topological changes. The TORA protocol is designed to minimize reaction to topological changes. A key concept in its design is that it decouples the generation of potentially far-reaching control message propagation from the rate of topological changes. Such messaging is typically localized to a very small set of nodes near the change without having to resort to a dynamic, hierarchical routing solution with its attendant complexity. (Park and Corson, 1997, p.2) The basic idea is as follows. When a node loses its last downstream link (i.e. becomes a local minimum) as a result of a link failure, the node selects a new height such that it becomes a global maximum by defining a new "reference level". By design, when a new reference level is defined, it is higher than any previously defined reference level. (Park and Corson, 1997, p.4) Detailed Description 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 Directed Acyclic Graph (DAG) by means of an ordered quintuple associated with each node 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 (RR) flag for that purpose, additionally the time since the last UPD (update-) packet was sent is recorded. Each node i maintains its height, Hi. 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 neighbor is (0,0,0,0,dest). (University of Luxembourg, SECAN-Lab, 2004-2005, para.1-5) Also each node maintains a link-state array with an entry LiSi for each link (i, j). if a neighbor j is higher than node i, the link is marked upstream (UP). If a neighbor j is lower than node i, the link is marked downstream (DN). If the neighbors height entry is NULL, the link is marked undirected. (Park and Corson, 1997, p.4) No two nodes may have the same height (i.e. the set of heights is totally-ordered). Information may flow from nodes with higher heights to nodes with lower heights. Conceptually, information can be thought of as a fluid that may only flow downhill. By maintaining a set of totally-ordered heights at all times, it is easy to see how loop-free, multipath routing is assured. Information would have to flow uphill to form a loop, and this is not permitted. (Institute for Systems Research, 2005, para. 4) 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. (Wikipedia, 2005, para. 3) TORA accomplishes three functions through use of control packets: Route creation (QRY) that is used for creating routes Route maintenance (UPD) that is used for both creating and maintaining routes Route erasure (CLR) that is used for erasing routes Route Creation A node which requires a link to a destination because it has no downstream neighbors 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 neighbor 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. if a node has at least one downstream neighbor and the height for that link is null it sets its height to the minimum of the heights of the neighbor 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). Otherwise it sends an UPD packet. A node receiving an update packet updates the height value of its neighbor in the table and takes one of the following actions: if the reflection bit of the neighbors height is not set and its route required flag is set it sets its height for the destination to that of its neighbors but increments d by one. It then deletes the RR flag and sends an UPD message to the neighbors, so they may route through it. if the neighbors 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 neighbors node in its table. This is best shown by an example from the original paper (Park and Corson, 1997, cited in University of Luxembourg, SECAN-Lab, 2004-2005, para.9) 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: There are five cases: Case 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 neighbors. If not it sets its height to NULL. Case 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 neighbors are not equal. The node then propagates the references level of its highest neighbor and sets the offset to a value, which is lower (-1) than the offset of all its neighbors with the maximum level. Case 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 neighbors of the node are equal with the reflection bit not set. The node then reflects back the reference height by setting the reflection bit. It's d value is set to 0. Case 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 neighbors 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. Case 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 heights of all the neighbors are equal with the reflection bit set and the oid of the neighbors 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. (Park and Corson, 1997, cited in University of Luxembourg, SECAN-Lab, 2004-2005, para.10-19) Route Erasure When a node has detected a partition it sets its height and the heights of all its neighbors 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 neighbors 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 neighbors its table matching the reflected reference level to NULL and updates their link status into undirected. (University of Luxembourg, SECAN-Lab, 2004-2005, para.10-19) Performance Park and Corson (1997, p.8) present a comparative summary of worst-case protocol complexities, augmented with a discussion of basic operation of several major protocol classes. The complexities of TORA, along with an Ideal Link-state (ILS) algorithm, the DUAL family of algorithms and DSDV protocol are shown in Table 1. Table 1. Complexity Comparison (Park and Corson, 1997, p.8) Protocol Time Complexity Communication Complexity ILS O(d) O(2|L|) DUAL (link failure, cost increase) O(x) O(6Dx) DUAL (link addition, cost decrease) O(d) O(L) DSDV (link failure) O(x) O(Dx) DSDV (periodic update) O(l) O(|L|) TORA (connected, postfailure) O(2l) O(2Dx) TORA (disconnected, postfailure) O(3l) O(3Dx) The comparison shows that TORA's worst case complexity is generally better then the algorithms to which it is most closely related. In many cases TORA would actually require only a single pass with Time Complexity O(l) and Communication Complexity O(Dx) to react to a link failure, further improving its performance. Additionally it has no explicit reaction to link additions further reducing its complexity. (Park and Corson, 1997, p.8) By the study of Cano and Manzoni (2000) cited in Aaron and Weng (2000-2001, p.3) TORA has very high consumption due to its aggregated messages for route discovery and maintenance. The study however, did not look into the effect of the protocol of the node deaths and its impact on the overall data transfer of the system. The study has shown the worst results of TORA in comparison with DSDV, AODV and DSR for network with node energy constraints. By the study of Liu (2002), TORA performs worst in the group of the protocols TORA, DSDV, AODV and DSR. DSR performs very well at all mobility rates and movement speeds. DSR performs very well in less stressful situations, such as smaller number of nodes or lower load/mobility. AODV performs as well as DSR at mobility rates and movement speeds. AODV performs better than DSR in more stressful situations. DSR generates less routing load than AODV. DSDV is predictable when node movement rates and movement speeds are low. Liu brings comparison between the four protocol of the fraction of application data packets successfully delivered (packet delivery ratio) as a function of pause time. The study of Liu (2002) displayed that DSR has least overhead, TORA has most in comparison between the four protocol of the number of routing packets sent (routing overhead) as a function of pause time. As TORA is able to localize its reaction to topological changes, it is best suited for relatively dense networks, only several nearby nodes involved in a reaction. Its effect of localization produces increase of scalability, but for relatively small networks (up to 50 nodes). (Liu, 2002) Conclusion The Temporally-Ordered Routing Algorithm (TORA) is highly adaptive distributed routing algorithm suitable for operation in mobile wireless networks. TORA can quickly create and maintain loop-free multipath routing to destinations for which routing is required with minimal communication overhead. It adapts to topological changes well and has an ability to detect network partitions and erase all invalid routes within limited time. As Buruhanudeen (2002, para. 11) writes, TORA has a number of advantages: it provides loop free paths at all instants, multiple routes so that if one path is not available, other is readily available. It also establishes routes quickly so that they may be used before the topology changes. TORA minimize algorithmic reactions/communication overhead and thus conserves available bandwidth and increases adaptability and is able to detect network partitions very quickly. Nevertheless Buruhanudeen (2002, para. 11) mentions that it has some drawbacks: since it uses internodal co-ordination it exhibits instability behavior similar to "count-to-infinity" problem in distance vector routing protocols. There is a potential for oscillations to occur, especially when multiple sets of coordinating nodes are concurrently detecting partitions, erasing routes, and building new routes based on each other. Though such oscillations are temporary and route convergence will ultimately occur. TORA displayed the worst packet delivery ratio and routing overhead in the group of the protocols TORA, DSDV, AODV and DSR. DSR displayed the best results at packet delivery ratio and routing overhead. However, TORA has a potential for small and relatively dense networks. References Aaron, A. and Weng, Jie. (2000-2001). Performance Comparison of Ad-hoc Routing Protocols for Network with Node Energy Constraints. Retrieved December 10, 2005, from http://www.stanford.edu/amaaron/ee360/EE360_FINAL_PAPER.pdf Buruhanudeen, S. (2002). Overview of Ad Hoc Routing Protocols. Retrieved December 10, 2005, from http://www.comp.brad.ac.uk/sburuha1/routingprot.htm Liu, J. (2002) Ad-hoc Routing Schemes. Retrieved December 10, 2005, from http://www.thefengs.com/wuchang/work/courses/cse581_winter2002/summaries/13/ Lundberg, D. (2002). Temporally-Ordered Routing Algorithm protocol (TORA). Retrieved December 10, 2005, from http://www.update.uu.se/davidl/msthesis/html/node8.html#SECTION000829000000000000000 Park, V. D. and Corson, M. S. (1997). A highly adaptive distributed routing algorithm for mobile wireless networks. Retrieved December 10, 2005, from http://cs-www.cs.yale.edu/homes/arvind/cs425/doc/tora.pdf Temporally-ordered routing algorithm. (2005) Retrieved December 10, 2005, from Wikipedia Website: http://en.wikipedia.org/wiki/Temporally-ordered_routing_algorithm Temporally-ordered routing algorithm. (2005). Retrieved December 10, 2005, from Institute for Systems Research of the University of Maryland Website: http://www.isr.umd.edu/ISR/accomplishments/037_Routing/ Temporally-Ordered Routing Algorithm (2004-2005). Retrieved December 10, 2005, from University of Luxembourg, SECAN-Lab Website: http://wiki.uni.lu/secan-lab/Temporally-Ordered+Routing+Algorithm.html Read More