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]