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

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

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

• A router that does not support BIER at all.
• 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.

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

7.2. Informative References

Authors' Addresses