Tech-invite   World Map
3GPPspecs     Glossaries     T+       IETF     RFCs     Groups     SIP     ABNFs

RFC 8279

 
 
 

Multicast Using Bit Index Explicit Replication (BIER)

Part 2 of 3, p. 13 to 29
Prev Section       Next Section

 


prevText      Top      ToC       Page 13 
5.  Advertising BFR-ids and BFR-Prefixes

   As stated in Section 2, each BFER is assigned (by provisioning) a
   BFR-id (for a given BIER sub-domain).  Each BFER must advertise these
   assignments to all the other BFRs in the domain.  Similarly, each BFR
   is assigned (by provisioning) a BFR-prefix (for a given BIER domain)
   and must advertise this assignment to all the other BFRs in the
   domain.  Finally, each BFR has been provisioned to use a certain set
   of Disposition BitStringLengths for each sub-domain and must
   advertise these to all other BFRs in the domain.

Top      Up      ToC       Page 14 
   If the BIER domain is also a link-state routing IGP domain (i.e., an
   OSPF or IS-IS domain), the advertisement of the BFR-prefix,
   <sub-domain-id, BFR-id>, and BitStringLength can be done using the
   advertisement capabilities of the IGP.  For example, if a BIER domain
   is also an OSPF domain, these advertisements can be done using the
   OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism.
   Details of the necessary extensions to OSPF and IS-IS will be
   provided in companion documents.  (See [OSPF_BIER_EXTENSIONS] and
   [ISIS_BIER_EXTENSIONS].)

   If, in a particular deployment, the BIER domain is not an OSPF or
   IS-IS domain, procedures suitable to the deployment must be used to
   advertise this information.  Details of the necessary procedures will
   be provided in companion documents.  For example, if BGP is the only
   routing algorithm used in the BIER domain, the procedures of
   [BGP_BIER_EXTENSIONS] may be used.

   These advertisements enable each BFR to associate a given
   <sub-domain-id, BFR-id> with a given BFR-prefix.  As will be seen in
   subsequent sections of this document, knowledge of this association
   is an important part of the forwarding process.

   Since each BFR needs to have a unique (in each sub-domain) BFR-id,
   two different BFRs will not advertise ownership of the same
   <sub-domain-id, BFR-id> unless there has been a provisioning error.

   o  If BFR-A determines that BFR-B and BFR-C have both advertised the
      same BFR-id for the same sub-domain, BFR-A MUST log an error.
      Suppose that the duplicate BFR-id is "N".  When BFR-A is
      functioning as a BFIR, it MUST NOT encode the BFR-id value N in
      the BIER encapsulation of any packet that has been assigned to the
      given sub-domain, even if it has determined that the packet needs
      to be received by BFR-B and/or BFR-C.

      This will mean that BFR-B and BFR-C cannot receive multicast
      traffic at all in the given sub-domain until the provisioning
      error is fixed.  However, that is preferable to having them
      receive each other's traffic.

   o  Suppose that BFR-A has been provisioned with BFR-id N for a
      particular sub-domain but that it has not yet advertised its
      ownership of BFR-id N for that sub-domain.  Suppose also that it
      has received an advertisement from a different BFR (say BFR-B)
      that is advertising ownership of BFR-id N for the same sub-domain.
      In such a case, BFR-A SHOULD log an error and MUST NOT advertise
      its own ownership of BFR-id N for that sub-domain as long as the
      advertisement from BFR-B is extant.

Top      Up      ToC       Page 15 
      This procedure may prevent the accidental misconfiguration of a
      new BFR from impacting an existing BFR.

   If a BFR advertises that it has a BFR-id of 0 in a particular
   sub-domain, other BFRs receiving the advertisement MUST interpret
   that advertisement as meaning that the advertising BFR does not have
   a BFR-id in that sub-domain.

6.  BIER Intra-Domain Forwarding Procedures

   This section specifies the rules for forwarding a BIER-encapsulated
   data packet within a BIER domain.  These rules are not intended to
   specify an implementation strategy; to conform to this specification,
   an implementation need only produce the same results that these rules
   produce.

6.1.  Overview

   This section provides a brief overview of the BIER forwarding
   procedures.  Subsequent subsections specify the procedures in more
   detail.

   To forward a BIER-encapsulated packet:

   1.  Determine the packet's sub-domain.

   2.  Determine the packet's BitStringLength and BitString.

   3.  Determine the packet's SI.

   4.  From the sub-domain, the SI, and the BitString, determine the set
       of destination BFERs for the packet.

   5.  Using information provided by the routing underlay associated
       with the packet's sub-domain, determine the next-hop adjacency
       for each of the destination BFERs.

   6.  It is possible that the packet's BitString will have one or more
       bits that correspond to BFR-ids that are not in use.  It is also
       possible that the packet's BitString will have one or more bits
       that correspond to BFERs that are unreachable, i.e., that have no
       next-hop adjacency.  In the following, we will consider the
       "next-hop adjacency" for all such bit positions to be the "null"
       next hop.

   7.  Partition the set of destination BFERs such that all the BFERs in
       a single partition have the same next hop.  We will say that each
       partition is associated with a next hop.

Top      Up      ToC       Page 16 
   8.  For each partition:

       a.  Make a copy of the packet.

       b.  Clear any bit in the packet's BitString that identifies a
           BFER that is not in the partition.

       c.  Transmit the packet to the associated next hop.  (If the
           next hop is the null next hop, the packet is discarded.)

   If a BFR receives a BIER-encapsulated packet whose <sub-domain, SI,
   BitString> triple identifies that BFR itself, then the BFR is also a
   BFER for that packet.  As a BFER, it must pass the payload to the
   multicast flow overlay.  If the BitString has bits set for other
   BFRs, the packet also needs to be forwarded further within the BIER
   domain.  If the BF(E)R also forwards one or more copies of the packet
   within the BIER domain, the bit representing the BFR's own BFR-id
   MUST be clear in all the copies.

   When BIER on a BFER is to pass a packet to the multicast flow
   overlay, it of course decapsulates the packet by removing the BIER
   header.  However, it may be necessary to provide the multicast flow
   overlay with contextual information obtained from the BIER
   encapsulation.  The information that needs to pass between the BIER
   layer and the multicast flow overlay is specific to the multicast
   flow overlay.  Specification of the interaction between the BIER
   layer and the multicast flow overlay is outside the scope of this
   specification.

   If the BIER encapsulation contains a "Time to Live" (TTL) value, this
   value is not, by default, inherited by the payload.  If a particular
   multicast flow overlay needs to know the TTL value, this needs to be
   specified in whatever specification defines the interaction between
   BIER and that multicast flow overlay.

   If the BIER encapsulation contains a Traffic Class field, a
   Type of Service field, a Differentiated Services field, or any field
   of that sort, the value of that field is not, by default, passed to
   the multicast flow overlay.  If a particular multicast flow overlay
   needs to know the values of such fields, this fact needs to be
   specified in whatever specification defines the interaction between
   BIER and that multicast flow overlay.

   When BIER on a BFER passes a packet to the multicast flow overlay,
   the overlay will determine how to further dispatch the packet.  If
   the packet needs to be forwarded into another BIER domain, then the
   BFR will act as a BFER in one BIER domain and as a BFIR in another.

Top      Up      ToC       Page 17 
   A BIER-encapsulated packet cannot pass directly from one BIER domain
   to another; at the boundary between BIER domains, the packet must be
   decapsulated and passed to the multicast flow overlay.

   Note that when a BFR transmits multiple copies of a packet within a
   BIER domain, only one copy will be destined to any given BFER.
   Therefore, it is not possible for any BIER-encapsulated packet to be
   delivered more than once to any BFER.

6.2.  BFR Neighbors

   The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those
   BFRs that, according to the routing underlay, are adjacencies of
   BFR-A.  Each BFR-NBR will have a BFR-prefix.

   Suppose a BIER-encapsulated packet arrives at BFR-A.  From the
   packet's encapsulation, BFR-A learns (a) the sub-domain of the packet
   and (b) the BFR-ids (in that sub-domain) of the BFERs to which the
   packet is destined.  Then, using the information advertised per
   Section 5, BFR-A can find the BFR-prefix of each destination BFER.
   Given the BFR-prefix of a particular destination BFER, say BFER-D,
   BFR-A learns from the routing underlay (associated with the packet's
   sub-domain) an IP address of the BFR that is the next hop on the path
   from BFR-A to BFER-D.  Let's call this next hop "BFR-B".  BFR-A must
   then determine the BFR-prefix of BFR-B.  (This determination can be
   made from the information advertised per Section 5.)  This BFR-prefix
   is the BFR-NBR of BFR-A on the path from BFR-A to BFER-D.

   Note that if the routing underlay provides multiple equal-cost paths
   from BFR-A to BFER-D, BFR-A may have multiple BFR-NBRs for BFER-D.

   Under certain circumstances, a BFR may have adjacencies (in a
   particular routing underlay) that are not BFRs.  Please see
   Section 6.9 for a discussion of how to handle those circumstances.

Top      Up      ToC       Page 18 
6.3.  The Bit Index Routing Table

   The "Bit Index Routing Table" (BIRT) is a table that maps from the
   BFR-id (in a particular sub-domain) of a BFER to the BFR-prefix of
   that BFER, and to the BFR-NBR on the path to that BFER.  As an
   example, consider the topology shown in Figure 1.  In this diagram,
   we represent the BFR-id of each BFR in the SI:xyzw form discussed in
   Section 3.

      ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D )
     4 (0:1000)             \                  \           1 (0:0001)
                             \                  \
                             ( E )              ( F )
                           3 (0:0100)         2 (0:0010)

                         Figure 1: BIER Topology 1

   This topology will result in the BIRT of Figure 2 at BFR-B.  The
   first column shows the BFR-id as a number and also (in parentheses)
   in the SI:BitString format that corresponds to a BitStringLength
   of 4.  (The actual minimum BitStringLength is 64, but we use 4 in the
   examples.)

   Note that a BIRT is specific to a particular BIER sub-domain.

               --------------------------------------------
               |     BFR-id     |  BFR-Prefix  | BFR-NBR  |
               | (SI:BitString) | of Dest BFER |          |
               ============================================
               |   4 (0:1000)   |     A        |     A    |
               --------------------------------------------
               |   1 (0:0001)   |     D        |     C    |
               --------------------------------------------
               |   3 (0:0100)   |     E        |     E    |
               --------------------------------------------
               |   2 (0:0010)   |     F        |     C    |
               --------------------------------------------

                Figure 2: Bit Index Routing Table at BFR-B

Top      Up      ToC       Page 19 
6.4.  The Bit Index Forwarding Table

   The "Bit Index Forwarding Table" (BIFT) is derived from the BIRT as
   follows.  (Note that a BIFT is specific to a particular sub-domain.)

   Suppose that several rows in the BIRT have the same SI and the same
   BFR-NBR.  By taking the logical OR of the BitStrings of those rows,
   we obtain a bit mask that corresponds to that combination of SI and
   BFR-NBR.  We will refer to this bit mask as the "Forwarding Bit Mask"
   (F-BM) for that <SI, BFR-NBR> combination.

   For example, in Figure 2, we see that two of the rows have the same
   SI (0) and same BFR-NBR (C).  The bit mask that corresponds to
   <SI=0, BFR-NBR-C> is 0011 ("0001" OR'd with "0010").

   The BIFT is used to map from the BFR-id of a BFER to the
   corresponding F-BM and BFR-NBR.  For example, Figure 3 shows the BIFT
   that is derived from the BIRT of Figure 2.  Note that BFR-ids 1 and 2
   have the same SI and the same BFR-NBR; hence, they have the
   same F-BM.

                   -------------------------------------
                   |      BFR-id    |  F-BM  | BFR-NBR |
                   | (SI:BitString) |        |         |
                   =====================================
                   |   1 (0:0001)   |  0011  |    C    |
                   -------------------------------------
                   |   2 (0:0010)   |  0011  |    C    |
                   -------------------------------------
                   |   3 (0:0100)   |  0100  |    E    |
                   -------------------------------------
                   |   4 (0:1000)   |  1000  |    A    |
                   -------------------------------------

                   Figure 3: Bit Index Forwarding Table

   This BIFT is programmed into the data plane and used to forward
   packets, applying the rules specified below in Section 6.5.

Top      Up      ToC       Page 20 
6.5.  The BIER Forwarding Procedure

   Below is the procedure that a BFR uses for forwarding a
   BIER-encapsulated packet.

   1.  Determine the packet's SI, BitStringLength, and sub-domain.

   2.  If the BitString consists entirely of zeroes, discard the packet;
       the forwarding process has been completed.  Otherwise, proceed to
       step 3.

   3.  Find the position (call it "k") of the least significant (i.e.,
       of the rightmost) bit that is set in the packet's BitString.
       (Remember, bits are numbered from 1, starting with the least
       significant bit.)

   4.  If bit k identifies the BFR itself, copy the packet, and send the
       copy to the multicast flow overlay.  Then clear bit k in the
       original packet, and go to step 2.  Otherwise, proceed to step 5.

   5.  Use the value k, together with the SI, sub-domain, and
       BitStringLength, as the "index" into the BIFT.

   6.  Extract from the BIFT the F-BM and the BFR-NBR.

   7.  Copy the packet.  Update the copy's BitString by AND'ing it with
       the F-BM (i.e., PacketCopy->BitString &= F-BM).  Then forward the
       copy to the BFR-NBR.  (If the BFR-NBR is null, the copy is just
       discarded.)  Note that when a packet is forwarded to a particular
       BFR-NBR, its BitString identifies only those BFERs that are to be
       reached via that BFR-NBR.

   8.  Now update the original packet's BitString by AND'ing it with the
       INVERSE of the F-BM (i.e., Packet->BitString &= ~F-BM).  (This
       clears the bits that identify the BFERs to which a copy of the
       packet has just been forwarded.)  Go to step 2.

   This procedure causes the packet to be forwarded to a particular
   BFR-NBR only once.  The number of lookups in the BIFT is the same as
   the number of BFR-NBRs to which the packet must be forwarded; it is
   not necessary to do a separate lookup for each destination BFER.

   When a packet is sent to a particular BFR-NBR, the BitString is not
   the only part of the BIER header that needs to be modified.  If there
   is a TTL field in the BIER header, it will need to be decremented.
   In addition, when either of the encapsulations of [MPLS_BIER_ENCAPS]
   is used, the BIFT-id field is likely to require modification, based
   on signaling from the BFR-NBR to which the packet is being sent.  The

Top      Up      ToC       Page 21 
   BIFT-id field of an incoming BIER packet implicitly identifies an SI,
   a sub-domain, and a BitStringLength.  If the packet is sent to a
   particular BFR-NBR, the BIFT-id field must be changed to whatever
   value that BFR-NBR has advertised for the same SI, sub-domain, and
   BitStringLength.  (If the encapsulation of Section 2.1 of
   [MPLS_BIER_ENCAPS] is used, this is essentially an MPLS label swap
   operation.)

   Suppose it has been decided (by the above rules) to send a packet to
   a particular BFR-NBR.  If that BFR-NBR is connected via multiple
   parallel interfaces, it may be desirable to apply some form of load
   balancing.  Load-balancing algorithms are outside the scope of this
   document.  However, if the packet's encapsulation contains an entropy
   field, the entropy field SHOULD be respected; two packets with the
   same value of the entropy field SHOULD be sent on the same interface
   (if possible).

   In some cases, the routing underlay may provide multiple equal-cost
   paths (through different BFR-NBRs) to a given BFER.  This is known as
   "Equal-Cost Multipath" (ECMP).  The procedures described in this
   section must be augmented in order to support load balancing over
   ECMP.  The necessary augmentations can be found in Section 6.7.

   In the event that unicast traffic to the BFR-NBR is being sent via a
   "bypass tunnel" of some sort, the BIER-encapsulated multicast traffic
   sent to the BFR-NBR SHOULD also be sent via that tunnel.  This allows
   any existing "fast reroute" schemes to be applied to multicast
   traffic as well as to unicast traffic.

   Some examples of these forwarding procedures can be found in
   Section 6.6.

Top      Up      ToC       Page 22 
   The rules given in this section can be represented by the following
   pseudocode:

   void ForwardBitMaskPacket (Packet)
   {
       SI=GetPacketSI(Packet);
       Offset=SI*BitStringLength;
       for (Index = GetFirstBitPosition(Packet->BitString); Index ;
            Index = GetNextBitPosition(Packet->BitString, Index)) {
           F-BM = BIFT[Index+Offset]->F-BM;
           if (!F-BM) continue;
           BFR-NBR = BIFT[Index+Offset]->BFR-NBR;
           PacketCopy = Copy(Packet);
           PacketCopy->BitString &= F-BM;
           PacketSend(PacketCopy, BFR-NBR);
           Packet->BitString &= ~F-BM;
       }
   }

                           Figure 4: Pseudocode

   This pseudocode assumes that, at a given BFER, the BFR-NBR entry
   corresponding to the BFER's own BFR-id will be the BFER's own
   BFR-prefix.  It also assumes that the corresponding F-BM has only
   one bit set, the bit representing the BFER itself.  In this case, the
   "PacketSend" function sends the packet to the multicast flow overlay.

   This pseudocode also assumes that the F-BM for the null next hop
   contains a 1 in a given bit position if and only if that bit position
   corresponds to either an unused BFR-id or an unreachable BFER.  When
   the BFR-NBR is null, the "PacketSend" function discards the packet.

Top      Up      ToC       Page 23 
6.6.  Examples of BIER Forwarding

   In this section, we give two examples of BIER forwarding, based on
   the topology in Figure 1.  In these examples, all packets have been
   assigned to the default sub-domain, all packets have SI=0, and the
   BitStringLength is 4.  Figure 5 shows the BIFT entries for SI=0 only.
   For compactness, we show the first column of the BIFT, the BFR-id,
   only as an integer.

           BFR-A BIFT            BFR-B BIFT            BFR-C BIFT
      -------------------   -------------------   -------------------
      | Id | F-BM | NBR |   | Id | F-BM | NBR |   | Id | F-BM | NBR |
      ===================   ===================   ===================
      |  1 | 0111 |  B  |   |  1 | 0011 |  C  |   |  1 | 0001 |  D  |
      -------------------   -------------------   -------------------
      |  2 | 0111 |  B  |   |  2 | 0011 |  C  |   |  2 | 0010 |  F  |
      -------------------   -------------------   -------------------
      |  3 | 0111 |  B  |   |  3 | 0100 |  E  |   |  3 | 1100 |  B  |
      -------------------   -------------------   -------------------
      |  4 | 1000 |  A  |   |  4 | 1000 |  A  |   |  4 | 1100 |  B  |
      -------------------   -------------------   -------------------

              Figure 5: BIFTs Used in the Forwarding Examples

6.6.1.  Example 1

   BFR-D, BFR-E, and BFR-F are BFERs.  BFR-A is the BFIR.  Suppose that
   BFIR-A has learned from the multicast flow overlay that BFER-D is
   interested in a given multicast flow.  If BFIR-A receives a packet of
   that flow from outside the BIER domain, BFIR-A applies the BIER
   encapsulation to the packet.  The encapsulation must be such that the
   SI is zero.  The encapsulation also includes a BitString, with just
   bit 1 set and with all other bits clear (i.e., 0001).  This indicates
   that BFER-D is the only BFER that needs to receive the packet.
   BFIR-A then follows the procedures of Section 6.5, as follows:

   o  Since the packet's BitString is 0001, BFIR-A finds that the first
      bit in the string is bit 1.  Looking at entry 1 in its BIFT, BFR-A
      determines that the bit mask F-BM is 0111 and the BFR-NBR is
      BFR-B.

   o  BFR-A then makes a copy of the packet and applies the F-BM to the
      copy: Copy->BitString &= 0111.  The copy's BitString is now 0001
      (0001 & 0111).

   o  The copy is now sent to BFR-B.

Top      Up      ToC       Page 24 
   o  BFR-A then updates the packet's BitString by applying the inverse
      of the F-BM: Packet->BitString &= ~F-BM.  As a result, the
      packet's BitString is now 0000 (0001 & 1000).

   o  As the packet's BitString is now zero, the forwarding procedure is
      complete.

   When BFR-B receives the multicast packet from BFR-A, it follows the
   same procedure.  The result is that a copy of the packet, with a
   BitString of 0001, is sent to BFR-C.  BFR-C applies the same
   procedures and, as a result, sends a copy of the packet, with a
   BitString of 0001, to BFR-D.

   At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
   F-BM of 0001 and a BFR-NBR of BFR-D itself.  This will cause a copy
   of the packet to be delivered to the multicast flow overlay at BFR-D.
   The packet's BitString will be set to 0000, and the packet will not
   be forwarded any further.

6.6.2.  Example 2

   This example is similar to example 1, except that BFIR-A has learned
   from the multicast flow overlay that both BFER-D and BFER-E are
   interested in a given multicast flow.  If BFIR-A receives a packet of
   that flow from outside the BIER domain, BFIR-A applies the BIER
   encapsulation to the packet.  The encapsulation must be such that the
   SI is zero.  The encapsulation also includes a BitString with
   two bits set: bit 1 is set (as in example 1) to indicate that BFR-D
   is a BFER for this packet, and bit 3 is set to indicate that BFR-E is
   a BFER for this packet.  That is, the BitString (assuming again a
   BitStringLength of 4) is 0101.  To forward the packet, BFIR-A follows
   the procedures of Section 6.5, as follows:

   o  Since the packet's BitString is 0101, BFIR-A finds that the first
      bit in the string is bit 1.  Looking at entry 1 in its BIFT, BFR-A
      determines that the bit mask F-BM is 0111 and the BFR-NBR is
      BFR-B.

   o  BFR-A then makes a copy of the packet and applies the F-BM to the
      copy: Copy->BitString &= 0111.  The copy's BitString is now 0101
      (0101 & 0111).

   o  The copy is now sent to BFR-B.

Top      Up      ToC       Page 25 
   o  BFR-A then updates the packet's BitString by applying the inverse
      of the F-BM: Packet->BitString &= ~F-BM.  As a result, the
      packet's BitString is now 0000 (0101 & 1000).

   o  As the packet's BitString is now zero, the forwarding procedure is
      complete.

   When BFR-B receives the multicast packet from BFR-A, it follows the
   procedure of Section 6.5, as follows:

   o  Since the packet's BitString is 0101, BFR-B finds that the first
      bit in the string is bit 1.  Looking at entry 1 in its BIFT, BFR-B
      determines that the bit mask F-BM is 0011 and the BFR-NBR is
      BFR-C.

   o  BFR-B then makes a copy of the packet and applies the F-BM to the
      copy: Copy->BitString &= 0011.  The copy's BitString is now 0001
      (0101 & 0011).

   o  The copy is now sent to BFR-C.

   o  BFR-B then updates the packet's BitString by applying the inverse
      of the F-BM: Packet->BitString &= ~F-BM.  As a result, the
      packet's BitString is now 0100 (0101 & 1100).

   o  Now BFR-B finds the next bit in the packet's (modified) BitString.
      This is bit 3.  Looking at entry 3 in its BIFT, BFR-B determines
      that the F-BM is 0100 and the BFR-NBR is BFR-E.

   o  BFR-B then makes a copy of the packet and applies the F-BM to the
      copy: Copy->BitString &= 0100.  The copy's BitString is now 0100
      (0100 & 0100).

   o  The copy is now sent to BFR-E.

   o  BFR-B then updates the packet's BitString by applying the inverse
      of the F-BM: Packet->BitString &= ~F-BM.  As a result, the
      packet's BitString is now 0000 (0100 & 1011).

   o  As the packet's BitString is now zero, the forwarding procedure is
      complete.

   Thus, BFR-B forwards two copies of the packet.  One copy of the
   packet, with BitString 0001, has now been sent from BFR-B to BFR-C.
   Following the same procedures, BFR-C will forward the packet to
   BFER-D.

Top      Up      ToC       Page 26 
   At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
   F-BM of 0001 and a BFR-NBR of BFR-D itself.  This will cause a copy
   of the packet to be delivered to the multicast flow overlay at BFR-D.
   The packet's BitString will be set to 0000, and the packet will not
   be forwarded any further.

   The other copy of the packet has been sent from BFR-B to BFER-E, with
   BitString 0100.

   At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an
   F-BM of 0100 and a BFR-NBR of BFR-E itself.  This will cause a copy
   of the packet to be delivered to the multicast flow overlay at BFR-E.
   The packet's BitString will be set to 0000, and the packet will not
   be forwarded any further.

6.7.  Equal-Cost Multipath Forwarding

   In many networks, the routing underlay will provide multiple
   equal-cost paths from a given BFR to a given BFER.  When forwarding
   multicast packets through the network, it can be beneficial to take
   advantage of this by load-balancing among those paths.  This feature
   is known as "Equal-Cost Multipath (ECMP) forwarding".

   BIER supports ECMP forwarding, but the procedures of Section 6.5 must
   be modified slightly.  Two ECMP procedures are defined.  In the first
   (described in Section 6.7.1), the choice among equal-cost paths taken
   by a given packet from a given BFR to a given BFER depends on
   (a) routing, (b) the packet's entropy, and (c) the other BFERs to
   which that packet is destined.  In the second (described in
   Section 6.7.2), the choice depends only upon the packet's entropy.

   There are trade-offs between the two forwarding procedures described
   here.  In the procedure of Section 6.7.1, the number of packet
   replications is minimized.  The procedure in Section 6.7.1 also uses
   less memory in the BFR.  In the procedure of Section 6.7.2, the path
   traveled by a given packet from a given BFR to a given BFER is
   independent of the other BFERs to which the packet is destined.
   While the procedures of Section 6.7.2 may cause more replications,
   they provide a more predictable behavior.

   The two procedures described here operate on identical packet formats
   and will interoperate correctly.  However, if deterministic behavior
   is desired, then all BFRs would need to use the procedure from
   Section 6.7.2.

Top      Up      ToC       Page 27 
6.7.1.  Non-deterministic ECMP

   Figure 6 shows the operation of non-deterministic ECMP in BIER.

          BFR-A BIFT            BFR-B BIFT            BFR-C BIFT
     -------------------   -------------------   -------------------
     | Id | F-BM | NBR |   | Id | F-BM | NBR |   | Id | F-BM | NBR |
     ===================   ===================   ===================
     | 1  | 0111 |  B  |   | 1  | 0011 |  C  |   | 1  | 0001 |  D  |
     -------------------   -------------------   -------------------
     | 2  | 0111 |  B  |   | 2  | 0011 |  C  |   | 2  | 0010 |  F  |
     -------------------   |    | 0110 |  E  |   -------------------
     | 3  | 0111 |  B  |   -------------------   | 3  | 1100 |  B  |
     -------------------   | 3  | 0110 |  E  |   -------------------
     | 4  | 1000 |  A  |   ------------------|   | 4  | 1100 |  B  |
     -------------------   | 4  | 1000 |  A  |   -------------------
                           -------------------

      ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D )
     4 (0:1000)             \                  \           1 (0:0001)
                             \                  \
                             ( E ) ------------ ( F )
                           3 (0:0100)         2 (0:0010)

                Figure 6: Example of Non-deterministic ECMP

   In this example, BFR-B has two equal-cost paths to reach BFER-F: one
   via BFR-C and one via BFR-E.  Since the BFR-id of BFER-F is 2, this
   is reflected in entry 2 of BFR-B's BIFT.  Entry 2 shows that BFR-B
   has a choice of two BFR-NBRs for BFER-B and that a different F-BM is
   associated with each choice.  When BFR-B looks up entry 2 in the
   BIFT, it can choose either BFR-NBR.  However, when following the
   procedures of Section 6.5, it MUST use the F-BM corresponding to the
   BFR-NBR that it chooses.

   How the choice is made is an implementation matter.  However, the
   usual rules for ECMP apply: packets of a given flow SHOULD NOT be
   split among two paths, and any entropy field in the packet's
   encapsulation SHOULD be respected.

   Note, however, that by the rules of Section 6.5, any packet destined
   for both BFER-D and BFER-F will be sent via BFR-C.

Top      Up      ToC       Page 28 
6.7.2.  Deterministic ECMP

   With the procedures of Section 6.7.1, where ECMP paths exist, the
   path a packet takes to reach any particular BFER depends not only on
   routing and on the packet's entropy but also on the set of other
   BFERs to which the packet is destined.

   For example, consider the following scenario in the network of
   Figure 6.

   o  There is a sequence of packets being transmitted by BFR-A, some of
      which are destined for both D and F and some of which are destined
      only for F.

   o  All the packets in this sequence have the same entropy value (call
      it "Q").

   o  At BFR-B, when a packet with entropy value Q is forwarded via
      entry 2 in the BIFT, the packet is sent to E.

   Using the forwarding procedure of Section 6.7.1, packets of this
   sequence that are destined for both D and F are forwarded according
   to entry 1 in the BIFT and thus will reach F via the path A-B-C-F.
   However, packets of this sequence that are destined only for F are
   forwarded according to entry 2 in the BIFT and thus will reach F via
   the path A-B-E-F.

   That procedure minimizes the number of packets transmitted by BFR-B.
   However, consider the following scenario:

   o  Beginning at time t0, the multicast flow in question needs to be
      received ONLY by BFER-F.

   o  Beginning at a later time, t1, the flow needs to be received by
      both BFER-D and BFER-F.

   o  Beginning at a later time, t2, the flow no longer needs to be
      received by D, but still needs to be received by F.

   Then, from t0 until t1, the flow will travel to F via the path
   A-B-E-F.  From t1 until t2, the flow will travel to F via the path
   A-B-C-F.  And from t2, the flow will again travel to F via the path
   A-B-E-F.

   The problem is that if D repeatedly joins and leaves the flow, the
   flow's path from B to F will keep switching.  This could cause F to
   receive packets out of order.  It also makes troubleshooting
   difficult.  For example, if there is some problem on the E-F link,

Top      Up      ToC       Page 29 
   receivers at F will get good service when the flow is also going to D
   (avoiding the E-F link) but bad service when the flow is not going
   to D.  Since it is hard to know which path is being used at any given
   time, this may be hard to troubleshoot.  Also, it is very difficult
   to perform a traceroute that is known to follow the path taken by the
   flow at any given time.

   The source of this difficulty is that, in the procedures of
   Section 6.7.1, the path taken by a particular flow to a particular
   BFER depends upon whether there are lower-numbered BFERs that are
   also receiving the flow.  Thus, the choice among the ECMP paths is
   fundamentally non-deterministic.

   Deterministic forwarding can be achieved by using multiple BIFTs,
   such that each row in a BIFT has only one path to each destination
   but the multiple ECMP paths to any particular destination are spread
   across the multiple tables.  When a BIER-encapsulated packet arrives
   to be forwarded, the BFR uses a hash of the BIER entropy field to
   determine which BIFT to use, and then the normal BIER forwarding
   algorithm (as described in Sections 6.5 and 6.6) is used with the
   selected BIFT.

   As an example, suppose there are two paths to destination X (call
   them "X1" and "X2") and four paths to destination Y (call them "Y1",
   "Y2", "Y3", and "Y4").  If there are, say, four BIFTs, one BIFT would
   have paths X1 and Y1, one would have X1 and Y2, one would have X2 and
   Y3, and one would have X2 and Y4.  If traffic to X is split evenly
   among these four BIFTs, the traffic will be split evenly between the
   two paths to X; if traffic to Y is split evenly among these four
   BIFTs, the traffic will be split evenly between the four paths to Y.

   Note that if there are three paths to one destination and four paths
   to another, 12 BIFTs would be required in order to get even splitting
   of the load to each of those two destinations.  Of course, each BIFT
   uses some memory, and one might be willing to have less optimal
   splitting in order to have fewer BIFTs.  How that trade-off is made
   is an implementation or deployment decision.



(page 29 continued on part 3)

Next Section