By Jonathan W. Hui and David E. Culler, Fellow IEEE
This excerpt of a paper published by IEEE discusses how recent developments make it possible, pragmatic, and efficient to use the IPv6 protocol for low-power multihop wireless networks.
Figure 1: Incorporating sensornets into an IP network is no different than with any other network technology. A sensornet simply forms another subnet within an IP-connected network. A sensornet subnet is the set of nodes that can communicate within the sensornet.
Some 40 years after the Internet was created to connect computers to one another and allow file transfer, remote login, and access to distant computation; computational processing is now in almost every device, machine, appliance, and instrument. And, they are increasingly able to communicate.
These deeply embedded computers present physical information—sensor readings, observations, actions, and events that occur over time at particular points in the real world. The web of real world data is used to optimize production, improve safety, and reduce energy consumption, waste, and pollution. The emergence of this new tier of the Internet has largely been enabled by a decade or so of intense research on low-power wireless embedded networks, or sensornets.
Sensornet researchers have tackled a number of networking challenges. With the observation that radio idle-listening dominates system energy consumption, numerous duty-cycled link protocols based on sampled listening and scheduling were proposed. Because the radio network topology must be inferred by observing communication with neighboring nodes, significant work went into link quality estimation that used link-layer information, physical-layer information, as well as their combination with routing information. Sensornet researchers demonstrated the need for hop-by-hop feedback to achieve greater visibility into the network, react quicker to local conditions, and avoid the high costs of end-to-end mechanisms. The need to disseminate information across the network shows up in a variety of applications and network-layer scenarios, and the Trickle algorithm provided a means to do so in an efficient and density aware manner that avoided the broadcast-storm problem.
Much of this work did not constrain itself to an architecture, leading to the development of numerous application-specific networking protocols that were hard to compose. Existing work sought to provide a communication architecture that could combine these disjoint networking protocols by placing the narrow waist of the protocol stack at the link layer. But by being agnostic to the network protocol in use, these architectures did not define broader networking issues of discovery, naming, addressing, configuration, and management.
Figure 2:A DHCPv6 server maintains entries for all addresses in use within its domain. If this server cannot be reached within a single IP hop, neighboring sensornet routers can proxy DHCPv6 messages so that nodes do not have to use a global address before its uniqueness is verified.
Many past standardization efforts for low-power wireless networking (such as ZigBee, Z-Wave, and WirelessHART) also believed that IP was too large and ill-suited for the needs of sensornets, leading them to develop ad hoc solutions not based on IP. Without a common network layer, these systems require an application-layer gateway to communicate with other systems or even the wider Internet. These application gateways are complex to design and manage.
Internet Protocol Version 6 (IPv6) is the designated successor of IPv4 as the network protocol for the Internet. In anticipation that networked devices will vastly outnumber conventional computer hosts, IPv6 expands the IP address space from 32 to 128 bits. The most widely used link technologies evenly split the IPv6 address space into a subnet prefix that uniquely identifies the subnet within the Internet and an interface identifier that uniquely identifies an interface within the subnet. IPv6 increases the minimum/maximum transmission unit (MTU) requirement from 576 to 1280 Bytes. To increase protocol efficiency and eliminate the need for ad hoc link-layer services to bootstrap the subnet, IPv6 includes scoped multicast as an integral part of its architecture. Core IPv6 components, such as neighbor discovery (ND), use link-local scoped multicast for address resolution and router discovery. The large IPv6 addresses are more amenable to cross-layer compression.
IPv6 network protocols were designed to support protocol options. Local IPv6 protocols that made link specific assumptions were specified only for those links, allowing adaptations for different link technologies. This generality and extensibility of the IPv6 networking protocols allows you to use mechanisms that have become pervasive in the sensornet community. Sampled listening, hop-by-hop recovery, and collection routing are just a few.
Incorporating sensornets into an IP network is no different than with any other network technology (Fig. 1). A sensornet simply forms another subnet within an IP-connected network. A sensornet subnet is a set of nodes that can communicate within the sensornet. Edge routers connect sensornet subnets to other subnets possibly built on different link technologies. While the sensornet network may only support IPv6, the edge router may implement IPv4-to-IPv6 translation. But most importantly, edge routers only forward datagrams at the network layer and do not maintain any application-layer state.
The challenges come from supporting IP and its essential services within a sensornet subnet. While IP has shown great success in using a range of link technologies (including wireless), the resource constraints inherent to sensornets challenge common assumptions.
An IP link is defined by those nodes that are reachable over a single IP hop. The most widely used link technologies (Ethernet, WiFi, and point-to-point) provide a single broadcast domain where all communication is transitive within the subnet. Ethernet subnets are often composed of multiple physical media connected by Ethernet switches. WiFi subnets are composed of clients that can only communicate directly with an access point at the physical layer due to physical limitations of radio communication and security mechanisms.
A crucial decision on bringing IPv6 to sensornets is whether to emulate a single broadcast domain. This is referred to as the mesh-under versus route-over debate. Mesh-under refers to the use of link-layer mesh routing protocols to emulate a single broadcast domain. Route-over refers to the use of IP routing to maintain “reachability” between nodes within a sensornet subnet.
Any node can send a single IP message to any subset of nodes in the subnet without the need to understand the physical topology. This simplifying property is used by IPv6 ND to query whether an IP address is in use, determine the link address for a given IP address, and redirect traffic to other neighbors.
Dynamic radio properties typical to sensornets lead to more complex forwarding and routing dynamics than those observed with Ethernet or WiFi. Strict resource constraints make it difficult to hide the complex dynamics of forwarding and routing within a sensornet. IP-based protocols would not have the necessary visibility to make informed decisions based on the underlying radio topology. Unlike Ethernet or WiFi, communication properties between any two pair of nodes can vary greatly especially when their path lengths differ by multiple hops. Basic tasks such as determining reachability and selecting a default router must take into account the underlying radio topology.
Supporting a broadcast service across multiple radio hops within a sensornet is also costly. A simple multicast message sent to the link-local all-nodes multicast address would require delivery to all nodes within the sensornet subnet. A multicast topology can help, but maintaining it also carries a significant cost. Furthermore, every node within the sensornet must incur the cost of receiving the message.
The lack of visibility also removes any ability for IP-based protocols and applications to use the subnet’s spatial structure to optimize performance. Existing work in data fusion that aggregates information from multiple sources along a forwarding topology would no longer apply.
A route-over sensornet subnet arch-itecture, however, equates a broadcast domain with the radio transmission range. The result is a sensornet subnet that may be composed of overlapping broadcast domains where each radio hop is an IP hop, (Fig. 2). By limiting the broadcast domain to the physical properties of the radio, IP-based protocols and applications can operate in concert with the spatial structure of the network.
IPv6 Address Architecture
Every IPv6 address (other than the un-specified address) may be used as a unique identifier for an interface. RFC 4007 defines two scopes: link local for uniquely identifying interfaces on a single link and global for uniquely identifying interfaces across the Internet.
By avoiding IP link emulation, the traditional IPv6 address architecture no longer applies to sensornet subnets. While the topological span of an IP link is defined by those interfaces within radio range, a link-local address assigned to an interface must be unique among interfaces reachable within two hops or more. Because time-varying radio characteristics make the set of two-hop neighbors an ill-defined set that changes over time, uniqueness is best expanded to that of the entire sensornet subnet.
Figure 3: IPv6 requires the link to carry a payload of up to 1280 B. The IPv6 base header is relatively large at 40 B. IPv6 over low-power wireless personal area networks (6LoWPAN) introduces an adaptation layer that sits at layer 2.5 (between the link and network layers).
IPv6 Address autoconfiguration
Nodes may autoconfigure an IPv6 address two ways:
—statelessly by combining a 64-b IEEE EUI-64 unique identifier with an IPv6 address prefix (e.g., link local or subnet ID) server,
—by using DHCPv6 to assign an address.
In both cases, the specifications require nodes to verify the address’ uniqueness. Because sensornet subnets are composed of overlapping link-local scopes, a single link-local multicast is not sufficient. Each subnet can avoid the need for multicast by implementing a central IPv6 address registration service that maintains all addresses in use within the subnet. Before using an address, a node must attempt to register an address with the service.
Implementing an IPv6 address registration service would duplicate much of the core function already provided by DHCPv6. A DHCPv6 server maintains entries for all addresses in use within its domain. Nodes obtain a leased address by making requests to the DHCPv6 server and may renew leases over time. If the DHCPv6 server cannot be reached within a single IP hop, neighboring sensornet routers can proxy DHCPv6 messages so that nodes do not have to use a global address before its uniqueness is verified, (Fig. 2).
IPv6 Neighbor discovery
The IPv6 ND protocol supports mechanisms necessary for neighboring IPv6 nodes to communicate, such as discovering each other’s presence, determining each other’s link-layer addresses, discovering neighboring routers, and maintaining reachability information to active neighbors.
IPv6 ND uses a neighbor cache to maintain this neighbor information. The cache’s utility depends on the difference between cache hits and misses. With IPv6 ND, for example, always incurring a cache miss would require an address resolution exchange before sending any unicast transmission. Instead, you can use a neighbor table where nodes can only perform unicast communication with neighbors resident in the neighbor table. The insertion/eviction policies are left to the routing protocol. While limited memory bounds the number of neighbors a node can communicate with, it also makes the energy cost of ND operations predictable.
IPv6 ND resolves IP to link-layer address mappings by sending a link-local multicast query and processing the response from the target neighbor. By using a table rather than a cache, the link-layer address mappings for next-hop neighbors that a node may communicate with are always resident in memory. An explicit query mechanism is not required since there is no possibility of a cache miss. Nodes obtain the link-layer address information from router advertisement (RA) messages sent by neighboring nodes Section V-D.
Neighbor Unreachability Detection (NUD) allows a node to determine if it can successfully send datagrams to IP neighbors. Rather than require a full NS/NA exchange to maintain reachability between routers, use link-layer acknowledgments in place of the NA message. IPv6 ND could not assume the use of link-layer acknowledgments because it is intended for links (like Ethernet) that do not provide such mechanisms, and such mechanisms are usually not sufficient to confirm that the target received the datagram at the IPv6 layer.
IPv6 ND specifies a protocol that allows hosts to discover and maintain default routes. Nodes may multicast a router solicitation (RS) message to the link-local all-routers address, asking for routers to announce themselves more quickly.
Adaptation and header compression
IPv6 requires the link to carry a payload of up to 1280 Bytes. Low-power radio links often do not support such a large payload—an IEEE 802.15.4 frame only supports 127 Bytes of payload and around 80 Bytes in the worst case (with extended addressing and full security information). Additionally, the IPv6 base header, shown in Fig. 3, is relatively large at 40 B. To handle these issues, IPv6 over low-power wireless personal area networks (6LoWPAN) introduces an adaptation layer that sits at layer 2.5 (between the link and network layers). 6LoWPAN defines a header encoding to support fragmentation when IPv6 datagrams do not fit within a single frame and compresses IPv6 headers to reduce header overhead.
Figure 4: This routing protocol helps address resource constraints and low-power wireless characteristics. At a high level, the protocol orients the link topology by constructing a directed acyclic graph (DAG). The roots of the DAG are administratively chosen and are typically nodes that forward the most traffic (such as edge routers). An up route is one that follows an edge toward the root and a down route is one that follows an edge away from the root. By routing along the DAG, all paths take the form of zero, one, or more up routes and zero, one, or more down routes
The fragmentation mechanism is simple and only provides the ability to encode a datagram using multiple link frames. It does not include end-to-end recovery of lost fragments expecting that link-layer acknowledgments will provide sufficient delivery success rates. The fragmentation header is 4–5 B and contains three fields: datagram size indicates the size of the datagram being fragmented, datagram tag identifies all fragments for a particular datagram, and datagram offset indicates the fragment’s location within the datagram. The datagram offset is always elided on the first fragment since its value is always zero.
Traditional header compression techniques used in IP networks are flow based, observing which portions of the header change rarely across packets within a flow and eliding those portions when possible. In sensornets, the path of a flow may change frequently due to time varying dynamics of low-power wireless communication.
When using traditional flow-based techniques, changing a next-hop route would require migrating the compression state to the new route, limiting the effectiveness of header compression. One compression format that does not require per-flow state compacts headers in two ways:
•by removing redundant information across the link, network, and transport layers
•by assuming common values for header fields and defining compact forms of those values
The routing issue for sensornet subnets differs from traditional IP networks for a few reasons:
•Because today’s most widely used links support a single broadcast domain, most existing routing protocols only provide reachability between subnets. However, if sensornet subnets are composed of multiple IP hops, sensornet nodes also need to implement IP routing protocols to communicate within the subnet.
•Resource constraints on sensornet nodes require routing protocols to operate with memory constrained and stale information—energy and channel capacity constrains how often nodes can communicate routing information and perform link quality estimation.
•The wireless topology is time varying and ill-defined. The routing protocol must infer the link topology using measurements generated from actual radio communication.
To address the resource constraints and low-power wireless characteristics, a new protocol orients the link topology by constructing a directed acyclic graph (DAG). The roots of the DAG are administratively chosen and are typically nodes that forward the most traffic (edge routers). Using a DAG allows the routing protocol to minimize resource requirements. State complexity is small and constant because nodes need only maintain up routes to its DAG parents. Communication requirements remain minimal because nodes only propagate DAG topology information towards the DAG root when establishing down routes.
The forwarder is responsible for queuing incoming datagrams, determining the next hop towards the destination, and delivering that datagram to the next hop. Due to resource constraints and the unreliable nature of low-power wireless communication, the IP forwarder must implement hop-by-hop recovery. The two most common reasons for delivery failures are 1) link transmission failures, and 2) queue congestion at the receiver. Both failures can be detected using hop-by-hop acknowledgments that indicate successful reception by the intended receiver.
The forwarder dequeues messages only on positive indication that it was successfully received at the network layer by the next hop. When link transmission failures occur, the forwarder performs another next-hop lookup and resubmits the datagram to the link layer. Doing so allows the forwarder to support rerouting and use forwarding table changes made by the routing protocol in response to transmission failures. When queuing failures occur, the forwarder performs congestion control by slowing the forwarding rate to the same next hop. Because datagrams are not dropped, congested nodes will apply back pressure all the way to the application source if necessary. To handle unforeseen persistent failures, the forwarder may drop datagrams after a large number of consecutive failures.
Always-on (but mostly off) link
IP protocols generally assume that the link is always on. This property simplifies IP protocols because they do not need to worry about scheduling when to deliver datagrams. Multicast simplifies ND and message delivery to arbitrary subsets of neighbors.
While traditional IP links are always on by constantly listening for packets, such idle listening is prohibitively costly in low-power wireless applications. However, by using existing duty-cycling techniques, it is possible to give the illusion that a receiver is always on even while it is actually off more than 99% of the time. The tradeoff is decreased communication throughput and increased communication latency.
Note: The full paper is available at IEEE. Parts were reprinted with permission.
Filed Under: Wireless, Networks • connectivity • fieldbuses, Wireless devices