4.2 MPLS System Functions
This section describes the MPLS functions of distributing labels, merging of LSPs, manipulating the MPLS label stack, and selecting a route on which to forward a labeled packet.
The distribution of labelswhich includes allocation, distribution, and withdrawal of label and FEC bindingsis the mechanism on which MPLS most depends. It is the simple fact of agreeing on the meaning of a label that makes simplified forwarding on the basis of a fixed-length label possible. Protocols defined to aid in achieving this agreement between cooperating network devices are thus of paramount importance to the proper functioning of MPLS.
Piggyback Label Distribution
Labels may be transported in routing (and related) protocol messages. The attraction of this approach is that by piggybacking label assignments in the same protocol that is used to transport or define the associations (e.g., FECs) bound to those labels, the degree of consistency in assignment, validity, and use of those labels is increased. Consistency is made better by eliminating the use of additional messages that may lag behind and introduce a latency period in which, for instance, a route advertisement and its corresponding label(s) are inconsistent. Note that the latency resulting from a lag between route and label updates can be significant at very high packet transport speeds even if the delay is very small.
Examples of piggyback label distribution are discussed in Rekhter and Rosen (w.i.p.) and Awduche et al. (w.i.p.). See also the section entitled Label Distribution in Chapter 6.
Generalized Label Distribution
Labels may also be distributed using protocols designed for that specific purpose.16 A label distribution protocol is useful under those circumstances in which no suitable piggyback protocol may be used. The attractions of this approach are as follows:
The scope of a label distribution protocol is orthogonal to specific routing (and related) protocols.
A label distribution protocol provides a direct means for determining the capabilities of LSR peers.
The protocol is more likely to be semantically complete 17 relative to the label distribution process.
LDP (Andersson et al. 2001) is an example of a label distribution protocol.
Merging in MPLS is the process of grouping FECs that will result in an identical forwarding path within an MPLS domain into a single LSP. Without this process, multiple LSPs will be set up to follow the same routed path toward an MPLS egress that is common for FECs associated with each LSP. This is not an efficient use of labels. However, the egress for the MPLS domain for a set of FECs may wish to use a finer granularity for the LSPs arriving at its input interfaces (for example, ensuring that no two streams of traffic, which the egress will forward to different next hops, share the same input labels).
In general, the best combination of efficiency and purpose is achieved by allowing downstream LSRs to control the merging granularity.
If an LSR, which is not an egress, waits until it has received a mapping from its downstream peer(s) and simply adopts the level of granularity provided by the mappings it receives, the downstream peer controls the granularity of resulting LSPs. This is the recommended approach when using ordered control. 18
If an LSR, which is not an egress, distributes labels upstream prior to having received label mappings from downstream, it may discover that the label mappings it subsequently receives are based on a different level of granularity. In this case, the LSR may have to do one of the following:
Withdraw some or all of its label mappings and reissue mappings with a matching granularity.
Merge streams associated with finer-granularity label mappings sent to upstream peers into a smaller set of coarser-granularity label mappings from downstream.
Choose a subset of finer-granularity label mappings from downstream to splice with the smaller set of coarser-granularity label mappings sent upstream. 19
An LSR operating in independent control mode that is merge capable may follow a policy that results in its typically sending slightly finer granularity mappings to upstream peers than it typically receives from its downstream peers. If it does this, it can then merge the streams received on the finer-granularity LSPs from upstream to send on to the coarser LSPs downstream.
An LSR operating in independent control mode that is not merge capable must either withdraw and reissue label mappings upstream to match the granularity used downstream or request matching-granularity label mappings from downstream.
Merging is an essential feature in getting MPLS to scale to at least as large as a typical routed network. With no merge capability whatever, LSPs must be established from each ingress point to each egress point (producing on the order of n2 LSPs, where n is the number of LSRs serving as edge nodes).20 With even partial merge capability, however, the number of LSPs required is substantially reduced (toward order n). With merge capability available and in use at every node, it is possible to set up multipoint-to-point LSPs such that only a single label is consumed per FEC at each LSRincluding all egress LSRs.
Different levels of merge capability are defined so that LSRs can support at least partial merge capability even when full merge capability is hard to do given the switching hardware (as is the case with many ATM switches).
Frame merge is the capability typical of standard routing and is a natural consequence of transport media that encapsulate an entire L3 packet inside an L2 frame. In this case, full merging occurs naturally and no action is required of the LSR. This is typically the case with non-ATM L2 technologies.
VC merge is the name applied to any technique that, when used with an ATM switch, allows it to effectively perform frame merging. Typically, this requires queuing cells associated with a single ATM Adaptation Layer (AAL) frame (if they are not actually reassembled) until the last one has been received. Those cells are then transmitted in the same order in which they were received, while being careful not to interleave them with cells from any other AAL frame being transmitted on the same VC. Interleaving cells using different VCIs is permissible; however, cells associated with the same VCI on any input interface must be transmitted without interleaving with cells received on other input interfaces (or the same interface using a different VCI) that will be transmitted using the same VCI.
Interleaving cells from different input VPI/VCIs onto the same output VPI/VCI makes it impossible for the receiver of the interleaved cells (from at least two sources) to determine where the frame boundaries should be when reassembling the cells into a higher-layer frame. The end-of-frame markers from multiple frames are interleaved as well, which would cause the cells from part of one frame to be assembled with cells from part of another frame (from a different source VPI/VCI), producing a completely useless assembled frame. To successfully merge traffic at the VPI/VCI level, the first cell from one input VPI/VCI must not be sent on an output VPI/VCI until the last cell from another input VPI/VCI has been sent on that same output VPI/VCI.
VC merging therefore requires that cells from each input VPI/VCI to be merged be queued until the last cell from other merging input VPI/VCIs has been sent on the same output VPI/VCI. Figure 4.2 shows the difference between interleaving and VC merging input VPI/VCIs onto a single output VPI/VCI. Using the train analogy from earlier, it is easy to see that the cars associated with one train must not become attached to the engine for another train in the process of merging the two trains onto the same track.
Figure 4.2 VC merging avoiding cell interleaving
VP merge is the name applied to any technique that provides for mapping distinct VCI numbers on different virtual paths (VPs) at input interfaces to the same VP at an output interface. Because distinct VCIs are used in transmitting cells on an output interface, it is not possible to interleave cells from different input streams at the output interface.
Label Stack Manipulation
Figure 4.3 illustrates stack manipulations associated with the label swap, pop, and push operations described in this section.
FIgure 4.3 Label andlabel stack manipulations
In a label swap, the label used to pick an ILM is swapped with a label provided as part of the swap label manipulation instruction in the NHLFE. The peer LSR associated with the next hop in the NHLFE distributed the new label to the local LSR at some point.
In a pop operation, the label used to pick an ILM is removed from the packet, and the next label in the stackif presentis put in its place. Each remaining label in the label stack is promoted one level (shifted left one word). If no label stack remains (the removed label's stack-entry bottom-of-stack bit is set), the packet is sent unlabeled on the interface indicated in the NHLFE.
In a push operation, a new label from an NHLFE is inserted, existing labels in the label stack are demoted one level (shifted right one word), and a new stack entry is made for the newly added label. If no stack existed previously, the LSR creates one stack entry containing the new label.
Note that for each pop or push operation, additional actions may be required (such as setting the bottom-of-stack bit if this is the first label being pushed, copying the TTL value from the previous top-level label to the new top-level label, and so on).
Methods for selecting routes in an LSR are discussed in this section.
Using Hop-by-Hop Routing
Hop-by-hop routing corresponds to normal routing. Each LSR is free to choose the next hop it will use in forwarding packets toward a destination (corresponding to an FEC), using its internal route computation.
Using Explicit Routing
Explicit routing is the process used when an individual LSR 21 specifies a nonempty set of the hops to be used in an LSP. If all the hops are specified, it is a strict explicit route. Otherwise, it is a loose explicit route. The path used to get from one explicit hop to the next may be determined using hop-by-hop routing or may itself be specified as a strict or loose explicit route.22 Based on this understanding of loose explicit routing, you should be able to see that "normal routing" is effectively a special case of loose explicit routing in which only the destination is specified.