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]