< draft-thubert-6lo-bier-dispatch-04.txt		draft-thubert-6lo-bier-dispatch-05.txt >
	6lo P. Thubert, Ed.		6lo P. Thubert, Ed.
	Internet-Draft Cisco		Internet-Draft Cisco
	Intended status: Standards Track Z. Brodard		Intended status: Standards Track Z. Brodard
	Expires: July 20, 2018 Ecole Polytechnique		Expires: January 25, 2019 Ecole Polytechnique
	H. Jiang		H. Jiang
	G. Texier		G. Texier
	Telecom Bretagne		Telecom Bretagne
	January 16, 2018		July 24, 2018
	A 6loRH for BitStrings		A 6loRH for BitStrings
	draft-thubert-6lo-bier-dispatch-04		draft-thubert-6lo-bier-dispatch-05
	Abstract		Abstract
	This specification extends the 6LoWPAN Routing Header to signal		This specification extends the 6LoWPAN Routing Header to signal
	BitStrings such as utilized in Bit Index Explicit Replication and its		BitStrings such as utilized in Bit Index Explicit Replication and its
	Traffic Engineering variant.		Traffic Engineering variant.
	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
	skipping to change at page 1, line 36 ¶		skipping to change at page 1, line 36 ¶
	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 https://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 July 20, 2018.		This Internet-Draft will expire on January 25, 2019.
	Copyright Notice		Copyright Notice
	Copyright (c) 2018 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
	(https://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
	skipping to change at page 2, line 13 ¶		skipping to change at page 2, line 13 ¶
	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 . . . . . . . . . . . . . . . . . . . . . . . . . 3		2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
	3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3		3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3
	4. The BIER-6LoRH encoding . . . . . . . . . . . . . . . . . . . 4		4. The BIER-6LoRH encoding . . . . . . . . . . . . . . . . . . . 4
	4.1. The Bit-by-bit BitStrings . . . . . . . . . . . . . . . . 4		4.1. The Bit-by-bit BitStrings . . . . . . . . . . . . . . . . 5
	4.2. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 5		4.2. The Enumeration BitStrings . . . . . . . . . . . . . . . 5
	4.3. Types of BIER-6LoRH header . . . . . . . . . . . . . . . 5		4.3. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 5
	5. Implementation Status . . . . . . . . . . . . . . . . . . . . 6		4.4. Types of BIER-6LoRH header . . . . . . . . . . . . . . . 6
	6. Security Considerations . . . . . . . . . . . . . . . . . . . 7		5. Implementation Status . . . . . . . . . . . . . . . . . . . . 8
	7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7		6. Security Considerations . . . . . . . . . . . . . . . . . . . 8
	8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 7		7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
	9. References . . . . . . . . . . . . . . . . . . . . . . . . . 7		8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8
	9.1. Normative References . . . . . . . . . . . . . . . . . . 7		9. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
	9.2. Informative References . . . . . . . . . . . . . . . . . 8		9.1. Normative References . . . . . . . . . . . . . . . . . . 8
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9		9.2. Informative References . . . . . . . . . . . . . . . . . 9
			Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
	1. Introduction		1. Introduction
	The type of information that needs to be present in a packet inside		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,		the LLN but not outside of the LLN varies with the routing operation,
	but there is overall a need for an extensible compression technique		but there is overall a need for an extensible compression technique
	that would simplify the IP-in-IP encapsulation, when needed, and		that would simplify the IP-in-IP encapsulation, when needed, and
	optimally compress existing routing artifacts found in LLNs.		optimally compress existing routing artifacts found in LLNs.
	The 6LoWPAN Routing Header (6LoRH) [RFC8025] [RFC8138] is such a		The 6LoWPAN Routing Header (6LoRH) [RFC8025] [RFC8138] is such a
	skipping to change at page 4, line 36 ¶		skipping to change at page 4, line 39 ¶
	The BIER 6LoRH (BIER-6LoRH) is a Critical 6LoWPAN Routing Header that		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		provides a variable-size container for a BitString such as, a but not
	limited to, a BIER BitString.		limited to, a BIER BitString.
	The capability to parse the BIER BitString is necessary to forward		The capability to parse the BIER BitString is necessary to forward
	the packet so the Type cannot be ignored.		the packet so the Type cannot be ignored.
	0 1		0 1
	0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8		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-24| BitString |		|1|0|0| Control |6LoRHType 15-29| BitString |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+
	Figure 1: The BIER-6LoRH		Figure 1: The BIER-6LoRH
	This specification provides a 5-bit Control field that can be used to		This specification provides a 5-bit Control field that can be used to
	encode information that is specific to the BitString. The type and		encode information that is specific to the BitString. The type and
	size of the BitString are encoded in the 6LoRHType.		size of the BitString are encoded in the 6LoRHType.
	4.1. The Bit-by-bit BitStrings		4.1. The Bit-by-bit BitStrings
	skipping to change at page 5, line 14 ¶		skipping to change at page 5, line 21 ¶
	locally significant to one group only. This specification uses the		locally significant to one group only. This specification uses the
	5-bits Control field to encode the group.		5-bits Control field to encode the group.
	When groups are used, it may be that a packet is sent to different		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		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.		can be prepended to a same packet, each one for a different group.
	As the packet flows along the multicast distribution tree, a BIER-		As the packet flows along the multicast distribution tree, a BIER-
	6LoRH header that has no more destination in a given branch may be		6LoRH header that has no more destination in a given branch may be
	removed to make the packet shorter.		removed to make the packet shorter.
	4.2. Bloom Filters		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		A Bloom Filter can be seen as an additional compression technique for
	the bitString representation. A Bloom Filter may generate false		the bitString representation. A Bloom Filter may generate false
	positives, which, in the case of BIER, result in undue forwarding of		positives, which, in the case of BIER, result in undue forwarding of
	a packet down a path where no listener exists.		a packet down a path where no listener exists.
	As an example, the Constrained-Cast [I-D.ietf-roll-ccast]		As an example, the Constrained-Cast [I-D.ietf-roll-ccast]
	specification employs Bloom Filters as a compact representation of a		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		match or non-match for elements in a set that may be larger than the
	number of bits in the BitString.		number of bits in the BitString.
	In the case of a Bloom Filter, a number of Hash functions must be run		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		to obtain a multi-bit signature of an encoded element. This
	specification uses the 5-bits Control field to signal an Identifier		specification uses the 5-bits Control field to signal an Identifier
	of the set of Hash functions being used to generate a certain		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		BitString, so as to enable the migration from a set of Hash functions
	to the next.		to the next.
	4.3. Types of BIER-6LoRH header		4.4. Types of BIER-6LoRH header
	The Type of a BIER-6LoRH header indicates the size of the BitString		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		and whether the BitString is operated as an uncompressed bit-by-bit
	mapping, or as a Bloom filter.		mapping, as an enumeration, or as a Bloom filter.
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| BitString | Encoding | Control field | BitString |		| BitString | Encoding | Control field | BitString |
	| Type | | | Size |		| Type | | | Size |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 15 | bit-by-bit | Group ID | 8 bits |		| 15 | bit-by-bit | Group ID | 8 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 16 | bit-by-bit | Group ID | 16 bits |		| 16 | bit-by-bit | Group ID | 16 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 17 | bit-by-bit | Group ID | 48 bits |		| 17 | bit-by-bit | Group ID | 32 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 18 | bit-by-bit | Group ID | 96 bits |		| 18 | bit-by-bit | Group ID | 56 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 19 | bit-by-bit | Group ID | 160 bits |		| 19 | bit-by-bit | Group ID | 96 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 20 | Bloom filter | Hash function Set ID | 8 bits |		| 20 | bit-by-bit | Group ID | 160 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 21 | Bloom filter | Hash function Set ID | 16 bits |		| 21 | bit-by-bit | Group ID | 256 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 22 | Bloom filter | Hash function Set ID | 48 bits |		| 22 | Enumeration | Number of elements | 4 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 23 | Bloom filter | Hash function Set ID | 96 bits |		| 23 | Enumeration | Number of elements | 6 bits |
	+--------------+--------------+----------------------+--------------+		+--------------+--------------+----------------------+--------------+
	| 24 | Bloom filter | Hash function Set ID | 160 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		Table 1: The BIER-6LoRH Types
	In order to address a potentially large number of devices, the		In order to address a potentially large number of devices, the
	BitString may grow very large. Yet, the maximum frame size for a		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		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		routing. With this specification, a number of BIER-6LoRH headers of
	a same type (bit-by-bit or Bloom filter) may be placed contiguously		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		in the packet. This results in a larger BitString that is the
	skipping to change at page 7, line 4 ¶		skipping to change at page 8, line 17 ¶
	A research-stage implementation was developed at Cisco's Paris		A research-stage implementation was developed at Cisco's Paris
	Innovation Lab (PIRL) by Zacharie Brodard. It was implemented on		Innovation Lab (PIRL) by Zacharie Brodard. It was implemented on
	OpenWSN open-source firmware and tested on the OpenMote-CC2538		OpenWSN open-source firmware and tested on the OpenMote-CC2538
	hardware. It implements the header types 15, 16, 17, 18 and 19 (bit-		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		by-bit encoding without group ID) in order to allow a BIER-TE
	protocol over IEE802.15.4e.		protocol over IEE802.15.4e.
	Links:		Links:
	github: https://github.com/zach-b/openwsn-fw/tree/BIER		github: https://github.com/zach-b/openwsn-fw/tree/BIER
	OpenWSN firmware: https://openwsn.atlassian.net/wiki/pages/		OpenWSN firmware: https://openwsn.atlassian.net/wiki/pages/
	viewpage.action?pageId=688187		viewpage.action?pageId=688187
	OpenMote hardware: http://www.openmote.com/		OpenMote hardware: http://www.openmote.com/
	6. Security Considerations		6. Security Considerations
	The security considerations of [RFC8138] apply.		The security considerations of [RFC8138] apply.
	7. IANA Considerations		7. IANA Considerations
	This document extends the IANA registry created by [RFC8138] for the		This document extends the IANA registry created by [RFC8138] for the
	6LoWPAN Routing Header Type, and adds the following values:		6LoWPAN Routing Header Type, and adds the following values:
	15..24 : BIER-6LoRH [RFCthis]		15..29 : BIER-6LoRH [RFCthis]
	8. Acknowledgments		8. Acknowledgments
	9. References		9. References
	9.1. Normative References		9.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,
	skipping to change at page 8, line 15 ¶		skipping to change at page 9, line 32 ¶
	9.2. Informative References		9.2. Informative References
	[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-06 (work in progress), November		draft-eckert-bier-te-arch-06 (work in progress), November
	2017.		2017.
	[I-D.ietf-6tisch-architecture]		[I-D.ietf-6tisch-architecture]
	Thubert, P., "An Architecture for IPv6 over the TSCH mode		Thubert, P., "An Architecture for IPv6 over the TSCH mode
	of IEEE 802.15.4", draft-ietf-6tisch-architecture-13 (work		of IEEE 802.15.4", draft-ietf-6tisch-architecture-14 (work
	in progress), November 2017.		in progress), April 2018.
	[I-D.ietf-bier-architecture]		[I-D.ietf-bier-architecture]
	Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and		Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and
	S. Aldrin, "Multicast using Bit Index Explicit		S. Aldrin, "Multicast using Bit Index Explicit
	Replication", draft-ietf-bier-architecture-08 (work in		Replication", draft-ietf-bier-architecture-08 (work in
	progress), September 2017.		progress), September 2017.
	[I-D.ietf-detnet-architecture]		[I-D.ietf-detnet-architecture]
	Finn, N., Thubert, P., Varga, B., and J. Farkas,		Finn, N., Thubert, P., Varga, B., and J. Farkas,
	"Deterministic Networking Architecture", draft-ietf-		"Deterministic Networking Architecture", draft-ietf-
	detnet-architecture-04 (work in progress), October 2017.		detnet-architecture-06 (work in progress), June 2018.
	[I-D.ietf-roll-ccast]		[I-D.ietf-roll-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-ietf-roll-ccast-01 (work in progress), October 2017.		draft-ietf-roll-ccast-01 (work in progress), October 2017.
	[I-D.thubert-6tisch-4detnet]		[I-D.thubert-6tisch-4detnet]
	Thubert, P., "6TiSCH requirements for DetNet", draft-		Thubert, P., "6TiSCH requirements for DetNet", draft-
	thubert-6tisch-4detnet-01 (work in progress), June 2015.		thubert-6tisch-4detnet-01 (work in progress), June 2015.
	[I-D.thubert-bier-replication-elimination]		[I-D.thubert-bier-replication-elimination]
	Thubert, P., Brodard, Z., and H. Jiang, "BIER-TE-based		Thubert, P., Eckert, T., Brodard, Z., and H. Jiang, "BIER-
	OAM, Replication and Elimination", draft-thubert-bier-		TE extensions for Packet Replication and Elimination
	replication-elimination-01 (work in progress), July 2017.		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		[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,
	<https://www.rfc-editor.org/info/rfc6282>.		<https://www.rfc-editor.org/info/rfc6282>.
	[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, <https://www.rfc-editor.org/info/rfc7102>.		2014, <https://www.rfc-editor.org/info/rfc7102>.
End of changes. 22 change blocks.
	34 lines changed or deleted		72 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/