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

The information below is for an old version of the document
Document Type Active Internet-Draft (individual)
Author R. Parameswaran 
Last updated 2016-08-26
Replaced by draft-ietf-trill-parent-selection
Stream (None)
Intended RFC status (None)
Formats pdf htmlized (tools) htmlized 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:Informational                            August 25, 2016
Expires: February 22, 2017

         TRILL: Parent node Shifts in Tree Construction, Mitigation.

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:

   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-

   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 The list of Internet-Draft
   Shadow Directories can be accessed at

Terminology and Acronyms.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
document are to be interpreted as described in [RFC2119].

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 and the associated parent-shift issue.

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

    A--   --B
   / \ \/   /\
  /   \/\ _/_ \
 /__ _/\  /   \\
//      \/     \\
1        2       3 
 \       |      /
  \      |     /
   \     |    /
    \    |   /
     \   |  /
      \  | /
       \ |/

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):

"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 
   be selected, and in tree 2 parent 0 will be selected.

   This is changed so that the selected parent MUST be (j-1) mod p.  As
   a result, in the case above, tree 1 will select parent 0, and tree 2
   will select parent 1.  This change is not backward compatible with
   [RFC6325].  If all RBridges in a campus do not determine distribution
   trees in the same way, then for most topologies, the RPFC will drop
   many multi-destination packets before they have been properly

3. Issues with the Trill tree construction algorithm.

With  this  tree construction mechanism in  mind,  let's  look  at  
the Spine-Leaf topology  presented  in  section  2  and  consider the 
calculation of Tree number 1 in Trill. Consider the spine-leaf network
presented in section 2, with spine nodes A, B and leaf nodes 1,2,3.
Show full document text