[Tinyos-devel] Multihop routing framework

[Philip Levis]

On Mar 12, 2007, at 12:00 PM, Romain Thouvenin wrote:

> Hello devel,
>
> This follows a discussion begun on tinyos-help about having a
> multihop routing framework on TinyOS 2.0, I hope I post on the right
> place.
>
> I am going to implement a multihop unicast routing protocol (DYMO) on
> TinyOS 2. When I checked if there is a framework or guidelines for
> that, I noticed there was such a framework in TinyOS 1.x, but not 2.0,
> so I requested information on tinyos-help, where I got a reply from
> Philip and Omprakash.
>
> I just started to think about adapting the framework to TinyOS 2 and
> my needs, while trying to keep something generic and partly reusable.
> Here is a link showing the components and their interfaces :
> http://www.daimi.au.dk/~romain/components-diagram.png
>
> This is basically the same principle as in TinyOS 1.x : a top-level
> component that abstracts the multihop routing. It is composed of three
> main components. One handle the received message, one handle the send
> commands, and the third one is the core routing components, which
> updates and provides routes to the send component. This last one is
> also made of three components. One implements the routing algorithms,
> one implements the packet format, and the third one keeps the routing
> table and manage neighbor discovery and monitoring.
>
> I guess that integrating this in TinyOS would require to describe the
> top-leve component, ForwardingEngine, MultiHopSend, RouteSelect and
> RoutingTable. The first three ones are described in TinyOS 1
> documentation.
> Here is how I see RoutingTable :
>
> interface RoutingTable {
>   command void update(nghbr_info_t *);
>   command nghbr_info_t * getRoute(addr_t);
>   command uint8_t size();
>   event void evicted(nghbr_info_t *, reason_t);
> }
>
> update adds or updates a routing entry, getRoute retrieves a routing
> entry (especially nextHop) from an address. nghbr_info_t is an
> abstraction like message_t, because routing protocols all require
> differents fields in their route entries.
>
>
> This is a first draft, you'll probably find various mistakes.
> First, the control is not really specified, but I don't really know
> how to do that. Do all the components provide a control ? Std or split
> ? Should a component handle the control of the whole multihop system ?
> Next, I think I have misunterstood the use or principle of
> RouteSelect. It is supposed to care about the format of the packet,
> since the routeSelect command takes a message as a parameter and fills
> the fields properly, but what prevents Multihop to use a different
> format from RouteSelector ?
>
>
> Here is where I am. What are your thoughts about that ? Is there  
> anything good ?

Rodrigo Fonseca might be a good person to talk to; he and a few other  
people had a paper in OSDI this year on something similar, a network  
layer architecture for implementing routing protocols. I know there's  
been some talk at Berkeley on porting it to TinyOS 2.0, but I don't  
know what the status is.

Phil