[net2-wg] Collection (and more in general, multihop routing)

[Rodrigo Fonseca]

Let me describe what we've been thinking as a
reasonable decomposition of the network layer for sensor nets. It is a
framework to structure routing protocols such as to allow reuse of
components that can vary independently in different routing
algorithms.

It is akin to separating the control plane from the data plane in
traditional IP networks, but more flexible, as will become apparent.
Collection routing is a natural fit for this, as well as many other
protocols, from single-destination ones to point-to-point
algorithms.

It may not apply to
all protocols, specially Trickle, but I would argue that Trickle
performs functions of the transport layer. More on that later.

The basic idea is to separate the network layer functions when sending
a message over potentially multiple hops into Forwarding and Routing.
Routing is the process that establishes the routes, i.e., where the
packets should go. Forwarding is how the packets are forwarded.

Let me give examples to make things clearer.

A *Routing topology* defines an addressing scheme and a way to get
paths to an address. So, a collection tree defines an empty address
(the root), and a gradient towards the root. There can be variants of
how you build the tree, but their commonality is this gradient. A
different example is geographic routing: an address there is the
coordinates of a node, and the path is established in a greedy fashion
by a set of nodes that shorten the distance to the destination. BVR is
another example, where addresses are tuples of coordinates. There are
many variations.

Conceptually independent of the routing topology, there are different
*forwarding disciplines*. The classic one is that a sender chooses a
next hop and send the packet to this node. A very different one is
opportunistic forwarding, which is receiver based: a node broadcasts a
message, and the neighbors that hear it and can improve on the
closeness to the destination decide whether or not to broadcast it.
There are many suppression games we can play and actually make this
viable.  There are also variations on the classic, sender based
forwarding: one can add network-layer reliability by trying different
neighbors that make progress towards the destination. When the first
one fails, you choose the next one.

The key insight is that there is a lot of potential for reuse and the
construction of new protocols by combining different routing and
forwarding schemes, and they are largely independent of each other.
Fusion would work on other topologies, as would synopsis diffusion,
for example. Opportunistic forwarding can work on any routing topology
that provides a global gradient towards a destination. I hope you get
the picture.

We propose then that the protocols be structured in a Routing Engine
and a Forwarding Engine. These live at the same layer -- the network
layer, but talk through a set of defined interfaces. A "protocol" per
se is the combination of a Routing Engine (RE) and a Forwarding
Engine, along with other common components which I won't discuss.

The application that sits on top of the networking layer knows what
protocol it wants to use, and thus the format of the Routing Engine
address. These are opaque to the forwarding engine, which happily asks
the Routing Engine for interpretation of the address. A bit more
generally, there are fields that will live in a Routing sub-header,
and fields that will live in a Forwarding sub-header.

The interfaces would look like this:

The Routing Engine implements:

interface RoutingEngineControl {
   command uint8_t getHeaderSize();
   command result_t initHeader(void * RoutingHeader, void * addr);
}

interface BasicRouting {
   command uint8_t getnexthops(void* RoutingHeader, SPHandle* nexthops, uint8_t
 max);
}

optionally,
interface CostBasedRouting {
       command result_t getMyCost(void * RoutingHeader, uint16_t *cost);
       command result_t getCost(void * RoutingHeader, SPHandle neighbor, uint16
_t *cost);
}

The interface that the application sees is provided by the forwarding
engine, are basically
interface SnaSend {
   command result_t send(void* address, TOS_MsgPtr msg, uint16_t length);
   command void* getBuffer(TOS_MsgPtr msg, uint16_t* length);

   event result_t sendDone(TOS_MsgPtr msg, result_t result);
   command result_t cancel(TOS_MsgPtr msg);
}
and

interface SnaReceive {
   event TOS_MsgPtr receive(TOS_MsgPtr msg, void* payload, uint16_t payloadLen)
;
}

The pseudo-code for the application and forwarding engine are as follows:

App:
  SnaSend.getBuffer(msg, &length);
  SnaSend.send(address*, msg, length)

Forwarding Engine:
  command getBuffer {
       BottomSend.getBuffer(
       RoutingEngineControl.getHeaderSize()
       Figure out buffer and return
  }
  command SnaSend.send(address*, msg, length) {
       call RoutingEngineControl.initHeader(header*, address*)
       call BasicRouting.getNextHops
       BottomSend.send(msg, nextHops[0]);
  }

...

Finally, collection.

Collection routing is a natural fit for this modularization. The
RoutingEngine will be, in the simplest case, a single rooted case, and
the opaque address will actually be trivially nothing. It does not
matter how the tree is built, there are many nice ways to build trees
and form gradients. There can also be multiple trees, and the address
in this case is simply the id of the root, for example.

The forwarding part is quite flexible. Given that the tree can provide
both the getNextHops and the getCost interfaces, we can run a host of
Forwarding Engines for the collection. Variations are, as I mentioned
above, the classic sender-based forwarding scheme, or a more different
opportunistic forwarding.

There is also the possibility of different routing engines running in
the same node to use the same forwarding engine, and vice-versa. The
big advantage is that we allow easy testing and developing of both
routing and forwarding schemes that can readily be used with other
forwarding and routing engines.

Rodrigo