Interview with Adam Dunkels

I discovered Protothreads through a link in Chris Double’s weblog on Saturday. This is a fascinating tiny library, written by Adam Dunkels, a researcher at the Swedish Insitute of Computer Science. The Protothreads library implements user-level in threads in portable ANSI C in a mere 20 lines of code, and each thread uses only 2 bytes of RAM! While having a few important limitations, this comes in handy for a lot of problems, especially when writing single-threaded network servers (using Protothreads, you don’t have to use state machines to do protocol handling). While checking out Protothreads, I stumbled across the very interesting link list that Adam Dunkels compiled while writing his library. From there, I got hooked and browsed the rest of Adam’s website.

He has written two incredible TCP/IP stacks aimed at embedded systems. The first one, uIP, is targeted at 8bit microcontrollers, and has a very low RAM usage (it runs with as few as 128 bytes RAM for full TCP/IP support). The development version of uIP uses Protothreads to offer a BSD-style socket interface while maintaining its low RAM usage. The second stack, lwIP, is targeted at bigger embedded systems, and offers a BSD-style API.

Adam is a computer scientist working in the field of sensor networks, which are a part of the research field of ubiquitous computing. Sensor networks consist of a myriad of little embedded systems gathering environmental data through a set of sensors. However, the real value of sensor networks stems from the communication between all these systems. As Adam put it, “the nodes are interchangeable: it is the data generated by the sensors that are the primary interest”. Besides uIP, which he uses as a mean to communicate between the sensor nodes, Adam works on Contiki, an embedded operating system. Contiki allows the dynamic loading of code on sensor nodes, which proves to be very useful when deploying sensor networks.

I emailed Adam a few questions about his software, embedded programming and sensor networks. He was very kind to provide exhaustive and very interesting answers. Enjoy the interview 🙂

Protothreads

These first three questions are about Protothreads, the minimal threading library Adam has written for his embedded platforms. Protothreads are inspired by coroutines, which can be sort of implemented in C using a neat little trick.

Question: Adam, what was your motivation to write protothreads?

Answer: The driver behind the development of protothreads was many years of writing event-driven code. After a while, one sees the need to have a nicer abstraction than finite state machines. Ordinary threads have many of the good properties of such an abstraction, but they have two problems: the RAM overhead is prohibitive on systems with very small memory resources —the typical target system for uIP—, and they require a fair amount of platform specific code. As I wanted to keep both uIP and Contiki as portable as possible, this was definitely a problem.

After thinking long and hard about this, as well as reading lot of papers on the subject of concurrency, the protothreads concept dawned on me. Very simple, yet powerful. Very little RAM overhead and possible to

implement in pure C. Perhaps the nicest thing is the extremely small size of the implementation. With all comments removed, the entire library can be reduced to 20 lines of code (that goes into a header file, no less!).

Question: What kind of software uses Protothreads currently?

Answer: Currently, the Contiki OS and the development version of the uIP TCP/IP stack are using protothreads. Among other things, they are used to implement a network API called “protosockets”, which are similar to the BSD socket API but based on protothreads. This means that they can be used without underlying full multithreading, which subsequently means less RAM overhead.

Question: What kind of software do you think will use Protothreads in the future?

Answer: I would expect that protothreads would find its biggest use in embedded systems, since that’s where the really tough memory constraints are. But you never know where this kind of software will end up. That’s the real beauty of releasing open source software: it might turn up in the most unexpected places.

lwIP and uIP

Adam Dunkels is working on the integration of TCP/IP with sensor networks, and has written two embedded TCP/IP stacks. uIP is aimed at very small embedded platforms, while lwIP is more similar to a BSD IP stack.

Question: What were the main problems you faced while developing uIP?

Answer: The biggest challenge of uIP is flushing out bugs in TCP. Every now and then a new weird corner case in TCP turns up. Typically, these bugs have a pretty lengthy sequence of events that has to be followed in order to reproduce the bug. Weird corner case bugs seem to be an inherent property of TCP; there was a working group in the IETF (Internet Engineering Task Force, the standardization body of the Internet’s communication protocols) that worked on this. They produced an RFC on the topic: RFC2525, “Known TCP Implementation Problems”, Paxson (editor).

Question: How did you structure your development cycle? For example, did you write a prototype following a certain approach, then discard it and rewrite, or did you work on the same “stack” throughout the project?

Answer: I am a proponent of the “discard and rewrite” principle, but I seldom manage to follow it myself… The base of uIP has been the same since the very first release. Perhaps this is a sign of a good design: it managed to capture the basic flow of control and structure of the code while being flexible enough to allow later enhancements such as protosockets and multiple network interfaces (which were not present in the first versions).

Question: What was you development setup while developing uIP? Did you test it on embedded devices directly? What kind of development tools did you use (for example, did you debug the stack directly on embedded devices?)

Answer: I do all code development under FreeBSD, running uIP as a user process. I almost never develop code high level code like a networking stack on a target device, but only verifies that everything works as expected. Of course, low level code such as device drivers cannot be developed without doing parts of the development on the target device.

In fact, I was not even the first person to run uIP on an embedded device – that was done by others that I was in email contact with. After a while, one gets a feeling for what kinds of problems that can arise when running on a target device and takes special care to tend to the “sensitive” parts of the code.

All in all, this development philosophy works surprisingly well.

Question: What kind of applications are using your embedded stacks lwIP and uIP? Which ones do you think are the most interesting?

Answer: lwIP and uIP are used in so many applications that I’ve lost track of most of them. I recently wrote down a list of companies and academic institutions that I know are using either lwIP or uIP and ended up with a list of 60 items – and this was purely from memory. And that’s just the applications that *I* know about.

Some of the more notable recent uIP applications are the CubeSat kit that uses uIP to communicate with so-called pico-satellites in space, and a container tracking and security system in which uIP is used to communicate with wireless reader terminals on cranes at ports and on ships at sea. Other uses include remote monitoring for waterworks, instruments used in bore holes, in weather stations, and in development kits for embedded devices. lwIP is also being used in a bunch of interesting applications such as TV transmission equipment used by BBC and CNN among others, and in devices that were used for the post production of the second Lord of the Rings films. lwIP is also used in numerous system development kits from e.g. Xilinx, Altera, and Analog Devices.

Question: Could you tell us something about the CubeSat?

Answer: From my point of view, the most interesting thing with uIP in theCubeSat kit is the extremely small packet buffer that is used. The RAM footprint for the entire uIP stack is as small as 128 bytes, where something like 96 bytes was used for the packet buffer. I never thought that such a small RAM configuration would ever be used in a real system. In their system, however, the space-to-earth communications link is not fast enough to warrant a larger buffer anyway.

Question: What is the advantage of using TCP/IP as a communication protocol between sensor nodes, instead of, say, a custom “over the wire” or “over the air” protocol, and then add maybe a TCP/IP gateway so that “normal” nodes can access the sensor network?

Answer: Most people working with sensor networks have designed custom protocols for the sensor network, but we’ve decided to go the other way and investigate if TCP/IP can be used even inside wireless sensor networks.

There is really only one advantage of using TCP/IP inside the sensor networks: ease of connectivity to IP networks. With a TCP/IP sensor network, any node can connect to outside networks without special proxies or protocol converters. The challenge lies in making TCP/IP as efficient as custom protocols. I don’t think we’ll be able to make it 100% as efficient, but if we can get it to be, say, 95% as efficient, then the extra advantage of connectivity may be worth it. Many applications of sensor networks require some form of external connectivity, and may therefore benefit from this work.

We are looking into five techniques that are intended to make TCP/IP viable for sensor networks:

• Spatial IP addressing. Normal IP addresses are based on network topology and each host has its own unique address. With spatial IP addressing, each sensor node constructs its own IP address from its spatial location. If two nodes get the same address, it does not really matter because the sensors’ identities are not particularly important: it is the data that is important.
• Application overlay routing. Routing in IP network is based on addresses and network topology, whereas routing in sensor networks is more effective if based on sensor data and interests. We implement data-centric routing by using an application overlay on top of TCP/IP.

• Shared context header compression. TCP/IP headers are large compared to what can be achieved with custom protocols. We note, however, that header compression works exceptionally well in sensor networks because all nodes already know each other – they share the same context. This enables headers to be compressed from 28 byted (UDP/IP headers) down to 1-3 bytes.

• Distributed TCP Caching (DTC). It is well-known that TCP performs poorly in wireless networks. With DTC, we let sensor nodes cache TCP segments for each other in order to perform localized retransmissions. This helps reducing the energy consumption of TCP.

• The uIP TCP/IP stack, which shows that TCP/IP can be efficiently implemented even on the severely constrained sensor nodes.

Embedded development

An Embedded Sensor Board.

Question: You said that after a while, one gets a feeling for what kinds of problems can arise when running on a target device. Could you summarize what the most important kinds of problems are, and how you go about working around them? I know this is a very general question 🙂

Answer: When working with embedded networking, there are a few issues that typically arise (from the top of my head): memory alignment, ROM vs RAM pointers, near/far pointers, byte order, stack size. Some platforms cannot read memory from addresses that are not nicely aligned and this typically becomes a problem when an application passes a misaligned pointer to the networking stack. If the network stack tries to read data in chunks of two or four bytes (i.e., using shorts or longs) the whole program will crash. Also, some platforms are of the “Harvard architecture” kind, where ROM and RAM have different address spaces. Usually a special instruction must be used to translate between the two. Again, the problem is when an application passes a pointer to the protocol stack and the protocol stack does not know if the pointer points to ROM or RAM. Issues are similar for near/far pointers.

Byte order is a problem, albeit a much smaller one. It basically boils down to always converting 16-bit quantities into host byte order when they are read from network data, and convert data back into network byte order when it is written to the network.

Stack size problems are typically much harder to find. They usually manifest themselves by simply crashing the device, without much evidence of why the system crashed. The problem is that the CPU stack for the application was under-provisioned and the stack would overwrite other sensitive memory.

Question: Do you have a favourite embedded platform, and in case you do, which one and why?

Answer: No, I don’t have any favorite platform 🙂

Sensor networks

The sensors Adam Dunkels is working with.

They are called “Embedded Sensor Board” and come from the FU Berlin.

Question: You are currently working on sensor networks. Could you briefly describe what your special area of interest is?

Answer: My main research interest in wireless sensor networks is trying to bring together TCP/IP (the Interent protocol suite) and sensor networks. The challenge is that the networks for which TCP/IP was designed are so essentially different from wireless sensor networks. Wireless sensor networks are based on low bandwidth radio communication channels with potentially high error-rates, whereas the Internet have high bandwidth

links with virtually no bit errors. The nodes in a sensor network are severely resource constrained (energy, memory, CPU), where as Internet nodes (PCs, workstations, routers) are high performance machines. And so

forth. But the most interesting thing is that the applications running on top of the networks are so completely different: in sensor networks, in most cases it is not even meaningful to talk about the individual node’s addresses because the nodes are interchangeable: it is the data generated by the sensors that are the primary interest. This is in stark contrast to the Internet, where it is of primary interest that data gets to or comes from a particular host. In order to bring TCP/IP into wireless sensor networks, there are a bunch of interesting problems that needs to be solved. (See my licentiate thesis for details).



Question: What do you think is going to be the future of sensor networks, which is a “hot” topic of research at the moment?

Answer: The area of sensor networks has grown tremendously over the last few years. I would say that one of the current trends is that sensor networks are getting mature enough to allow people to make real deployments and experiments with them. Also, there are numerous companies that have been formed around these concepts.

As part of this trend, I am on the organization committee for the REALWSN’05 workshop on real-world issues with wireless sensor networks. The workshop is focused on things like software development, experimentation, and applications of real-world sensor networks. There are also a few other workshops around similar topics (e.g. IEEE EmNetS-II and SIGCOMM E-WIND).

Contiki OS



Question: You developed an operating system for sensor devices named Contiki, which allows dynamic loading of code in a sensor network. I must admit I have never seen a sensor network at work, so I am very interested in hearing about how you use dynamic loading of code in day-to-day operation.



Answer: Traditionally, operating systems for tiny embedded systems and for sensor networks (e.g. TinyOS) have required that a single monolithic binary of the entire system (OS + applications) is built and downloaded into each device. When developing software for wireless sensor networks, which may be composed or large numbers of nodes, this is not very practical. If we need to manually collect the nodes in order to download a new binary image, it takes hours to reprogram even a small network (20 nodes). There are ways to download the monolithic binary to sensors using the radio, however.

What Contiki does is that it allows us to dynamically load and unload individual applications running in the wireless sensor nodes. That is, we can leave the OS running on the nodes and only replace a small application program. The application program is broadcast to all nodes using the radio. I am attaching a few photos from my office just to get a feeling of the amount of sensor nodes we have in prototype networks.

When we were developing a prototype sensor networks together with Saab Technologies, we initially did not have the dynamic loader working and were forced to manually collect and reprogram the nodes using a parallel cable attached to a PC. With 20 nodes, just downloading new code onto them took a very long time. When we got the dynamic loader working, we could cut down the reprogramming time from hours to seconds.

(See Adam Dunkels, Thiemo Voigt, Niclas Bergman, and Mats Jönsson. “The Design and Implementation of an IP-based Sensor Network for Intrusion Monitoring“. In Swedish National Computer Networking Workshop, Karlstad, Sweden, November 2004.) Later this year, we will be deploying a sensor network in the Gulf of Bothnia that will be used to monitor the water temperature. Being able to remotely reprogram the network will be great for this network: we don’t really want to swim out and dive down to the nodes in order to reprogram them 😉

A screenshot of the Contiki simulator.

Question: In a similar way, how do you develop, test and deploy the software you are working on? Do you simulate the network? Do you have an army of deployed sensors? How do test the function of you software in case of sensor/hardware failure?

Answer: I do most of the software development in a small network simulator I have written. It runs each Contiki node as a separate process and has a very simple radio simulation model. The network is displayed in a window and radio communication is shown as circles. The simulator allows me to debug individual nodes with gdb, and to get a feeling for the traffic patterns in the network. I am attaching a screenshot.

As for debugging a deployed network, I personally don’t have a good solution. I know, however, that there are researchers working on this problem and hopefully their work will lead to better ways to develop and test software running inside wireless sensor networks.

General

And last but not least, a few general questions about the books Adam reads, and what he thinks about Opensource.

Question: What books, papers or articles were the most influential for your work and the way you program?

Answer: I don’t have any particular book or paper that I consider to be the most influential for my work. I read a lot of papers and follow conferences in the general networking area, but on wireless sensor networks in particular, and I also try to keep up with operating systems research and related areas.

Question: As an open-source developer, how do you find the time to develop open-source software? I think that as a computer science researcher, this is going to be easier than for other programmers, but did you encounter any problems when releasing your software? Did you have to make any compromises? How did you choose the license you release uIP, lwIP, Protothreads and Contiki?

Answer: Yes, I am one of the lucky few that are able to develop open-source software as part of my profession. My lab at SICS (the Computer and Network Architectures laboratory) are very open to open source software. Most of us run FreeBSD, and when I started at SICS back in 2000 at least two of us were actively working on the system and one was a FreeBSD committer. So releasing my software as open source have never been a problem.

When I first was planning on releasing the first version of lwIP I didn’t know that much about open source and free software. I initially wanted to release the lwIP code under the GPL but after talking about this with my lab manager, we decided to release it under the BSD license instead. This has turned out to be a really good decision: the BSD license have allowed people to use the code without being forced to open up their entire source code. This has led to a lot of people using the software, which in turn has led to a lot of people contributing a lot of both good patches and entire modules of code.

Question: How do you feel about software patents? Did software patents change the way you write and release sourcecode?

Software patents seem to do more harm than good.