< draft-thubert-roll-bier-00.txt   draft-thubert-roll-bier-01.txt >
ROLL P. Thubert, Ed. ROLL P. Thubert, Ed.
Internet-Draft Cisco Internet-Draft Cisco
Updates: 6282,6550,6775 (if approved) July 27, 2017 Updates: 6282,6550,6775 (if approved) January 22, 2018
Intended status: Standards Track Intended status: Standards Track
Expires: January 28, 2018 Expires: July 26, 2018
RPL-BIER RPL-BIER
draft-thubert-roll-bier-00 draft-thubert-roll-bier-01
Abstract Abstract
This specification extends RPL to provide unicast and multicast This specification extends RPL to provide unicast and multicast
routing based on bitStrings such as used in Bit Index Explicit routing based on bitStrings such as used in Bit Index Explicit
Replication and its source-routed Traffic Engineering variant, which Replication and its source-routed Traffic Engineering variant, which
correspond to RPL storing and non-storing modes respectively. correspond to RPL storing and Non-Storing Modes respectively.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 28, 2018. This Internet-Draft will expire on July 26, 2018.
Copyright Notice Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Extensions to RFC 6550 . . . . . . . . . . . . . . . . . . . 5 4. Extensions to RFC 6550 . . . . . . . . . . . . . . . . . . . 5
4.1. RPL-BIER MOPs . . . . . . . . . . . . . . . . . . . . . . 6 4.1. RPL-BIER MOPs . . . . . . . . . . . . . . . . . . . . . . 6
4.1.1. RPL-BIER non-storing mode . . . . . . . . . . . . . . 6 4.1.1. RPL-BIER Non-Storing Mode . . . . . . . . . . . . . . 6
4.1.2. RPL-BIER storing mode . . . . . . . . . . . . . . . . 6 4.1.2. RPL-BIER Storing Mode . . . . . . . . . . . . . . . . 6
4.2. BitString Information . . . . . . . . . . . . . . . . . . 7 4.2. BitString Information . . . . . . . . . . . . . . . . . . 7
5. Updating the 6LoWPAN Framework . . . . . . . . . . . . . . . 8 5. Updating the 6LoWPAN Framework . . . . . . . . . . . . . . . 8
5.1. Extensions to RFC 6775 . . . . . . . . . . . . . . . . . 8 5.1. Extensions to RFC 6775 . . . . . . . . . . . . . . . . . 8
5.2. Extensions to RFC 6282 . . . . . . . . . . . . . . . . . 9 5.2. Extensions to RFC 6282 . . . . . . . . . . . . . . . . . 9
5.3. New Neighbor Discovery Options and Messages . . . . . . . 9 5.3. New Neighbor Discovery Options and Messages . . . . . . . 9
5.3.1. 6LoWPAN ND Bit Position Option . . . . . . . . . . . 9 5.3.1. 6LoWPAN ND Bit Position Option . . . . . . . . . . . 9
5.3.2. Address Mapping Message . . . . . . . . . . . . . . . 10 5.3.2. Address Mapping Message . . . . . . . . . . . . . . . 10
6. BitString formats . . . . . . . . . . . . . . . . . . . . . . 11 6. BitString formats . . . . . . . . . . . . . . . . . . . . . . 11
6.1. Bit-by-bit BitStrings . . . . . . . . . . . . . . . . . . 11 6.1. Bit-by-bit BitStrings . . . . . . . . . . . . . . . . . . 11
6.1.1. Allocating a Bit Position in a Bit-by-bit BitString . 12 6.1.1. Allocating a Bit Position in a Bit-by-bit BitString . 12
skipping to change at page 3, line 19 skipping to change at page 3, line 19
RPL is a Distance-Vector protocol, which, compared to link-state RPL is a Distance-Vector protocol, which, compared to link-state
protocols, limits the amount of topological knowledge that needs to protocols, limits the amount of topological knowledge that needs to
be installed and maintained in each node. RPL also leverages Routing be installed and maintained in each node. RPL also leverages Routing
Stretch to reduce further the amount of control traffic and routing Stretch to reduce further the amount of control traffic and routing
state that is required to operate the protocol. Finally, broken state that is required to operate the protocol. Finally, broken
routes may be fixed lazily and on-demand, based on dataplane routes may be fixed lazily and on-demand, based on dataplane
inconsistency discovery, which avoids wasting energy in the proactive inconsistency discovery, which avoids wasting energy in the proactive
repair of unused paths. repair of unused paths.
RPL enables various trade-offs between routing stretch, amount of RPL enables various trade-offs between routing stretch, amount of
routing state and packet size, with the introdution of different routing state and packet size, with the introduction of different
modes of operation (MOPs): modes of operation (MOPs):
o With Reactive Discovery of Point-to-Point (P2P) Routes (aka on- o With Reactive Discovery of Point-to-Point (P2P) Routes (aka on-
demand) [RFC6997][I-D.ietf-roll-aodv-rpl], a limited number of demand) [RFC6997][I-D.ietf-roll-aodv-rpl], a limited number of
routes are optimized on-demand, between select pairs of devices routes are optimized on-demand, between select pairs of devices
for which a service with some particular characteristics is for which a service with some particular characteristics is
needed. needed.
o In Storing mode of operation (aka storing mode), Multipoint to o In Storing Mode of operation (aka Storing Mode), Multipoint to
Point (MP2P) routes from the LLN nodes to the root and Point to Point (MP2P) routes from the LLN nodes to the root and Point to
Multipoint (P2MP) routes from the root to the LLN nodes are Multipoint (P2MP) routes from the root to the LLN nodes are
optimized, but P2P routes between LLN nodes are stretched via a optimized, but P2P routes between LLN nodes are stretched via a
common parent. In storing mode, RPL requires that nodes maintain common parent. In Storing Mode, RPL requires that nodes maintain
routing information for the maximum number of child nodes in their routing information for the maximum number of child nodes in their
sub-DODAG. If a network is composed of similar nodes, this means sub-DODAG. If a network is composed of similar nodes, this means
that each node should be able to store a number of routes that is that each node should be able to store a number of routes that is
in the order of the total number of nodes in the network. in the order of the total number of nodes in the network.
o In Non-Storing mode of operation (aka non-storing mode), MP2P and o In Non-Storing Mode of operation (aka Non-Storing Mode), MP2P and
P2MP routes are also optimized, but downwards routes can only be P2MP routes are also optimized, but downwards routes can only be
computed by the root and P2MP forwarding relies on strict source- computed by the root and P2MP forwarding relies on strict source-
routing. This increases the size of the packets and limits the routing. This increases the size of the packets and limits the
depth of the DODAG. The non-storing mode also results in depth of the DODAG. The Non-Storing Mode also results in
additional stretch for P2P routes, whereby all packets must additional stretch for P2P routes, whereby all packets must
transit via the root following the default route all the way up, transit via the root following the default route all the way up,
to be then source-routed down. to be then source-routed down.
In order to alleviate the issues above and improve the existing In order to alleviate the issues above and improve the existing
multicast operations, this specification introduces the use of multicast operations, this specification introduces the use of
bitStrings in RPL LLNs. BitStrings are already used in the art as a bitStrings in RPL LLNs. BitStrings are already used in the art as a
datapath analog to one or more IPv6 [RFC8200] addresses: datapath analog to one or more IPv6 [RFC8200] addresses:
o With the Bit Index Explicit Replication (BIER), introduced in the o With the Bit Index Explicit Replication (BIER), introduced in the
"BIER Architecture" [I-D.ietf-bier-architecture], each it in a "BIER Architecture" [RFC8279], each it in a bitStrings represents
bitStrings represents a particular destination. This a particular destination. This specification introduces a RPL-
specification introduces a RPL-BIER storing mode that applies BIER BIER Storing Mode that applies BIER operations to RPL Storing
operations to RPL storing mode. Mode.
o "Traffic Engineering for Bit Index Explicit Replication" o "Traffic Engineering for Bit Index Explicit Replication"
[I-D.eckert-bier-te-arch] (BIER-TE) adds support for Traffic [I-D.eckert-bier-te-arch] (BIER-TE) adds support for Traffic
Engineering by explicit hop-by-hop forwarding and loose hop Engineering by explicit hop-by-hop forwarding and loose hop
forwarding of packets along a unicast route. With BIER-TE, each forwarding of packets along a unicast route. With BIER-TE, each
bit in a bitStrings represents a particular intermediate link. bit in a bitStrings represents a particular intermediate link.
This specification introduces a RPL-BIER non-storing mode that This specification introduces a RPL-BIER Non-Storing Mode that
applies BIER-TE operations to RPL non-storing mode. applies BIER-TE operations to RPL Non-Storing Mode.
This specification provides new signaling in RPL to enable RPL-BIER This specification provides new signaling in RPL to enable RPL-BIER
operations. In addition to classical bitStrings, this specification operations. In addition to classical bitStrings, this specification
proposes an new technique that derives from Bloom Filters. This proposes an new technique that derives from Bloom Filters. This
technique provides elasticity to the size of the bitString, which is technique provides elasticity to the size of the bitString, which is
not constrained to a fixed number of entries, and a trade-off between not constrained to a fixed number of entries, and a trade-off between
the number of bits that are needed for routing and the chances to the number of bits that are needed for routing and the chances to
waste energy forwarding down a path where no target exist. The Bloom waste energy forwarding down a path where no target exist. The Bloom
Filters mechanism applies to RPL-BIER in both modes of operations. Filters mechanism applies to RPL-BIER in both modes of operations.
In order to carry routing information in a concise fashion in a Low- In order to carry routing information in a concise fashion in a Low-
Power Wireless Personal Area Network (6LoWPAN) for Route-Over use Power Wireless Personal Area Network (6LoWPAN) for Route-Over use
cases, the 6LoWPAN adaptation layer framework [RFC4944] [RFC6282] was cases, the 6LoWPAN adaptation layer framework [RFC4944] [RFC6282] was
extended with the 6LoWPAN Routing Header (6LoRH) specification extended with the 6LoWPAN Routing Header (6LoRH) specification
[RFC8138], which uses the 6LoWPAN Paging Dispatch [RFC8025]. The [RFC8138], which uses the 6LoWPAN Paging Dispatch [RFC8025]. The
original specification includes the formats necessary for RPL such as original specification includes the formats necessary for RPL such as
the Source Route Header (SRH) and is intended to be extended for the Source Route Header (SRH) and is intended to be extended for
additional routing artifacts. A companion document to this, the additional routing artifacts. A companion document to this, the
"6loRH for BitStrings" [I-D.thubert-6lo-bier-dispatch], "6loRH for BitStrings" [I-D.thubert-6lo-bier-dispatch],
specification, proposes new 6LoRH formats to enable the concise specification, proposes new 6LoRH formats to enable the concise
encoding of the BIER bitstrings and of the Bloom Filters described encoding of the BIER bitStrings and of the Bloom Filters described
therein. therein.
In the current practive of LLN networks, the non-storing mode is In the current practice of LLN networks, the Non-Storing Mode is
largely favored, because it does not place a restriction on how large largely favored, because it does not place a restriction on how large
a network formed of a particular device can become. One major a network formed of a particular device can become. One major
benefit of introducing bitStrings is that the amount of state that is benefit of introducing bitStrings is that the amount of state that is
required for routing in storing mode is no more growing in the order required for routing in Storing Mode is no more growing in the order
of the total number of nodes in the network but linearly with the of the total number of nodes in the network but linearly with the
number of children attached to the RPL router. In other words, the number of children attached to the RPL router. In other words, the
maximum number of children that a router is willing to accept maximum number of children that a router is willing to accept
determines both the size of the Neighbor Cache for 6LoWPAN Neighbor determines both the size of the Neighbor Cache for 6LoWPAN Neighbor
Discovery (6LoWPAN ND) [RFC6775][I-D.ietf-6lo-rfc6775-update] and the Discovery (6LoWPAN ND) [RFC6775][I-D.ietf-6lo-rfc6775-update] and the
size of the routing table that is required in RPL-BIER storing mode. size of the routing table that is required in RPL-BIER Storing Mode.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
[RFC2119]. [RFC2119].
The Terminology used in this document is consistent with and The Terminology used in this document is consistent with and
incorporates that described in Terms Used in Routing for Low-Power incorporates that described in Terms Used in Routing for Low-Power
skipping to change at page 5, line 27 skipping to change at page 5, line 27
Node Networks [RFC7228]. Node Networks [RFC7228].
The term "byte" is used in its now customary sense as a synonym for The term "byte" is used in its now customary sense as a synonym for
"octet". "octet".
"RPL", "RPL Packet Information" (RPI) and "RPL Instance" are defined "RPL", "RPL Packet Information" (RPI) and "RPL Instance" are defined
in the "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks" in the "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks"
[RFC6550] specification. [RFC6550] specification.
The terms Bit-Forwarding Egress Routers (BFR), BFR-id and bitString The terms Bit-Forwarding Egress Routers (BFR), BFR-id and bitString
are defined in [I-D.ietf-bier-architecture]. A bitString indicates a are defined in [RFC8279]. A bitString indicates a continuous
continuous sequence of bits indexed by an offset in the sequence. sequence of bits indexed by an offset in the sequence. The leftmost
The leftmost bit is bit 0 and corresponds to the value 0x80 of the bit is bit 0 and corresponds to the value 0x80 of the leftmost byte
leftmost byte in the BitString. With this specification, a bitString in the BitString. With this specification, a bitString maybe used to
maybe used to encode one or more unsigned integer(s) as a bit encode one or more unsigned integer(s) as a bit position in the
position in the bitString (bit-by-bit), or a Bloom filter. bitString (bit-by-bit), or a Bloom filter.
3. Applicability 3. Applicability
BIER and other bit-indexed methods that would leverage bitStrings BIER and other bit-indexed methods that would leverage bitStrings
will generally require additional information in the packet to will generally require additional information in the packet to
complement the bitString. For instance, BIER has the concept of a complement the bitString. For instance, BIER has the concept of a
BFR-id and an Entropy value in the BIER header. Since those BFR-id and an Entropy value in the BIER header. Since those
additional fields depend on the bit-indexed method, they are expected additional fields depend on the bit-indexed method, they are expected
to be transported separately from the bitString. This specification to be transported separately from the bitString. This specification
concentrates on the bitString and a group identifier which enables a concentrates on the bitString and a group identifier which enables a
network to grow beyond the size of one bitString. network to grow beyond the size of one bitString.
TBD Do we need entropy ? TBD Do we need entropy ?
4. Extensions to RFC 6550 4. Extensions to RFC 6550
This specification introduces two new modes of operation for RPL, the This specification introduces two new modes of operation for RPL, the
RPL-BIER non-storing mode which is discussed in Section 4.1.1 and the RPL-BIER Non-Storing Mode which is discussed in Section 4.1.1 and the
RPL-BIER storing mode which is discussed in Section 4.1.2. A new RPL-BIER Storing Mode which is discussed in Section 4.1.2. A new
Control Message Options (CMO) is introduced to transport the Control Message Options (CMO) is introduced to transport the
bitStrings in Section 4.2. bitStrings in Section 4.2.
4.1. RPL-BIER MOPs 4.1. RPL-BIER MOPs
In RPL-BIER modes of operation, one or more RPL Target Option are In RPL-BIER modes of operation, one or more RPL Target Option are
replaced by a new BitString Information Option which represent the replaced by a new BitString Information Option which represent the
advertised target(s) by a combination of a bitString and control advertised target(s) by a combination of a bitString and control
information. information.
4.1.1. RPL-BIER non-storing mode 4.1.1. RPL-BIER Non-Storing Mode
In Non-Storing RPL-BIER, a bit in classical BIER bit-by-bit In Non-Storing RPL-BIER, a bit in classical BIER bit-by-bit
bitStrings (see Section 6.1) or a set of bits in a Bloom Filter (see bitStrings (see Section 6.1) or a set of bits in a Bloom Filter (see
Section 6.2) is associated to a next-hop from the perspective of an Section 6.2) is associated to a next-hop from the perspective of an
intermediate router. RPL non-storing mode DAO messages are used to intermediate router. RPL Non-Storing Mode DAO messages are used to
advertise the relation between a target and its parent (transit) advertise the relation between a target and its parent (transit)
directly to the root. directly to the root.
If multiple Targets Options were to be placed consecutively to If multiple Targets Options were to be placed consecutively to
factorize a Transit Information Option (TIO) in a classical RPL non- factorize a Transit Information Option (TIO) in a classical RPL Non-
storing mode DAO message, they are replaced by a single BIO with the Storing Mode DAO message, they are replaced by a single BIO with the
aggregated bitString that represents all these targets. aggregated bitString that represents all these targets.
4.1.2. RPL-BIER storing mode 4.1.2. RPL-BIER Storing Mode
In RPL-BIER storing mode, a bit in classical BIER Bit-by-bit In RPL-BIER Storing Mode, a bit in classical BIER Bit-by-bit
bitStrings (see Section 6.1) or a set of bits in a Bloom Filter (see bitStrings (see Section 6.1) or a set of bits in a Bloom Filter (see
Section 6.2) is associated to a final destination. RPL storing mode Section 6.2) is associated to a final destination. RPL Storing Mode
DAO messages are used to advertise recursively the targets to the DAO messages are used to advertise recursively the targets to the
parent(s) all the way to the root. parent(s) all the way to the root.
The BitString Information Option(s) in the DAO message contain The BitString Information Option(s) in the DAO message contain
collectively an aggregated bitString that represents the advertising collectively an aggregated bitString that represents the advertising
node and all of its descendants. Parents save the bitString per node and all of its descendants. Parents save the bitString per
child, and use it to forward down the DODAG as discussed in child, and use it to forward down the DODAG as discussed in
Section 6.1.3. Section 6.1.3.
The Transit Information Option is not used. The lack of transit The Transit Information Option is not used. The lack of transit
skipping to change at page 7, line 17 skipping to change at page 7, line 17
Section 6.7 of [RFC6550] specifies optional CMOs to be placed in RPL Section 6.7 of [RFC6550] specifies optional CMOs to be placed in RPL
messages such as the Destination Advertisement Object (DAO) message. messages such as the Destination Advertisement Object (DAO) message.
The RPL Target Option and the Transit Information Option (TIO) are The RPL Target Option and the Transit Information Option (TIO) are
such optional fields; the former indicates a node to be reached and such optional fields; the former indicates a node to be reached and
the latter specifies a parent that can be used to reach that node. the latter specifies a parent that can be used to reach that node.
Options may be factorized; one or more contiguous TIOs apply to the Options may be factorized; one or more contiguous TIOs apply to the
one or more contiguous Target options that immediately precede the one or more contiguous Target options that immediately precede the
TIOs in the RPL message. TIOs in the RPL message.
This specification introduces a new CMO, the BitString Information This specification introduces a new CMO, the BitString Information
option (BIO). A BIO is used as an alterate to one or more Target option (BIO). A BIO is used as an alternate to one or more Target
Option(s) in Storing and non-storing mode DAOs usig bit-by-bit Option(s) in Storing and Non-Storing Mode DAOs using bit-by-bit
bitStrings, and its format is as follows: bitStrings, and its format is as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 0x0B | Option Length | BitStringType | Group ID | | Type = 0x0B | Option Length | BitStringType | Group ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ + + +
. . . .
skipping to change at page 9, line 14 skipping to change at page 9, line 14
5.2. Extensions to RFC 6282 5.2. Extensions to RFC 6282
This specification also extends the 6LoWPAN framework with the This specification also extends the 6LoWPAN framework with the
capability to transform an address into a tuple (Control field, capability to transform an address into a tuple (Control field,
bitString) as part of the 6LoWPAN Header Compression [RFC6282] bitString) as part of the 6LoWPAN Header Compression [RFC6282]
(6LoWPAN HC). Since the 6LBR and the Header Compression functions (6LoWPAN HC). Since the 6LBR and the Header Compression functions
are typically collocated, the latter may exploit local tables built are typically collocated, the latter may exploit local tables built
by the former to map a destination IPv6 address into a bitString. by the former to map a destination IPv6 address into a bitString.
In storing mode, P2P stretched routing via a common parent can be In Storing Mode, P2P stretched routing via a common parent can be
obtained if the destination is expressed as a tuple (Control field, obtained if the destination is expressed as a tuple (Control field,
bitString). This can be achieved with a BAR/BAC exchange with the bitString). This can be achieved with a BAR/BAC exchange with the
6LBR. 6LBR.
5.3. New Neighbor Discovery Options and Messages 5.3. New Neighbor Discovery Options and Messages
In order to allocate and lookup a bitString, this specification In order to allocate and lookup a bitString, this specification
extends 6LoWPAN ND with the following new messages and formats. extends 6LoWPAN ND with the following new messages and formats.
5.3.1. 6LoWPAN ND Bit Position Option 5.3.1. 6LoWPAN ND Bit Position Option
skipping to change at page 11, line 35 skipping to change at page 11, line 35
6. BitString formats 6. BitString formats
This specification introduces two BitString formats, the bit-by-bit This specification introduces two BitString formats, the bit-by-bit
and the Bloom Filter. and the Bloom Filter.
6.1. Bit-by-bit BitStrings 6.1. Bit-by-bit BitStrings
In the bit-by-bit case, each bit is mapped in an unequivocal fashion In the bit-by-bit case, each bit is mapped in an unequivocal fashion
with a single addressable resource in the network. In RPL-BIER with a single addressable resource in the network. In RPL-BIER
storing mode, this is an IPv6 address as advertised in RPL storing Storing Mode, this is an IPv6 address as advertised in RPL Storing
mode DAO messages, whereas in RPL-BIER non-storing mode, this is a Mode DAO messages, whereas in RPL-BIER Non-Storing Mode, this is a
parent-child relationship as advertised in RPL non-storing mode DAO parent-child relationship as advertised in RPL Non-Storing Mode DAO
messages. messages.
if every node in a large network is given one or more bits in a bit- if every node in a large network is given one or more bits in a bit-
by-bit bitString, then the bitString may grow very large and lead to by-bit bitString, then the bitString may grow very large and lead to
undesirably large overhead in the data plane. BIER allows to divide undesirably large overhead in the data plane. BIER allows to divide
a potentially the very large abstract bitString into segments, aka a potentially the very large abstract bitString into segments, aka
groups, indexed by a groupID. groups, indexed by a groupID.
In the protocol elements that use a bitString, only the relevant In the protocol elements that use a bitString, only the relevant
group(s) are transported, and the advertised bitString is in fact the group(s) are transported, and the advertised bitString is in fact the
skipping to change at page 12, line 47 skipping to change at page 12, line 47
routers must be aware of. routers must be aware of.
If the 6LBR accepts the registration, then it returns a DAC message If the 6LBR accepts the registration, then it returns a DAC message
with a status of 0 indicating success, adding a 6LoWPAN ND Bit with a status of 0 indicating success, adding a 6LoWPAN ND Bit
Position Option (Section 5.3.1) to the DAC message to indicate the Position Option (Section 5.3.1) to the DAC message to indicate the
groupID and bit. groupID and bit.
The 6LR maintains a binding cache entry (BCE) for the 6LN based on The 6LR maintains a binding cache entry (BCE) for the 6LN based on
successful DAC messages. With this specification, the 6LR also successful DAC messages. With this specification, the 6LR also
stores the matching between the address and the bitString and uses it stores the matching between the address and the bitString and uses it
for searching its children when forwarding packets in non-storing for searching its children when forwarding packets in Non-Storing
mode (see Section 6.1.3). Mode (see Section 6.1.3).
If the 6LN child does not support the BIER encoding If the 6LN child does not support the BIER encoding
(e.g.[I-D.thubert-6lo-bier-dispatch]), then the packet is converted (e.g.[I-D.thubert-6lo-bier-dispatch]), then the packet is converted
in a format that the child supports (e.g.[RFC8138]). in a format that the child supports (e.g.[RFC8138]).
6.1.2. Aggregation of Bit-by-bit BitStrings 6.1.2. Aggregation of Bit-by-bit BitStrings
BitStrings are aggregated by a 'OR' operation so that all the bits BitStrings are aggregated by a 'OR' operation so that all the bits
that are set in either bitString is set in the resulting bitString. that are set in either bitString is set in the resulting bitString.
In the concise form of a tuple (groupID, bitString), the aggregation In the concise form of a tuple (groupID, bitString), the aggregation
is done on a group-by-group basis, between segments of a same group. is done on a group-by-group basis, between segments of a same group.
In RPL-BIER storing mode, the bit-by-bit BitStrings are passed from In RPL-BIER Storing Mode, the bit-by-bit BitStrings are passed from
child to parent using DAO messages, in a fashion similar to RPL child to parent using DAO messages, in a fashion similar to RPL
storing mode [RFC6550]. The BitString Information option (Figure 1) Storing Mode [RFC6550]. The BitString Information option (Figure 1)
is used in replacement of the Target option. A DAO message contains is used in replacement of the Target option. A DAO message contains
one BIO per group, and the parent that receives the messages one BIO per group, and the parent that receives the messages
associates the BIO information to the advertising child. In order to associates the BIO information to the advertising child. In order to
build a DAO message, the parent regenerates its own BIO, one per build a DAO message, the parent regenerates its own BIO, one per
group, by aggregating the bitStrings from all of its children with group, by aggregating the bitStrings from all of its children with
its own, and places the resulting BIOs in the DAO message. its own, and places the resulting BIOs in the DAO message.
6.1.3. Forwarding Based on Bit-by-bit BitStrings 6.1.3. Forwarding Based on Bit-by-bit BitStrings
Forwarding is based on matching a bitString in a packet with those of Forwarding is based on matching a bitString in a packet with those of
skipping to change at page 13, line 36 skipping to change at page 13, line 36
packet. For multicast packets, all matching children get a copy. packet. For multicast packets, all matching children get a copy.
Matches are found by scanning all children and performing bitwise Matches are found by scanning all children and performing bitwise
operations as follows. operations as follows.
In order to search for a match, a reference bitString is initialized In order to search for a match, a reference bitString is initialized
with the destination bitString in the packet. A match is found with with the destination bitString in the packet. A match is found with
a child if the bitwise 'AND' between the reference bitString and the a child if the bitwise 'AND' between the reference bitString and the
bitString stored for that child does not result in a NULL bitString bitString stored for that child does not result in a NULL bitString
of all zeroes. of all zeroes.
In non-storing mode, a packet is copied to all matching children, In Non-Storing Mode, a packet is copied to all matching children,
which are found by trying all children. which are found by trying all children.
In non-storing mode, if a child is selected for forwarding, then an In Non-Storing Mode, if a child is selected for forwarding, then an
'XOR' operation is performed between the reference bitString and the 'XOR' operation is performed between the reference bitString and the
bitString resulting from the 'AND' operation. If the 'XOR' operation bitString resulting from the 'AND' operation. If the 'XOR' operation
does not result in a NULL bitString, denoting that more children does not result in a NULL bitString, denoting that more children
should get the packet, then the result of the 'XOR' operation becomes should get the packet, then the result of the 'XOR' operation becomes
the new reference bitString and the search continues. The 'XOR' the new reference bitString and the search continues. The 'XOR'
operation allows to stop the search loop as soon as all matches are operation allows to stop the search loop as soon as all matches are
found; it also avoids forwarding twice to a same destination along found; it also avoids forwarding twice to a same destination along
different downwards path in the DODAG. different downwards path in the DODAG.
6.1.4. Reliable Multicast based on Bit-by-bit BitStrings 6.1.4. Reliable Multicast based on Bit-by-bit BitStrings
skipping to change at page 15, line 38 skipping to change at page 15, line 38
+------+-------------+---------------+ +------+-------------+---------------+
RPL Control Codes RPL Control Codes
This document is updating the registry created by RFC 6550 for the This document is updating the registry created by RFC 6550 for the
RPL 3-bit Mode of Operation (MOP) as follows: RPL 3-bit Mode of Operation (MOP) as follows:
+-----------+---------------------------------------+---------------+ +-----------+---------------------------------------+---------------+
| MOP value | Description | Reference | | MOP value | Description | Reference |
+-----------+---------------------------------------+---------------+ +-----------+---------------------------------------+---------------+
| 6 | RPL-BIER non-storing mode of | This document | | 6 | RPL-BIER Non-Storing Mode of | This document |
| | operation | | | | operation | |
| | | | | | | |
| 7 | RPL-BIER Storing mode of operation | This document | | 7 | RPL-BIER Storing Mode of operation | This document |
+-----------+---------------------------------------+---------------+ +-----------+---------------------------------------+---------------+
DIO Mode of operation DIO Mode of operation
10. Acknowledgments 10. Acknowledgments
11. References 11. References
11.1. Normative References 11.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC4443] Conta, A., Deering, S., and M. Gupta, Ed., "Internet [RFC4443] Conta, A., Deering, S., and M. Gupta, Ed., "Internet
Control Message Protocol (ICMPv6) for the Internet Control Message Protocol (ICMPv6) for the Internet
Protocol Version 6 (IPv6) Specification", STD 89, Protocol Version 6 (IPv6) Specification", STD 89,
RFC 4443, DOI 10.17487/RFC4443, March 2006, RFC 4443, DOI 10.17487/RFC4443, March 2006,
<http://www.rfc-editor.org/info/rfc4443>. <https://www.rfc-editor.org/info/rfc4443>.
[RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J.,
Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur,
JP., and R. Alexander, "RPL: IPv6 Routing Protocol for JP., and R. Alexander, "RPL: IPv6 Routing Protocol for
Low-Power and Lossy Networks", RFC 6550, Low-Power and Lossy Networks", RFC 6550,
DOI 10.17487/RFC6550, March 2012, DOI 10.17487/RFC6550, March 2012,
<http://www.rfc-editor.org/info/rfc6550>. <https://www.rfc-editor.org/info/rfc6550>.
[RFC6775] Shelby, Z., Ed., Chakrabarti, S., Nordmark, E., and C. [RFC6775] Shelby, Z., Ed., Chakrabarti, S., Nordmark, E., and C.
Bormann, "Neighbor Discovery Optimization for IPv6 over Bormann, "Neighbor Discovery Optimization for IPv6 over
Low-Power Wireless Personal Area Networks (6LoWPANs)", Low-Power Wireless Personal Area Networks (6LoWPANs)",
RFC 6775, DOI 10.17487/RFC6775, November 2012, RFC 6775, DOI 10.17487/RFC6775, November 2012,
<http://www.rfc-editor.org/info/rfc6775>. <https://www.rfc-editor.org/info/rfc6775>.
[RFC8200] Deering, S. and R. Hinden, "Internet Protocol, Version 6 [RFC8200] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", STD 86, RFC 8200, (IPv6) Specification", STD 86, RFC 8200,
DOI 10.17487/RFC8200, July 2017, DOI 10.17487/RFC8200, July 2017,
<http://www.rfc-editor.org/info/rfc8200>. <https://www.rfc-editor.org/info/rfc8200>.
[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>.
11.2. Informative References 11.2. Informative References
[I-D.bergmann-bier-ccast] [I-D.bergmann-bier-ccast]
Bergmann, O., Bormann, C., Gerdes, S., and H. Chen, Bergmann, O., Bormann, C., Gerdes, S., and H. Chen,
"Constrained-Cast: Source-Routed Multicast for RPL", "Constrained-Cast: Source-Routed Multicast for RPL",
draft-bergmann-bier-ccast-02 (work in progress), October draft-bergmann-bier-ccast-02 (work in progress), October
2016. 2016.
[I-D.eckert-bier-te-arch] [I-D.eckert-bier-te-arch]
Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Traffic Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Traffic
Engineering for Bit Index Explicit Replication BIER-TE", Engineering for Bit Index Explicit Replication BIER-TE",
draft-eckert-bier-te-arch-05 (work in progress), June draft-eckert-bier-te-arch-06 (work in progress), November
2017. 2017.
[I-D.ietf-6lo-backbone-router] [I-D.ietf-6lo-backbone-router]
Thubert, P., "IPv6 Backbone Router", draft-ietf-6lo- Thubert, P., "IPv6 Backbone Router", draft-ietf-6lo-
backbone-router-04 (work in progress), July 2017. backbone-router-05 (work in progress), January 2018.
[I-D.ietf-6lo-rfc6775-update] [I-D.ietf-6lo-rfc6775-update]
Thubert, P., Nordmark, E., and S. Chakrabarti, "An Update Thubert, P., Nordmark, E., Chakrabarti, S., and C.
to 6LoWPAN ND", draft-ietf-6lo-rfc6775-update-06 (work in Perkins, "An Update to 6LoWPAN ND", draft-ietf-6lo-
progress), June 2017. rfc6775-update-11 (work in progress), December 2017.
[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-07 (work in
progress), June 2017.
[I-D.ietf-roll-aodv-rpl] [I-D.ietf-roll-aodv-rpl]
Anamalamudi, S., Zhang, M., Sangi, A., Perkins, C., and S. Anamalamudi, S., Zhang, M., Sangi, A., Perkins, C., and S.
Anand, "Asymmetric AODV-P2P-RPL in Low-Power and Lossy Anand, "Asymmetric AODV-P2P-RPL in Low-Power and Lossy
Networks (LLNs)", draft-ietf-roll-aodv-rpl-01 (work in Networks (LLNs)", draft-ietf-roll-aodv-rpl-02 (work in
progress), March 2017. progress), September 2017.
[I-D.thubert-6lo-bier-dispatch] [I-D.thubert-6lo-bier-dispatch]
Thubert, P., Brodard, Z., Jiang, H., and G. Texier, "A Thubert, P., Brodard, Z., Jiang, H., and G. Texier, "A
6loRH for BitStrings", draft-thubert-6lo-bier-dispatch-03 6loRH for BitStrings", draft-thubert-6lo-bier-dispatch-04
(work in progress), July 2017. (work in progress), January 2018.
[RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler,
"Transmission of IPv6 Packets over IEEE 802.15.4 "Transmission of IPv6 Packets over IEEE 802.15.4
Networks", RFC 4944, DOI 10.17487/RFC4944, September 2007, Networks", RFC 4944, DOI 10.17487/RFC4944, September 2007,
<http://www.rfc-editor.org/info/rfc4944>. <https://www.rfc-editor.org/info/rfc4944>.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", RFC 5226, IANA Considerations Section in RFCs", RFC 5226,
DOI 10.17487/RFC5226, May 2008, DOI 10.17487/RFC5226, May 2008,
<http://www.rfc-editor.org/info/rfc5226>. <https://www.rfc-editor.org/info/rfc5226>.
[RFC6282] Hui, J., Ed. and P. Thubert, "Compression Format for IPv6 [RFC6282] Hui, J., Ed. and P. Thubert, "Compression Format for IPv6
Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, Datagrams over IEEE 802.15.4-Based Networks", RFC 6282,
DOI 10.17487/RFC6282, September 2011, DOI 10.17487/RFC6282, September 2011,
<http://www.rfc-editor.org/info/rfc6282>. <https://www.rfc-editor.org/info/rfc6282>.
[RFC6997] Goyal, M., Ed., Baccelli, E., Philipp, M., Brandt, A., and [RFC6997] Goyal, M., Ed., Baccelli, E., Philipp, M., Brandt, A., and
J. Martocci, "Reactive Discovery of Point-to-Point Routes J. Martocci, "Reactive Discovery of Point-to-Point Routes
in Low-Power and Lossy Networks", RFC 6997, in Low-Power and Lossy Networks", RFC 6997,
DOI 10.17487/RFC6997, August 2013, DOI 10.17487/RFC6997, August 2013,
<http://www.rfc-editor.org/info/rfc6997>. <https://www.rfc-editor.org/info/rfc6997>.
[RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and [RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and
Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January
2014, <http://www.rfc-editor.org/info/rfc7102>. 2014, <https://www.rfc-editor.org/info/rfc7102>.
[RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for [RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for
Constrained-Node Networks", RFC 7228, Constrained-Node Networks", RFC 7228,
DOI 10.17487/RFC7228, May 2014, DOI 10.17487/RFC7228, May 2014,
<http://www.rfc-editor.org/info/rfc7228>. <https://www.rfc-editor.org/info/rfc7228>.
[RFC8025] Thubert, P., Ed. and R. Cragie, "IPv6 over Low-Power [RFC8025] Thubert, P., Ed. and R. Cragie, "IPv6 over Low-Power
Wireless Personal Area Network (6LoWPAN) Paging Dispatch", Wireless Personal Area Network (6LoWPAN) Paging Dispatch",
RFC 8025, DOI 10.17487/RFC8025, November 2016, RFC 8025, DOI 10.17487/RFC8025, November 2016,
<http://www.rfc-editor.org/info/rfc8025>. <https://www.rfc-editor.org/info/rfc8025>.
[RFC8138] Thubert, P., Ed., Bormann, C., Toutain, L., and R. Cragie, [RFC8138] Thubert, P., Ed., Bormann, C., Toutain, L., and R. Cragie,
"IPv6 over Low-Power Wireless Personal Area Network "IPv6 over Low-Power Wireless Personal Area Network
(6LoWPAN) Routing Header", RFC 8138, DOI 10.17487/RFC8138, (6LoWPAN) Routing Header", RFC 8138, DOI 10.17487/RFC8138,
April 2017, <http://www.rfc-editor.org/info/rfc8138>. April 2017, <https://www.rfc-editor.org/info/rfc8138>.
Author's Address Author's Address
Pascal Thubert (editor) Pascal Thubert (editor)
Cisco Systems, Inc Cisco Systems, Inc
Building D Building D
45 Allee des Ormes - BP1200 45 Allee des Ormes - BP1200
MOUGINS - Sophia Antipolis 06254 MOUGINS - Sophia Antipolis 06254
FRANCE FRANCE
 End of changes. 56 change blocks. 
82 lines changed or deleted 82 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/