Internet DRAFT - draft-zzhang-bier-algorithm

draft-zzhang-bier-algorithm







BIER                                                            Z. Zhang
Internet-Draft                                          Juniper Networks
Intended status: Standards Track                             A. Dolganow
Expires: August 19, 2018                                           Nokia
                                                           A. Przygienda
                                                        Juniper Networks
                                                       February 15, 2018


                            BIER Algorithms
                     draft-zzhang-bier-algorithm-00

Abstract

   This document specifies signaling and procedures for non-SPF BIER
   tree computation covering several practical use cases discussed in
   deployment scenarios.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC2119.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on August 19, 2018.

Copyright Notice

   Copyright (c) 2018 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



Zhang, et al.            Expires August 19, 2018                [Page 1]

Internet-Draft               bier-algorithm                February 2018


   (https://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Terminologies . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   3.  BIER Tree Computation Algorithms  . . . . . . . . . . . . . .   2
   4.  Specification . . . . . . . . . . . . . . . . . . . . . . . .   3
     4.1.  Handling BIER Incapable Routers via a different SPF Tree    3
     4.2.  Computing Maximum Disjoint Trees for Subdomains Sharing a
           Topology  . . . . . . . . . . . . . . . . . . . . . . . .   4
     4.3.  Dealing with Ingress Replication Degradation  . . . . . .   4
     4.4.  Scaling up BIER with Traffic Engineering  . . . . . . . .   5
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   5
   6.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   5
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   5
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .   5
     7.2.  Informative References  . . . . . . . . . . . . . . . . .   6
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   6

1.  Terminologies

   Familiarity with BIER protocols and procedures is assumed.  Some
   terminologies are listed below for convenience.

2.  Introduction

   In the BIER architecture, a multicast specific routing underlay (not
   necessarily congruent with the unicast topology), or multiple routing
   underlays (again not necessarily congruent with the unicast
   topologies) could be used for forwarding BIER packets.  A routing
   underlay used for BIER is specified today as combination of a routing
   topology [RFC5120] and a calculation algorithm (BAR
   [I-D.ietf-bier-isis-extensions]) per sub-domain.  Currently, BAR is
   unspecified beside a single codepoint taken for basic unicast SPF
   alignment.

3.  BIER Tree Computation Algorithms

   OSPF Extensions for BIER [I-D.ietf-bier-ospf-bier-extensions] and
   ISIS Extensions for BIER [I-D.ietf-bier-isis-extensions] specify




Zhang, et al.            Expires August 19, 2018                [Page 2]

Internet-Draft               bier-algorithm                February 2018


   currently an BIER AlgoRithm (BAR, originally Tree-ID) field in the
   BIER sub-TLV:

           """ BAR: ... 0 is the only supported value defined in this
                    document and represents Shortest Path First (SPF)
                    algorithm based on IGP link metric.  This is the
                    standard shortest path algorithm as computed by
                    the OSPF protocol. ... """

   This document proposes to define codepoints for additional algorithms
   outlined in the architecture document to handle BIER incapable
   routers within BIER topologies and solve other challenges that BIER
   faces when deployed over standard SPF.  Moreover we describe the need
   for an algorithm that deals with computations where subdomains can
   share the same multi topology for protection purposes while computing
   disjoint trees.  We also mention a more difficult fanout limitation
   problem that can benefit from a new algorithm and quickly mention
   possible traffic engineering implications.

   Whatever the computation algorithm used, all routers in the same area
   are recommended to use the same method to prevent blackholes or
   stable loops.  If a mix is used (for example by using different BAR
   for different stream forwarding or using different BAR on different
   BFIRs), a special care must be given to prevent blackholes and/or
   loops.

   If an alternative method to BAR 0 is used, then the routers MUST
   signal that method by the means of a different BAR value.  The method
   is expected to specify compatibility to other BAR values if so
   desired.

   In case where multiple BAR values are present in the same routing
   underlay each set of routers with same BAR may split from the routers
   with a different BAR value, effectively partitioning the network for
   a given multicast stream forwarding.

4.  Specification

4.1.  Handling BIER Incapable Routers via a different SPF Tree

   Section 6.9 of the BIER Architecture Specification [RFC8279] touches
   on possible methods of dealing with BIER incapable routers.  As most
   practical alternative BIER incapable routers can be simply pruned
   during the SPF calculation from the candidate list.  This case
   presents itself if multi topology cannot be deployed due to some
   considerations or it is desired to cross non BIER routers via
   tunneling.




Zhang, et al.            Expires August 19, 2018                [Page 3]

Internet-Draft               bier-algorithm                February 2018


   To be exact, in the rest of the document, a BIER incapable router
   refers to any of the following:

   o  A router that does not support BIER at all.

   o  A BFR that does not advertise the specific <subdomain, multi
      topology, BAR, encapsulation, BSL> for which a particular
      calculation is being performed.  We denote this for simplicity as
      <SD,MT,BAR,ENC,BSL> combination in further discourse.

   A new BAR value (suggested value of 1) is defined in this document to
   specify the method of pruning BIER incapable routers (not putting
   them onto the candidate list when encountered during SPF).  Any
   router supporting this method and provisioned to use this method MUST
   signal this BAR value.

   Observe further that this allows to use in brown field deployments
   routers that do not support BIER at all but can easily tunnel it.
   The modification of the algorithm will use any forwarding adjacency
   to a BIER capable router then.

4.2.  Computing Maximum Disjoint Trees for Subdomains Sharing a Topology

   For certain class of multicast deployments it is desirable to send
   data across two BIER subdomains that are maximally disjoint.  While
   this can be addressed by using multiple completely disjoint
   topologies, such a method has to basically partition the network and
   precondition multi topology deployments or multiple IGPs.  A more
   efficient method is to compute the tree for a subdomain while
   avoiding another subdomain on the same multi-topology.  Future
   version of this document will provide a detailed algorithm to
   calculate the tree and claim a BAR registry value.

4.3.  Dealing with Ingress Replication Degradation

   BIER, when following strict SPF unicast routing is bound to degrade
   into ingress replication in certain topologies when it follows SPF or
   the fanout may overwhelm the replication capacity of a specific
   system.  One possibility is to prune the topology using multi
   topology deployment which may limit the recovery potential on link
   failures, a better one is obviously to compute a specialized tree
   that limits the fanout.  Future version of this document will provide
   a detailed algorithm to calculate the tree and claim a BAR registry
   value.







Zhang, et al.            Expires August 19, 2018                [Page 4]

Internet-Draft               bier-algorithm                February 2018


4.4.  Scaling up BIER with Traffic Engineering

   Suggested traffic engineering architecture for BIER
   [I-D.ietf-bier-te-arch] offers a very limited scalability only.  It
   would be desirable to subject BIER to proper TE point-to-multipoint
   computation.  Albeit BIER results can be shaped with multi topology
   again, a computation including TE metrics and constraints and maybe
   even multicast specific metrics like node fanouts could introduce a
   distributed, scalable TE for BIER.  Such a computation could be
   performed in a centralized fashion of course and resulting BIFTs
   downloaded to routers as well but such an approach is outside the
   scope of this document.

5.  IANA Considerations

   This document proposes to create BIER AlgoRithm registry with the
   following initial values.

   0: Default SPF calculation that includes all nodes.

   1: SPF calculation that prunes routers that do not support the
      <SD,MT,BAR,ENC,BSL> combination for which the calculation is
      performed before putting them on the candidate list.

6.  Acknowledgements

   To be provided.

7.  References

7.1.  Normative References

   [RFC1925]  Callon, R., "The Twelve Networking Truths", RFC 1925,
              DOI 10.17487/RFC1925, April 1996,
              <https://www.rfc-editor.org/info/rfc1925>.

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

   [RFC5120]  Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
              Topology (MT) Routing in Intermediate System to
              Intermediate Systems (IS-ISs)", RFC 5120,
              DOI 10.17487/RFC5120, February 2008,
              <https://www.rfc-editor.org/info/rfc5120>.





Zhang, et al.            Expires August 19, 2018                [Page 5]

Internet-Draft               bier-algorithm                February 2018


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

7.2.  Informative References

   [I-D.ietf-bier-isis-extensions]
              Ginsberg, L., Przygienda, T., Aldrin, S., and Z. Zhang,
              "BIER support via ISIS", draft-ietf-bier-isis-
              extensions-07 (work in progress), February 2018.

   [I-D.ietf-bier-ospf-bier-extensions]
              Psenak, P., Kumar, N., Wijnands, I., Dolganow, A.,
              Przygienda, T., Zhang, Z., and S. Aldrin, "OSPF Extensions
              for BIER", draft-ietf-bier-ospf-bier-extensions-12 (work
              in progress), February 2018.

   [I-D.ietf-bier-te-arch]
              Eckert, T., Cauchie, G., Braun, W., and M. Menth, "Traffic
              Engineering for Bit Index Explicit Replication (BIER-TE)",
              draft-ietf-bier-te-arch-00 (work in progress), January
              2018.

Authors' Addresses

   Zhaohui Zhang
   Juniper Networks

   EMail: zzhang@juniper.net


   Andrew Dolganow
   Nokia

   EMail: andrew.dolganow@nokia.com


   Antoni Przygienda
   Juniper Networks

   EMail: prz@juniper.net








Zhang, et al.            Expires August 19, 2018                [Page 6]