RUNES
Reconfigurable Ubiquitous Networked Embedded Systems

RUNES patner UCL demonstrated a new routing algorithm for Delay Tolerant Networks in Budapest on the 8th of June 2006. The goal of this routing algorithm is to restrict the network load while guaranteeing delivery of messages to the destination with a high probability. The algorithm is based upon the concept of Delay Tolerant Networking (DTN), ie. tries to route messages within the network when there is no an end-to-end path available between the source and the destination of the message. For this purpose, messages are stored locally at every DTN router when they are received by the router. Then, a particular router holding the message, will forward a copy of the message to a "next-hop" router when there is connectivity between the two routers. Connectivity between routers will eventually occur, as DTN routers move within the network environment.

In contrast to Epidemic protocols, the RUNES DTN routing algorithm does not forward a copy the message to each member of the "next-hop" routers neighbourhood (ie. to all routers it finds it has connectivity), but selects the best canditates of "next-hop" routers, based on the position of the "next-hop" routers in the network topology. Thus, if a "next-hop" router is far from the destination (in number of hops), it is considered as a "bad candidate" for delivering the message to the destination and another(s) "next-hop" router(s) with a smaller number of hops to the destination will get the copy of the message. The calculation of the distances in terms of numbers of hops to the destination is done at runtime, as routing tables are dynamically exchanged and updated when two individual DTN routers meet.

Apart from constraining the replication of messages based on the distance of the "next-hop" router to the destination (ie. destination-based routing), the RUNES DTN routing algorithm implements a source-based routing functionallity at the same time. This means that the distance in number of hops between the source of the message and the current router holding the message is taken into consideration. This is done for the following purpose. If a router gets a copy of the message and no "next-hop" routers are found due to lack of connectivity, then the router can drop the message if it sees that it is far away from the source of the message. Dropping the message is a good policy to restrirct use of unnessacary copies, as this router is not likely to deliver the message, as no "next-hop" router is available to deliver the message. However, if the distance of the message from the source is small, then the router should anyway keep the copy of the message, since there are not many replicas of the message within the network (ie. the message has not travelled a lot within the network). More information on the technical aspects of the RUNES DTN routing algorithm can be found in deliverable D4.3.

DTN routing algorithm demonstrator setup.

The demo in Budapest showed use of the algorithm in the sensors domain, where sensors are running the Contiki OS. The routing algorithm was implemented as a module of the Contiki kernel. Assume that the source S generated a message destined to D and no connectivity exists between any sensor in the domain. Node A then moves within the radio coverage of node S and gets a copy the message. Then, A moves towards node B and finally meets B, but B does not get a copy from A, as B's distance from D is infinite (B never meets D as they are not connected by any path). Then, A starts moving towards D. When A meets S again, S does not get a copy of the message as A knows that S has already a copy of the message. However, when A finally meets D, A delivers the message to D, D being the destination of the message.

The demo showed how the DTN technology works in scenarios where sensor nodes are often disconnected and also how the RUNES DTN routing algorithm can restrict forwarding of messages to paths that are not likely to deliver the message to the destination (the path starting from Node B in the demo). This is the goal of the RUNES DTN routing algorithm: To restrict the number of replicas is an network (and thus the network load), still guaranteeing delivery of messages to the destination with a high probability.

For further information contact Dr Leonidas Lymberopoulos.