| Internet Engineering Task Force | A. Przygienda |
| Internet-Draft | J. Tantsura |
| Intended status: Standards Track | Ericsson |
| Expires: September 10, 2015 | March 09, 2015 |
Automatic Assignment of BIER BFR-ids in ISIS
draft-prz-bier-bfrid-assignment-00
Specification of an ISIS extension to support auto-election of BFR IDs in BIER using ISIS.
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 RFC 2119 [RFC2119] .
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 http://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 September 10, 2015.
Copyright (c) 2015 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 (http://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.
Bit Index Explicit Replication (BIER) [I-D.draft-wijnands-bier-architecture-04] defines an architecture where all intended multicast receivers are encoded as bitmask in the Multicast packet header within different encapsulations such as [I-D.draft-wijnands-mpls-bier-encapsulation-02]. A router that receives such a packet will forward the packet based on the Bit Position in the packet header towards the receiver(s), following a precomputed tree for each of the bits in the packet. Each receiver is represented by a unique bit in the bitmask corresponding to its BFR-id. BFR-ids are sub-domain specific.
Once the number of receivers becomes large (i.e. many sets are present) or receivers choose to participate in many independent sub-domains, assignment of a unique BIER bit to a node is a non-trivial problem that can benefit highly from an automated solution. The usual trade-offs are either a centralized (server) approach or a distributed approach which (from experience with other protocols such as DHCP or OSPF), provide at the cost of additional protocol complexity higher availability.
This document presents necessary, optional extensions to the currently deployed ISIS for IP [RFC1195] protocol to support automatic election of BFR-ids by means of a distributed protocol. This document defines new TLVs to be advertised by every router participating in BIER signaling and supporting such an election. In case some nodes are statically configured with a BFR-id, the protocol can detect misconfiguration, i.e. overlapping bit assignments or otherwise respects statically assigned BFR ids.
This extension operates seamlessly in a backwards compatible fashion with BIER procedures for ISIS as defined in [I-D.draft-przygienda-bier-isis-ranges-02]. Only BFRs implementing this extensions benefit from automatic assignment.
Some of the terminology specified in [I-D.draft-wijnands-bier-architecture-04] is replicated here and extended by necessary definitions:
This document adds the following new sub-sub-TLVs to the registry of sub-TLVs for BIER Info sub-TLV.
This document adds the following new TLV to the registery of ISIS TLVs.
The following sections present BIER IGP protocol procedures for the auto-election and maintainance of unique BIER BFR-ids across subdomains. Compared to purely administrative assignment of the bitmask use of those procedures largely facilitates deployment of BIER in large setups. The election and bit assignment procedures described in the according sections indicate how the BFRs participate in an election mechanism that allows them to
After a sub-domain <MT,SD,MLs> [I-D.draft-przygienda-bier-isis-ranges-02] is enabled, the according election procedures for D-BFR and Backup D-BFR are performed based upon the set of available BIER-PE sub-sub-TLVs. Given the fact that SD is uniquely tied to its MT per today's architecture and MLs are of no further importance to the introduced procedures, a sub-domain will be abbreviated without loss of generality as <SD>.
The election is indebted to and largely modeled (to the point of quoting parts of it verbatim) after the DR OSPF Election procedure in OSPF [RFC2328] which has proven to work exceedingly well over many years in the field.
This section describes the algorithm used for calculating a network's Designated BFR and Backup Designated BFR and procedures that allow those to allocate bit mask bits to a participating BFER in a sub-domain SD which we designate as BFER<SD>. The election runs per SD the router is participating in. The initial time a router runs the election algorithm, the D-BFR<SD> and BD-BFR<SD> are initialized to 0.0.0.0 or equivalent empty router ID. This indicates the lack of both a Designated BFR<SD> and a Backup Designated BFR<SD>.
The D-BFR<SD> election algorithm proceeds as follows:
The following steps MUST then be executed, considering only those routers that remain on the list:
The reason behind the election algorithm's complexity is the desire for an orderly transition from BD-BFR<SD> to D-BFR<SD>, when the current D-BFR<SD> fails. This orderly transition is ensured through the introduction of hysteresis: no new BD-BFR<SD> can be chosen until the old Backup accepts its new D-BFR<SD> responsibilities.
The above procedure may elect the same router to be both D-BFR<SD> and BD-BFR<SD>, although that router will never be the calculating router (Router X<SD>) itself. The elected D-BFR<SD> may not be the router having the highest Router Priority for <SD>, nor will the BD-BFR<SD> necessarily have the second highest Router Priority. If Router X<SD> is not itself eligible to become D-BFR<SD>, it is possible that neither a BD-BFR<SD> nor a D-BFR<SD> will be selected in the above procedure. Note also that if Router X<SD> is the only router that is eligible to become D-BFR<SD>, it will select itself as D-BFR<SD> and there will be no BD-BFR<SD> for the network.
A router that assumes D-BFR role for a given <SD> combination invokes additional set of procedures as synchronization and election point for all the BFRs in <SD>.
Each BFER includes a strongly abbreviated DHCP-like FSM to obtain from the D-BFR<SD> its BMP or to advertise an administrative preference of its BMP.
The procedure is initiated by a BFER<SD> announcing in BIER Info sub-TLV for <SD> its assigned bit (or request for BMP assignment). The D-BFR<SD> initiates then a set of procedures to assign BMPs to such BFER in the <SD> or announces collisions.
Observe that BFERs can request (or announce) the bits even before a BDR<SD> has been chosen so the election and assignment are largely orthogonal sets of procedures.
A router that is elected BD-BFR<SD> MUST mirror in its advertisements the exact state of the D-BFR<SD> and on each received advertisement maintains its internal states to use as starting point in all D-BFR<SD> procedures in case it looses connectivity (i.e. it cannot compute SPF reachability to the D-BFR in standard topology) to the D-BFR<SD>.
A BFER in <SD> controls its BMP in the set by providing values in its BIER Info sub-TLV for <SD> and signalling towards B-DR using A and R bits per Section 9.2. If it advertises the BFR-id without A or R bit set it indicates a fixed value it has chosen administratively.
It may request the assignment of a BMP by setting the R bit. The prefered BFR-id is signalled by providing a BFR-id value. The D-BFR MUST try to keep the preferred setting value when choosing BMP for the BFER. All other BFRs MUST NOT use the BFR-id value when the R bit is set. In case of routers not understanding this extensions, the behavior is enforced by the means of the C bit.
Once the BFER has been assigned a value from D-BFR and is willing to accept it, it MUST copy the value into the BFR-id field in the BIER-PE-BMPs it receives and set the A bit while clearing the R bit.
On the other side, the D-BFR for <SD> advertises the BMP assignments by the means of advertising BIER-PE-BMP for <SD>.
In the normal case a router will assume its role as D-BFR<SD> promoting itself from BD-BFR<SD> with its own set of procedures. Based on those it will hold the state of the abdicating D-BFR<SD> and it MUST use this state as initial state for the D-BFR procedures it initiates per Section 4.2 . This should warranty a seamless fall-over without changes in the assignments of bits for BFERs for the according <SD> which SHOULD take preference over all other considerations. Observe that the implication is that a configured administrative preference MUST NOT be used unless changed or set explicitly again. The FSMs visualize this behavior more explicitly.
+------+
| ==== | E1 = PE Expired OR
| Init | PI Expired New Admin
| ==== | Pref
+-+----+ +--+
| | |
| Joined SD +--------++ |
| Rcvd First PE for SD Lost DR | ======= <-+
| +--------------+ Passive |
+-v----+ | | ======= |
| ==== | | +^--------+
| Wait |Timer +--------v-+ Lost |
| ==== +------------> ======== +-------------+
+------+ | Election |
+---------+ ======== +--------+
| Won BDR +^-------^-+ Won DR |
| | | |
| | |New DR |
+----v+ | |Seen +v---+
| === +---------+ +---------+ == |
| BDR | New BDR | DR |
+--> === | Lost DR +---+ == |
| ++----+ | +^---+
| | E1 | |
+---+ Diff R Flag | |
New DR PE Diff A Flag | |
New Admin Pref +-------v+ |
| BMP +---+
| Assign |
+--------+
The full set of procedures can be described as a finite state machine per <SD> run within each participating BFR with the following events and transitions
If A flag was not present before and
The procedures prescribed guarantee a complete backwards compatiblity to [I-D.draft-przygienda-bier-isis-ranges-02]. During the assignment procedure the according values are hidden from BFRs lacking this extension by the means of the C bit. Once assigned, they become visible. On the other hand, BFR-id values chosen by the BFRs without election extensions are respected in assignment.
Some of the new information is carried within the the existing BIER Info sub-TLV per [I-D.draft-przygienda-bier-isis-ranges-02] and some presents a new ISIS TLV.
This sub-sub-TLV is included in the BIER Info sub-TLV of the according sub-domain as specified by [I-D.draft-przygienda-bier-isis-ranges-02]. It MUST be included in the BIER Info sub-TLV only once, otherwise the first instance is used.
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | D-BFR Priority| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | D-BFR ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | BD-BFR ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Ver|C|0 0 0 A R| subdomain-id | BFR-id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV is advertised only for the <SD> for which the router has been elected to be D-BDR<SD> or BD-BDR<SD>. It can repeat multiple times.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|R R R R| MT-ID | subdomain-id |# of Assigments|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<---+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| AF |E|Stats| Assigned BFR-id | Prefix Length | # Bit
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Mask
| Address Prefix (variable) | Assgn
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
<---+
The assignments SHOULD be sorted on BFER-ID. Assignments MUST NOT repeat when the TLV is advertised multiple times and a router discovering such condition MUST issue an adequate warning. When multiple assignments for the same BFR are found, the first one in first TLV MUST be used and all others disregarded.
The assignments MUST NOT repeat any BIER Info sub-TLVs that have the R and A bit cleared, e.g. purely administrative assignments. A router discovering such condition MUST issue an adequate warning and disregard such assignments.
The assignments MUST repeat all assigned BIER Info sub-TLVs (that have A bit set). When such assignment is not advertised anymore, the according BFER MUST interpret that as loss as assignment, i.e. start with R bit again or set the BFR-id to invalid BFR-id.
Implementations must assure that malformed TLV and sub-TLV permutations do not result in errors which cause hard protocol failures.
TBD.