6lo P. Thubert, Ed.
Internet-Draft Cisco
Updates: 4944 (if approved) Z. Brodard
Intended status: Standards Track Ecole Polytechnique
Expires: December 30, 2016 H. Jiang
G. Texier
Telecom Bretagne
June 28, 2016
A 6loRH for BitStrings
draft-thubert-6lo-bier-dispatch-00
Abstract
This specification extends the 6LoWPAN Routing Header to signal
BitStrings such as utilized in Bit Index Explicit Replication and its
Traffic Engineering variant.
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 December 30, 2016.
Copyright Notice
Copyright (c) 2016 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
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
Thubert, et al. Expires December 30, 2016 [Page 1]
Internet-Draft A 6loRH for BitStrings June 2016
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3
4. The BIER-6LoRH encoding . . . . . . . . . . . . . . . . . . . 4
4.1. The Bit-by-bit BitStrings . . . . . . . . . . . . . . . . 4
4.2. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 5
4.3. Types of BIER-6LoRH header . . . . . . . . . . . . . . . 5
5. Implementation Status . . . . . . . . . . . . . . . . . . . . 6
6. Security Considerations . . . . . . . . . . . . . . . . . . . 6
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 7
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 7
9.1. Normative References . . . . . . . . . . . . . . . . . . 7
9.2. Informative References . . . . . . . . . . . . . . . . . 8
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8
1. Introduction
The type of information that needs to be present in a packet inside
the LLN but not outside of the LLN varies with the routing operation,
but there is overall a need for an extensible compression technique
that would simplify the IP-in-IP encapsulation, when needed, and
optimally compress existing routing artifacts found in LLNs.
The 6LoWPAN Routing Header [I-D.ietf-roll-routing-dispatch] (6LoRH)
specification is such a technique, that extends the 6lo adaptation
layer framework [RFC4944],[RFC6282] so as to carry routing
information for Route-over use cases. The original specification
includes the formats necessary for RPL such as the Source Route
Header (SRH) and is intended to be extended for additional routing
artifacts.
The Bit Index Explicit Replication (BIER), as introduced in the BIER
Architecture [I-D.ietf-bier-architecture], can be used as an
alternate artifact to route multicast as well as unicast traffic.
The Traffic Engineering for Bit Index Explicit Replication
[I-D.eckert-bier-te-arch] (BIER-TE) adds support for traffic
engineering by explicit hop-by-hop forwarding and loose hop
forwarding of packets along a unicast route.
This specification provides additional formats for the 6LoRH
compression to carry BitStrings such as used for Bit Index Explicit
Thubert, et al. Expires December 30, 2016 [Page 2]
Internet-Draft A 6loRH for BitStrings June 2016
Replication and its Traffic Engineering variant (BIER and BIER-TE,
respectively).
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
[RFC2119].
The Terminology used in this document is consistent with and
incorporates that described in Terms Used in Routing for Low-Power
and Lossy Networks (LLNs). [RFC7102].
Other terms in use in LLNs are found in Terminology for Constrained-
Node Networks [RFC7228].
The term "byte" is used in its now customary sense as a synonym for
"octet".
"RPL", "RPL Packet Information" (RPI) and "RPL Instance" are defined
in the RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks
[RFC6550] specification.
The terms Bit-Forwarding Egress Routers (BFR), BFR-id and BitString
are defined in [I-D.ietf-bier-architecture]. A BitString indicates a
continuous sequence of bits indexed by an offset in the sequence.
The leftmost bit is bit 0 and corresponds to the value 0x80 of the
leftmost octet in the BitString.
3. Applicability
BIER and other bit-indexed methods that would leverage BitStrings
will generally require additional information in the packet to
complement the BitString. For instance, BIER has the concept of a
BFR-id and an Entropy value in the BIER header. Since those
additional fields depend on the bit-indexed method, they are expected
to be transported separately from the BitString. This specification
concentrates on the BitString alone.
The DetNet Data Plane Protocol and Solution Alternatives
[I-D.dt-detnet-dp-alt] document details how BIER-TE can be leveraged
to activate the Deterministic Networking Replication and Elimination
functions in a manner that is abstract to the data plane forwarding
information. An adjacency, which is represented by a bit in the BIER
header, can be mapped in the data plane to an Ethernet hop, a Label
Switched Path, or it may correspond to a loose or a strict IPv6
Source Routed Path.
Thubert, et al. Expires December 30, 2016 [Page 3]
Internet-Draft A 6loRH for BitStrings June 2016
In the context of LLNs, the 6TiSCH Architecture
[I-D.ietf-6tisch-architecture] introduces the concept of a Track that
is a directional traffic-engineered path between a source and a
destination. A Track is indicated in a packet by a Source or
Destination IPv6 Address and a RPL Local Instance. The RPL Instance
is carried in an IPv6 packet as part of the RPL Packet Information
(RPI), and a bit in the RPI indicates whether the Instance is Local
to the Source or the Destination Address. The RPI can be compressed
as a RPI 6LoRH header (RPI-6LoRH) as described in
[I-D.ietf-roll-routing-dispatch].
The 6TiSCH requirements for DetNet [I-D.thubert-6tisch-4detnet]
indicate that a 6TiSCH Track may leverage replication and elimination
as defined in DetNet. This specification enables this behavior as
follows: if a BIER-6LoRH is positioned right after a RPI-6LoRH, then
the BitString in the BIER-6LoRH applies to the context of the Track
indicated by the source or destination address of the packet and the
local Instance ID associated to the source or destination of the
packet.
4. The BIER-6LoRH encoding
The BIER 6LoRH (BIER-6LoRH) is a Critical 6LoWPAN Routing Header that
provides a variable-size container for a BitString such as, a but not
limited to, a BIER BitString.
The capability to parse the BIER BitString is necessary to forward
the packet so the Type cannot be ignored.
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+
|1|0|0| Control |6LoRHType 15-19| BitString |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+
Figure 1: The BIER-6LoRH
This specification provides a 5-bit Control field that can be used to
encode information that is specific to the BitString. The type and
size of the BitString are encoded in the 6LoRHType.
4.1. The Bit-by-bit BitStrings
In the bit-by-bit case, each bit is mapped in an unequivocal fashion
with a single addressable resource in the network. This may rapidly
lead to large BitStrings, and BIER allows to divide a network into
groups that partition the network so that a given BitString is
Thubert, et al. Expires December 30, 2016 [Page 4]
Internet-Draft A 6loRH for BitStrings June 2016
locally significant to one group only. This specification uses the
5-bits Control field to encode the group.
When groups are used, it may be that a packet is sent to different
groups at the same time. In that case, multiple BIER-6LoRH headers
can be prepended to a same packet, each one for a different group.
As the packet flows along the multicast distribution tree, a BIER-
6LoRH header that has no more destination in a given branch may be
removed to make the packet shorter.
4.2. Bloom Filters
A Bloom Filter can be seen as a compression technique for the
BitString. A Bloom Filter may generate false positives, which, in
the case of BIER, result in undue forwarding of a packet down a path
where no listener exists.
As an example, the Constrained-Cast [I-D.bergmann-bier-ccast]
specification employs Bloom Filters as a compact representation of a
match or non-match for elements in a set that may be larger than the
number of bits in the BitString.
In the case of a Bloom Filter, a number of Hash functions must be run
to obtain a multi-bit signature of an encoded element. This
specification uses the 5-bits Control field to signal an Identifier
of the set of Hash functions being used to generate a certain
BitString, so as to enable the migration from a set of Hash functions
to the next.
4.3. Types of BIER-6LoRH header
The Type of a BIER-6LoRH header indicates the size of words used to
build the BitString and whether the BitString is operated as an
uncompressed bit-by-bit mapping, or as a Bloom filter.
Thubert, et al. Expires December 30, 2016 [Page 5]
Internet-Draft A 6loRH for BitStrings June 2016
+---------+--------------+----------------------+----------------+
| Type | Encoding | Control field | BitString Size |
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| 15 | bit-by-bit | Group ID | 8 bits |
| 16 | bit-by-bit | Group ID | 16 bits |
| 17 | bit-by-bit | Group ID | 32 bits |
| 18 | bit-by-bit | Group ID | 64 bits |
| 19 | bit-by-bit | Group ID | 128 bits |
+---------+--------------+----------------------+----------------+
| 20 | Bloom filter | Hash function Set ID | 8 bits |
| 21 | Bloom filter | Hash function Set ID | 16 bits |
| 22 | Bloom filter | Hash function Set ID | 32 bits |
| 23 | Bloom filter | Hash function Set ID | 64 bits |
| 24 | Bloom filter | Hash function Set ID | 128 bits |
+---------+--------------+----------------------+----------------+
Figure 2: The BIER-6LoRH Types
In order to address a potentially large number of devices, the
BitString may grow very large. Yet, the maximum frame size for a
given MAC layer may limit the number of bits that can be dedicated to
routing. With this specification, a number of BIER-6LoRH headers of
a same type (bit-by-bit or Bloom filter) may be placed contiguously
in the packet. This results in a larger BitString that is the
concatenation of the BitStrings in the individual headers in the
order they are appearing in the packet.
5. Implementation Status
A research implementation was developed at Cisco's Paris Innovation
Lab (PIRL) by Zacharie Brodard.
The implementation is based on openWSN
(https://openwsn.atlassian.net/wiki/pages/
viewpage.action?pageId=688187), and was tested on OpenMote hardware
(http://www.openmote.com/).
The implementation covers 6LoRH Types 15 to 18 for 6TiSCH Tracks, and
does not attempt to support Bloom Filters.
6. Security Considerations
The security considerations of [I-D.ietf-roll-routing-dispatch]
apply.
Thubert, et al. Expires December 30, 2016 [Page 6]
Internet-Draft A 6loRH for BitStrings June 2016
7. IANA Considerations
This document extends the IANA registry created by
[I-D.ietf-roll-routing-dispatch] for the 6LoWPAN Routing Header Type,
and adds the following values:
15..24 : BIER-6LoRH [RFCthis]
8. Acknowledgments
9. References
9.1. Normative References
[I-D.ietf-roll-routing-dispatch]
Thubert, P., Bormann, C., Toutain, L., and R. Cragie,
"6LoWPAN Routing Header", draft-ietf-roll-routing-
dispatch-00 (work in progress), March 2016.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
[RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler,
"Transmission of IPv6 Packets over IEEE 802.15.4
Networks", RFC 4944, DOI 10.17487/RFC4944, September 2007,
<http://www.rfc-editor.org/info/rfc4944>.
[RFC6550] Winter, T., Ed., Thubert, P., Ed., 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,
DOI 10.17487/RFC6550, March 2012,
<http://www.rfc-editor.org/info/rfc6550>.
[RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and
Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January
2014, <http://www.rfc-editor.org/info/rfc7102>.
[RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for
Constrained-Node Networks", RFC 7228,
DOI 10.17487/RFC7228, May 2014,
<http://www.rfc-editor.org/info/rfc7228>.
Thubert, et al. Expires December 30, 2016 [Page 7]
Internet-Draft A 6loRH for BitStrings June 2016
9.2. Informative References
[I-D.bergmann-bier-ccast]
Bergmann, O., Bormann, C., Gerdes, S., and H. Chen,
"Constrained-Cast: Source-Routed Multicast for RPL",
draft-bergmann-bier-ccast-01 (work in progress), April
2016.
[I-D.dt-detnet-dp-alt]
Korhonen, J., Farkas, J., Mirsky, G., Thubert, P.,
Zhuangyan, Z., and L. Berger, "DetNet Data Plane Protocol
and Solution Alternatives", draft-dt-detnet-dp-alt-00
(work in progress), March 2016.
[I-D.eckert-bier-te-arch]
Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Traffic
Engineering for Bit Index Explicit Replication BIER-TE",
draft-eckert-bier-te-arch-03 (work in progress), March
2016.
[I-D.ietf-6tisch-architecture]
Thubert, P., "An Architecture for IPv6 over the TSCH mode
of IEEE 802.15.4", draft-ietf-6tisch-architecture-10 (work
in progress), June 2016.
[I-D.ietf-bier-architecture]
Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and
S. Aldrin, "Multicast using Bit Index Explicit
Replication", draft-ietf-bier-architecture-03 (work in
progress), January 2016.
[I-D.thubert-6tisch-4detnet]
Thubert, P., "6TiSCH requirements for DetNet", draft-
thubert-6tisch-4detnet-01 (work in progress), June 2015.
[RFC6282] Hui, J., Ed. and P. Thubert, "Compression Format for IPv6
Datagrams over IEEE 802.15.4-Based Networks", RFC 6282,
DOI 10.17487/RFC6282, September 2011,
<http://www.rfc-editor.org/info/rfc6282>.
Authors' Addresses
Thubert, et al. Expires December 30, 2016 [Page 8]
Internet-Draft A 6loRH for BitStrings June 2016
Pascal Thubert (editor)
Cisco Systems
Village d'Entreprises Green Side
400, Avenue de Roumanille
Batiment T3
Biot - Sophia Antipolis 06410
FRANCE
Phone: +33 4 97 23 26 34
Email: pthubert@cisco.com
Zacharie Brodard
Ecole Polytechnique
Route de Saclay
Palaiseau 91128
FRANCE
Phone: +33 6 73 73 35 09
Email: zacharie.brodard@polytechnique.edu
Hao Jiang
Telecom Bretagne
2, rue de la Chataigneraie
Cesson-Sevigne 35510
FRANCE
Phone: +33 7 53 70 97 34
Email: hao.jiang@telecom-bretagne.eu
Geraldine Texier
Telecom Bretagne
2, rue de la Chataigneraie
Cesson-Sevigne 35510
FRANCE
Phone: +33 2 99 12 70 38
Email: geraldine.texier@telecom-bretagne.eu
Thubert, et al. Expires December 30, 2016 [Page 9]