[SensorNetArch] MAC + Network Layer Idea

[Jerry Zhao]

Ee's comments are very interesting. I have been thinking about this for
a while as well but related to both MAC layer interface and address
management. I'd like to chime in with some comments.

Maybe it is too long and Many of them are quite random rather than
coherent. But hope this can lead to more discussion in the mailing list.

Thanks,
Jerry


Joe's talk yesterday presented the power of B-MAC flexibility and
efficiency in the framework of factored network stack. B-MAC provides
many knobs for upper layers to fine-tune different MAC layer
functionality but all of these knobs are still for MAC layer
functionalities. Can we stride a bit further to see what we should push
into the mac layer from upper layer for even more flexibility and
efficiency?  

My primary proposal here is that 1) the MAC layer in SP stack should
support (or provide interface to support) richer communication
primitives in addition to broadcast and unicast: namely,
anycast/multicast and the corresponding acknowledgment mechanism. 2)
(very very handwaving) it seems many protocols in SP stack are
receiver-centric. For MAC layer, it should provide an interface for
packet filtering in addition to current simple address matching.       

(Here maybe I pushed too hard to break the layer boundary. I totally
aware many of the primitives can be placed upon MAC rather than in MAC
layer. ) 

In the SNA proposal, we argue that a wide range of address-free
protocols in SP stack is an important building block in SNA.  Let's just
focus on MAC layer, i.e. in the one-hop neighborhood vicinity: 

1. Inherently different from the _WIRED_ IP network, the RF radio
transceiver (unless we can envision something more advance for
sensornet) is all broadcast based. Thus there is no physical "Link" at
MAC layer but rather a RF coverage cell. (Of course, any fine-grain
TDMA, coarse-grain scheduling or FH/DSSS coding can create virtual links
but still the media is shared.) 

In the WIRED Internet, since many interfaces are point-to-point "link"
based, routing protocols are unicast based according to assessment of
individual links. For multicast protocols, packets are dispatched to
different outgoing _interfaces_(links). For those shared media e.g.
ethernet, only broadcast and unicast are supported by hub and switch.
Mutlicasting is supported by the router/switch with IGMP or filtered at
the receiver side.   

Current design of sensornet MAC layer continues such a design and only
supports two primitives: unicast (with optional ack) and broadcast (w/o
ack). To some extent, current routing layer (GPSR/BVR) does not take
full advantage of broadcast nature, either. To me, it is not just an
implementation detail but rather fundamental.   

2. However, many of communication patterns in appearing sensornet
application/protocols work better with broadcast/anycast than unicast.
For example:

Trickle is based on broadcast primitive only. 
Synopsis Diffusion can be implemented with anycast, i.e. if any of node
on upstream "ring" receives the partial result, synopsis diffusion will
work. 
For routing protocols such as GPSR or BVR, instead of forwarding to the
best next-hop candidate, opportunistic forwarding to all candidate nodes
(those with smaller distance to dest) can potentially reduce overall
transmissions (energy cost) for delivering the packet to dest.  

Those multicast based operation will require more complicate suppression
scheme (for example in trickle) than those with unicast only. However,
even only with unicast primitives, it also requires some suppression on
retransmission/duplicates.(e.g. what if ack is lost, and you try to
route to an alternative next-hop node.)   

Note that there are still many details to work out: e.g. if packet loss
to all neighbors are strongly correlated (e.g. due to collision), such
broadcast-style primitive does not help much...           

3. Partially resulting from the shared and noisy nature of RF channel,
many of operations in those applications/protocols above are
receiver-centric rather than sender-centric: Control decision is made at
receiver side rather than transmitter side. Though action may happen at
the sender side based on the feedback from receiver. 

Trickle adjust timer/counter based on messages received. Each node are
both sender and receiver, but decision is according to messages received
rather than messages sent. 
In opportunistic forwarding in synopsis diffusion or BVR, the sender
need indication from the receiver in the anycast group.   
Even for unicast based routing, sender ceases to retransmit only when
ack received from receiver or max retry is exceeded.        

Such strong feedback loop at each hop (instead of end2end in TCP) makes
acknowledgment as important as data itself. It also requires efficient
data processing at receiver side.  

MAC Layer and up

If my argument that anycast-style communication is common and useful in
sensornet, is valid, what functionality should we push into MAC layer
and what we should not?

1. Anycast support

Anycast and multicast support can be implemented upon current MAC layer
design with only broadcast and unicast. Anycast/multicast messages are
packaged as broadcast packet at MAC layer. Ack messages are packaged as
a whole separate MAC frame. Drawback: a) MAC at each node has to pick up
all broadcast packets for the upper layer to process. Most of them will
be dropped. b) Ack messages are quite costy, compared to unicast ack.

Do we need a sensornet IGMP to allocate group address for anycast(e.g.
Ee's suggestion of TOS_PARENT_ADDR)? A simple probabilistic approach:
The group address is the hashed bitmap e.g. bloom filter of group member
addresses. MAC will match local address with the group address to
identify if a node belongs to the group.        


2. Anycast acknowledgment

Alternatively, we can implement a very simple anycast primitive: i.e.
broadcast with aggregated acknowledgment. 

I briefly talked to Joe by email about anycast ack support on
Mica/MICA2/Telos. It seems to me that the aggregated ack from multiple
receivers is feasible for many modulation schemes. 


The architectural question is: Do we need to push more semantics in MAC
layer ack in addition to binary success/failure? It seems to me that the
semantics difference between multicast, anycast and "somecast" is in the
condition of acknowledgment. For example, shall we design an fancier
aggregate ack with information of the percentage of group member
received the packet? Will this be helpful for the upper layer and can be
implemented in mac layer easily and efficiently.   

3. Packet filtering and processing in MAC layer

MAC layer could be the most efficient place to process the data: once a
node find the first byte that indicates packet is not valid or not
interested to the application, it can stop reception and put radio to
sleep till end of packet immediately to save energy.  However, usually
this won't work since MAC layer itself can not tolerate too much
processing delay during reception.   

But if we push to this direction just a bit, can we push some simple
packet processing into MAC layer? Maybe not for application layer but
routing layer might find such interface useful. 

For example we can push the TinyOS AM architecture even further: MAC
layer can provide a "packet-filter" like interface to define receiver
behavior. i.e. AM matching rule is in MAC layer, and it is not only
about the AM-type value but some fields in the header or even the data
payload. Of course, we can not push too much processing overhead in MAC
layer but a simple packet filtering by both header (address/AM_TYPE) and
data can at least abandon packet reception immediately when an unhooked
AM_TYPE is found. 

It can also support multicast filitering: With perhaps a stripped down
version of Berkeley packet filter, for example, considering Ee's
synopsis diffusion case, we can install a filter: only receive a
broadcast message with AM-TYPE==synopsis_type and data[7](which
corresponding to transmitter's  hop distance)>my_hop_distance. Thus we
can efficiently filter useful synopsis diffusion messages.     

Now I should shut up since I definitely said too much.