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, <draft-ietf-idmr-pim-sm-spec-09.txt>, Estrin,
Farinacci, Helmy, Thaler, Deering, Handley, Jacobson, Liu, Sharma,
Wei, October, 1996
Farinacci [Page 7]