6lo                                                      P. Thubert, Ed.
Internet-Draft                                                     Cisco
Intended status: Standards Track                              Z. Brodard
Expires: August 1, 2019                              Ecole Polytechnique
                                                                H. Jiang
                                                               G. Texier
                                                        Telecom Bretagne
                                                        January 28, 2019


                         A 6loRH for BitStrings
                   draft-thubert-6lo-bier-dispatch-06

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 https://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 August 1, 2019.

Copyright Notice

   Copyright (c) 2019 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
   (https://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 August 1, 2019                 [Page 1]


Internet-Draft           A 6loRH for BitStrings             January 2019


   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.  The Enumeration BitStrings  . . . . . . . . . . . . . . .   5
     4.3.  Bloom Filters . . . . . . . . . . . . . . . . . . . . . .   5
     4.4.  Types of BIER-6LoRH header  . . . . . . . . . . . . . . .   6
   5.  Implementation Status . . . . . . . . . . . . . . . . . . . .   8
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   8
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   8
   8.  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .   8
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .   8
     9.2.  Informative References  . . . . . . . . . . . . . . . . .   9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  10

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 (6LoRH) [RFC8025] [RFC8138] 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 [RFC8279], 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
   Replication and its Traffic Engineering variant (BIER and BIER-TE,
   respectively).



Thubert, et al.          Expires August 1, 2019                 [Page 2]


Internet-Draft           A 6loRH for BitStrings             January 2019


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 [RFC8279].  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 and a group identifier which enables a
   network to grow beyond the size of one bitString.

   Within the context of "the Deterministic Networking (DetNet)
   Architecture" [I-D.ietf-detnet-architecture] ), the "BIER-TE-based
   OAM, Replication and Elimination"
   [I-D.thubert-bier-replication-elimination] 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 August 1, 2019                 [Page 3]


Internet-Draft           A 6loRH for BitStrings             January 2019


   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 [RFC8138].

   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-29|  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 August 1, 2019                 [Page 4]


Internet-Draft           A 6loRH for BitStrings             January 2019


   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.

   The encoding value indicates the size of the BitString.  The size of
   the BitString used in a given packet is smallest that can represent
   all of the bits that are set for this particular packet, so for a
   same network various sizes may be used for different packets
   depending on the destinations.

4.2.  The Enumeration BitStrings

   For unicast and when very few destinations are targeted for a given
   message, it may be that it is more economical to list the bit offsets
   one by one than it is to represent the full BitString that can hold
   all of the bit offsets.

   In the Enumeration case, a BitString actually encodes the offset of
   one bit as an unsigned integer, using the number of bits indicated in
   the control field, and BitStrings are concatenated without
   intermediate padding.  The overall concatenation must be aligned to a
   byte boundary.  To achieve this, trailing bits are added to the right
   of the concatenation as padding to the next byte boundary.

   To optimize the compression, the lower numbers can be expressed with
   less bits, and multiple Enumeration BIER-6LoRH headers may be used to
   encode offsets that require different numbers of bits for their
   representation.

4.3.  Bloom Filters

   A Bloom Filter can be seen as an additional compression technique for
   the bitString representation.  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.ietf-roll-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.





Thubert, et al.          Expires August 1, 2019                 [Page 5]


Internet-Draft           A 6loRH for BitStrings             January 2019


   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.4.  Types of BIER-6LoRH header

   The Type of a BIER-6LoRH header indicates the size of the BitString
   and whether the BitString is operated as an uncompressed bit-by-bit
   mapping, as an enumeration, or as a Bloom filter.







































Thubert, et al.          Expires August 1, 2019                 [Page 6]


Internet-Draft           A 6loRH for BitStrings             January 2019


   +--------------+--------------+----------------------+--------------+
   |  BitString   |   Encoding   |    Control field     |  BitString   |
   |     Type     |              |                      |     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       |   56 bits    |
   +--------------+--------------+----------------------+--------------+
   |      19      |  bit-by-bit  |       Group ID       |   96 bits    |
   +--------------+--------------+----------------------+--------------+
   |      20      |  bit-by-bit  |       Group ID       |   160 bits   |
   +--------------+--------------+----------------------+--------------+
   |      21      |  bit-by-bit  |       Group ID       |   256 bits   |
   +--------------+--------------+----------------------+--------------+
   |      22      | Enumeration  |  Number of elements  |    4 bits    |
   +--------------+--------------+----------------------+--------------+
   |      23      | Enumeration  |  Number of elements  |    6 bits    |
   +--------------+--------------+----------------------+--------------+
   |      24      | Enumeration  |  Number of elements  |    8 bits    |
   +--------------+--------------+----------------------+--------------+
   |      25      | Bloom filter | Hash function Set ID |    8 bits    |
   +--------------+--------------+----------------------+--------------+
   |      26      | Bloom filter | Hash function Set ID |   16 bits    |
   +--------------+--------------+----------------------+--------------+
   |      27      | Bloom filter | Hash function Set ID |   48 bits    |
   +--------------+--------------+----------------------+--------------+
   |      28      | Bloom filter | Hash function Set ID |   96 bits    |
   +--------------+--------------+----------------------+--------------+
   |      29      | Bloom filter | Hash function Set ID |   160 bits   |
   +--------------+--------------+----------------------+--------------+

                       Table 1: 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.






Thubert, et al.          Expires August 1, 2019                 [Page 7]


Internet-Draft           A 6loRH for BitStrings             January 2019


5.  Implementation Status

   A research-stage implementation was developed at Cisco's Paris
   Innovation Lab (PIRL) by Zacharie Brodard.  It was implemented on
   OpenWSN open-source firmware and tested on the OpenMote-CC2538
   hardware.  It implements the header types 15, 16, 17, 18 and 19 (bit-
   by-bit encoding without group ID) in order to allow a BIER-TE
   protocol over IEE802.15.4e.

   Links:

      github: https://github.com/zach-b/openwsn-fw/tree/BIER

      OpenWSN firmware: https://openwsn.atlassian.net/wiki/pages/
      viewpage.action?pageId=688187

      OpenMote hardware: http://www.openmote.com/

6.  Security Considerations

   The security considerations of [RFC8138] apply.

7.  IANA Considerations

   This document extends the IANA registry created by [RFC8138] for the
   6LoWPAN Routing Header Type, and adds the following values:

      15..29 : BIER-6LoRH [RFCthis]

8.  Acknowledgments

9.  References

9.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://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,
              <https://www.rfc-editor.org/info/rfc4944>.







Thubert, et al.          Expires August 1, 2019                 [Page 8]


Internet-Draft           A 6loRH for BitStrings             January 2019


   [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,
              <https://www.rfc-editor.org/info/rfc6550>.

   [RFC8025]  Thubert, P., Ed. and R. Cragie, "IPv6 over Low-Power
              Wireless Personal Area Network (6LoWPAN) Paging Dispatch",
              RFC 8025, DOI 10.17487/RFC8025, November 2016,
              <https://www.rfc-editor.org/info/rfc8025>.

   [RFC8138]  Thubert, P., Ed., Bormann, C., Toutain, L., and R. Cragie,
              "IPv6 over Low-Power Wireless Personal Area Network
              (6LoWPAN) Routing Header", RFC 8138, DOI 10.17487/RFC8138,
              April 2017, <https://www.rfc-editor.org/info/rfc8138>.

   [RFC8279]  Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A.,
              Przygienda, T., and S. Aldrin, "Multicast Using Bit Index
              Explicit Replication (BIER)", RFC 8279,
              DOI 10.17487/RFC8279, November 2017,
              <https://www.rfc-editor.org/info/rfc8279>.

9.2.  Informative References

   [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-06 (work in progress), November
              2017.

   [I-D.ietf-6tisch-architecture]
              Thubert, P., "An Architecture for IPv6 over the TSCH mode
              of IEEE 802.15.4", draft-ietf-6tisch-architecture-19 (work
              in progress), December 2018.

   [I-D.ietf-detnet-architecture]
              Finn, N., Thubert, P., Varga, B., and J. Farkas,
              "Deterministic Networking Architecture", draft-ietf-
              detnet-architecture-10 (work in progress), December 2018.

   [I-D.ietf-roll-ccast]
              Bergmann, O., Bormann, C., Gerdes, S., and H. Chen,
              "Constrained-Cast: Source-Routed Multicast for RPL",
              draft-ietf-roll-ccast-01 (work in progress), October 2017.






Thubert, et al.          Expires August 1, 2019                 [Page 9]


Internet-Draft           A 6loRH for BitStrings             January 2019


   [I-D.thubert-6tisch-4detnet]
              Thubert, P., "6TiSCH requirements for DetNet", draft-
              thubert-6tisch-4detnet-01 (work in progress), June 2015.

   [I-D.thubert-bier-replication-elimination]
              Thubert, P., Eckert, T., Brodard, Z., and H. Jiang, "BIER-
              TE extensions for Packet Replication and Elimination
              Function (PREF) and OAM", draft-thubert-bier-replication-
              elimination-03 (work in progress), March 2018.

   [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,
              <https://www.rfc-editor.org/info/rfc6282>.

   [RFC7102]  Vasseur, JP., "Terms Used in Routing for Low-Power and
              Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January
              2014, <https://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,
              <https://www.rfc-editor.org/info/rfc7228>.

Authors' Addresses

   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





Thubert, et al.          Expires August 1, 2019                [Page 10]


Internet-Draft           A 6loRH for BitStrings             January 2019


   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 August 1, 2019                [Page 11]