Internet DRAFT - draft-yang-trill-parent-seletion

draft-yang-trill-parent-seletion



TRILL Working Group                                         Howard Yang
Internet Draft                                            Cisco Systems
Intended status: Standards Track                          Ayan Banerjee
                                                          Cisco Systems
                                                        Donald Eastlake
                                                                 Huawei
                                                          Radia Perlman
                                                             Intel Labs
Expires: January 17, 2016                                 July 17, 2015

               TRILL: Parent Selection in Distribution Trees
                 <draft-yang-trill-parent-seletion-05.txt>

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79. This document may not be modified,
   and derivative works of it may not be created, except to publish it
   as an RFC and to translate it into languages other than English.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

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

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

   This Internet-Draft will expire on January 17, 2016.

Copyright Notice

   Copyright (c) 2013 IETF Trust and the persons identified as the
   document authors. All rights reserved.

Yang, et al            Expires January 17, 2016                [Page 1]
Internet-Draft         Trill: Parent Selection                July 2015

   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.

Abstract

   This document describes a protocol extension in TRILL IS-IS and a
   parent selection tiebreak algorithm in the calculation of
   distribution trees in TRILL. The proposal is to modify the current
   algorithm to improve the stability of the distribution trees when
   multiple equal cost parents are present. It also offers the
   capabilities of pinning down multi-destination traffic and re-shaping
   the distribution trees to improve the traffic load balancing.

Table of Contents

   1. Introduction ................................................... 3
   1.1. Conventions used in this document ............................ 3
   2. Problem Definition ............................................. 3
   3. Explicit Parent Selection Algorithm ............................ 5
   3.1. Implicit Selection vs. Explicit Selection .................... 5
   3.1.1. Explicit Selection is a Preference ......................... 6
   3.1.2. Explicit Selection is a Local Decision ..................... 7
   3.1.3. Explicit Selection is honoews only if viable ............... 7
   3.2. Migration and Capability Sub-TLV ............................. 7
   3.2.1. A Second Approach in the Mixed Environment ................. 6
   4. Sub-TLV Extensions to IS-IS .................................... 9
   4.1. Parent Selection Algorithm Version Sub-TLV ................... 9
   4.2. Explicit Parent Preference Sub-TLV .......................... 10
   5. Operation of RBridge .......................................... 10
   6. Other Applications ............................................ 11
   7. Security Considerations ....................................... 12
   8. IANA Considerations ........................................... 12
   9. Conclusions ................................................... 12
   10. References ................................................... 12
   10.1. Normative References ....................................... 12

Yang, et al             Expires January 17, 2016                [Page 2]
Internet-Draft          Trill: Parent Selection                July 2015

   11. Acknowledgments .............................................. 13

1. Introduction

   The IETF has standardized the TRILL protocol [RFC6325], which
   provides transparent Layer 2 forwarding using encapsulation with a
   hop count and link state routing. TRILL provides optimal pair-wise
   forwarding without configuration, safe forwarding even during
   periods of temporary loops, and support for multipathing of both
   unicast and multicast traffic as well as supporting VLANs. In
   Section 4.5.1 of [RFC6325], a tiebreak algorithm is described to
   select a parent node when there are multiple equal cost parents. It
   uses the tree number as a parameter in the algorithm.

   While the algorithm described in [RFC6325] is simple and elegant to
   achieve the goal of traffic load splitting, it exhibits an undesired
   behavior that a link status change in one tree causes the re-
   selection of paths in other trees, which impacts the stability of
   the distribution trees in the event of a link status flap.

   This document presents a solution to the above problem with the
   introduction of protocol extension in IS-IS and a modification of
   the parent selection tiebreak algorithm.

1.1. Conventions used in this document

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

   In this document, these words will appear with that interpretation
   only when in ALL CAPS. Lower case uses of these words are not to be
   interpreted as carrying RFC-2119 significance.

   In this document, the characters ">>" preceding an indented line(s)
   indicates a compliance requirement statement using the key words
   listed above. This convention aids reviewers in quickly identifying
   or finding the explicit compliance requirements of this RFC.

2. Problem Definition

   In the following example of TRILL network, there are two groups of
   RBridges or nodes: one group consists of RBridges X, Y and Z (Let's
   call it spine node group). The other group consists of RBridges A, B,

Yang, et al            Expires January 17, 2016                [Page 3]
Internet-Draft         Trill: Parent Selection                July 2015

   C, and D (Let's call it leaf node group). Each spine node has one
   link connecting to each leaf node. There are no links connecting any
   two spine nodes. There are no links between any two leaf nodes,
   either. (In this document, node and RBridge are used
   interchangeably.)

         +-----------+     +------------+     +-----------+
         |   X       |     | Y          |     | Z         |
         |           +--+  |            |  +--+           |
         +---+-+---+-+  |  ++-+------+-++  |  +-+-+---+---+
             | |   |    |   | |      | |   |    | |   |
             | |   +----|---|-|------|-|-+ |    | |   |
             | |        |   | |      | | | |    | |   |
             | |        | +-|-|------|-|-|-|----+ |   |
             | |        | | | |      | | | |      |   |
             | +--------|-|-|-|------|-|-|-|------|-+ |
             |          | | | |      | | | |      | | |
             | +--------|-|-|-|------|-|-|-|------+ | |
             | |        | | | |      | | | |        | |
             | | +------|-|-+ |      | +-|-|------+ | |
             | | |      | |   |      |   | |      | | |
         +---+-+-+-+  +-+-+---+-+  +-+---+-+-+  +-+-+-+---+
         | A       |  | B       |  | C       |  | D       |
         |         |  |         |  |         |  |         |
         +---------+  +---------+  +---------+  +---------+

   Assume three multi-destination distribution trees are to be
   calculated, with Tree 1 rooted at X, Tree 2 at Y, and Tree 3 at Z.
   Assuming the 7-octet IS-IS IDs of A, B, C, D are in ascending order.

   When a tree, for example, Tree 2 (rooted at Y), is calculated, and
   when node X is to be added to the tree, there are 4 equal cost
   possible parents: A, B, C, D. To pick one as the parent, a tiebreak
   algorithm is needed. Section 4.5.1 of [RFC6325] describes a parent
   selection tiebreak algorithm: For each node N, if N has p parents of
   equal cost, then order the parents in ascending order according to
   the 7-octet ISIS-ID and number them starting at zero. For Tree j,
   choose N's parent as choice (j-1) mod p. (See also [RFC7180] for 
   the correction of the algorithm.) We call the algorithm "original
   tiebreak algorithm".

   Applying this algorithm, on Tree 2, B is selected as the parent node
   for X, that is, link XB is on Tree 2. (In this document, link XB
   means the link between node X and node B.) Similarly, when Tree 3 is

Yang, et al            Expires January 17, 2016                [Page 4]
Internet-Draft         Trill: Parent Selection                July 2015

   calculated, C is selected as the parent for X. (On Tree 1, A is
   selected as the parent for Y and Z).

   In the event when the link XA goes down, Tree 1 will select B as the
   parent node for Y and Z, as there are only 3 equal cost parents (B,
   C, and D) for Y or Z now. This change on Tree 1 is expected, as XA
   was on Tree 1.

   But observe the changes on Tree 2 and 3: Tree 2 now changes to select
   C as the parent node for X, due to the failure of link XA. Similarly,
   Tree 3 changes to select D as the parent node for X.

             Parent of X on Tree 2    Parent of X on Tree 3
   XA is up            B                        C
   XA is down          C                        D

   Although link XA is only on Tree 1, its link status change caused the
   re-selection of the parents on other trees. That is, the status
   change on one seemingly unrelated link causes the re-selection of the
   parent nodes and the changes of the tree paths on other trees.

   This behavior affects the stability of the multi-destination
   distribution trees in TRILL.

   We propose the following modifications to solve the problem.

   In addition, network designers and administrators wish to "pin" the
   multi-destination traffic to the paths. They prefer to have the
   traffic follow trees with some deterministic in nature. The proposal
   here offers such a tool to "pin" down the traffic to the trees.

3. Explicit Parent Selection Algorithm

3.1. Implicit Selection vs. Explicit Selection

   In the current parent selection tiebreak algorithm, when there are p
   parent nodes, we list them in the ascending order and assignment a
   number to them starting from 0. And Tree j selects the node (j-1) mod
   p, in the ordered list as its parent. We call this selection
   "implicit selection".

   In the previous example, when the link XA is up, in the calculation
   of Tree 2, when node X is being added to the tree, B is chosen as the
   parent. This is implicit selection. In the proposed algorithm, this
   implicit selection is noted down on X. That is, on X, (Tree 2, B) is

Yang, et al            Expires January 17, 2016                [Page 5]
Internet-Draft         Trill: Parent Selection                July 2015

   saved in memory to be used later on. Similarly, on X, (Tree 3, C) is
   also noted down in the parent selection database.

   When link XA goes down, the new implicit selections change for X on
   Tree 2 and 3. The new implicit selections are (Tree 2, C) and (Tree
   3, D). Now we propose to change the algorithm to override this.

   After the link XA goes down, X detects such link status change, and
   checks against its parent selection database. X then makes a
   conscious decision and advertises, in its LSP, the previously saved
   selections (Tree 2, B) and (Tree 3, C). Such advertised selections
   are called "explicit selections".

   The essence of the proposed algorithm is: instead of relying on the
   well-known algorithm for everyone to pick C as the parent for X on
   Tree 2 and D on Tree 3, X advertises the explicit selection
   preference and suggests everybody that B should continue to be the
   parent for X on Tree 2, and C on Tree 3.

   The way to advertise such explicit selections is to put them in the
   TLVs of X's LSP, which are propagated to all the nodes in the TRILL
   network.

   The new tiebreak algorithm is then modified in such a way that when
   node X is to be considered to be added to a tree, the RBridge running
   the algorithm looks for explicit "parent selection preference" TLVs
   in X's LSP. If no such TLV is present, the current algorithm is used
   and the implicit selection is chosen. If there is an explicit
   selection in LSP, this parent selection preference advertisement must
   be honored, if it is a viable option, meaning it is among the list of
   currently available equal cost shortest path parent choices.

   In our example, since X advertises (Tree 2, B), and B is a viable
   option, B is therefore chosen as the parent for X on Tree 2.
   Similarly, C is chosen as parent for X on Tree 3.

   This achieves our goal of keeping the parent selections unchanged on
   Tree 2 and Tree 3 when link XA goes down.

3.1.1. Explicit Selection is a Preference

   When a node advertises the explicit parent selection, such
   advertisement is a preference, which may or may not be honored. The
   explicit selection is honored only when it is among the equal cost
   parent choices.

Yang, et al            Expires January 17, 2016                [Page 6]
Internet-Draft         Trill: Parent Selection                July 2015

   In the previous example, if Links XA and YB both go down the same
   time, when calculation Tree 2, and when X is added to the tree path,
   X's advertisement of (Tree 2, B) cannot be honored, as B is not 
   viable. X advertised that it preferred to choose B as the parent on 
   Tree 2, but such preference is not honored. In such case, the
   original tiebreak algorithm is applied and C is chosen as the parent.

   It is worthwhile to point out that in the above case when both XA and
   YB go down, with the proposed algorithm when X advertises (Tree 2, B)
   and (Tree 3, C), and Y advertises (Tree 1, A) and (Tree 3, C), Tree 3
   is not affected by the link status changes.

3.1.2. Explicit Selection is a Local Decision

   It is up to an RBridge to decide whether or not to advertise any
   explicit selection preference. For example, in the above example, X
   can choose not to advertise any explicit selection even when link XA
   goes down, and allow all the nodes in the network to continue to
   select the implicit selections (which of course causes changes to
   Trees 2 and 3). X can even advertise a different node, for example,
   (Tree 2, D).

   Whether or not to advertise or which node to advertise is a local
   decision. This characteristic makes it possible to have a smooth 
   system software upgrade and migration in the TRILL network.

   It is also the responsibility of the local node to decide when to
   stop any preference advertisement.

3.1.3. Explicit Selection is honored only if viable

   Before the explicit selection advertisement is honored, a "viability
   check" must be performed. If the explicit advertisement is among the
   choices of equal cost shortest path parents, then it is viable. Only
   viable explicit advertisements are to be honored. This is to ensure
   that the multi-destination trees resulting from the new algorithm are
   still the SPF trees (short path trees).

3.2. Migration and Capability Sub-TLV

   It is important that all the RBridges in the TRILL network runs the
   same SPF algorithm (including tiebreak algorithm) for the
   distribution tree calculation. Therefore, in the software upgrade and
   migration case, until all the RBridges are upgraded with the
   capability to run the new explicit selection tiebreak algorithm, any
   RBridge must continue to run the original tiebreak algorithm
   described in Section 4.5.1 of [RFC6325].

Yang, et al            Expires January 17, 2016                [Page 7]
Internet-Draft         Trill: Parent Selection                July 2015

   To achieve the migration goal, a new router-capability sub-TLV will
   be introduced, which will indicate whether or not an RBridge is
   capable to run the new algorithm. The absence of such sub-TLV in the
   LSP implies that the RBridge is not capable to run the new algorithm.

   RBridge must inspect the LSPs of all the reachable nodes before the
   tree calculation. When an RBridge detects that there is at least one
   RBridge which does not advertise this capability sub-TLV, it should
   not advertise any explicit selections, and the implicit selections
   MUST be chosen, and any explicit selection advertisement is ignored.

   In a mixed environment where the network consists of RBs running both
   existing algorithm and the proposed enhanced algorithm, the above
   approach prevents loops when mutli-destination trees are calculated.
   Although, with this approach, until all the RBs are upgraded to run
   the new algorithm, none of the RBs can take advantage of the new
   algorithm.

3.2.1. A Second Approach in the mixed environment

   A second proposal is to introduce a new flag in the highest priority
   RB's LSP. This flag signals to all the RBs in the network which
   algorithm to run, when highest priority RB's LSP is propagated.

   Let's call the existing parent selection algorithm "V0", and let's
   call the new proposed parent selection algorithm "V1".

   If the new flag in the highest priority RB indicates to run V0, then
   all the RBs continue to run the existing algorithm, and should ignore
   any explicit parent advertisements, if they exist.

   If the new flag in the highest priority RB indicates to run V1, then
   all the RBs which understand this flag MUST run the new algorithm. Of
   course, all those RBs which have not been upgraded will not
   understand this flag and will continue to run the existing algorithm.

   We also need to introduce a new TLV or sub-TLV in the ISIS hellos to
   indicate whether an RB supports the new enhanced algorithm. And an RB
   running V1 must not form ISIS adjacency with RBs running V0.

   With this approach, RBs can be turned on to run the new algorithm as
   they are upgraded, and do not have to wait until all the RBs are
   upgraded. The drawbacks of this approach are that it requires an
   additional configuration (to set the flag on highest priority RB to
   signal which version to run), and the V1 and V0 RBs are partitioning
   the network (as they do not form adjacency with each other).

Yang, et al            Expires January 17, 2016                [Page 8]
Internet-Draft         Trill: Parent Selection                July 2015

   Summary of this approach: Each RBridge announces, in its Hellos (and
   possibly also in its LSP), whether it can use the new tree
   algorithm. The highest priority RBridge R1 announces, in its LSP,
   whether to run the new or old algorithm.  R1 makes the decision
   based solely on configuration.  If R1 announces using the new
   algorithm, and there are still old RBridges that do not support the
   new algorithm, then new RBridges will refuse to form an adjacency
   with them.

4. Sub-TLV Extensions to IS-IS

   Two new sub-TLVs are introduced in below sub-sections. Both sub-TLVs
   can be carried in Router Capability TLV. The Router Capability TLV is
   defined in [RFC4971]. 

4.1. Parent Selection Algorithm Version Sub-TLV

   The Parent Selection Algorithm Version sub-TLV indicates the maximum
   version of the algorithm supported by an RBridge. By implication,
   lower versions are also supported. If this sub-TLV is missing, the
   originating RBridge only supports the based version, which is the
   original algorithm described in Section 4.5.1 of [RFC6325].

   This sub-TLV can also be used in ISIS hellos in port capability TLV
   if the second approach is used in the mixed environment (Section
   3.2.1).

   +-+-+-+-+-+-+-+-+
   | Type          |                  (1 byte)
   +-+-+-+-+-+-+-+-+
   | Length        |                  (1 byte)
   +-+-+-+-+-+-+-+-+
   | Max-version   |                  (1 byte)
   +-+-+-+-+-+-+-+-+

   o  Type: Router Capability sub-TLV type, set to PARENT-SELECT-VER.

   o  Length: 1.

   o  Max-version: Set to maximum version supported. 0: base version. 1:
      Explicit Parent Selection algorithm.

Yang, et al            Expires January 17, 2016                [Page 9]
Internet-Draft         Trill: Parent Selection                July 2015

4.2. Explicit Parent Preference Sub-TLV

   The Explicit Parent Preference Sub-TLV is a list of pairs of tree
   number and IS-IS ID. It includes the explicit parent selection
   advertisements which indicate which nodes the originating RBridge
   prefers in the equal cost multiple parent case for the trees.

   +-+-+-+-+-+-+-+-+
   | Type          |                (1 byte)
   +-+-+-+-+-+-+-+-+
   | Length        |                (1 byte)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Tree Number a               |  (2 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | IS-IS ID                    |  (7 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Tree Number b               |  (2 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | IS-IS ID                    |  (7 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Tree Number (...)           |  (2 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | IS-IS ID (...)              |  (7 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Type: Router Capability sub-TLV type, set to PARENT-PREFERENCE.

   o  Length: 9*n, where n is the number of trees listed.

   o  Tree Number: This is the tree number on which the explicit parent
      node will be specified in the next IS-IS ID field.

   o  IS-IS ID: The 7-octet IS-IS ID of the parent node for the
      originating node on the tree whose number is specified in the
      previous "Tree Number" field.

5. Operation of RBridge

   An RBridge MUST examine the LSPs of all the reachable nodes before
   each calculation of multi-destination distribution trees. Depending
   on the examination result, the RBridge can be in one of the following
   two states:

Yang, et al            Expires January 17, 2016               [Page 10]
Internet-Draft         Trill: Parent Selection                July 2015

   o  "Ineligible" state: if there is at least one node which does not
      include the "Parent Selection Algorithm Version" sub-TLV, or it
      includes a lower version than "Explicit Parent Selection" version.

   o  "Eligible" state: if all the reachable nodes includes the "Parent
      Selection Algorithm Version" sub-TLV, and the version is greater
      or equal to "Explicit Parent Selection" Version (version 1)

   An RBridge must follow the following rules.

   An RBridge can include the "Parent Selection Algorithm Version" sub-
   TLV in Router-Capability TLV, although such include is not mandatory.

   In "Ineligible" state, the RBridge should not include "Explicit
   Parent Preference" sub-TLV in its LSP. It MUST ignore any "Explicit
   Parent Preference" in other nodes' LSPs, if there is any. And it MUST
   run the original parent selection algorithm ([RFC6325] as modified by
   [RFC7180]).

   In "Eligible" state, the RBridge can include "Explicit Parent
   Preference" sub-TLV in its LSP. It MUST run the modified tiebreak
   algorithm in the distribution tree calculation: when a node X is
   added into the tree j, and when there are p number of equal cost
   parent choices, the RBridge MUST exam the "Explicit Parent
   Preference" sub-TLV in X's LSP, and MUST take one of the following
   actions:

   1. If the Explicit Parent Preference is among the equal cost parent
      choices, the explicit parent preference MUST be honored.

   2. Otherwise, the Explicit Parent Preference MUST be ignored. Select
      the choice of (j-1) mod p, as described in the original tiebreak
      algorithm.

6. Other Applications

   The proposed algorithm provides a tool to influence the tree parent
   node selection, and further makes it possible to re-shape the
   distribution trees. It is demonstrated how to improve the stability
   of the distribution trees with the tool.

   With this tool, network engineers can also redirect multi-destination
   traffic and improve traffic load sharing. For example, in our
   previous example, while X can advertise (Tree 2, B) as explicit
   parent preference, but X can also advertise (Tree 2, D) instead. This
   makes it possible to utilize link XD, which in some cases may be
   desirable for the purposes of traffic engineering.

Yang, et al            Expires January 17, 2016               [Page 11]
Internet-Draft         Trill: Parent Selection                July 2015

7. Security Considerations

   No additional security risk is introduced by using the mechanisms
   proposed in this document.

   For TRILL general Security Considerations, see [RFC6325].

8. IANA Considerations

   This document introduces two new router-capability sub-TLVs that
   require code point assignment:

   o  Parent selection tiebreak algorithm version, to be assigned from
      the IANA "IS-IS TLV Codepoints Registry".

   o  Explicit parent selection, to be assigned from the IANA "IS-IS TLV
      Codepoints Registry".

9. Conclusions

   This document presents a parent selection tiebreak algorithm in the
   calculation of distribution trees in TRILL. A protocol extension in
   IS-IS is defined, and a network migration strategy is also designed.
   The proposed algorithm provides a tool to influence the parent node
   selection, which can improve the stability and traffic load sharing
   of the distribution trees when multiple equal cost parents are
   present. It also offers a tool to network administrators to pin down
   the multi-destination traffic to trees in more deterministic way.

10. References

10.1.  Normative References

   [RFC6325] Perlman, R., Eastlake, D., Dutt, D., Gai, S., and A.
             Ghanwani, "RBridges: Base Protocol Specification", RFC
             6325, June 2011.

   [RFC7180] D. Eastlake, M. Zhang, A. Ghanwani, V. Manral, A.
             Banerjee, "TRILL: Clarifications, Corrections, and
             Updates", May 2014.

   [RFC4971] Vasseur, JP. and N. Shen, "Intermediate System to
             Intermediate System (IS-IS) Extensions for Advertising
             Information", 2007.

Yang, et al            Expires January 17, 2016               [Page 12]
Internet-Draft         Trill: Parent Selection                July 2015

11. Acknowledgments

   The authors would like to thank Abhay Roy, Erik Nordmark, Varun Shah,
   Ramkumar Parameswaran and Deepak Sreekantan for review and
   suggestions.

   This document was prepared using 2-Word-v2.0.template.dot.

Yang, et al            Expires January 17, 2016               [Page 13]
Internet-Draft         Trill: Parent Selection                July 2015

Authors' Addresses

   Howard Yang
   Cisco Systems
   170 West Tasman Drive, San Jose, CA 95134

   Email: howardy@cisco.com

   Ayan Banerjee
   Cisco Systems
   170 West Tasman Drive, San Jose, CA 95134

   Email: ayabaner@gmail.com

   Donald Eastlake
   Huawei R&D USA
   155 Beaver Street, Milford, MA 01757

   Phone: 1-508-333-2270
   Email: d3e3e3@gmail.com

   Radia Perlman
   Intel Labs
   2200 Mission College Blvd., Santa Clara, CA 95054-1549

   Phone: 1-408-765-8080
   Email: radia@alum.mit.edu