4 Only propagating updates

Since nodes are already programmed before deployment, programming after deployment is likely to consist of small changes. Fixing a bug or adding a feature often leaves most of the code intact. By only sending the changed code, communication can be greatly reduced.

4.1 Diff-like approach

In [Reij03], a method is proposed to send only the differences between two versions of the code. Instead of transmitting code, an edit script is sent. This edit script describes how the new version can be made from the old version and the information in the edit script. Such a method is already widely used in distributing source code on the Internet, using the Unix diff and patch tools.

The authors observe that a small change in the source code often means many changes in the binary code image, because addresses shift. When the length of a function early on in the code is changed, all addresses of succeeding functions and data change. Any reference to these functions and data must also change.

Address shift

Figure 2: Address shift: when a small change is made, addresses throughout the whole program change.

To optimize this, a special instruction is added to the edit script which shifts all references in a specific code block with a certain amount. This way, address shifts can be compensated.

4.2 Loading modules

Some operating systems designed for nodes are able to load and unload programs. These operating systems often have limited functionality in their kernel and can load programs dynamically.

In the SOS operating system ([Han05]), it is possible to load modules, which are very much like programs. The modules can interact with each other with direct calls, kernel calls or message passing. When a module initializes, it has to register its public functions and their addresses with the kernel. This way, when another module calls one of these functions, the kernel knows where it is.

Whereas the function calls in SOS are resolved when the call is made, the Contiki operating system ([Dun04]) uses a relocation function which updates programs to refer to the correct addresses.

In [Dun06], the authors observe that when distributing pre-linkedPre-linked programs are linked at compile-time. modules, installation fails when not all nodes have the same code image. The new module references functions and data outside the module. Normally, these references are resolved by the relocation step, which is performed at runtime. However, this does not work when the node has a different code image than which the module was linked with.

[Dun06] proposes to transmit dynamic modules and link these on the node. The authors implemented a dynamic linker on top of the Contiki operating system. They successfully linked programs on a node, showing that dynamic linking is possible even on resource-limited systems.