[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 02 03

Network Working Group                                          L. Yong
Internet Draft                                                  W. Hao
                                                            D. Eastlake
Category: Standard Track                                         Huawei

Expires: January 2014                                    July 8, 2013

         ISIS Protocol Extension For Building Distribution Trees


   This document proposes an IS-IS protocol extension for automatically
   building bi-directional distribution trees to transport multi-
   destination traffic in an IP network.

Status of this document

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

   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

   This Internet-Draft will expire on January 8, 2014.

Yong, et al                                                    [Page 1]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

Copyright Notice

   Copyright (c) 2013 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.

Table of Contents

   1. Introduction...................................................3
      1.1. Conventions used in this document.........................4
   2. IS-IS Protocol Extension.......................................4
      2.1. RTADDR sub-TLV............................................4
      2.2. RTADDRV6 sub-TLV..........................................6
      2.3. The Group Address Sub-TLV.................................7
   3. Procedures.....................................................8
      3.1. Distribution Tree Computation.............................8
      3.2. Parent Selection..........................................8
      3.3. Parallel Local Link Selection.............................9
      3.4. Tree Selection for a Group...............................10
      3.5. Pruning a Distribution Tree for a Group..................10
      3.6. RPF Mechanism............................................10
      3.7. Forwarding Using a Pruned Distribution Tree..............10
      3.8. Local Forwarding at Edge Router..........................11
      3.9. Distribution Tree across different IGP Levels............12
   4. Backward Compatibility........................................12
   5. Security Considerations.......................................12
   6. IANA Considerations...........................................12
   7. Acknowledgements..............................................12
   8. References....................................................12
      8.1. Normative References.....................................12
      8.2. Informative References...................................13

Yong, et al.                                                   [Page 2]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

1. Introduction

   The computer virtualization and cloud applications motivate the DC
   network virtualization technology [NVO3FRWK]. This technology
   decouples the end-points networking from the DC physical
   infrastructure network in terms of address space and configuration

   DC network virtualization solutions are necessary to carry all types
   of traffic in today's DC physical networks including multi-
   destination traffic. It is also desirable to use IP network as the
   DC underlying network for the overlay virtual networks [NVO3FRWK].

   IP network technology does not yet support multi-destination traffic
   forwarding. A variant of Protocol Independent Multicast (PIM)
   solutions [RFC4601] [RFC5015] are designed to carry IP multicast
   traffic over IP networks. However the PIM solutions use their own
   hello protocol and hop-to-hop Join/Leave message so each router does
   not have global information about the receivers; in the PIM
   solution, the data packets could be forwarded unnecessarily to the
   Rendezvous Point(RP), and then get dropped there when no receiver at
   all or the sender and receivers for a multicast group are on the
   same branch towards the RP, which consumes network resources.
   Furthermore PIM solutions maintain a lot of soft-state, have
   intensive CPU utilization, and have additional convergence time
   besides IGP's under a failure condition.

   Although the PIM protocol is mature and has been deployed in IP
   networks, applying PIM to the IP network that supports the Network
   Virtualization can be an extreme challenge [MCASTISS]. For example,
   VXLAN [VXLAN] solutions requires multicast support in the underlying
   network to simulate overlay L2 broadcast capability, where every
   edge node in an overlay virtual network (VN) is a multicast source
   and receiver. An overlay VN topology may be sparse and dynamic
   compared to the underlying IP network topology. Also large number of
   overlay VNs may exist in a DC, which PIM solutions can't scale to.

   This document uses extensions to the IS-IS protocol to build a
   distribution tree for multi-destination traffic transport in an IP
   network.  A router uses Router Capability message to announce the
   tree root address and the multicast groups associated to the tree.
   With this information, routers in the IGP can compute rooted
   distribution trees by using the link state information, i.e. LSDB,
   and shortest path algorithm. Edge routers include information in
   their LSPs to announce their multicast group-memberships. Routers
   perform distribution tree pruning for each multicast group based on

Yong, et al.                                                   [Page 3]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

   router's group membership announcement. A router forwards the multi-
   destination traffic along the pruned tree.

   In this solution, edge routers use IGMP query messages to inform the
   attached hosts and the hosts use IGMP report message to response
   with their interested multicast group(s).  The edge routers announce
   interested multicast groups in their LSPs so they are flooded to
   whole network.

   The benefits of this solution are 1) protocol convergence: use
   single protocol for both unicast and multicast traffic transport and
   get the same convergence time for unicast and multicast traffic. 2)
   multi-destination transport simplification: rely on the LSDB for
   computing a distribution tree and not run PIM hello protocol. 3)
   forwarding efficiency: no need to always forward the traffic to the
   RP; 4) better scalability: no need to maintain heavy PIM soft
   states. TRILL [RFC6325] has used IS-IS protocol for both single
   destination and multi-destination packet transport, which proves the
   protocol capability for doing both.

  1.1. Conventions used in this document

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

2. IS-IS Protocol Extension

  2.1.  RTADDR sub-TLV

   This is the sub-TLV of Router Capability TLV. Each RTADDR sub-TLV
   contains a root IPv4 address and multicast group addresses that
   associate to the tree. A router may use multiple RTADDR sub-TLVs to
   announce multiple root addresses and associated multicast groups
   with each root. RTADDR sub-TLV format is below.

Yong, et al.                                                   [Page 4]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

      |Type=RTADDR    |                  (1 byte)
      |   Length      |                  (1 byte)
      |                      Root IPv4 Address                        |
      | RESV  |       Topology ID   |    (2 byte)
      | Tree Priority |                  (1 byte)
      |Num of Groups  |                  (1 byte)
      |                   Group Address (1)                           |
      |                   Group Mask (1)                              |
      ~                                                               ~
      |                   GROUP Address (N)                           |
      |                   Group Mask (N)                              |


     Type: sub-TLV of Router Capability for RTADDR (TBD)

     Length: variable depending on the number of associated groups

     Topology ID: This field carries a topology ID [RFC5120] or zero if
     topologies are not in use.

     Root IP Address: IPv4 Address for a root

     Tree Priority: high number means higher priority. Zero means no

     Num of Groups: the number of group addresses

     Group Address: IPv4 Address for the group

     Group Mask: multicast group range

Yong, et al.                                                   [Page 5]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

   One router may be the root for multiple trees, each tree associates
   to a set of multicast groups. In this case, a router encodes
   multiple RTADDR sub-TLVs to announce root addresses, one for each
   root, in a router capability TLV. The group address/mask in
   different sub-TLVs can overlap. See section 3 for detail.

  2.2. RTADDRV6 sub-TLV

   This sub-TLV is used in IPv6 network. It has the same format and
   usage except that the addresses are in IPv6.

Yong, et al.                                                   [Page 6]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

      |Type = RTADDRV6|                  (1 byte)
      |   Length      |                  (1 byte)
      |                                                               |
      +                                                               +
      |                                                               |
      +                     Root IPv6 Address                         +
      |                                                               |
      +                                                               +
      |                                                               |
      | RESV  |       Topology ID   |    (2 byte)
      | Tree Priority |                  (1 byte)
      |Num of Groups  |                  (1 byte)
      |                                                               |
      +                                                               +
      |                                                               |
      +                  Group IPv6 Address (1)                       +
      |                                                               |
      +                                                               +
      |                                                               |
      |                                                               |
      +                                                               +
      |                                                               |
      +                     MASK(1)                                   +
      |                                                               |
      +                                                               +
      |                                                               |
      ~                                                               ~

  2.3. The Group Address Sub-TLV

   The Group Address TLV and a set of Group Address sub-TLVs are
   defined in RFC6326-bis [RFC6326BIS]. The GIP-ADDR and GIPV6-ADDR
   sub-TLVs are used in this solution. An edge router uses the GIP-ADDR
   sub-TLV or GIPV6-ADDR to announce its interested multicast groups.

Yong, et al.                                                   [Page 7]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

   The GIP-ADDR sub-TLV applies to an IPv4 network and GIPV6-ADDR sub-
   TLV for IPv6 network.

   When using a GIP-ADDR or GIPV6-ADDR sub-TLV, the field VLAN-ID MUST
   set to zero and be ignored. Other field usage remains the same as

3. Procedures

   When an operator selects a router as a distribution tree root,
   he/she configures the tree root address and associated multicast
   groups on the router. A tree root address can be an interface
   address or router loopback address. After the configuration, the
   router will include a RTADDR sub-TLV, inside a router capability TLV,
   where the tree root address and multicast groups are specified. If
   multiple trees are configured on the router, multiple RTADDR sub-
   TLVs are added in one router capability TLV to specify individual
   tree roots. For IPv4 network, RTADDR sub-TLV is used. For IPv6,
   RTADDRV6 sub-TLV is used. Note that the rest of document specifies
   the processes for an IPv4 network only and the processes for an IPv6
   network is the same.

   Operator may associate one multicast group to more than one tree for
   the redundancy purpose and use the tree priority to specify the
   primary tree preference. Section 3.2 describes the primary tree

  3.1. Distribution Tree Computation

   Upon receiving RTADDR sub-TLVs, routers track the tree roots and
   associated multicast groups. When the LSDB stabilizes, routers
   calculate all rooted trees according to the LSDB and shortest path

   One multicast group may associate to multiple trees. It is important
   that all the routers choose the same tree for a multicast group.
   Section 3.2 and 3.3 describes the tiebreaking rule for primary tree
   selection for a multicast group and parent selection in case of
   equal-cost to potential children.

  3.2. Parent Selection

   It is important, when building a distribution tree, that all routers
   choose the same links for the tree. Therefore, when there are equal
   costs from a potential child node to possible parent nodes, all
   routers need to use the same tiebreakers. It is also desirable to

Yong, et al.                                                   [Page 8]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

   allow splitting of traffic on as many links as possible in such
   situations. TRILL [RFC6325] achieves this by defining multiple
   rooted trees and using the tiebreakers to enable these trees to
   choose different parents. This draft uses the same tiebreakers as
   TRILL [RFC6325].

   If there are k distribution trees in the network, when each router
   computes these trees, the k trees calculated are ordered and
   numbered from 0 to k-1 in ascending order according to root IP

   The tiebreaker rule is: When building the tree number j, remember
   all possible equal cost parents for router N.  After calculating the
   entire "tree" (actually, directed graph), for each router 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.

  3.3. Parallel Local Link Selection

   If there are parallel links between two routers, say R1 and R2,
   these parallel links would be visible to R1 and R2, but not to other
   routers. If this bundle of parallel links is included in a tree, it
   is important for R1 and R2 to decide which link to use; if the R1-R2
   link is the branch for multiple trees, it is desirable to split
   traffic over as many link as possible. However the local link
   selection for a tree irrelevant to other Routers. Therefore, the
   tiebreaking algorithm need not be visible to any Routers other than
   R1 and R2.

   When there are L parallel links between R1 and R2 and they both are
   on K trees. L links are ordered from 0 to L-1 in ascending order of C                                                                           i                                                                           r                                                                           c                                                                            u                                                                            i                                                                            t                                                                                                                                                         D                                                                            I
   Circuit ID as associated with the adjacency by the router with the
   highest System ID, and K trees are ordered from 0 to K-1 in
   ascending order of root IP addresses. The tiebreaker rule is: for
   tree k, select the link as choice k mod L.

   Note that if multiple distribution trees are configured in a network
   or on a router, better load balance among parallel links through the
   tie-breaking algorithm can be achieved. Otherwise, if there is only
   one tree is configured, then only one link in parallel links can be
   used for the corresponding distribution tree. However, calculating
   and maintaining many trees is resource consuming. Operators need to
   balance between two.

Yong, et al.                                                   [Page 9]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

  3.4. Tree Selection for a Group

   Routers receive one or more possible multicast group-range-to-tree
   mappings. Each mapping specifies a range of multicast groups. It is
   possible that a group-range is associated with multiple trees that
   may have the same or different priority. When a multicast group-
   range associates with more than one tree, all routers has to select
   the same tree for the group-range. The tiebreaker rules specified in
   PIM [RFC4601] are used. They are:

   o  Perform longest match on group-range to get a list of trees.

   o  Select the tree with highest priority.

   o  If only one tree with the highest priority, select the tree for
      the group-range.

   o  If multiple trees are with the highest priority, use the PIM hash
      function to choose one. PIM hash function is described in section
      4.1.1 in RFC4601 [RFC4601].

  3.5. Pruning a Distribution Tree for a Group

   Routers prune the distribution tree for each associated multicast
   group, i.e. eliminating branches that have no potential downstream
   receivers.  Multi-destination packets SHOULD only be forwarded on
   branches that are not pruned. The assumption here is that a
   multicast source is also a multicast receiver but a multicast
   receiver may not be a multicast source.

   Routers prune the trees based on the groups specified in GRADD-TLV
   from edge routers. Routers maintain a list of adjacency interfaces
   that are on the pruned tree for a multicast group. Among these
   interfaces, one interface may be toward the tree-root router and
   other are toward the egress routers.

  3.6. RPF Mechanism

   For the further study.

  3.7. Forwarding Using a Pruned Distribution Tree

   Forwarding a multi-destination packet follows the pruned tree for
   the group that the packet belongs to. It is done as follows.

Yong, et al.                                                  [Page 10]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

   o  The router receives a multi-destination packet with group IP
      address that does not associated with any tree, the packet MUST
      be dropped.

   o  Else check if the link that the packet arrives on is one of the
      ports in the pruned distribution tree. If not, the packet MUST be

   o  Else perform RPF checking (section 3.5). If it fails, the packet
      SHOULD be dropped.

   o  Else the packet is forwarded onto all the adjacency interfaces in
      the list for the group except the interface where the packet

  3.8. Local Forwarding at Edge Router

   Upon receiving a multi-destination packet, besides forwarding it
   along the pruned tree, an edge router may also need to forward the
   packet to the local hosts attached to it. This is referred to as
   local forwarding in this document.

   The local group database is needed to keep track of the group
   membership of the router's directly attached network or host. Each
   entry in the local group database is a [group, network/host] pair,
   which indicates that the attached network has one or more hosts
   belonging to the multicast group. When receiving a multi-destination
   packet, the edge router forwards the packet to the network/host that
   match the [group, network/host] pair in the local group database.

   The local group database is built through the operation of the
   IGMPv3 [RFC3376].  When an edge router becomes Designated Router on
   an attached network, say N1, it starts sending periodic IGMPv3 Host
   Membership Queries on the network. Hosts then respond with IGMPv3
   Host Membership Reports, one for each multicast group to which they
   belong. Upon receiving a Host Membership Report for a multicast
   group A, the router updates its local group database by
   adding/refreshing the entry [Group A, N1]. If at a later time
   Reports for Group A cease to be heard on the network, the entry is
   then deleted from the local group database. The Designated Router
   further sends the LSP message with GRADDR sub-TLV to inform other
   routers about the group memberships in the local group database
   A router MUST ignore Host Membership Reports received on those
   networks where the router has not been elected Designated Router.

Yong, et al.                                                  [Page 11]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

  3.9. Distribution Tree across different IGP Levels

   Coming soon.

4. Backward Compatibility

   If a router does not support the distribution tree function
   described in this document, distribution tree computation MUST NOT
   include this router. This may result the incomplete tree. Operator
   can build a tunnel between two routers, which allows a single rooted
   tree to be built. How to build the tunnel is outside scope of this

5. Security Considerations

   Coming soon.

6. IANA Considerations

   The document requires two new sub-TLVs, RTADDR and RTADDRV6 for the
   Router Capability TLV in IANA registry.

7. Acknowledgements

   Authors like to thank Mike McBride and Linda Dunbar for their
   valuable inputs.

8. References

  8.1. Normative References

   [RFC3376] Cain B., etc, ''Internet Group Management Protocol, Version
   3'', rfc4604, October 2002

   [RFC4601] Fenner, B., etc, ''Protocol Independent multicast -                                                                   - Sparse
   Mode (PIM-SM): Protocol Specification'', rfc4601, August 2006

   [RFC5015] Handley, M., etc, ''Bidirectional Protocol Independent
   Multicast (BIDIR-PIM'', rfc5015, October 2007

   [RFC6325]  Perlman, R., et al, ''Routing Bridges (RBridges): Base
   Protocol Specification'', RFC6325, July 2011

   [RFC6326]  Eastlake D, et al, ''   Transparent Interconnection of

Yong, et al.                                                  [Page 12]

Internet-Draft    ISIS Ext. For Distribution Tree             July 2013

   Lots of Links (TRILL) Use of IS-IS'', RFC6326, July 2011

  8.2. Informative References

   [MCASTISS] Ghanvani, A., ''Multicast Issues in Networks Using NVO3'',
   draft-ghanwani-nvo3-mcast-issues-00, work in progress

   [NVO3FRWK] Lasserre, M., ''Framework for DC Network Virtualization'',
   draft-ietf-nvo3-framework-02.txt, work in progress.

   [RFC6326BIS]  Eastlake, D., etc, ''Transparent Interconnection of
   Lots of Links (TRILL) Use of IS-IS'', draft-ietf-isis-rfc6326bis-01,
   work in progress

   Authors' Addresses

   Lucy Yong
   Huawei USA
   5340 Legacy Drive
   Plano, TX  75025 USA

   Phone:  469-277-5837
   Email: lucy.yong@huawei.com

   Weiguo Hao
   Huawei Technologies
   101 Software Avenue,
   Nanjing 210012

   Phone: +86-25-56623144
   Email: haoweiguo@huawei.com

   Donald Eastlake
   155 Beaver Street
   Milford, MA 01757 USA

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

Yong, et al.                                                  [Page 13]

Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/