TRILL: Parent node Shifts in Tree Construction, Mitigation.
draft-rp-trill-parent-selection-02

Document Type Active Internet-Draft (individual)
Last updated 2017-02-23
Stream (None)
Intended RFC status (None)
Formats plain text pdf html bibtex
Stream Stream state (No stream defined)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date
Responsible AD (None)
Send notices to (None)
Trill WG                                                R. Parameswaran,
INTERNET-DRAFT                              Brocade Communications, Inc.
Intended Status:Experimental                          February 23, 2017
Expires: August 27, 2017

         TRILL: Parent node Shifts in Tree Construction, Mitigation.
           <draft-rp-trill-parent-selection-02.txt>
Abstract 

This draft documents a known problem in the Trill tree construction 
mechanism and offers two different approaches to solve the problem.

Status of This Memo

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

   Distribution of this document is unlimited. Comments should be sent
   to the authors or the TRILL working group mailing list:
   trill@ietf.org.

   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/1id-abstracts.html. The list of Internet-Draft
   Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Terminology and Acronyms.

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

Table of Contents

        1. Introduction...............................................1
        2. Tree construction in Trill.................................2
        3. Issues with the Trill tree construction algorithm..........2
        4. Alternative A - Using the Affinity sub-TLV.................4
        5. Alternative B - Variant of the Djikstra SPF algorithm......7
            5.1 Choice of the policy function........................11
        6. Network wide selection of computation algorithm...........13
        7. Relationship to draft-ietf-trill-resilient-trees..........14
        8. Security Considerations...................................16
        9. IANA Considerations.......................................16
       10. Informative References....................................16

1. Introduction.

Trill is a data center technology that uses link-state routing 
mechanisms in a layer 2 setting, and serves as a replacement 
for spanning-tree.  Trill uses trees rooted at pre-determined nodes 
as a way to distribute multi-destination traffic. Multi-destination 
traffic includes traffic such as layer-2 broadcast frames, unknown 
unicast flood frames, and layer 2 traffic with multicast MAC 
addresses (collectively referred to as BUM traffic). Multi-destination 
traffic is typically hashed onto one of the available trees and sent 
over the tree, potentially reaching all nodes in the network (hosts 
behind which may own/need the packet in question).

2. Tree construction in Trill.

Tree construction in Trill is defined by [RFC6325], with additional
corrections defined in [RFC7780].

The tree construction mechanism used in Trill codifies 
certain tree construction steps which make the resultant trees
very brittle. Specifically, the parent selection mechanism in Trill
causes problems in case of node failures. Trill uses the following rule
- when constructing an SPF tree, if there are multiple possible
parents for a given node (i.e. if multiple upstream nodes can
potentially pull in a given node during SPF, all at the same 
cumulative cost, then the parent selection is imposed in the
following manner):

[RFC6325]:
"When building the tree number j, remember all possible
equal cost parents for node N.  After calculating the entire 'tree'
(actually, directed graph), for each node N, if N has 'p' parents,
then order the parents in ascending order according to the
7-octet IS-IS ID considered as an unsigned integer, and number them
starting at zero. For tree j, choose N's parent as choice j mod p."

There is an additional correction posted to this in [RFC7780]:

[RFC7780], Section 3.4:

   "Section 4.5.1 of [RFC6325] specifies that, when building 
   distribution tree number j, node (RBridge) N that has multiple 
   possible parents in the tree is attached to possible parent 
   number j mod p.  Trees are numbered starting with 1, but possible 
   parents are numbered starting with 0.  As a result, if there are 
   two trees and two possible parents, then in tree 1 parent 1 will 
Show full document text