RFC 3031 - 5. Label Distribution Procedures (Hop-by-Hop)

Label Distribution Procedures (Hop-by-Hop)

In this section, we consider only label bindings that are used for traffic to be label switched along its hop-by-hop routed path. In these cases, the label in question will correspond to an address prefix in the routing table.

5.1. The Procedures for Advertising and Using labels

There are a number of different procedures that may be used to distribute label bindings. Some are executed by the downstream LSR, and some by the upstream LSR.

The downstream LSR must perform:

  -  The Distribution Procedure, and

  -  the Withdrawal Procedure.

The upstream LSR must perform:

  -  The Request Procedure, and

  -  the NotAvailable Procedure, and

  -  the Release Procedure, and

  -  the labelUse Procedure.

The MPLS architecture supports several variants of each procedure.

However, the MPLS architecture does not support all possible combinations of all possible variants. The set of supported combinations will be described in section 5.2, where the interoperability between different combinations will also be discussed.

5.1.1. Downstream LSR: Distribution Procedure

The Distribution Procedure is used by a downstream LSR to determine when it should distribute a label binding for a particular address prefix to its label distribution peers. The architecture supports four different distribution procedures.

Irrespective of the particular procedure that is used, if a label binding for a particular address prefix has been distributed by a downstream LSR Rd to an upstream LSR Ru, and if at any time the attributes (as defined above) of that binding change, then Rd must inform Ru of the new attributes.

If an LSR is maintaining multiple routes to a particular address prefix, it is a local matter as to whether that LSR binds multiple labels to the address prefix (one per route), and hence distributes multiple bindings.

5.1.1.1. PushUnconditional

Let Rd be an LSR. Suppose that:

X is an address prefix in Rd's routing table

Ru is a label distribution peer of Rd with respect to X

Whenever these conditions hold, Rd must bind a label to X and distribute that binding to Ru. It is the responsibility of Rd to keep track of the bindings which it has distributed to Ru, and to make sure that Ru always has these bindings.

This procedure would be used by LSRs which are performing unsolicited downstream label assignment in the Independent LSP Control Mode.

5.1.1.2. PushConditional

Let Rd be an LSR. Suppose that:

  1. X is an address prefix in Rd's routing table

  2. Ru is a label distribution peer of Rd with respect to X

  3. Rd is either an LSP Egress or an LSP Proxy Egress for X, or
     Rd's L3 next hop for X is Rn, where Rn is distinct from Ru, and
     Rn has bound a label to X and distributed that binding to Rd.

Then as soon as these conditions all hold, Rd should bind a label to X and distribute that binding to Ru.

Whereas PushUnconditional causes the distribution of label bindings for all address prefixes in the routing table, PushConditional causes the distribution of label bindings only for those address prefixes for which one has received label bindings from one's LSP next hop, or for which one does not have an MPLS-capable L3 next hop.

This procedure would be used by LSRs which are performing unsolicited downstream label assignment in the Ordered LSP Control Mode.

5.1.1.3. PulledUnconditional

Let Rd be an LSR. Suppose that:

X is an address prefix in Rd's routing table

Ru is a label distribution peer of Rd with respect to X

Ru has explicitly requested that Rd bind a label to X and
     distribute the binding to Ru

Then Rd should bind a label to X and distribute that binding to Ru. Note that if X is not in Rd's routing table, or if Rd is not a label distribution peer of Ru with respect to X, then Rd must inform Ru that it cannot provide a binding at this time.

If Rd has already distributed a binding for address prefix X to Ru, and it receives a new request from Ru for a binding for address prefix X, it will bind a second label, and distribute the new binding to Ru. The first label binding remains in effect.

This procedure would be used by LSRs performing downstream-on-demand label distribution using the Independent LSP Control Mode.

5.1.1.4. PulledConditional

Let Rd be an LSR. Suppose that:

  1. X is an address prefix in Rd's routing table

  2. Ru is a label distribution peer of Rd with respect to X

  3. Ru has explicitly requested that Rd bind a label to X and
     distribute the binding to Ru

  4. Rd is either an LSP Egress or an LSP Proxy Egress for X, or
     Rd's L3 next hop for X is Rn, where Rn is distinct from Ru, and
     Rn has bound a label to X and distributed that binding to Rd

Then as soon as these conditions all hold, Rd should bind a label to X and distribute that binding to Ru. Note that if X is not in Rd's routing table and a binding for X is not obtainable via Rd's next hop for X, or if Rd is not a label distribution peer of Ru with respect to X, then Rd must inform Ru that it cannot provide a binding at this time.

However, if the only condition that fails to hold is that Rn has not yet provided a label to Rd, then Rd must defer any response to Ru until such time as it has receiving a binding from Rn.

If Rd has distributed a label binding for address prefix X to Ru, and at some later time, any attribute of the label binding changes, then Rd must redistribute the label binding to Ru, with the new attribute. It must do this even though Ru does not issue a new Request.

This procedure would be used by LSRs that are performing downstream- on-demand label allocation in the Ordered LSP Control Mode.

In section 5.2, we will discuss how to choose the particular procedure to be used at any given time, and how to ensure interoperability among LSRs that choose different procedures.

5.1.2. Upstream LSR: Request Procedure

The Request Procedure is used by the upstream LSR for an address prefix to determine when to explicitly request that the downstream LSR bind a label to that prefix and distribute the binding. There are three possible procedures that can be used.

5.1.2.1. RequestNever

Never make a request. This is useful if the downstream LSR uses the PushConditional procedure or the PushUnconditional procedure, but is not useful if the downstream LSR uses the PulledUnconditional procedure or the the PulledConditional procedures.

This procedure would be used by an LSR when unsolicited downstream label distribution and Liberal Label Retention Mode are being used.

5.1.2.2. RequestWhenNeeded

Make a request whenever the L3 next hop to the address prefix changes, or when a new address prefix is learned, and one doesn't already have a label binding from that next hop for the given address prefix.

This procedure would be used by an LSR whenever Conservative Label Retention Mode is being used.

5.1.2.3. RequestOnRequest

Issue a request whenever a request is received, in addition to issuing a request when needed (as described in section 5.1.2.2). If Ru is not capable of being an LSP ingress, it may issue a request only when it receives a request from upstream.

If Rd receives such a request from Ru, for an address prefix for which Rd has already distributed Ru a label, Rd shall assign a new (distinct) label, bind it to X, and distribute that binding. (Whether Rd can distribute this binding to Ru immediately or not depends on the Distribution Procedure being used.)

This procedure would be used by an LSR which is doing downstream-on- demand label distribution, but is not doing label merging, e.g., an ATM-LSR which is not capable of VC merge.

5.1.3. Upstream LSR: NotAvailable Procedure

If Ru and Rd are respectively upstream and downstream label distribution peers for address prefix X, and Rd is Ru's L3 next hop for X, and Ru requests a binding for X from Rd, but Rd replies that it cannot provide a binding at this time, because it has no next hop for X, then the NotAvailable procedure determines how Ru responds. There are two possible procedures governing Ru's behavior:

5.1.3.1. RequestRetry

Ru should issue the request again at a later time. That is, the requester is responsible for trying again later to obtain the needed binding. This procedure would be used when downstream-on-demand label distribution is used.

5.1.3.2. RequestNoRetry

Ru should never reissue the request, instead assuming that Rd will provide the binding automatically when it is available. This is useful if Rd uses the PushUnconditional procedure or the PushConditional procedure, i.e., if unsolicited downstream label distribution is used.

Note that if Rd replies that it cannot provide a binding to Ru, because of some error condition, rather than because Rd has no next hop, the behavior of Ru will be governed by the error recovery conditions of the label distribution protocol, rather than by the NotAvailable procedure.

5.1.4. Upstream LSR: Release Procedure

Suppose that Rd is an LSR which has bound a label to address prefix X, and has distributed that binding to LSR Ru. If Rd does not happen to be Ru's L3 next hop for address prefix X, or has ceased to be Ru's L3 next hop for address prefix X, then Ru will not be using the label. The Release Procedure determines how Ru acts in this case. There are two possible procedures governing Ru's behavior:

5.1.4.1. ReleaseOnChange

Ru should release the binding, and inform Rd that it has done so. This procedure would be used to implement Conservative Label Retention Mode.

5.1.4.2. NoReleaseOnChange

Ru should maintain the binding, so that it can use it again immediately if Rd later becomes Ru's L3 next hop for X. This procedure would be used to implement Liberal Label Retention Mode.

5.1.5. Upstream LSR: labelUse Procedure

Suppose Ru is an LSR which has received label binding L for address prefix X from LSR Rd, and Ru is upstream of Rd with respect to X, and in fact Rd is Ru's L3 next hop for X.

Ru will make use of the binding if Rd is Ru's L3 next hop for X. If, at the time the binding is received by Ru, Rd is NOT Ru's L3 next hop for X, Ru does not make any use of the binding at that time. Ru may however start using the binding at some later time, if Rd becomes Ru's L3 next hop for X.

The labelUse Procedure determines just how Ru makes use of Rd's binding.

There are two procedures which Ru may use:

5.1.5.1. UseImmediate

Ru may put the binding into use immediately. At any time when Ru has a binding for X from Rd, and Rd is Ru's L3 next hop for X, Rd will also be Ru's LSP next hop for X. This procedure is used when loop detection is not in use.

5.1.5.2. UseIfLoopNotDetected

This procedure is the same as UseImmediate, unless Ru has detected a loop in the LSP. If a loop has been detected, Ru will discontinue the use of label L for forwarding packets to Rd.

This procedure is used when loop detection is in use.

This will continue until the next hop for X changes, or until the loop is no longer detected.

5.1.6. Downstream LSR: Withdraw Procedure

In this case, there is only a single procedure.

When LSR Rd decides to break the binding between label L and address prefix X, then this unbinding must be distributed to all LSRs to which the binding was distributed.

It is required that the unbinding of L from X be distributed by Rd to a LSR Ru before Rd distributes to Ru any new binding of L to any other address prefix Y, where X != Y. If Ru were to learn of the new binding of L to Y before it learned of the unbinding of L from X, and if packets matching both X and Y were forwarded by Ru to Rd, then for a period of time, Ru would label both packets matching X and packets matching Y with label L.

The distribution and withdrawal of label bindings is done via a label distribution protocol. All label distribution protocols require that a label distribution adjacency be established between two label distribution peers (except implicit peers). If LSR R1 has a label distribution adjacency to LSR R2, and has received label bindings from LSR R2 via that adjacency, then if adjacency is brought down by either peer (whether as a result of failure or as a matter of normal operation), all bindings received over that adjacency must be considered to have been withdrawn.

As long as the relevant label distribution adjacency remains in place, label bindings that are withdrawn must always be withdrawn explicitly. If a second label is bound to an address prefix, the result is not to implicitly withdraw the first label, but to bind both labels; this is needed to support multi-path routing. If a second address prefix is bound to a label, the result is not to implicitly withdraw the binding of that label to the first address prefix, but to use that label for both address prefixes.

5.2. MPLS Schemes: Supported Combinations of Procedures

Consider two LSRs, Ru and Rd, which are label distribution peers with respect to some set of address prefixes, where Ru is the upstream peer and Rd is the downstream peer.

The MPLS scheme which governs the interaction of Ru and Rd can be described as a quintuple of procedures: <Distribution Procedure, Request Procedure, NotAvailable Procedure, Release Procedure, labelUse Procedure>. (Since there is only one Withdraw Procedure, it need not be mentioned.) A "*" appearing in one of the positions is a wild-card, meaning that any procedure in that category may be present; an "N/A" appearing in a particular position indicates that no procedure in that category is needed.

Only the MPLS schemes which are specified below are supported by the MPLS Architecture. Other schemes may be added in the future, if a need for them is shown.

5.2.1. Schemes for LSRs that Support Label Merging

If Ru and Rd are label distribution peers, and both support label merging, one of the following schemes must be used:

  1. <PushUnconditional, RequestNever, N/A, NoReleaseOnChange,
     UseImmediate>

     This is unsolicited downstream label distribution with
     independent control, liberal label retention mode, and no loop
     detection.

  2. <PushUnconditional, RequestNever, N/A, NoReleaseOnChange,
     UseIfLoopNotDetected>

     This is unsolicited downstream label distribution with
     independent control, liberal label retention, and loop
     detection.

  3. <PushConditional, RequestWhenNeeded, RequestNoRetry,
     ReleaseOnChange, *>

     This is unsolicited downstream label distribution with ordered
     control (from the egress) and conservative label retention
     mode.  Loop detection is optional.

  4. <PushConditional, RequestNever, N/A, NoReleaseOnChange, *>

     This is unsolicited downstream label distribution with ordered
     control (from the egress) and liberal label retention mode.
     Loop detection is optional.

  5. <PulledConditional, RequestWhenNeeded, RequestRetry,
     ReleaseOnChange, *>

     This is downstream-on-demand label distribution with ordered
     control (initiated by the ingress), conservative label
     retention mode, and optional loop detection.

  6. <PulledUnconditional, RequestWhenNeeded, N/A, ReleaseOnChange,
     UseImmediate>

     This is downstream-on-demand label distribution with
     independent control and conservative label retention mode,
     without loop detection.









  7. <PulledUnconditional, RequestWhenNeeded, N/A, ReleaseOnChange,
     UseIfLoopNotDetected>

     This is downstream-on-demand label distribution with
     independent control and conservative label retention mode, with
     loop detection.

5.2.2. Schemes for LSRs that do not Support Label Merging

Suppose that R1, R2, R3, and R4 are ATM switches which do not support label merging, but are being used as LSRs. Suppose further that the L3 hop-by-hop path for address prefix X is <R1, R2, R3, R4>, and that packets destined for X can enter the network at any of these LSRs. Since there is no multipoint-to-point capability, the LSPs must be realized as point-to-point VCs, which means that there needs to be three such VCs for address prefix X: <R1, R2, R3, R4>, <R2, R3, R4>, and <R3, R4>.

Therefore, if R1 and R2 are MPLS peers, and either is an LSR which is implemented using conventional ATM switching hardware (i.e., no cell interleave suppression), or is otherwise incapable of performing label merging, the MPLS scheme in use between R1 and R2 must be one of the following:

  1. <PulledConditional, RequestOnRequest, RequestRetry,
     ReleaseOnChange, *>

     This is downstream-on-demand label distribution with ordered
     control (initiated by the ingress), conservative label
     retention mode, and optional loop detection.

     The use of the RequestOnRequest procedure will cause R4 to
     distribute three labels for X to R3; R3 will distribute 2
     labels for X to R2, and R2 will distribute one label for X to
     R1.

  2. <PulledUnconditional, RequestOnRequest, N/A, ReleaseOnChange,
     UseImmediate>

     This is downstream-on-demand label distribution with
     independent control and conservative label retention mode,
     without loop detection.

  3. <PulledUnconditional, RequestOnRequest, N/A, ReleaseOnChange,
     UseIfLoopNotDetected>

     This is downstream-on-demand label distribution with
     independent control and conservative label retention mode, with
     loop detection.

5.2.3. Interoperability Considerations

It is easy to see that certain quintuples do NOT yield viable MPLS schemes. For example:

  -  <PulledUnconditional, RequestNever, *, *, *>
     <PulledConditional, RequestNever, *, *, *>

     In these MPLS schemes, the downstream LSR Rd distributes label
     bindings to upstream LSR Ru only upon request from Ru, but Ru
     never makes any such requests.  Obviously, these schemes are
     not viable, since they will not result in the proper
     distribution of label bindings.

     -  <*, RequestNever, *, *, ReleaseOnChange>

     In these MPLS schemes, Rd releases bindings when it isn't using
     them, but it never asks for them again, even if it later has a
     need for them.  These schemes thus do not ensure that label
     bindings get properly distributed.

In this section, we specify rules to prevent a pair of label distribution peers from adopting procedures which lead to infeasible MPLS Schemes. These rules require either the exchange of information between label distribution peers during the initialization of the label distribution adjacency, or a priori knowledge of the information (obtained through a means outside the scope of this document).

  1. Each must state whether it supports label merging.

  2. If Rd does not support label merging, Rd must choose either the
     PulledUnconditional procedure or the PulledConditional
     procedure.  If Rd chooses PulledConditional, Ru is forced to
     use the RequestRetry procedure.

     That is, if the downstream LSR does not support label merging,
     its preferences take priority when the MPLS scheme is chosen.









  3. If Ru does not support label merging, but Rd does, Ru must
     choose either the RequestRetry or RequestNoRetry procedure.
     This forces Rd to use the PulledConditional or
     PulledUnConditional procedure respectively.

     That is, if only one of the LSRs doesn't support label merging,
     its preferences take priority when the MPLS scheme is chosen.

  4. If both Ru and Rd both support label merging, then the choice
     between liberal and conservative label retention mode belongs
     to Ru.  That is, Ru gets to choose either to use
     RequestWhenNeeded/ReleaseOnChange (conservative) , or to use
     RequestNever/NoReleaseOnChange (liberal).  However, the choice
     of "push" vs. "pull" and "conditional" vs. "unconditional"
     belongs to Rd.  If Ru chooses liberal label retention mode, Rd
     can choose either PushUnconditional or PushConditional.  If Ru
     chooses conservative label retention mode, Rd can choose
     PushConditional, PulledConditional, or PulledUnconditional.

     These choices together determine the MPLS scheme in use.