--- /dev/null
+================================
+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
+============================================================================
projects / tinyos-2.x.git / commitdiff