Internet DRAFT - draft-krol-core-featurecast
draft-krol-core-featurecast
Network Working Group M. Krol
Internet-Draft F. Rousseau
Intended status: Informational A. Duda
Expires: May 17, 2015 Grenoble Institute of Technology
November 25, 2014
Featurecast: Data-Centric Group Communication
draft-krol-core-featurecast-00
Abstract
This document presents Featurecast, a group communication service in
which addressing and routing are based on node features defined as
predicates. For instance, one can send a packet to the address
composed of features [ temperature and Room D ] to reach all nodes
with a temperature sensor located in Room D. Each node constructs its
address from the set of its features and disseminates the features in
the network so that intermediate nodes can build routing tables.
With Featurecast, a node can send a packet to a set of nodes matching
given features. Featurecast fits into IPv6 address field without any
additional headers.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 17, 2015.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
Krol, et al. Expires May 17, 2015 [Page 1]
Internet-Draft Featurecast November 2014
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Conventions used in this document . . . . . . . . . . . . . 3
2. Featurecast . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. Featurecast Address . . . . . . . . . . . . . . . . . . . . 4
2.2. Compact Representation of Features . . . . . . . . . . . . 5
2.2.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2. Compact Representations . . . . . . . . . . . . . . . . . 6
3. Featurecast Routing . . . . . . . . . . . . . . . . . . . . . 7
3.1. Collection Tree . . . . . . . . . . . . . . . . . . . . . . 7
3.2. Constructing Routing Tables . . . . . . . . . . . . . . . . 7
3.3. Forwarding . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4. Topology Maintenance . . . . . . . . . . . . . . . . . . . 8
3.5. Featurecast Control Messages . . . . . . . . . . . . . . . 8
3.5.1. Feature Advertisement . . . . . . . . . . . . . . . . . . 9
3.5.2. Feature Disconnect . . . . . . . . . . . . . . . . . . . 9
4. Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Normative References . . . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11
1. Introduction
This document introduces Featurecast, a network layer group
communication service well suited for sensor networks. Featurecast
supports data-centric group communication in which addresses
correspond to a set of features characterizing sensor nodes.
Features are defined as predicates, so we can represent them in a
compact way in address fields and in routing tables. To create
routing tables, every node in the network defines a set of its
features and advertise them in the network. Applications can then
use Featurecast to send a packet to a group of nodes matching the
features: e.g. [ 4th floor and temperature ] or [ light and sector A
]. Featurecast constructs routing tables based on single elements
(building A, 4th floor) and not on their combination (temperature on
the 1st floor in building A), which significantly reduces overhead
and memory usage. The size of routing tables only depends on the
number of features and not on the size of the network.
Featurecast closely reflects the relationships between sensors,
actuators, and the real world. Nodes can freely create and define
Krol, et al. Expires May 17, 2015 [Page 2]
Internet-Draft Featurecast November 2014
features that may be specific to a particular application or a given
deployment scenario. There is no need for any central repository or
a feature mapping service. Close coupling between features and
addresses relieves application developers from the use of name
services such as DNS, because an address is derived from a set of
features and conveys high level semantics that would otherwise be
represented using names. Featurecast extends the standard notion of
multicast with a more general definition of groups: instead of one
address representing a multicast group, a Featurecast address defines
a group membership based on a set of features. With Featurecast, a
node has implicitly an address for every subset of its features. So
a node defining "building A" and "temperature" may receive packets
sent to the address representing "building A", "temperature", and
"temperature in building A".
Featurecast takes advantage Bloom Filters and hashing, does not
define any specific grammar for features, which makes it extremely
flexible and easy to use. Featurecast uses a specific compact
encoding allowing for fitting a feature address into the multicast
IPv6 address field.
1.1. Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
Feature - a single element of Featurecast addresses representing a
node characteristic such as "temperature" or "building A".
Bloom Filter - probabilistic data structure for compact
representation of a set of elements. To insert an element into a
filter, we compute one or several hash functions on the element and
set all the resulting bits to 1. To check whether an element belongs
to the set, we compute the same hash functions on the element and
check if all corresponding bit positions are set to 1.
Collection Tree - Directed Oriented Acyclic Graph connecting all
nodes in the networks.
Merged Element - a list containing all features defined on the node
and all features available through this node.
Krol, et al. Expires May 17, 2015 [Page 3]
Internet-Draft Featurecast November 2014
2. Featurecast
Featurecast defines a group communication service for wireless sensor
networks in which we usually want to designate relevant sensor nodes
or data sources by means of their characteristics and not with low
level identifiers or addresses. For instance, we may want to get the
"average temperature on the 1st floor" or send a command to "turn off
all the lights in the building". Such reasoning is close to
applications that take advantage of sensors and actuators.
Obviously, we could support such messages by associating a multicast
group with each query, however, the number of such groups may quickly
become too large, because of all possible combinations of
characteristics. We introduce below the notion of Featurecast
addresses, present the construction of routing tables, and the
forwarding process.
2.1. Featurecast Address
We assume that each sensor defines a set of its features, for
instance its capability of sensing the environment (temperature,
humidity), location ("sector 5", "1st floor"), state (low-energy), or
some other custom features (my favorite nodes). Features are
predicates, i.e., statements that may be true or false (in the
previous examples, we explicitly stated features that are true).
Predicates are commonly used to represent the properties of objects
and we use them here to represent the properties of sensors: if f is
a predicate on sensor X, we say that f is a property of sensor X.
Note that features are not attributes (i.e., name:value pairs), which
allows us to represent them in a much more compact way without
loosing any flexibility. We assume that there is no coordination in
defining features, but all features are known and each node can
define its features at will. A sensor node derives its Featurecast
address from its features. More formally, a node address is the set:
A = {f_1 , f_2 , ..., f_n }, f_i belongs to F, where f_i is a feature
predicate and F is the set of all possible features with cardinality
of N. Features in the network may evolve in time and nodes may change
their features, for instance the location of a node may change when
it moves or a sensor may define a state of high temperature when
exceeding a given threshold. Note that N, the total number of
features in the network does not depend on the number of nodes, but
rather on applications that define node characteristics. A
destination address may contain a subset of features-we say that it
matches a node address, if the node address contains the destination
address: with D = {f_1 , f_2 , ..., f_k }, f_i belonging to F, D
matches A, if D is in A. For instance, a packet to [ temperature, 1st
floor ] will match nodes defining both "temperature" and "1st floor"
in their addresses. We can consider the node address as a
representative of all possible multicast groups that would be created
Krol, et al. Expires May 17, 2015 [Page 4]
Internet-Draft Featurecast November 2014
based on the node features to make it reachable for any combination
of features using the traditional multicast groups. Note that this
definition is significantly different from the IP multicast in which
we have to create a group for every combination of features and not
only for every feature. Featurecast uses IPv6 header format
[RFC2460]. Encoded features are stored in the Destination Address
field. The Featurecast Prefix field MUST be set to ff0f.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| Traffic Class | Flow Label |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Payload Length | Next Header |Hop Limit |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Source Address +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Featurecast Prefix | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| |
+ Encoded Features +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1
2.2. Compact Representation of Features
2.2.1. Requirements
Featurecast addresses need to be represented in a compact way, but at
the same time, we wanted an open network able to accept any feature
defined on the nodes. Moreover, the addressing scheme should not
depend on the number of features defined in the network, because we
do not want to force the user to define a hierarchy of features.
Most of data-centric approaches use a grammar exchanged in a text
form, which may raise issues when integrating such solutions into
real life scenarios. We also wanted our approach to still use user
friendly addresses, while being easily stored and processed by nodes
and we need fixed-length addresses for efficient forwarding and
possibility to integrate Featurecast within the standard IPv6
addressing scheme with 112 bits in the multicast IPv6 address. Such
Krol, et al. Expires May 17, 2015 [Page 5]
Internet-Draft Featurecast November 2014
integration will show that even data-centric approaches can have the
same overhead as address-centric solutions and allow easy integration
with existing networks. A part of such an IPv6 address can be
designed for a global prefix, which can be routed in the Internet.
Finally, we wanted to take into account resource constraints (memory
size) of sensor nodes for storing routing tables and avoid global
synchronization mechanisms disseminating a mapping between features
and their binary representation. Such a solution would require a
significantly higher volume of communications and could delay packet
forwarding during the feature update.
2.2.2. Compact Representations
For encoding Featurecast addresses, we propose to take advantage of
Bloom Filters [bf_survey]. Featurecast uses 112 least significant
bits of the IPv6 address as a Bloom Filter with 2 hash functions. At
the beginning, a Bloom Filter MUST be empty, it means all bits shall
be set to 0. Every feature we want to put into the address MUST be
hashed using both hash functions. The output from each hash function
indicates which bit in the Bloom Filter shall be set to 1. If a bit
was already set to 1 by previous features, it MUST NOT be changed.
For routing tables, Featurecast needs to store much more features
than in the address field, because potentially all features defined
in the network may appear in a routing table. We propose an encoding
in which each feature is hashed using the same 2 hash functions as
for the Featurecast address and we store the resulting Bloom Filter
in the form of two numbers (1-112) indicating positions in the
corresponding Bloom Filter. For example, a feature that sets bits on
positions 5 and 76 in the Bloom Filter, will be represented by these
two numbers in the routing table. A node compares the bit positions
in the entry of the routing table with the bits set in the packet
destination address. In the routing table, each entry contains a
neighbor ID and corresponding set of features. Figure 2 presents the
compact feature representation. "Building A" after being hashed sets
the 6th and 7th bit in the node address, thus in the routing tables
it is represented by numbers 6 and 7. In the same way "temperature"
sets the 2nd and 9th bit in the filter, while being represented by
those two numbers in the routing table.
+-+-+-+-+
----------------- "building A" ------------ | 6 | 7 |
| | +-+-+-+-+
0 1 0 0 0 1 1 0 1 0 0
| | +-+-+-+-+
------------------------- "temperature" ----------- | 2 | 9 |
+-+-+-+-+
Node Address Routing Table
Krol, et al. Expires May 17, 2015 [Page 6]
Internet-Draft Featurecast November 2014
Figure 2
3. Featurecast Routing
3.1. Collection Tree
Featurecast builds upon an existing unicast routing structure, a
Collection Tree constructed for instance with RPL [RFC6550]. It can
work on top of any protocol providing such a structure. Featurecast
can work with multiple Collection Trees, e.g. multiple RPL instances
created by different sinks.
3.2. Constructing Routing Tables
Forwarding packets based on Featurecast addresses requires the
construction of routing tables. A node needs to maintain a list of
all features it knows about associated with children nodes through
which a given feature is reachable. Nodes create routing tables
based on feature advertisements that propagate in the network
following the Collection Tree.
+-+-+-+-+-+-+-+
|Temperature | -> Node 1, Node 2
+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+
|Building A | -> Node 2, Node 3
+-+-+-+-+-+-+-+
Figure 3
After receiving an advertisement from a child, a node adds the
features from the advertisement to the routing table with the sender
ID. If a feature already exists in the routing table, the parent
simply adds the sender ID to the feature entry. The routing table
only contains single features reachable through a given neighbor and
not their combinations. Figure 4 presents an example: Node 4
maintains an entry for each feature reachable through Node 3. Every
node maintains also a special Merged Entry (ME) that contains all
features defined by the node and all features reachable through its
children.
+-+-+-+
1 |A, B |
+-+-+-+ --> +-+-+-+ +-+-+-+
3 |A, C | --> 4 | C, D|
+-+-+-+ --> +-+-+-+ +-+-+-+
2 |B, C | A -> 3
Krol, et al. Expires May 17, 2015 [Page 7]
Internet-Draft Featurecast November 2014
+-+-+-+ B -> 3
C -> 3
Figure 4
3.3. Forwarding
When features have propagated in the network and routing tables
contain the information on features, nodes can send packets to
Featurecast addresses. The destination address is a Bloom Filter
with a set of features that intermediate nodes look up in the routing
tables. They interpret the address as a conjunction of all features
and forward the packet to all neighbors advertising all features
present in the address.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Temperature |Building A |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+
|Temperature | -> Node 1, Node 2
+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+
|Building A | -> Node 2, Node 3
+-+-+-+-+-+-+-+
Figure 5
In the example in Figure 5, both "Temperature" and "Building A" are
present in the destination address. However, only "Node 2"
advertises both of them, so the packet will be forwarded only to
"Node 2". As a result, the destination will receive a given packet
if its address contains all features in the destination address.
3.4. Topology Maintenance
It is possible that some neighbors of a sensor nodes disconnect due
to topology changes, node failures, or battery depletion. For
detecting disconnected peers and maintain a valid topology,
Featurecast relies on the feedback from layer 2. If a packet cannot
be transmitted to a neighbor, Featurecast deletes the information
involving the neighbor from its routing table.
3.5. Featurecast Control Messages
Krol, et al. Expires May 17, 2015 [Page 8]
Internet-Draft Featurecast November 2014
Featurecast encapsulates its messages in ICMPv6 packets with the type
value set to 160. Featurecast uses two types of messages to
construct and maintain routing tables.
3.5.1. Feature Advertisement
The process of advertising features starts at leaf nodes that send
their features to their preferred parent. Parents obtain the
features from their children nodes, add their own features, and
forward the list of features reachable through them to their own
parent. The process continues up to the root of the Collection Tree.
Finally, the root node obtains the list of all features in the
network and it can use it to forward packets to relevant neighbors.
The sink can also initialize the process in the reverse direction by
sending its features to children nodes, which speeds up machine-to-
machine communication. When a node receives an advertisement with
features already in its routing table, it does not forward it to its
neighbors and ignores subsequent advertisements, so most of the
changes in features will only result in localized transmissions.
The Feature Advertisement message contains the type set to 0, the
number of features in the message, and the list of encoded features
represented as two 1 byte numbers indicating positions in the Bloom
Filter. Nodes resend Feature Advertisements when a new parent in the
Collection Tree is chosen and after any modification of its Merged
Element.
A node receiving an advertisement MUST replace the older entries with
the information from the most recent message.
0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
|Type |Number of features |Encoded features
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
Figure 6
3.5.2. Feature Disconnect
The message contains only the type set to 1. Feature Disconnect
SHOULD be sent to the previous parent (if any), when a new parent is
chosen. After receiving the message, the parent deletes from its
routing table the routing entries advertised by the given neighbor.
0
0 1 2 3 4 5 6 7
Krol, et al. Expires May 17, 2015 [Page 9]
Internet-Draft Featurecast November 2014
+-+-+-+-+-+-+-+-+
|Type |
+-+-+-+-+-+-+-+-+
Figure 7
The protocol that constructs the Collection Tree MUST inform
Featurecast after choosing a new preferred parent, so that
Featurecast can send Feature Advertisement and Feature Disconnect
messages. The Collection Tree protocol MUST inform Featurecast after
a neighbor failure/disconnection, so that the corresponding entry can
be deleted from the routing table.
A node MUST send a Feature Advertisement after changing its preferred
parent in the Collection Tree and after any modification of its
Merged Element. After any modification of the routing table or
features defined directly on the node, the node MUST rebuild its
Merged Entry. If it was modified, a Feature Advertisement MUST be
sent to its preferred parent.
4. Use Cases
Rahman et al. defined how CoAP should be used in a group
communication context when assuming support for IPv6 multicast at the
network layer [draft-ietf-core-groupcomm-25].
However, even in small networks with a small number of rooms/
buildings/floors, one will need a huge number of multicast groups to
provide all possible combinations ("sensors in room 1", "temperature
sensors on 1st floor in building A" etc.), which is impossible with a
limited amount of sensor resources. For example in a scenario with 2
buildings, 4 floors, 2 wings, and 4 rooms, one needs 225 IP multicast
groups, while Featurecast requires only 12 features.
URI authority Targeted group of nodes
--------------------------------------- --------------------------
all.bldg6.example.com "all nodes in building 6"
all.west.bldg6.example.com "all nodes in west wing,
building 6"
all.floor1.west.bldg6.example.com "all nodes in floor 1,
west wing, building 6"
all.bu036.floor1.west.bldg6.example.com "all nodes in office bu036,
floor1, west wing, building 6"
Figure 8
To establish COAP communication, every node has an assigned URI such
as "node1.bu036.floor1.west.bldg6.example.com" (node1 in office
Krol, et al. Expires May 17, 2015 [Page 10]
Internet-Draft Featurecast November 2014
bu036, floor1, west wing, building 6). To follow the same scenario
under Featurecast, sensors can decompose such an URI and put each
element separately into its own Featurecast address as illustrated in
Figure 9.
node1.bu036.floor1.west.bldg6.example.com
| | | | | | |
\|/ \|/ \|/ \|/ \|/ \|/ \|/
* * * * * * *
+-++-+-+-+-+-++-+-+-+-+-+-+-++-+-+-+-+-+-
| Featurecast Address |
+-+-+-+-+-+-+-++-+-+-+-+-+-+-++-+-+-+-+-+-
Figure 9
Nodes can define multiple URIs. If one wants to send a packet to all
nodes in building 6, one has to specify the URI "bldg6.example.com",
translate it into a Featurecast address using Bloom Filters, and send
the packet to the destination address.
5. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,
Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.
Alexander, "RPL: IPv6 Routing Protocol for Low-Power and
Lossy Networks", RFC 6550, March 2012.
[RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", RFC 2460, December 1998.
[draft-ietf-core-groupcomm-25]
Rahman, A. and E. Dijk, "Group Communication for CoAP",
draft 1113, September 2014.
[bf_survey]
Mitzenmacher, M., "Network Applications of Bloom Filters:
A Survey", Annual Allerton Conference on Communication,
Control, and Computing 2002, 2002.
Authors' Addresses
Krol, et al. Expires May 17, 2015 [Page 11]
Internet-Draft Featurecast November 2014
Michal Krol
Grenoble Institute of Technology
681 rue de la Passerelle
Saint Martin D'Heres 38400
France
Email: Michal.Krol@imag.fr
Franck Rousseau
Grenoble Institute of Technology
681 rue de la Passerelle
Saint Martin D'Heres 38400
France
Email: Franck.Rousseau@imag.fr
Andrzej Duda
Grenoble Institute of Technology
681 rue de la Passerelle
Saint Martin D'Heres 38400
France
Email: Andrzej.Duda@imag.fr
Krol, et al. Expires May 17, 2015 [Page 12]
