Supervisor: Kaisa Sere

5.2 Introduction to TRP

TRP defines the network as a tree or a collection of trees that have developed independently, and which can be joined together at later time by so-called interlinks. An interlink connects two nodes that find that they do not belong to the same tree. A root is a node that booted and did not find other nodes in its vicinity. When a node finds that it is in the vicinity of other nodes, belonging to a tree, it will join this tree by associating itself with a node that has a route that contains the fewest hops (shallowest) to the root. This is possible because every node keeps track of the level it is on and informs the new node about this in a hello message. The shallowest neighbor of the new node will form its preferred link towards the root. Every node sends local information to its preferred neighbor whenever it changes in an update message. The local information that a node sends contains a list of the node’s neighbors, itself and the lists that was received from its children. As this is done in every child-parent relationship, it will result in dissemination of information in a controlled way and every subroot of every subtree knows which nodes belong to its subtree. Therefore, the root’s routing table contains routes (knows next-hops) to every node and can calculate which nodes have interlinks to other trees. To clarify this, there is a distinct loop-free path from every leaf to the root through which periodic updates are sent and the updates accumulate at every level of the tree as nodes add themselves to the list. In this way a partial routing table will be set up at every node in the form of a tree in which every subroot knows which nodes belong to its subtree. This tree of preferred links is needed in the attempt to prohibit network-wide searches when a node needs to be found by using a "divide-and conquer" method. Since every node (subroot or root) knows which nodes are located in its subtree, it can deduce that a route query does not have to be forwarded to any particular branch in the subtree at all. In the case that there is a extra- or interlink in a forwarding subroot’s subtree then the path to the node with the link can be found and forwarded to. Every "up cast" (towards the root) of a message, containing a route query will increase the probability that a grandparent will have a route to the destination node, and is able to answer the query.

A route query message (RQM) is a message that indicates a query of route from the initiator (source) of the query to a destination node. RQMs are sent to the preferred neighbor but also through extralinks, interlinks and to branches that contain extralinks or interlinks. The extralinks are so-called because they have to be omitted when the network topology is viewed as a tree, in order to set the paths for the updates to travel (see figure 5-1). It is then this tree view that forms the basis for the divide-and-conquer scheme which can be used in forwarding decisions. The extralinks are links to neighbors that are not preferred. This must not be understood that the extralinks would be dropped altogether. They are still used to forward data messages and route queries because otherwise discovery of shortest path could not be guaranteed. Therefore the tree structure can be taken advantage of in certain situations.
TRP uses a semi proactive (table driven), semi reactive (on-demand) approach. It is proactive because of the updates that are sent whenever a change in the routing table occurs (i.e. a node receives a new update or a link is broken to a neighbor). On the other hand if a node demands a route to a non-(grand) child the protocol will have to react with the discovery process and issue a discovery control message. A fundamental idea in TRP is that every network can be seen as a graph or as a tree if strategically chosen extralinks are disabled in certain situations.

Fig. 5 15: Views of the network.