draft-eckert-bier-rbs.txt

BIER                                                      T. Eckert, Ed.
Internet-Draft                                Futurewei Technologies USA
Intended status: Experimental                                   M. Menth
Expires: 25 April 2023                           University of Tuebingen
                                                                 X. Geng
                                                                X. Zheng
                                                                 R. Meng
                                                                   F. Li
                                                      Huawei 2012 NT Lab
                                                         22 October 2022


    Recursive BitString Structure (RBS) Addresses for BIER and MSR6
                        draft-eckert-bier-rbs-00

Abstract

   This memo introduces a compact data-structure representation of
   multicast trees called "Recursive Bitstring Structure" (RBS) and its
   use for (stateless) forwarding of packets that include this structure
   in their header.  It is intended as an alternative to "flat"
   bitstring addresses as used in BIER and BIER-TE or possible
   forwarding plane variations such as MSR6.  RBS aims to improve
   performance and scalability over flat bitstrings and simplify
   operations.

   Operations is simplified because RBS does not require the use,
   management and optimization of network-wide configured address spaces
   BIFT-ID and SI and because one common RBS mechanism can replace flat
   bitstring addresses for both shortest-path forwarding and tree
   engineered forwarding.  It intends to improve performance by allowing
   multicast to sparse set of receivers in larger networks with fewer
   packets and it intends to improve scalability by requiring less BIFT
   state on routers.

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/.







Eckert, et al.            Expires 25 April 2023                 [Page 1]

Internet-Draft                  bier-rbs                    October 2022


   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 25 April 2023.

Copyright Notice

   Copyright (c) 2022 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 Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  BIER review . . . . . . . . . . . . . . . . . . . . . . .   4
     1.2.  BIER-TE review  . . . . . . . . . . . . . . . . . . . . .   4
     1.3.  RBS introduction  . . . . . . . . . . . . . . . . . . . .   5
   2.  RBS Network Architecture  . . . . . . . . . . . . . . . . . .   6
     2.1.  Controller centric  . . . . . . . . . . . . . . . . . . .   6
     2.2.  Distributed/Decentralized . . . . . . . . . . . . . . . .   7
     2.3.  Host-to-host  . . . . . . . . . . . . . . . . . . . . . .   7
   3.  Overview  . . . . . . . . . . . . . . . . . . . . . . . . . .   7
     3.1.  Example . . . . . . . . . . . . . . . . . . . . . . . . .   8
     3.2.  RBS-BIFT  . . . . . . . . . . . . . . . . . . . . . . . .   9
     3.3.  RBS Address . . . . . . . . . . . . . . . . . . . . . . .   9
     3.4.  Processing on R1 in the example . . . . . . . . . . . . .  10
   4.  Specification . . . . . . . . . . . . . . . . . . . . . . . .  11
     4.1.  RBS Address . . . . . . . . . . . . . . . . . . . . . . .  11
     4.2.  RBS-BIFT  . . . . . . . . . . . . . . . . . . . . . . . .  11
     4.3.  RBS address creation  . . . . . . . . . . . . . . . . . .  12
     4.4.  Common RBS processing . . . . . . . . . . . . . . . . . .  12
     4.5.  Reciving RBS packets  . . . . . . . . . . . . . . . . . .  12
     4.6.  Encapsulation considerations  . . . . . . . . . . . . . .  12
     4.7.  RBS forwarding Pseudocode . . . . . . . . . . . . . . . .  13
   5.  Using RBS with BIER and RFC8296 encapsulation . . . . . . . .  15
   6.  Using RBS with IPv6 extension header encapsulation  . . . . .  15
   7.  Security considerations . . . . . . . . . . . . . . . . . . .  16
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  16



Eckert, et al.            Expires 25 April 2023                 [Page 2]

Internet-Draft                  bier-rbs                    October 2022


   9.  Changelog . . . . . . . . . . . . . . . . . . . . . . . . . .  16
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  17
     10.1.  Normative References . . . . . . . . . . . . . . . . . .  17
     10.2.  Informative References . . . . . . . . . . . . . . . . .  17
   Appendix A.  High-speed implementation considerations . . . . . .  18
   Appendix B.  Complete RBS example . . . . . . . . . . . . . . . .  19
   Appendix C.  Replication efficiency performance considerations  .  19
     C.1.  Reducing number of duplicate packet copies  . . . . . . .  19
     C.2.  Statistical Analysis of performance gain  . . . . . . . .  20
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  23

1.  Introduction

   This memo introduces a compact data-structure representation of
   multicast trees called "Recursive Bitstring Structure" (RBS) and its
   use for (stateless) forwarding of packets that include this structure
   in their header.  It is intended as an alternative to "flat"
   bitstring addresses in BIER and BIER-TE or their possible variations
   such as MSR6.  RBS aims to improve performance and scalability over
   flat bitstrings and simplify operations.

   Operations is simplified because RBS does not require the use,
   management and optimization of network-wide configured address spaces
   BIFT-ID and SI and because one common RBS mechanism can replace flat
   bitstring addresses for both shortest-path forwarding and tree
   engineered forwarding.

   This document calls the bitstring addressing used today in BIER and
   BIER-TE "flat" solely as simple to remember distinction to the
   "recursive" bitstring addressing used by RBS.

   The document is structured as follows:

   The introduction reviews the aspect of BIER and BIER-TE that RBS
   intends to improve on to then give an introduction to RBS.

   The architecture section describes the models how RBS can integrate
   into comprehensive forwarding architectures such as those defineed by
   BIER/BIER-TE.

   The Overview section explains RBS address encoding and forwarding
   based on an example

   The Specification section defines normative requirements of RBS
   including forwarding Pseudocode.

   The section on using RBS with BIER and RFC8296 encapsulation
   describes proposed normative aspects when applying RBS to BIER.



Eckert, et al.            Expires 25 April 2023                 [Page 3]

Internet-Draft                  bier-rbs                    October 2022


   Appendices discuss High-speed implementation considerations and
   current insight into how well RBS can help to reducing the number of
   of packet required to be sent with RBS.

1.1.  BIER review

   In BIER, each bit of a bitstring indicates a BIER egres router
   (BFER).  When using [RFC8296] encapsulation, BitString can have a
   BitStringLength (BSL) of 2^N, N=6...12.  Routers may not be able to
   support up to 2^12=496 long BitStrings.  The most common BSL assumed
   to be supported is 256.

   When a network has a number M of BFER, M >> BSL support by routers in
   the network, it it necessary to use multiple "sets" of BitStrings
   across the network to address all BFER.  Each set has a SetIdentifier
   (SI).  BFER are identified in BIER via their BFR-id which is (SI <<
   N | 2^BP ), where BP is the BitPosition, the bit in the BitString
   used for this BFER: the lower N bits of the BFR-id are the BP of the
   BFER and the high order bits the SI.  In [RFC8279] this is also shown
   as (SI:BitString), where the BitString has only the BP of the BFER
   set.

   When a network requires k SI to address all BFER, then a message that
   needs to be sent to k arbitrary BFER in the network may require to
   send as many as k BIER packets - when each of the k BFER has a
   different SI.  The total number of packets required for any possible
   set of receiver BFER is a stochastial matter.  At best, BIER can
   reduce the number of packet required to reach M BFER to M/BSL.

   Intelligent allocation of BFR-id can lead to a more efficient
   delivery of BIER traffic.  Consider a network requiring k SI and
   random allocation of BFR-id so that every edge area of the network
   has at least one BFR in each of the k BFR.  This makes it more likely
   that up to k BIER packets need to be sent into such an area to reach
   subsets of BFR in it.  Compare this to an allocation that attempts to
   minimize the number of SI used by BFR in each individual area.  This
   will result in fewer BIER packets required to reach subsets of BFR in
   such an area.

1.2.  BIER-TE review

   Whereas BIER relies on hop-by-hop routing to direct its traffic, Tree
   Engineering for BIER (BIER-TE, [RFC9262]) is based on explicit source
   routing by encoding the whole delivery tree in a BitString.  This is
   done to support similar type of requirements as those that require
   explicit source routing in IP unicast, also called traffic steering,
   such as SRH in IPv6, but also multicast specific ones, such as lowest
   cost trees (so-called Steiner trees).



Eckert, et al.            Expires 25 April 2023                 [Page 4]

Internet-Draft                  bier-rbs                    October 2022


   BIER-TE was designed to reuse the packet encodings of BIER and as
   much as feasible of the BIER forwarding plane.  It therefore relies
   on the same type of flat BitStrings (and their addressing via SI) as
   BIER.  In BIER-TE, each bit of a BitString indicates an adjacency.
   In the most simple case those adjacencies are subnet adjacent BFR for
   the edges of the multicast tree which are called forward_connected()
   in BIER-TE, and local_decap() adjacencies for the leaves of the tree
   - effectively its BFER.

   Because BIER-TE needs to represent the whole delivery tree and not
   only its leaves/BFER in the BitString, intelligent and efficient
   allocation of BP is even more important than in BIER, and a
   significant number of BP in every SI must be allocated to transit
   hops of the network to allow defining BIER-TE trees across those
   transit hops.  In large networks this may also lead to the need to
   allocate BP across multiple SI for the same transit hops and thus a
   much larger total number of BP required to represent a smaller number
   of BFER and transit hop adjacencies - and in result also more BIER-TE
   packets required for the same message to send to the larger number of
   different SI required.

1.3.  RBS introduction

   One way to understand the Recursive BitString Structure address is to
   think of it as an evolution of BIER-TE flat bitstrings.  Every single
   BFR processing a BIER-TE bitstring only needs to look at a small
   subset of the BP in it: those BP that indicate adjacencies of this
   BFR.  All the other bits are ignored because they are adjacencies on
   other BFR.

   Consider we decompose a BIER-TE BitString into separate smaller
   bitstrings - one each for every BFR on the multicast tree that we
   want to encode.  The BitString for each BFR now only needs to have a
   BP for each subnet adjacent (neighbor) BFR.  And an equivalent to the
   local_decap() BP to indicate to the BFR itself to be a leaf/BFER on
   the multicast tree itself.

   With this step, RBS eliminates the complex optimization problems
   resulting from the flat BitStrings: There is no need anymore for a
   network wide SI address space and optimizing which adjacencies and
   BFR-id to put into which SI.  There is no hard partitioning by SI: A
   tree can span an arbitrary subset of BFR.  Just the total encoded
   size of the tree needs to fit into an appropriate maximum header
   field size.  And if the target tree is too large, then it can
   arbitrarily be broken up into overlapping subtrees - all originating
   at the sender, but each only delivering to a subset of BFER small
   enough so the encoded tree fits into the target packet header size.
   And none of these optimization have to happen at network



Eckert, et al.            Expires 25 April 2023                 [Page 5]

Internet-Draft                  bier-rbs                    October 2022


   configuration time by seeding optimized BIFT, but it happens when
   building an RBS address on on ingres router or with the help of a
   controller.

   The RBS encoding is called recursive, because it consists of such a
   local BitString for the first BFR of the tree (BFIR), followed by a
   sequence of RBS sub-trees, one for each adjacent BFR whose BP is set
   in the first BFR BitString.  Whenever a packet is forwarded to such
   an adjacent BFR, the RBS addressing information is appropriately
   updated such that that BFR will only have to examine the local
   BitString for that BFR.  In result, every BFR in RBS only has to
   examine - like in BIER and BIER-TE a single BitString.  What really
   changes is that instead of clearing bits in a flat bitstring as done
   in BIER/BIER-TE, every hop advances the decoding othe RBS address
   structure to look at a differnt, small local BitString.

2.  RBS Network Architecture

2.1.  Controller centric

   RBS may simply use the same network architecture as BIER-TE as shown
   in Figure 1, and operations of the Controller is significantly
   simplified because the complex allocation of BP across SI, especially
   the allocation of BP for transit adjacencies is eliminated.

                       Optional
      |<-IGMP/PIM->  multicast flow   <-PIM/IGMP->|
                        overlay

                       [Controller]
   control plane   .  ^      ^     ^
                  .  /       |      \     BIFT configuration
        ..........  |        |       |    per-flow RBS setup
       .            |        |       |
      .             v        v       v
   Src (-> ... ) -> BFIR-----BFR-----BFER -> (... ->) Rcvr

                   |<----------------->|
                RBS-address forwarding plane

    |<.............. <- RBS domain ---> ...............|

                 |<--------------------->|
                 Routing underlay (optional)

                 Figure 1: RBS Architecture with Controller





Eckert, et al.            Expires 25 April 2023                 [Page 6]

Internet-Draft                  bier-rbs                    October 2022


2.2.  Distributed/Decentralized

   Instead of a controller centric network architecture, RBS also lends
   itself to a distributed/decentralized model, similar to the typical
   deployment model of BIER, with extensions to a link-state IGP routing
   protocol.

   Every BFR can autoamtically allocate its BFR neighbors and derive the
   size of its local BitString and allocation of BP to each neighbor
   from it.  This is then signalled via appropriate link-state IGP
   extensions.

   BFIR can derive not only the hop-by-hop paths towards BFER from this
   IGP information, but also the necessary local BitString for each BFR
   on a tree.  In the most simple cae, these paths are the shorted-paths
   normally calculated by link-state IGP, but for traffic-engineering
   purposes, this can easily include all type of constrained path
   calculations.

   It is this model that would be attractive, when there are no tree
   engineering / traffic engineering requirements, but RBS is simply
   used to replace flat bitstrings for BIER to simplify its operations
   and (depending on size / topology of network) improve its scale /
   performance.

2.3.  Host-to-host

   To eliminate the need for an IP Multicast flow overlays and allow
   utilization of benefits of bitstring addressing at the application
   level (e.g.: eliminating group membership management for the
   network), the RBS domain may extend all the way into Sender/Receiver
   hosts.  This is possible with BIER/BIER-TE as well, but when the
   total numer of sender/receiver hosts is for example a factor 10
   larger than the number of BFR in BIER, then the elimination of the
   network wide SI/BP allocation issue of BIER/BIER-TE could help to
   make this model easier deployable with RBS than with BIER-TE/BIER.

   To avoid dependencies against initial operating system level network
   stack upgrades on hosts, such deployment option could for example be
   introduced by tunneling the RBS packets over UDP to first-hop BFIR/
   BFER as well as appropriate routing / controller plane extensions.

3.  Overview

   This section gives a more thourough run through the life of a packet
   forwarded with an RBS address.





Eckert, et al.            Expires 25 April 2023                 [Page 7]

Internet-Draft                  bier-rbs                    October 2022


3.1.  Example

   Figure 2 shows the example network topology.  R1 has network
   connections to R2, R3, R4, R5 (not shown) and R6.  R3 and R4 have
   connections to R1, R7, R8, R9 and R10.  R9 has connections to R3, R4,
   and further, not shown routers.  For the purpose of explaining RBS,
   it is irrelevant whether those connections are separate L2 point-to-
   point links or adjacencies on shared LANs.

   The example multicast tree encoded as an RBS address utilizing
   topology informtion as explained in Section 2 is R1 -> (R2, R3 ->
   (R7), R4 -> (R9 -> (...), R10), R6): The packet originates in the
   trees root R1, which needs to form the appropriate packet header with
   this trees RBS address and replicate the packet to R2, R3, R4 and R6.
   R2, R4 and R6 should receive the packet as domain egres routers.  R3
   should only replicate the pcket to R7, and R7 should replicate the
   packet to R9 and R10.  R10 should only receive the packet, R9 should
   receive the packet and further replicate it to further routers not
   shown.

                   +---+
                   |R1 | (root)
                   +-+-+
               ...........................
        .......    .           .          .
     ...           .            .          ....
     |             |            |            |
   +-v-+         +-v-+        +-v-+ (rcvr/ +-v-+
   | R2| (rcvr)  |R3 |(vertex)|R4 | leaf)  |R6 | (rcvr)
   +-+-+         +---+        +---+        +---+
                   .            .
        .................................
     ...           .         .        .....
     |             |         |            |
   +-v-+         +-v-+     +-v-+        +-v-+
   |R7 | (recvr) |R8 |     |R9 |(rcvr/  |R10| (rcvr)
   +-+-+         +---+     +---+ vertex +---+
                             .
                           .....
                       .... more vertex/leaves...

                    Figure 2: Example Topology/RBS tree

   R7, R10 and some MSER behind R9.  Given how R7, R8, R8, R10 and the
   router behind R9 can be reached via both either R3 and R4, this tree
   involves an explicit packet steering and replication (tree
   engineering) choice of using R3 instead of R4 to reach R7, and R4
   instead of R3 to reach R9, R10 (and routers below R9).



Eckert, et al.            Expires 25 April 2023                 [Page 8]

Internet-Draft                  bier-rbs                    October 2022


3.2.  RBS-BIFT

   Every router has an RBS "Bit Index Forwarding Table" (RBS-BIFT) that
   defines which BitPosition (BP) (1..N) indicates which adjacency.
   Figure 3, shows the example RBS-BIFT for R1.

   +--+-------+----------+
   |BP|R Flag | Adjacency|
   +--+-------+----------+
   | 1|      0|   receive|
   +--+-------+----------+
   | 2|      0|       R2 |
   +--+-------+----------+
   | 3|      1|       R3 |
   +--+-------+----------+
   | 4|      1|       R4 |
   +--+-------+----------+
   | 5|      0|       R5 |
   +--+-------+----------+
   | 6|      0|       R6 |
   +--+-------+----------+

                            Figure 3: BIFT on R1

   The "receive" adjacency is the BP indicating that the packet is to be
   received by the router itself.  The (R)ercursive flag indicates
   whether the adjacency when set in the BitString of an RBS address
   will have a subtree (Recursive Unit, see below) associated with it.

   The absence of the R flag allows for more compact RBS encodings or
   adjacencies that for the purpose of RBS are not used for transit.  In
   the example, R2, R5 and R6 are connected to R1 but also leaf router
   in the topology.  Hence they have R=0 in the RBS-BIFT of R1.

3.3.  RBS Address

   The RBS address as shown in Figure 4 consists of RU-Length, RU-Offset
   and RecursiveUnit0.  Depending on packet header encoding, these
   fields do not need to be encoded squentially.












Eckert, et al.            Expires 25 April 2023                 [Page 9]

Internet-Draft                  bier-rbs                    October 2022


   A RecursiveUnit (RU) is the unit of data processed by a particular
   router Rx on the multicast tree encoded by the RBS address.  RU0 is
   the RU processed by the root of the tree.  An RU consists of the
   BitString whose length is the length of the RBS-BIFT of Rx, followed
   by (N-1) AddressFields and N RUs.  N is the number of BP set in
   BitString with R=1 flag set - e.g. which do need an RU in the RBS
   address.  Each AddressField indicates the length of one RU.  There
   are only N-1 AF for N RU because the length of the N'th RU can be
   derived by calculation, saving for every router on the tree one AF
   field, and therefore resulting in a more compact encoding.

   RU-Offset indicates the offset of the current RU from the start of
   RU0. '$' in Figure 4 is the first bit of RU0, and a value of RU-
   Offset=0 indicates that the RU starts at '$' - and is therefore RU0.

   For every copy of an RBS packet made by a router, RU-Offset and RU-
   Length are updated.  None of the other fields of the RBS-Address are
   modified for RBS forwarding.

          +----------------------+
          | RU-Length            |
          +----------------------+
          | RU-Offset            |
          +----------------------+
          |$ RecursiveUnit0 (RU0)|
          +----------------------+
         .                       .
    .....                         ................
   .                                              .
   +-----------+-----+     +--------+---+     +----+
   | BitString | AF1 | ... | AF(n-1)|RU1| ... |RU N|
   +-----------+-----+     +--------+---+     +----+

                           Figure 4: RBS Address

3.4.  Processing on R1 in the example

   In the example, the root of the tree is is R1, so the BitString of
   RU0 is as shown in Figure 5

     BitString (of RU0)
    1 2 3 4 5 6
   +-+-+-+-+-+-+-..-+...+...+
   |0|1|1|1|0|1|AF1 |RU1|RU2|
   +-+-+-+-+-+-+-..-+...+...+

                         Figure 5: RU for R1 (RU0)




Eckert, et al.            Expires 25 April 2023                [Page 10]

Internet-Draft                  bier-rbs                    October 2022


   When RBS forwarding in a router processes the RBS address, the length
   of the BitString is known from the length of the RBS-BIFT.  In the
   case of R1 it is therefore known to be 6 bits long.

   Two of the BP set in the BitString, BP3 for R3 and for R4 have R=1 in
   the RBS-BIFT of R1, therefore (N-1)=1 AF field must follow and N=2 RU
   must follow in the RBS address for RU0 - one for R3, one for R4.

   When R1 creates packet copies to R3 and R4, it will rewrite RU-Length
   and RU-Offset accordingly, so that RU-offset will point to RU1 for
   the packet towards R3 and to RU2 for the packet towards R4, and RU-
   Length indicates the length of RU1 or RU2.

   This forwarding process repeats on every hop along the tree.  When a
   packet copy is made on a BP with R=0, RU-Length is set to 0.  When
   such a packet copy is received, it indicates that no further RU
   lookup is required, and the packet is only received - same as
   processing for a receive BU.

4.  Specification

4.1.  RBS Address

   Any RBS router MUST support to parse its RU with AF entries that are
   8 bit in size.  Any RBS routers SHOULD support to decode a variable
   length AF encoding, where 0XXXXXXX (8-bit length AF field) is used to
   encode a 7-bit XXXXXXX (0..127) values, and where 1XXXXXXXXXXXX is
   used to encode an 12-bit value XXXXXXXXXXX.  All values indicate the
   size of an RU in bits, therefore allowing up to 4096 bit long RU.

   An RBS router MUST support processing the BitString size of its
   configured RBS-BIFT (see Section 4.2).

   RBS routers MUST suport RU-Length and RU-Offset encodings of 12 bits.

4.2.  RBS-BIFT

   An Router must support for its RBS-BIFT to be configured with a
   number of entries ranging between min(k,1024), where k is an
   implementation specific number, no less than the number of physical
   interfaces on the router.

   The leftmost bit in an RBS RU Bitstrings is RBS-BIFT entry 1.

   The type of adjacencies to be supported depend on the encapsulation
   and are out of scope.





Eckert, et al.            Expires 25 April 2023                [Page 11]

Internet-Draft                  bier-rbs                    October 2022


4.3.  RBS address creation

   Upon creation of the RBS header with an RBS-Address, RU-Length MUST
   be set to the length of RU0 and RU-offset is set to 0.

4.4.  Common RBS processing

   Whether a header with an RBS address is created/imposed on the root
   of an RBS tree or received from another RBS router, encapsulation
   independent processing of the packet by RBS forwarding is the same.

   Parsing RBS-Address, generating copies and rewriting RU-Length and
   RU-Offset for each copy is formally described in Section 4.7

4.5.  Reciving RBS packets

   When a packet copy is received with RU-Length=0, the packet is
   "received" - it is passed up the stack to an appropriate receiving
   entity based on the encapsulation parameters.

   When a packet copy is made for a receive BP, its RU-Length is set to
   0 and the packet is processed as if it was received with RU-Length=0.

4.6.  Encapsulation considerations

   The total length of an RBS address is not included in the definition
   of an RBS address here.  This length is assumed to be provided by
   some other packet header field, because it is not required to parse
   an RBS address itself, but is only required to parse beyond an RBS
   address in a packet header by an RBS unaware parser.  The field that
   carries RU0 may be larger (for example due to padding) than RU0
   itself without problems for the RBS parsing/processing described
   here.

   Additional forwarding rules may be established by specific
   encapsulations such as BIER OAM processing steps when using BIER with
   RFC8296 encapsulation.

   Given how the processing of the RBS address describes a naturally
   loop-free rewrite operation, no further loop-prevention mechanism is
   required in packet processing with RBS addresses, but no harm is done
   if this is still performed (on appropriate header TTL fields
   independent of RBS).








Eckert, et al.            Expires 25 April 2023                [Page 12]

Internet-Draft                  bier-rbs                    October 2022


4.7.  RBS forwarding Pseudocode

   The following RBS forwarding (derived from C language) pseudocode
   assumes all pointers (and dereferencing them) are using bit-accurate
   addresses so that of calculation of starting bit addresses of address
   fields and RU in RU0 can be shown with as simple code as if byte
   addressing for pointers was used.  byte addressing of pointers was
   used.  This is NOT supported by C language!

  void ForwardRBS(Packet)
  {
    // parse bit accurate addresses of RBS address fields in Packet into
    // RBS.{RULength,RUOffset,RU0}
    RBS = ParseRBSAddress(Packet);

    if(*(RBS.RULength) == 0) return ReceiveRBS(Packet);
    RU  = RBS.RU0 + *(RBS.RUOffset);
    RUL = *(RBS.RULength);

    BitStringA = RU
    AddressingField =  BitStringA + BIFT.entries;

    // [1] calculate number of R=1 BP set in BitString
    CopyBitString(*BitStringA, *RecursiveBits, BIFT.entries);
    And(*RecursiveBits,*BIFTRecursiveBits, BIFT.entries);
    N = CountBits(*RecursiveBits, BIFT.entries);

    // Start of first RecursiveUnit in RBS address
    // After AddressingField array with 8-bit length fields
    RecursiveUnit = AddressingField + (N - 1) * 8;

    RemainLength = *(RBS.RULength);
    Index = GetFirstBitPosition(*BitStringA);
    while (Index) {
      PacketCopy = Copy(Packet);
      RBSc = ParseRBSAddress(PacketCopy)
      if (BIFT.BP[Index].adjacency == receive)
        *(RBSc.RULength) = 0;
        ReceiveRBS(PacketCopy);
        next;
      }

      If (BIFT.BP[Index].recursive) {
        if(N == 1) {
          RecursiveUnitLength = RemainLength;
        } else {
          RecursiveUnitLength = *AddressingField;
          N--;



Eckert, et al.            Expires 25 April 2023                [Page 13]

Internet-Draft                  bier-rbs                    October 2022


          AddressingField += 8;
          RemainLength -= RecursiveUnitLength;
          RemainLength -= 8; // 8 bit of AddressingField
        }
        *(RBSc.RUOffset) = RecursiveUnit - RU0
        *(RBSc.RULength) = RecursiveUnitLength
        RecursiveUnit += RecursiveUnitLength;
      } else {
        *(RBSc.RUOffset) = 0
        *(RBSc.RULength) = 0
        *(MSR6c.SegmentsLeft) -= 1
      }
      SendTo(PacketCopy, BIFT.BP[Index].adjacency)
      Index = GetNextBitPosition(*BitStringA, Index);
    }
  }

                   Figure 6: RBS forwarding Pseudocode

   Explanations for Figure 6.

   ForwardRBS(Packet) processes the RBS address independent of its
   encapsulation.  ParseRBSAddress(Packet) parses the header of Packet
   to create a list of bit-accurate pointers to the elements of an RBS
   address: RBS.{RULength,RUOffset,RU0}.

   BitStringA is the address of the RBS address BitString in Packet.
   Other variables use names matching those from the packet header
   figures (without " -_").

   The BFR local BIFT has a total number of BIFT.entries addressable BP
   1...BIFTentries.  The BitString therefore has BIFT.entries bits.

   BIFT.RecursiveBits is a BitString pre-filled by the control plane
   with all the BP with the recursive flag set.  This is constructed
   from the Recursive flag setting of the BP of the BIFT.  The code
   starting at [1] therefore counts the number of recursive BP in the
   packets BitString.

   Because the AddressingField does not have an entry for the last
   (potentially only) RecursiveUnit, its length has to be calculated By
   subtracting the length of the prior N-1 RecursiveUnits from RULength
   as received.  This is done via variable RemainLength.

   For every PacketCopy that is to be forwarded, the RU-Length and RU-
   Offset fields are updated.  SendTo(packet,adjacency) takes care of
   any encapsulation/architecture specific further rewrites of the
   packet headers based on the adjcency of the BP.



Eckert, et al.            Expires 25 April 2023                [Page 14]

Internet-Draft                  bier-rbs                    October 2022


5.  Using RBS with BIER and RFC8296 encapsulation

   RBS can be used in a BIER domain by introducing as a per-subdomin
   mode of forwarding, exactly the same as [RFC8279] (non-TE) BIER and
   [RFC9262] BIER-TE can co-exist in a BIER.

   In BIER deployments, RBS can most easily replace BIER-TE, and using a
   centralized controller and therefore simplify and esier scale
   deployment of tree engineering.  RBS should also be able to replace
   BIER in networks with link-state routing protocols and reduce the
   number of replicated packets in large networks.  This requires as
   aforementioned the change from hop-by-hop routing to sourc-routing.

   When using BIER, RBS routers are BFR, RBS ingres routers are BFIR,
   RBS egres routers are BFER.  Routers may support multiple RBS-BIFT
   through different BIFT-ID or SI.  This may be useful when specific
   constructs such as slices of the network are only allowed to use a
   subset of the adjacencies of the network.

   The RBS address is encoded as a binary string concatenating
   {RULenth,RUOffset,RU0} into the BitString field in [RFC8296] packet
   headers.  Without changes to [RFC8296], the length of this field has
   to be a power of 2 sized.  The RBS address SHOULD be zero-padded to
   the size used.

   In BIER, the BitStringLength (BSL) expects to indicate different
   BIFT.  When using RBS addresses, it SHOULD be possible for all
   supported BSL to refer to the same RBS-BIFT, so that upon imposition
   of an RBS-Address the smallest power of 2 BitString size can be used
   without duplication of BIFT state on routers.

   SendTo() of RBS forwarding pseudocode Section 4.7 needs to take care
   of any BIER specific rewrites of the [RFC8296] BIER header,
   specifically the BIFT-id derived from the RBS-BIFT adjacency.

   TBD: This description does not outline, how much of existing BIER IGP
   extensions could be reused with RBS and how.

6.  Using RBS with IPv6 extension header encapsulation

   Solutions for stateless IP multicast have been proposed to the IETF
   under the name Multicast Source Routing for IPv6 (MSR6).  They are
   based on putting the stateless multicast structures into an IPv6
   routing extension headers and using per-steering-hop rules according
   to or derived from [RFC8200], Section 4.4 rules.  IPv6 forwarding")
   for source routing.





Eckert, et al.            Expires 25 April 2023                [Page 15]

Internet-Draft                  bier-rbs                    October 2022


   SendTo() of RBS forwarding pseudocode Section 4.7 needs to take care
   of any IPv6 specific rewrites of the IPv6 header (IPv6 Destination
   address) and IPv6 routing extension header.

   For complete support of IPv6 multicast with [RFC8200] compliant
   source routing, it is necessary for the IPv6 routing extension header
   to not only carry the RBS address information but also an IPv6
   multicast destination address field.

   [I-D.eckert-msr6-rbs] is a proposed IPv6 extension header design for
   MSR6 using RBS that is supporting IPv6 multicast.

7.  Security considerations

8.  Acknowledgements

   This work is based on the design published by Sheng Jiang, Xu Bing,
   Yan Shen, Meng Rui, Wan Junjie and Wang Chuang {jiangsheng|bing.xu|ya
   nshen|mengrui|wanjunjie2|wangchuang}@huawei.com, see [CGM2Design].
   Many thanks for Bing Xu (bing.xu@huawei.com) for editorial work on
   the prior variation of this work [I-D.xu-msr6-rbs].

9.  Changelog

   [RFC-editor: please remove]

   This document is written in https://github.com/cabo/kramdown-rfc2629
   markup language.  This documents source is maintained at
   https://github.com/toerless/multicast-rbs, please provide feedback to
   the bier@ietf.org and/or msr6@ietf.org mailing list and submit an
   Issue to the GitHub.

   This draft is derived from and superceeds [I-D.eckert-bier-cgm2-rbs]
   as follows:

   *  Removes larger architectural context (CGM2) and refocusses on only
      RBS.

   *  Add explanation about possible distributed/decentralized control
      plane via link-state IGP to complement the central controller
      based approach.

   *  Define its procedures independent of specific architectures such
      as BIER wih RFC8296 encapsulation or proposed MSR encoding.







Eckert, et al.            Expires 25 April 2023                [Page 16]

Internet-Draft                  bier-rbs                    October 2022


   *  Inherits the RBS specific improvements originally introduced with
      [I-D.eckert-msr6-rbs].  RU-Length and RU-Offset to avoid rewriting
      complete RBS address with the RU of the next hop and instead just
      updating these two indices when forwarding RBS address.

   *  Adds specific proposed encapsulation details for BIER.

10.  References

10.1.  Normative References

   [RFC8200]  Deering, S. and R. Hinden, "Internet Protocol, Version 6
              (IPv6) Specification", STD 86, RFC 8200,
              DOI 10.17487/RFC8200, July 2017,
              <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>.

   [RFC8296]  Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A.,
              Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation
              for Bit Index Explicit Replication (BIER) in MPLS and Non-
              MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January
              2018, <https://www.rfc-editor.org/info/rfc8296>.

   [RFC9262]  Eckert, T., Ed., Menth, M., and G. Cauchie, "Tree
              Engineering for Bit Index Explicit Replication (BIER-TE)",
              RFC 9262, DOI 10.17487/RFC9262, October 2022,
              <https://www.rfc-editor.org/info/rfc9262>.

10.2.  Informative References

   [CGM2Design]
              Jiang, S., Xu, B. (Robin)., Shen, Y., Rui, M., Junjie, W.,
              and W. Chuang, "Novel Multicast Protocol Proposal
              Introduction", 10 October 2021,
              <https://github.com/BingXu1112/CGMM/blob/main/Novel%20Mult
              icast%20Protocol%20Proposal%20Introduction.pptx>.










Eckert, et al.            Expires 25 April 2023                [Page 17]

Internet-Draft                  bier-rbs                    October 2022


   [I-D.eckert-bier-cgm2-rbs]
              Eckert, T. T. and B. Xu, "Carrier Grade Minimalist
              Multicast (CGM2) using Bit Index Explicit Replication
              (BIER) with Recursive BitString Structure (RBS)
              Addresses", Work in Progress, Internet-Draft, draft-
              eckert-bier-cgm2-rbs-01, 9 February 2022,
              <https://www.ietf.org/archive/id/draft-eckert-bier-cgm2-
              rbs-01.txt>.

   [I-D.eckert-msr6-rbs]
              Eckert, T. T., Geng, X., Zheng, X., Meng, R., and F. Li,
              "Recursive Bitstring Structure (RBS) for Multicast Source
              Routing over IPv6 (MSR6)", Work in Progress, Internet-
              Draft, draft-eckert-msr6-rbs-00, 11 July 2022,
              <https://www.ietf.org/archive/id/draft-eckert-msr6-rbs-
              00.txt>.

   [I-D.xu-msr6-rbs]
              Xu, B., Geng, X., and T. T. Eckert, "RBS(Recursive
              BitString Structure) for Multicast Source Routing over
              IPv6", Work in Progress, Internet-Draft, draft-xu-msr6-
              rbs-01, 30 March 2022, <https://www.ietf.org/archive/id/
              draft-xu-msr6-rbs-01.txt>.

Appendix A.  High-speed implementation considerations

   RBS was designed with high-speed, low-cost forwarding hardware and
   possible backward compatibility with potentially existing flat-
   bitstring look-up and replication hardware in mind.

   Because RBS requires to only perform replication on each router on a
   single bitstring, it could be possible to reuse existing bitstring
   replication hardware, or design future hardware such that it supports
   BIER, BIER-TE and RBS bitstrings.

   The calculations required to process an RBS header are the added
   complexity of processing RBS packets are the additional new cost of
   RBS.  It has to be seen whether / how these are feasible at the low-
   end of high-speed forwarding plane hardware, especially P4.  Further
   optimizations to reduce calculations are possible, but at the expense
   of compression of the RBS address.

   RBS also minimizes write-cycles to packet memory by only requiring
   per-packet-copy rewrites of the RU-Length and RU-Offset fields.  With
   mandatory encoding of 12 bits each, these are 24 bits to rewrite and
   should therefore be causing minimal cost with todays high-speed
   forwarding hardware.




Eckert, et al.            Expires 25 April 2023                [Page 18]

Internet-Draft                  bier-rbs                    October 2022


Appendix B.  Complete RBS example

   TBD: Need to rewrite more elaborete multi-hop example from
   [I-D.eckert-bier-cgm2-rbs] with RU-Offset, RU-Length.

Appendix C.  Replication efficiency performance considerations

   This section discusses in more detail the number of packets required
   to reach a set of receivers when using flat bitstrings vs. RBS
   addresses.  The first sub-section gives a hopefully simple to
   understand theoretical topology example, the second sub-section
   presents initial results of a real-world, large-network simulation.

C.1.  Reducing number of duplicate packet copies

   If the total size of an RBS encoded delivery tree is larger than a
   supported maximum RBS header size, then the controller simply needs
   to divide the tree into multiple subtrees, each only addressing a
   part of the BFER (leaves) of the target tree and pruning any
   unnecessary branches.

                B1
               /  \
         B2    B3
           /   \  /  \
          /     \/    \
        B4      B5     B6
      /..|     /  \    |..\
   B7..B99  B100..B200 B201...B300

                     Figure 7: Simple Topology Example

   Consider the simple topology in Figure 7 and a multicast packet that
   needs to reach all BFER B7...B300.  Assume that the desired maximum
   RBM header size is such that a RBS address size of <= 256 bits is
   desired.  The controller could create an RBS address
   B1=>B2=>B4=>(B7..B99), for a first packet, an RBS address
   B1=>B3=>B5=>(B100..B200) for a second packet and a third RBS address
   B1=>B3=>B6=>B201...B300.

   The elimination of larger BIFT state in BFR through multiple SI in
   BIER/BIER-TE does come at the expense of replicating initial hops of
   a tree in RBS addresses, such as in the example the encoding of
   B1=>B3 in the example.

   Consider that the assignment of BFIR-ids with BIER in the above
   example is not carefully engineered.  It is then easily possible that
   the BFR-ids for B7..B99 are not sequentially, but split over a larger



Eckert, et al.            Expires 25 April 2023                [Page 19]

Internet-Draft                  bier-rbs                    October 2022


   BFIR-id space.  If the same is true for all BFER, then it is possible
   that each of the three BFR B4,B5 and B6 has attached BFER from three
   different SI and one may need to send for example three multiple
   packets to B7 to address all BFER B7..B99 or to B5 to address all
   B100..B200 or B6 to address all B201...B300.  These unnecessary
   duplicate packets across B4, B5 or B6 are because of the addressing
   principle in BIER and are not necessary in RBS, as long as the total
   length of an RBS address does not require it.

C.2.  Statistical Analysis of performance gain

   TBD: Comparison of number of packets/header sizes required in large
   real-world operator topology between BIER/BIER-TE and RBS.  Analysis:
   Gain in dense topology

   Topology description: 1.  Typical topology of Beijing Mobile in
   China. 2.  All zones dual homing access to backbone. 3.  Core layer:
   4 nodes full mesh connected 4.  Aggregation layer: 8 nodes are
   divided into two layers, with full interconnection between the layers
   and dual homing access to the core layer on the upper layer. 5.
   Aggregation rings: 8 rings, 6 nodes per ring 6.  Access rings: 3600
   nodes, 18 nodes per ring

                     ┌──────┐          ┌──────┐
                     │      ├──────────┤      │
                    /└──────┘\        /└──────┘\   Interconnected
                   /   / | \  \      /  / | \   \   BackBone
          ┌──────┐/   /  |  \  \    /  /  |  \   \┌──────┐
          │      │   /   |   \  \  /  /   |   \   │      │
          └───┬──┘  /    |    \  \/  /    |    \  └─┬────┘
              │    /     |     \ /\ /     |     \   │
           ┌──┴───┐      |      /  \      |      ┌──┴───┐
           │      │------------+ \/ +------------│      │
           └──────┘\     |       /\       |     /└──────┘
                    \    |      /  \      |    /
                     \ ┌──────┐/    \┌──────┐ /
                      \│      ├──────┤      │/
                       └───┬──┘      └───┬──┘
                           │   \     /   │  Dual Return Access
                           │    \   /    │
                           │     \ /     │
                           │      /      │
                           │     / \     │
                         ┌─┴───┐/   \┌───┴─┐
                         │     ├─────┤     │
                         └─┬───┘\   /└───┬─┘
                           │     \ /     │  Core Layer
                           │      /      │



Eckert, et al.            Expires 25 April 2023                [Page 20]

Internet-Draft                  bier-rbs                    October 2022


                           │     / \     │
                         ┌─┴───┐/   \┌───┴─┐
                        /│     ├─────┤     │\
                       / └──┬──┘\   /└──┬──┘ \
                      /     │\   \ /   /│     \   Zone1
                     /      │ \   \   / │      \
                    /       │  \ / \ /  │       \
                   /   +----│---+   +---│----+   \
                  /   /     │    \ /    │     \   \
                 /   /      │     +     │      \   \
                /   /       │    / \    │       \   \
              ┌───┐/       ┌┴──┐/   \┌──┴┐       \┌───┐
              │   │\      /│   │     │   │\      /│   │
              └─┬─┘ \    / └─┬─┘\   /└─┬─┘ \    / └─┬─┘  Aggregation
                │    \  /    │   \ /   │    \  /    │    Layer
                │     \/     │    /    │     \/     │
                │     /\     │   / \   │     /\     │
              ┌─┴─┐  /  \  ┌─┴─┐/   \┌─┴─┐  /  \  ┌─┴─┐
              │   │--    --│   │     │   │--    --│   │
              └───┘        └───┘\   /└───┘\       └───┘
                           / | \ \ /  / |  \
                          /  |  \ \  /  |   \
                         /   |   / \/   |    \
                        / +--|--+ \/+---|---+ \
                       / /   |    /\    |    \ \
                    ┌───┐   ┌┴──┐/  \┌───┐   ┌───┐   ASBR
                    │   │   │   │    │   │   │   │
                    └─┬─┘   └─┬─┘    └─┬─┘   └─┬─┘
                      │       │        │       │
                      │       │        │       │
                    ┌─┴─┐   ┌─┴─┐    ┌─┴─┐   ┌─┴─┐
                    │   │   │   │    │   │   │   │
                    └─┬─┘   └─┬─┘    └─┬─┘   └─┬─┘
                      │       │        │       │
                      │       │ 8Rings │       │
                    ┌─┴─┐   ┌─┴─┐ ...┌─┴─┐   ┌─┴─┐
                    │   │---│   │    │   │---│   │
                ----└───┘   └───┘    └───┘\  └───┘
               /   /   \  \   |  \       \ \    |  \
             /    /     \  \  |   \       \ +---|-+ \
            /    /       \  +-|---+\       \    |  \ \
          /     /         \   |    \\       \   |   \ \
         /     /           \  |     \\       \  |    \ \
        /     /             \ |      \\       \ |     \ \
   ┌───┐   ┌───┐           ┌───┐   ┌───┐       ┌───┐   ┌───┐ CSBR
   │   │   │   │           │   │   │   │       │   │   │   │
   └─┬─┘   └─┬─┘           └─┬─┘   └─┬─┘       └─┬─┘   └─┬─┘
     │       │    Access     │       │           │       │



Eckert, et al.            Expires 25 April 2023                [Page 21]

Internet-Draft                  bier-rbs                    October 2022


     │       │    Rings      │       │           │       │
   ┌─┴─┐   ┌─┴─┐  ...      ┌─┴─┐   ┌─┴─┐       ┌─┴─┐   ┌─┴─┐
   │   │   │   │           │   │   │   │       │   │   │   │
   └─┬─┘   └─┬─┘           └─┬─┘   └─┬─┘       └─┬─┘   └─┬─┘
     │       │               │       │           │       │
     │       │               │       │           │       │
   ┌─┴─┐   ┌─┴─┐           ┌─┴─┐   ┌─┴─┐       ┌─┴─┐   ┌─┴─┐
   │   │   │   │           │   │   │   │       │   │   │   │
   └───┘...└───┘           └───┘...└───┘       └───┘...└───┘

                       Figure 8: Validation Topology

   Comparison notes:

   1.  RBS: We randomly select egress points as group members, with the
       total number ranging from 10 to 28800 (for sake of simplicity, we
       assume merely one client per egress point).  The egress points
       are randomly distributed in the topology with 10 runs for each
       value, showing the average result in our graphs as below.  The
       total number of samples is 60

   2.  BIER: We divide the overall topology into 160 BIER domains, each
       of which includes 180 egress points, providing the total of 28000
       egress points.

   3.  Simulation: In order to compare the BIER against the in-packet
       tree encoding mechanism, we limit the size of the header to 256
       bits (the typical size of a BIER header).

   Results are shown in the following image: https://user-
   images.githubusercontent.com/92767820/153332926-defe38e4-1b63-4b16-
   852f-feaae487d307.png

   Conclusions:

   1.  BIER reaches its 160 packet replication limit at about 500 users,
       while the in-packet tree encoding reaching its limit of 125
       replications at about 12000 users.  And the following decrease of
       replications is caused by the use of node-local broadcast as a
       further optimization.

   2.  For the sake of comparison, the same 256-bit encapsulation limit
       is imposed on RBS, but we can completely break the 256-bit
       encapsulation limit, thus allowing the source to send fewer
       multicast streams.

   3.  RBS encoding performs significantly better than BIER in that it
       requires less packet replications and network bandwidth.



Eckert, et al.            Expires 25 April 2023                [Page 22]

Internet-Draft                  bier-rbs                    October 2022


Authors' Addresses

   Toerless Eckert (editor)
   Futurewei Technologies USA
   2220 Central Expressway
   Santa Clara,  CA 95050
   United States of America
   Email: tte@cs.fau.de


   Michael Menth
   University of Tuebingen
   Germany
   Email: menth@uni-tuebingen.de


   Xuesong Geng
   Huawei 2012 NT Lab
   China
   Email: gengxuesong@huawei.com


   Xiuli Zheng
   Huawei 2012 NT Lab
   China
   Email: zhengxiuli@huawei.com


   Rui Meng
   Huawei 2012 NT Lab
   China
   Email: mengrui@huawei.com


   Fengkai Li
   Huawei 2012 NT Lab
   Email: lifengkai@huawei.com














Eckert, et al.            Expires 25 April 2023                [Page 23]