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

[henri dubois-ferriere]

I don't understand all the details of the proposal (ie, what exactly
does getnexthops return, what is a SPHandle, why/when would the
CostBasedRouting interface be used), but still a few high-level
points:

- Is it necessary for the app to know what protocol is implementing
the collection interface beneath it? (and hence, be aware of the
addressing scheme being used). Can't we just have
   command result_t collect(TOS_MsgPtr msg, uint16_t length);
and not specify the address (since this is message is for "collection" anyway.

- Similarly, my understanding of the 3rd-to last para is that if we
have multiple sinks, the address would be chosen by the app to
indicate up which tree to send a message. In other words, a component
above Collection must make the routing/collection decision of which
tree to use. Shouldn't this be transparent to the application?

- It might be nice to have some sort of Intercept interface to allow
in-network processing (if we have a clear enough idea of this..)

Henri

On 15/12/05, Rodrigo Fonseca <rfonseca at cs.berkeley.edu> wrote:
> 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
>
> _______________________________________________
> net2-wg mailing list
> net2-wg at millennium.berkeley.edu
> https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/net2-wg
>