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]
