tep136.txt

tinyos-2.x.rar

================================
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
| 
| [e-mail]
|
|
| Matus Harvan
| Information Security
| IFW C 48.1
| ETH Zentrum
| Haldeneggsteig 4
| 8092 Zurich
| Switzerland
|
| phone - [phone]
| email - [e-mail]
|
|
| Omprakash Gnawali
| Ronald Tutor Hall (RTH) 418 
| 3710 S. McClintock Avenue
| Los Angeles, CA 90089 
|
| phone - [phone]
| email - [e-mail]

6. References
============================================================================