Roadmap to an IP Stack in TinyOS

+ +++ + + + + + + + + + + + + + +

TEP:	136
Group:	Network Protocol Working Group
Type:	Informational
Status:	Draft
TinyOS-Version:	> 2.1
Author:	Stephen Dawson-Haggerty, Matus Harvan, and Omprakash Gnawali

Abstract

Recently, there has been renewed interest in the applicability of Internet +Protocol-based networking for low power, embedded devices. This interest is +being driven by several sources. One, emerging standards from the IETF are +beginning to make it possible to design efficient, compatible +implementations of IP for this class of resource-constrained device. Two, +there has been an emergence of a significant number of both open and closed IP +embedded IP stacks which demonstrate the applicability of this model of +networking. Third, a set of recent academic papers have made the case that +this network architecture is a significant research enabler and shown in more +detail the structure of a full stack.

In this TEP, we briefly explain how IP mechanisms map onto the well-studied +problems of the sensor network community like collection routing and local +aggregation. Next, we discuss the current "state of the standards." Finally, +we propose a path for the adoption of IP within TinyOS.

1. IP Requirements and Mechanisms

There are two versions of IP: IPv4 (RFCXXX) and IPv6 (RFCXXX). Previous +studies have indicated that IPv6 is more applicable to the low-power, embedded +space then IPv4 for various reasons; most standardization efforts have focused +on adapting IPv6 to these devices. Therefore, we consider only IPv6.

1.1 IPv6 Routing

A central question for implementing IPv6 in sensor networks is what has become +know as "route over" vs. "mesh under" in the IETF. In mesh under networking, +routing is done on layer two addresses, and every host is one hop from every +other. Although this is the most compatible with existing assumptions about +subnet design, it leads to significant redundancies and inefficiencies in this +space. The alternative, so called route-over exposes the radio topology at +the IP layer. While not strictly compatible with some IPv6 mechanisms, this +is becomming the favored approach since a single set of tools can be used to +debug. For the rest of this TEP we assume that route over is the model.

There are a number of existing routing protocols for IPv6, some targeted at +wireless links. However, IPv6 itself does not require any particular routing +protocol to be used with a domain; common choices in wired networks are OSPF +and IS-IS. Recent study in the IETF has indicated that existing protocols are +probably not appropriate for this space [draft-ietf-roll-protocols-02], and so +further work is needed on this point. Existing protocols with TinyOS +implementations such as DYMO or S4 may be appropriate for this task; +collection and dissemination protocols like CTP or Drip are probably not +directly applicable since they are address-free, although the insight gained +from their implementations may be transferable.

1.2 Addressing

The most well-known property of IPv6 is probably it's address length. An IPv6 +address is 128 bits long. Within this space, IPv6 defines unicast, anycast, +and multicast address ranges; each of these ranges further have properties of +their own. For a full explaination of IPv6 addressing we refer the reader to, +for example, [OReilly, RFC], we cover briefly some of the important details.

1.2.1 Unicast Addressing

Unicast addresses in IPv6 consist of two parts: the network identifier (the +first 64 bits), and the interface identifier (the second). The interface +identifier is a flat space, and may be derived from the interface's MAC +address, a random number, or other mechanism. IPv6 contains mechanisms to +ensure that the interface ID is unique within the subnet. The network +may be assigned using many different mechanisms, but some network identifiers +are special.

Unlike IPv4, each interface in IPv6 is multihomed: it is expected to have +multiple IPv6 addresses. When an interface is brought up, IPv6 contains +mechanisms to configure the interface with a locally unique, non-routable +address known as the link-local address. This address has the network +identifier fe80::, and can be used for communication between hosts in the same +subnet.

In a TinyOS IPv6 stack, this address range might be used to allow TinyOS nodes +to communicate locally without routing, for instance to enable local +aggregation. If the TinyOS hosts can assign themselves link-local addresses +derived from their IEEE802.15.4 16-bit short id, or full 64-bit EUID. For +instance, a node with short ID 16 might assign the address fe80::10 to its +802.15.4 interface. These addresses would not be routed; an IP stack would +send directly to the short id 0x10 contained in the address.

IPv6 also contains several mechanisms to allow a host to obtain a +publicly-routable network identifier. TinyOS hosts communicating with these +addresses could contact nodes in other sensor networks or on the internet; the +fact that they are multihomed allows them to use both public and link-local +addresses simultaneously.

1.2.2 Multicast Addressing

IPv6 contains a multicast address range; addresses beginning with the byte +containing all ones (0xff) are multicast addresses. Following this byte are +four bits of flags and four bits of "scope". For instance, scope 1 is +node-local, and scope 2 is link local. IPv6 defines many well-known multicast +groups [http://www.iana.org/assignments/ipv6-multicast-addresses]; of most interest here are the "link-local all nodes" and "link +local all-routers" addresses: ff02::1 and ff02::2, respectively. Depending on +weather TinyOS IP hosts are also IP routers, these addresses are effecitvely +link-local broadcast addresses which might be mapped into the layer 2 +broadcast address (0xffff). Thus IPv6 contains mechanisms for local +broadcast.

There is also a site-local scope defined in IPv6 (5) with a similar ff05::2 +address. "Site local" is an administratively defined scope in IPv6, and might +naturally consist of an entire sensor network. Thus, sending to this address +would correspond to disseminating a value to each node in the network and +could be implemented with a trickle-based algorithm.

Futhermore, the TinyOS community could develop additional conventions to +provide and address for scoped flooding or delivery to nodes with particular +capabilities. A full IP multicast implementation within the sensor network +could be used for many things including control applications or +publish-subscribe network layers which have previously been special purpose.

1.2.3 Anycast Addressing

Anycast addresses indicate that the packet should be delivered to at least one +host with the anycast address. This seems initially similar to the model for +collection routing such as MultiHopLQI or CTP, in that a collection report is +delivered to a single root. However, it is more likeley that those +"collection roots" in an IP-based infrastructure are not actually the final +destination for the data; they are likely to only be intermediate routers who +send the data on to a final destination. Therefore, while there may be +applications for anycast addressing, we do not believe this addressing mode to +be appropriate in the common case.

1.3 IPv6 Configuration Mechanisms

As alluded to earlier, IPv6 contains two mechanisms to allow internet hosts to +become associated with a public network identifier. These methods are +stateless autoconfiguration and DHCPv6. Stateless autoconfiguration defines +Router Solicitations and Router Advertisements. A host joining a network +sends router solicitations to the link-local all-routers address (ff02::2) +using his link-local address as the source address. Routers respond with a +Router Advertisement containing, among other things, a public network +identifier which the host may use.

In a TinyOS IP implementation, router solicitations and advertisements might +be used for default route selection on the hosts, as well as neighbor +discovery.

1.4 Extension Mechanisms

A common idiom in TinyOS is to provide "stacked" headers by implementing a +series of components, all of which implement the Packet interface. IPv6 +supports this a more flexible way with options headers. These headers fall +into one of two categories: hop-by-hop options headers and destination option +headers. These headers are chained together with small, two-octet common +header fields which identifiy the header type of the next header, and the +length of that options header. This allows hosts to process a header chain +even if they do not know how to interpret all of the options headers.

These headers are commonly used for protocol options, or to piggyback data on +outgoing packets. For instance, a link estimator component could add an extra +"link options" header to occasional outgoing packets as an options header, +while avoiding the overhead when it is not necessary to do so. This header +architecture is significantly more flexible then the existing TinyOS packet +architecture, although it does come at the slight cost of complexity.

2. The State of the Standards

All of the previously defined mechanisms are well defined for IPv6 in various +RFCs. However, most nodes running TinyOS are significantly more +resource-constrained then typical IPv6 hosts. Thus, there is ongoing work on +adapting these mechanisms to the characteristics of embedded devices.

2.1 Header Compression

The first issue which must be addressed is the sheer size of the IPv6 header: +40 octets. Of this, 32 octets are the source and destination addresses of the +packet. The IETF has published RFC4944 which describes a header compression +technique known as HC1. However, this scheme has significant problems, most +importantly the inability to take advantage of 16-bit short identifiers when +available. There have been a sequence of internet drafts proposing improved +techinques such as HC1g, and HC. The most recent version of these drafts is +draft-hui-6lowpan-hc-02, and there are strong indications that the working +group will depreciate HC1 from RFC4944 in the future.

2.2 MTU

IPv6 requires a minimum link MTU of 1280 octets in RFCXXX. Clearly, this is +much larger then the IEEE802.15.4 link MTU of 127 octets. RFC4944 defines +"layer 2.5" fragmentation which allow packets up to this MTU to be transfered +over small MTU links. While there are some issues have been raised with this +scheme, it seems likely to remain relatively unaltered.

2.3 Autoconfiguration

IPv6 stateless autoconfiguration as originally defined has some problems, +expecially once a "route over" network topology is established; for instance, +Duplicate Address Detection is likely to require some changes. A subcomittee +of the 6lowpan working group is currently investigating these issues is is +likely to propose adaptation mechanisms but they are currently in flux.

2.4 Routing

It is currently not possible to develop a standards-compliant routing layer, +as the relevant standards do not exist. Work in this direction is occuring in +the Roll working group, but a full specification is likely some way off.

3. The TinyOS Way

As the previous sections have shown, many sensor network abstractions map well +into IPv6 mechanisms, with a significant gain in clarity of abstraction. +However, standards are currently unavailable to specifiy exactly how this +should be accomplished. Therefor, our position is that TinyOS should move +quickly to incorporate existing techinques and standards into an IPv6 stack +where possible, while taking liberties with the standards when doing so +improves performance or simplifies implementation. Given that the standards +themselves are in a state of flux, having an open implementation which +demonstrates challenges and feasible mechaninisms is likely to be of +significant value.

The most important places where it may be necessary to move ahead of the +standards are the routing; an IPv6 stack with no routing will not be as useful +as one with it. One open question is weather we choose a routing algorithm +which functions in a completly decentralized fashion like AODV, OLSR, DYMO, +S4, or many existing protocols or choose one which imposes more hierarchy on +deployments. We do note that existing standards like Zigbee and WirelessHART +both contain multi-tier architectures with devices of differing capabilities. +This has also been a common deployment model in many applications, but it +limits the utility to places where this is possible. The correct long-term +answer is probably to support both types of routing.

4. Conclusion

This document is meant to introduce readers to the ways in which IPv6 +mechanisms can be used in a TinyOS-based sensor network deployment, and how +they relate to previous work. It does not address any implementation issues, +which will be presented in a later TEP.

5. Authors

+Stephen Dawson-Haggerty

+Computer Science Division

+University of California, Berkeley

+410 Soda Hall

+Berkeley, CA 94701

+

+stevedh@eecs.berkeley.edu

+

+

+Matus Harvan

+Information Security

+IFW C 48.1

+ETH Zentrum

+Haldeneggsteig 4

+8092 Zurich

+Switzerland

+

+phone - +41 44 63 26876

+email - mharvan@inf.ethz.ch

+

+

+Omprakash Gnawali

+Ronald Tutor Hall (RTH) 418

+3710 S. McClintock Avenue

+Los Angeles, CA 90089

+

+phone - +1 213 821-5627

+email - gnawali@usc.edu

+

6. References

Traffic Control

+ +++ + + + + + + + + + + + + + + + + + + + + + +

TEP:	137
Group:	Core Working Group
Type:	Documentary
Status:	Draft
TinyOS-Version:	2.x
Author:	David Moss, Mark Hays, and Mark Siner
Draft-Created:	3-Sept-2009
Draft-Version:	1.0
Draft-Modified:	2009-09-30
Draft-Discuss:	TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>

Note

This memo documents a part of TinyOS for the TinyOS Community, and +requests discussion and suggestions for improvements. Distribution +of this memo is unlimited. This memo is in full compliance with +TEP 1.

Abstract

This memo proposes traffic control interfaces to be provided by an optional +traffic control layer integrated at the highest levels of communication +stacks. These traffic control mechanisms are targeted to help improve acknowledgment +success rate, energy efficiency, fairness, and routing reliability on +any wireless platform. The available reference implementation is a platform +independent radio stack layer designed to consume a very small memory footprint.

1. Introduction

As the traffic rate of a wireless sensor network increases, the probability +of collision, dropped packets, and missed acknowledgments also increases, +even with sophisticated CSMA/CA implementations.

It is important, especially in the case mesh networks, for packets to be +delivered reliably and acknowledgments to be returned successfully on a hop-by- +hop basis. One method to improve reliability is to reduce the rate of +transmissions from each node within the network.

Traffic Control has been in use for years in many different wired and wireless +applications[1]_,[2]_,[3]_. TinyOS already has traffic control +mechanisms integrated directly into some networking libraries, such as CTP[4]_ +and Dissemination[5]_. The use of Trickle[6]_ algorithms, also used +within CTP and Dissemination, further reduces the rate of traffic throughout a +network to improve delivery performance and prevent livelock. There has +yet to be a centralized method of traffic control that throttles traffic +generated from any component of a user's application.

The traffic control interfaces proposed in this TEP are very basic, and are +intended to support many different traffic control implementations. +Two interfaces assist the application layer in controlling behavior: +TrafficControl and TrafficPriority.

The reference implementation presented here is integrated as a optional and +generic radio stack layer (providing a Send and using a SubSend interface) and +uses acknowledgments to dynamically adjust the transmit throttle. Other traffic +control implementations could employ more sophisticated techniques to control +throughput, but likely at the cost of a larger memory footprint.

The ultimate goal is to allow developers to use mesh networking protocols and/or +their own protocols without having to worry about implementing any kind of +traffic control timer mechanism for each separate component.

2. Desired Behavior

Ideally, a traffic control layer SHOULD attempt to balance the rate of +transmissions from a single node with the channel throughput capacity. +This implies an adaptive control mechanism. If the channel is +busy, nodes should add delay between packets to let other nodes transmit. +Similarly, if the channel is not busy, a node should be allowed access to +the channel more often to prevent inefficient channel downtime. Traffic +control SHOULD NOT listen to the channel for long periods of time to determine +the appropriate access rates, because that defeats the purpose of low power +communications layers used elsewhere.

The traffic control implementation SHOULD have the option to be activated or +deactivated on a system-wide level as well as a packet level. This allows for +individual high or low priority packets. Traffic control SHOULD be deactivated +by default, until the application or networking layers explicitly enable it.

Finally, the traffic control mechanism SHOULD be small in code size to fit +on the limited program memory available on most wireless platforms. There +SHOULD NOT be additions or modifications to a packet's metadata structure +that enables or disables traffic control on a per-packet basis; +instead, per-packet priorities SHOULD be performed with a request/call back +procedure. This keeps RAM requirements low and can be optimized out at compile +time if those functions are not used.

We also recommend any traffic control layer be implemented as an optional +compile time add-on to a core radio stack or within the ActiveMessageC platform +communication stack definition. This allows applications that do not require +traffic control to remove its memory footprint from the system.

3. TrafficControlC Component Signature

The signature of TrafficControlC is RECOMMENDED as follows:

+configuration TrafficControlC {
+  provides {
+    interface Send;
+    interface TrafficControl;
+    interface TrafficPriority[am_id_t amId];
+  }
+
+  uses {
+    interface Send as SubSend;
+  }
+}
+

The Send interface provided on top and SubSend interface used underneath +allow the TrafficControlC component to be integrated as a generic layer +within any radio stack.

4. TrafficControl Interface

The TrafficControl interface allows the application layer to enable or +disable traffic control from a system-wide level. It also +allows an application to set and get the current delay between packets. +For most systems, we expect that the setDelay() and getDelay() commands may not be +used often and will most likely get optimized out at compile time; however, some +systems may care to explicitly increase or decrease the delay between packets or +collect statistics on how the traffic control layer is performing.

The TEP proposes the following TrafficControl interface:

+interface TrafficControl {
+
+  command void enable(bool active);
+
+  command void setDelay(uint16_t delay);
+
+  command uint16_t getDelay();
+
+}
+

5. TrafficPriority Interface

The TrafficPriority interface is parameterized by active message ID. It is a +simple request / call back interface that allows components in the application layer to +configure individual packets for priorities on a scale from 0 (lowest priority, default) to +5 (highest priority, get the packet out immediately). There are several advantages +to this call back method. Metadata does not need to be added +to the end of every message_t. Additionally, a component that captures a requestPriority(...) +event is not required to adjust the priority as it would if the event returned +a value.

When a packet enters the traffic control layer, and traffic control is +enabled, the TrafficPriority interface MUST signal out the event +requestPriority(...). This event, with all the extra information it provides, +allows the application layer to decide whether the packet is a high priority +packet or not. Calling the setPriority(uint8_t priority) command within the +requestPriority(...) event MAY adjust the traffic control mechanisms applied +to the current packet. To aid in the definition of priority, two definitions +are available in TrafficControl.h:

+enum {
+  TRAFFICPRIORITY_LOWEST = 0,
+  TRAFFICPRIORITY_HIGHEST = 5,
+};
+

It is up to the traffic control implementation to define the meaning of each priority +level. In the reference implementation, a priority of 0 +is the default low priority level that employs the full traffic control delays. +Anything above 0 in the reference implementation is considered to be at the +highest priority.

If no areas of the application layer care to change the +packet's priority, a default event handler will capture the requestPriority(...) +event and do nothing. This would result in all packets being sent at a low +priority with full traffic control mechanisms enforced.

The TEP proposes the following TrafficPriority interface, to be provided as an +interface parameterized by AM type:

+interface TrafficPriority {
+
+  event void requestPriority(am_addr_t destination, message_t \*msg);
+
+  command void setPriority(uint8_t priority);
+
+}
+

6. Reference Implementation

An implementation of the proposed traffic control layer can be found in the +CCxx00 radio stack in +tinyos-2.x-contrib/blaze/tos/chips/ccxx00_addons/trafficcontrol, with +interfaces located in +tinyos-2.x-contrib/blaze/tos/chips/ccxx00_single/interfaces and a dummy +implementation located in +tinyos-2.x-contrib/blaze/tos/chips/ccxx00_single/traffic.

In this implementation, the default core radio stack (ccxx00_single) includes +an empty stub for traffic control. Users that wish to include the +traffic control implementation in their systems simply override the default +stub component with the ccxx00_addons/trafficcontrol directory.

The reference implementation works as follows. All nodes start with a default +of 4 seconds between each packet. Changes are made to the time between outbound +packets only when a unicast packet is sent with the request for acknowledgment +flag set. The reception of an acknowledgment is used as a basic indicator of +channel activity. For each acknowledgment received, the amount of time between +packets is decreased so the next packet will get sent faster. For each dropped +acknowledgment, the amount of time between packets increases, causing the +next packet to be sent later.

When the transmission rate reaches a boundary (1 second per packet per node +fastest, 10 seconds per packet per node slowest), it is reset to the default +rate of 4 seconds per packet per node. This prevents nodes from unfairly +capturing the channel.

Testing this traffic control layer in a congested test bed setting of 16 nodes +with multiple hidden terminals resulted in the acknowledgment success rate +moving from 27-50% without traffic control to 90-100% with traffic control. +The memory footprint increased by 260 bytes ROM / 16 bytes RAM with the +inclusion of the traffic control layer.

5. Author Addresses

+David Moss

+Rincon Research Corporation

+101 N. Wilmot Suite 101

+Tucson AZ  85750

+email: mossmoss at gmail dot com

+

+Mark Hays

+Rincon Research Corporation

+101 N. Wilmot Suite 101

+Tucson AZ  85750

+email: mhh at rincon dot com

+

+Mark Siner

+Rincon Research Corporation

+101 N. Wilmot, Suite 101

+Tucson, AZ  85750

+email: mks at rincon dot com

+

6. Citations

+ + + + + +

[1]	Bret Hull, Kyle Jamieson, Hari Balakrishnan. "Mitigating Congestion in Wireless Sensor Networks." In the Proceedings of the ACM Sensys Conference 2004

+ + + + + +

[2]	Wan, C.-Y., Eisenman, S., and Campbell, A. "CODA: Congestion Detection and Avoidance in Sensor Networks." In the Proceedings of the ACM Sensys Conference 2003

+ + + + + +

[3]	Woo, A., and Culler, D. "A Transmission Control Scheme for Media Access in Sensor Networks." In ACM MOBICOM 2001

+ + + + + +

[4]	Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Sukun Kim, Philip Levis, and Alec Woo.. "TEP123: Collection Tree Protocol"

+ + + + + +

[5]	Philip Levis and Gilman Tolle. "TEP118: Dissemination of Small Values."

+ + + + + +

[6]	Philip Levis, Neil Patel, David Culler, and Scott Shenker. "Trickle: A Self-Regulating Algorithm for Code Maintenance and Propagation in Wireless Sensor Networks." In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004).