Tuesday, February 3, 2009

TinyOS and Great Duck Island

System Architecture Directions for Networked Sensors
(Hill et al., ASPLOS 2000)

An Analysis of a Large Scale Habitat Monitoring Application
(Szewczyk et al., Sensys '04)

Today was our first proper class and we had a fantastic discussion! Everyone came prepared to talk about the papers, and I think it helped to do a little icebreaking before we got into the discussion itself. I'm really looking forward to the rest of the semester.

I wanted to kick off the class with these two "classic" papers on sensor networks, to help lay the groundwork for the rest of the term. These are great papers, and though I've read them a few times, it is interesting to revisit them now. TinyOS is almost 10 years old, and it's nice to return to the vintage work with some new perspective.

On reading both papers again, I was struck at how low level they both are. The ASPLOS paper really goes bottom-up from the hardware platform and does not indulge in laying out a broader perspective for the field of sensor networks as a whole. Neither paper portends the fetish for complex in-network processing or fancy decentralized algorithms that has taken over much of the community. (I'm one of those fetishists myself, but it's interesting how straight these papers play it.)

We started out talking about what is fundamentally different about sensor networks than conventional computing systems. Most folks seemed to have drunk the TinyOS Kool-Aid and agreed it was all about high concurrency, limited memory, and limited energy. I wanted to press on the point of high concurrency a bit. Aren't ALL computer systems fundamentally concurrent and event-driven? All operating systems are driven by interrupts (keyboard and mouse events, packets coming in, timers going off); are sensor networks really more concurrent than conventional systems? OK, well maybe it has something to do with the lack of buffering, and energy limitations. Now we are getting somewhere - what is fundamental about this? Finally we hit on what I think is essential here: that the limited resources conflate with the concurrency demands to force the programmer to be really "intimate" with their events. You can't hide behind threads or processes anymore: events are part and parcel of what you deal with as a programmer in this domain, so the OS structure had better expose them in a lean and flexible way.

I also wanted to challenge the assumption that motes need to be so small and memory-constrained. Where did this idea come from? The ASPLOS paper more or less assumes it; but if you look carefully at a lot of the potential applications it's not so obvious that you can't get away with, say, a PDA-class device. Strikingly, some of the early design decisions on the mote hardware had some pretty significant impact on the design of TinyOS. My favorite example is that RFM radio, which requires that you bit-bang it to transmit or receive; requiring a context switch every 50 usec (once per bit)! I wonder what would have happened had Jason Hill chosen a better radio or more powerful MCU when he designed the WeC mote. We could be in a very different place today.

But, why the asceticism? TinyOS forces you to tie both hands behind your back and peck at the keyboard with your nose to program... no threads, no sockets, heck, not even malloc or printf. Was this some kind of self-flagellation, doing penance for years of building bigger and faster computers (NOW)?

To understand this lineage one has to go back to the origin of the Berkeley TinyOS effort, which originated with Kris Pister's "Smart Dust" project. That group was developing mm^3 devices integrating extremely simple computation, communication, and sensing. David Culler had the bright idea to build a version of this using off-the-shelf components, to approximate that "plausible future" and study the possibilities enabled by this space. So from the get-go you're talking very resource constrained, and (this is critical) SMALL devices. That fundamental tenet of the sensor network design space was established early on and largely continues to this day; I still see sensor networks based around 16-bit MCUs and the CC2420 when they could just as well use a proper processor and 802.11 radio (for example, if the sensors are powered).

I wouldn't call this merely an academic exercise; but I think we learned a great deal about the fundamentals of this new design space by forcing ourselves to abandon some of our long-held attachments to such luxuries as virtual memory and protection domains. Had we tried to shoehorn PDAs running Linux and make them look kinda, sorta like "sensor networks" I think we would have missed an important opportunity to dig deeper and reveal some essential truths.