Internet Draft
Network Working Group                                     Dino Farinacci
Internet Draft                                             cisco Systems
Expiration Date: March 2000                                Yakov Rekhter
                                                           cisco Systems
                                                          September 1999

  Partitioning Label Space among Multicast Routers on a Common Subnet
             <draft-farinacci-multicast-label-part-01.txt>

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026 except that the right to
   produce derivative works is not granted.

   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.

Abstract

   There are 3 major functions that must be performed to achieve
   multicast Label Switching. 1) Label Allocation, which requires each
   multicast Label Switching Router (LSR) to have a label value range
   that it uses. 2) Label Binding, using the labels allocated, a LSR
   must assign them to multicast routes. 3) Label Binding Distribution,
   after binding label values to routes, they must be distributed to
   other LSRs so they all forward on a common and consistent
   distribution tree.

   In this document we present how labels are allocated uniquely across

Farinacci                                                       [Page 1]

Internet Draft             Label Partitioning             September 1999

   multicast capable LSRs on a LAN and point-to-point IP subnets.

1. Introduction

   This memo specifies a simple algorithm to partition a label
   allocation space among multicast LSRs on a common media. So that each
   range allocated to a router is unique and non overlapping with any
   range allocated to any other LSR on that network media.

   Since an upstream LSR will use a single label for a multicast packet,
   all downstream LSRs, on the same subnet as the upstream router, must
   be ready to use it to do multicast label forwarding.  Therefore, no
   other LSR, on the subnet, can use the same label or it would be
   ambiguous which multicast distribution tree to forward on. Therefore,
   each LSR might be potentially an upstream LSR for different multicast
   distribution trees and needs its own label range.

   This procedure can be used for any label binding and distribution
   scheme, be it upstream or downstream multicast label distribution.

2. LAN Procedure

   Each multicast LSR on a LAN is configured with the label table size
   it will use for the LAN interface. An approximate router-count will
   also be configured. This allows a router to allocate a range equal to
   1/router-count of the label table size. This label table is used for
   multicast label forwarding only.

   When a multicast LSR boots up or enables the LAN interface to do
   multicast routing, it will advertise in PIM Hello messages the label
   table size, router count, the label range it randomly selects, and
   optionally its priority. The lower range label value and the higher
   range label value accompany the advertisement. If a LSR doesn't
   advertise its priority, it is treated as if the LSR would advertise
   the highest possible priority.

   If there is another LSR that has selected the same range, then the
   following procedures are used to determine which of the two LSRs
   would be able to keep its range, and which would be required to
   allocate another label range.  If the two LSRs have different
   priority, then the one with the lower priority is required to
   allocate another label range. If the two LSRs have the same priority,
   then the one with the lower IP address on the LAN is required to
   allocate another label range. In both cases the label range is
   allocated randomly. If as a result of these procedures a LSR has to
   allocate another label range, then the LSR has to withdraw its label

Farinacci                                                       [Page 2]

Internet Draft             Label Partitioning             September 1999

   bindings from its currently allocated range, and then (after it
   allocates another range) reallocate its bindings.

   A LSR can be configured to use more than one label range if one
   believes it will be an upstream LSR for many flows. It just inserts
   additional advertisements in the same PIM Hello message. The label
   table size and router-count should be the same in all advertisements
   contained in a message.

3. Point-to-point Procedure

   On point-to-point links since there can only be one forwarder from a
   LSR's point of view (the other end of the link), each LSR can use the
   entire label table size as their label range. There is no conflict
   because there can be one and only one downstream neighbor for a given
   distribution tree.

   Also, the label table size advertised in PIM Hello messages over
   point-to-point links don't have to be the same size. The router-count
   is ignored for point-to-point advertisements.

4. Configuration Errors

   If the label table size is not configured consistently on all LSRs
   connected to a LAN, the smallest table size advertised by any LSR
   will be used.

   If the router-count is not configured consistently on all LSRs
   connected to a LAN, the smallest router-count value advertised by any
   LSR will be used. This means the largest division of the label table
   space will occur.

5. Subnet Partitioning

   When a subnet partitions and new multicast LSRs come up, they will
   allocate label ranges that are unique to their partition. When the
   partition heals, there may be conflicts. Once the PIM Hellos messages
   are received by LSRs on the other side of the partition, they will
   determine there is a label range allocation conflict and immediately
   perform the tie breaking rules described above.

6. Exceeding the Label Table Size

   When a LSR cannot allocate a label range because all ranges within

Farinacci                                                       [Page 3]

Internet Draft             Label Partitioning             September 1999

   the label table size have been allocated, it will not participate in
   binding labels to multicast routes. Packets for these routes will not
   be label switched.  However, the LSR is still capable of label
   switching a packet as either an upstream or downstream LSR on that
   LAN. This is the case when another router is binding labels for the
   multicast route and has an allocated a label range successfully.

Farinacci                                                       [Page 4]

Internet Draft             Label Partitioning             September 1999

7. PIM Hello Packet Format

   The PIM Hello message will carry 2 new OptionTypes (called "Label
   Parameters" and "VCI Capability") as specified in [2]. A router that
   sends a PIM Hello with the Label Parameters option is regarded as
   being label-capable. This Option can appear multiple times in a Hello
   packet if a LSR wants to allocate multiple ranges. When this option
   appears multiple times in the Hello message, the Label Table Size and
   Router Count must be the same for each Label Parameters Option
   supplied in the message.

   When sent on point-to-point links, this option should have Router
   Count, Lower Label Range, and Upper Label Range set to 0. These
   fields are ignored on receipt.

   Label Parameters TLV

   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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      OptionType = 17          |      OptionLength = 16        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Label Table Size                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Router Count                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Lower Label Range                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Upper Label Range                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   OptionType "Label Parameters"
      Set to value 17 decimal.

   OptionLength
      The option is 16 bytes in length.

   Label Table Size
      The size of the TIB, in number of entries, the sending router
      supports on the interface the Hello is sent on.

   Router Count
      The approximate maximum number of routers that may be connected to
      the subnet the Hello is sent on.

   Lower Label Range
      The lower label value in the label range that was been randomly
      selected by the sending router. This value must be less than the

Farinacci                                                       [Page 5]

Internet Draft             Label Partitioning             September 1999

      Upper Label Range value.

   Upper Label Range
      The upper label value in the label range that was been randomly
      selected by the sending router. This value must be greater than
      the Lower Label Range value.

   VCI Capability TLV

   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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      OptionType = 18          |      OptionLength = 1         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Direction   |
   +-+-+-+-+-+-+-+-+

   Direction
      When set to 0, VCI capability is bidirectional. When set to 1, VCI
      capability is unidirectional. Bidirectional capability indicates
      an ATM-LSR issuing this option can, within a single VPI, support
      binding  of the same VCI to different routes on the different
      directions of the link. Unidirectional capability indicates an
      ATM-LSR issuing this option can, within a single VPI, a single VCI
      may appear in one binding only. In such systems when a VCI has
      been bound in one direction on the link it may not be used in the
      other.

   Priority TLV

   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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      OptionType = 19          |      OptionLength = 4         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Priority                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Priority
      When several LSRs on a LAN allocate the same label range, this
      field is used to determine which one of those LSRs may keep the
      allocation.  The Priority field is treated as a 32-bits unsigned
      integer. Higher value is associated with higher Priority.

8. Security Considerations

Farinacci                                                       [Page 6]

Internet Draft             Label Partitioning             September 1999

   Security considerations are not discussed in this memo.

9. Acknowledgments

   Contributions to this work has been made by Yakov Rekhter.

10. Author's Address:

   Dino Farinacci
   Cisco Systems, Inc.
   170 Tasman Drive
   San Jose, CA, 95134

   Email: dino@cisco.com

   Yakov Rekhter
   Cisco Systems, Inc.
   170 Tasman Drive
   San Jose, CA, 95134

   Email: yakov@cisco.com

11. References

   [1] Label Switching Architecture Overview, draft-ietf-mpls-arch-
   02.txt, Rosen, Viswanathan, Callon, June 1998

   [2] Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
   Specification, , Estrin,
   Farinacci, Helmy, Thaler, Deering, Handley, Jacobson, Liu, Sharma,
   Wei, October, 1996

Farinacci                                                       [Page 7]