Tutorial: Introduction to MPLS Label Distribution and Signaling

Rick Gallaher, CISSP, is owner of Dragonfly Associates LLC http://dragonfly-associates.com and author of  Rick Gallaher's MPLS Training Guide

November 1, 2001

In the first tutorial, we discussed the data flow and the foundational concepts of MPLS networks. In this section, we will introduce the concepts and application of MPLS label distribution and introduce MPLS signaling. Moving forward, there will be a tutorial on Advanced MPLS Signaling.

Vocabulary

• Border Gateway Protocol (BGP)
• Binding
• Constrained Router Label Distribution Protocol (CR-LDP)
• Down Stream on Demand (DOD)
• Down Stream Unsolicited (DOU)
• Explicit Routing
• Independent Control
• Implicit Routing
• Intermediate System to Intermediate System (IS-IS)
• Label Distribution Protocol (LDP)
• Next Hop Label Forward Entry (NHLFE)
• Ordered Control
• Open Shortest Path First with Traffic Engineering (OSPF-TE)
• Resource Reservation Setup Protocol with Traffic Engineering (RSVP-TE)

The Early Days of Switching

Circuit switching by label is not new.  A quick look back at telephony shows us how signaling was done in the “old days.”  A telephone switchboard had patch cables and jacks; each jack was numbered to identify its location.  When a call came in, an operator would plug in a patch cord into the properly numbered jack.  This is a relatively simple concept.

Recalling these days, we find that although the process seemed simple enough, it was really hard work. Telephone operators would attend school for weeks and go through an apprenticeship before qualifying to operate a switchboard because the rules for connecting, disconnecting, and prioritizing calls were complex and varied from company to company.

Figure 1 Label Switching in the Early Days

Some of the rules included:

• Never disconnect the red jacks – these are permanent connections.
• Connect only the company executives to the jacks labeled for long distance.
• Never connect an executive to a noisy circuit.
• If there are not enough jacks when an executive needs to make a call, disconnect the lower priority calls.
• When “Mr. Big’s” secretary calls up at 9 a.m. to reserve a circuit for 10 a.m.–noon, make sure that the circuit is ready and that and you’ve placed the call by 9:50 a.m.
• In an emergency, all circuits can be controlled by the fire department.

So one operator had to know the permanent circuits (red jacks), the switched circuits, the prioritization scheme, and the reservation protocols.  When automatic switching came along, the same data and decision-making processes had to be loaded into a software program.

The MPLS switches must also be trained – they must learn all the rules and when to apply them. Two methods are used to make these switches.  One method uses hard programming; it is similar to how a router is programmed for static routing.   Static programming eliminates the ability to dynamically reroute or manage traffic.

Modern networks change on a dynamic basis.  To accommodate this need, many network engineers have chosen to use the second method: dynamic signaling and label distribution.  Dynamic label distribution and signaling can use one of several protocols, with each its given advantages and disadvantages. Because this is an emerging technology, we have not seen the dust fully settle on the most dominant label and signaling protocols.  

Yet despite the selection of protocols and their tradeoffs, the basic concepts of label distribution and signaling remain consistent across the protocols.

At a minimum, MPLS switches must learn how to process packets with incoming labels. Sometimes this is called a cross-connect table.   For example, label 101 in at port A will go out port B with a label swapped for 175.  The major advantage of using cross-connect tables instead of routing is that cross-connect tables can be processed at the “data link” layer, where processing is considerably faster than routing.

We will start our discussion using a simple network (figure 2) with four routers.  Each router has designated ports. For the sake of illustration, the ports have been given a simple letter a, b, s, h, a, and e. These port identifications are router specific.  The data flows from the input a of r1 to the input of r4.  This basic network diagram will be enhanced as we progress through MPLS signaling.

Figure 2:  Basic MPLS Network with 4 Routers

CONTROL OF LABEL DISTRIBUTION

There are two modes used to load these tables.  Each router could listen to routing tables, make its own cross-connect tables, and inform others of its information.  These routers would be operating independently. Independent control occurs when there is no designated label manager, and when every router has the ability to listen to routing protocols, generate cross-connect tables, and distribute them.  (Figure 3)

Figure 3:  Independent Control

The other model is ordered control, as shown in Figure 4.  In the ordered control mode, one router – typically the egress LER – is responsible for distributing labels.

Each of the two models has its tradeoffs. Independent control provides for faster network convergence.  Any router that hears of a routing change can relay that information to all other routers.  The disadvantage is that there is not one point of control making traffic, which makes engineering more difficult.

Ordered control has the advantages of better traffic engineering and tighter network control; however, its disadvantages are that convergence time is slower and the label controller is the single point of failure.

Figure 4: Ordered Control (pushed)

The Triggering of Label Distribution

Within ordered control, there are two major methods to trigger the distribution of labels.
These are called down-stream unsolicited and down-stream on demand.

DOU

In figure 4, we saw the labels “pushed” to the down-stream routers.  This push is based upon the decisions of the label manager router. When labels are sent out unsolicited by the label manager, it is known asdown-stream unsolicited (DOU).

For example: The label manager may use a trigger point (such as a time interval) to send out labels or label refresh messages every 45 seconds.   Or, a label manager may use the change of standard routing tables as a trigger – when a router changes, the label manager may send out label updates to all affected routers.


OD

When labels are requested, they are “pulled” down or demanded, so this method has been called pulled or down-stream on demand (DOD).  Note in Figure 5, that in the first step   the labels are requested and in the second step the labels are sent.

Figure 5:  Down-stream on Demand  (DOD)

Whether the labels arrive via independent or ordered control, or via DOD or DOU, the label switch router (LSR) creates a cross-connect table similar to the one shown in Figure 6.

The connect tables are sent to router r3 to r1. The tables heading read: label-in, port-in, label-out, port-out, and instruction (I).  In this case, the instruction is to swap (s).  It is important to note that the labels and cross-connect tables are router specific.

After the cross-connect tables are loaded, the data can flow from router 1 to router 4 with each router following its instructions to swap the labels.

Figure 6: LSR with Cross-connect Tables Populated

After the cross-connect tables are loaded, the data can now follow a designated LSP (label switch path) and flow from route 1 to router 4, as shown in Figure 7.

Figure 7:  Data Flow on LSP

REVIEW

As a brief review, we learned that routers need cross-connect tables in order to make switching decisions.  The routers can receive these tables from their neighbors via independent control or from a label manager via ordered control.

A label manger can send labels on demand (called down-stream on demand) or it can send labels when it decides to, even though it has not been requested by the down-stream routers, by using down-stream unsolicited (DOU).

With these basic concepts understood, there are some more advanced concepts to consider.  For instance, just how are labels sent to routers? What vehicle will be used to carry these labels?  How is the quality of service information relayed or sent to the routers? 

Reviewing from the first article, MPLS packets carry labels; however, the packets do not have an area that tells routers how to process the packet for quality of service (QoS).

Recalling that traffic can be separated into groups called forward equivalence classes (FECs), and that FECs can be assigned to label switch paths (LSP), we can perform traffic engineering to force high-priority FECs on to high-quality LSP and lower priority FECs on to lower-quality LSP.  The mapping of traffic using different QoS standards will cause the distribution of label and maps to be more complex.

Figure 8 shows a drawing of what goes on inside a LSR. There are two planes: the data plane and the control plane.  Labeled packets enter at input a with a label of 1450 and exit port b with a label of 1006. This function takes place in the cross-connect table. This table can also be called the next hop label forwarding entry table (NHLFE).  

Figure 8: A Closer Look at the Router

This database is not a stand-alone database.  It connects to two additional databases in the control plane: the FEC data and the FEC-to-NHLFE database.  The FEC database contains, at a minimum, the the destination IP address, but it can also contain traffic characteristics and packet processing requirements. Data in this database must be related to a label; the process of relating an FEC to a label is called binding.
Here is an example of how labels and FECs are set-up:

FEC Database

FEC	Protocol	Port
192.168.10.1	06	443	guaranteed no packet loss
192.168.10.2	11	69	best efforts
192.168.10.3	06	80	controlled load

Free Label Table
100-10,000 are not in use at this time
FEC to NHLFE Table

FEC	Label in	Label out
192.168.10.1	1400	100
192.168.10.2	500	101
192.168.10.3	107	103

NHLFE Table

Label in	Label out
1400	100
500	101
107	103

So we see that packets with labels can be quickly processed when entering the data plane, if the labels are bound to an FEC.  However, a lot of background processing must be done to the data traffic off line before a cross-connect table can be established.


Protocols

Finding a transport vehicle to build these complex tables is of the utmost concern to network designers.  What is needed is a protocol that can carry all of the necessary data while, at the same time, be fast, self-healing, and maintain very high reliability.

The MPLS workgroup and design engineers created the Label Distribution Protocol.
(LDP). This protocol works like a telephone call. When labels are bound, they stay bound until there is a command to tear down the call. This hard-state operation is less “chatty” than a protocol that requires refreshing. The LDP protocols provide implicit routing.

Other groups argue against using a new untested label distribution protocol when there exist routing protocols that can be modified or adapted to carry the bindings. Thus, some existing routing protocols have been modified to carry information for labels.  The Border Gateway Protocol (BPG) and IS-IS work well for distributing label information along with routing information.

The LDP, BGP and IS-IS protocols establish the Label Switch Path (LSPs), but do little for traffic engineering, because routed traffic could be redirected onto a high priority LSP, causing congestion.

To overcome this problem, the signaling protocols were established to create traffic tunnels (explicit routing) and allow for better traffic engineering.  They are Constraint Route Label Distribution Protocol (CR-LDP) and Resource Reservation Setup Protocol (RSVP-TE). In addition, the Open Shortest Path First (OSPF) routing protocol has undergone modifications to handle traffic engineering (OSPF-TE); however, it is not currently widely used.

Protocol	Routing	Traffic engineering
LDP	Implicit	NO
BGP	Implicit	NO
IS-IS	Implicit	NO
CR-LPD	Explicit	YES
RSVP-TE	Explicit	YES
OSPF-TE	Explicit	YES

Summary

In this article, we learned that one of several protocols could be used to dynamically program switches to build the cross-connect tables.  In the next article we will further explore the details and tradeoffs of the label distribution and signaling protocols.

Suggested URLs:

CD-LDP VS RSVP-TE   http://www.dataconnection.com/download/crldprsvp.pdf

George Mason University
   http://www.gmu.edu/news/release/mpls.html

Network Training
   http://www.globalknowledge.com/

MPLS Links Page
   http://www.rickgallaher.com/mplslinks.htm

MPLS Resource Center
   http://MPLSRC.COM

RSVP
   http://www.juniper.net/techcenter/techpapers/200006-08.html

Special thanks to:

I would like to thank Uyless Black, Susan Gallaher, and Amy Quinn for their assistance, reviewing, and editing.

A special thank you to all those who assisted me with information and research on the MPLSRC OP mail list, especially: Syed Ali, Adithya Bhat, Krishna Kishore, Irwin Lazar, Christopher Lewis, Vic Nowoslawski, Mario Puras, Mehdi Sif, and Geoff Zinderdine.

Rick Gallaher, CISSP, is owner of Dragonfly Associates LLC http://dragonfly-associates.com and author of  Rick Gallaher's MPLS Training Guide

Read More

Tutorial: An Introduction to MPLS

Rick Gallaher, CISSP, is owner of Dragonfly Associates LLC http://dragonfly-associates.com and author of  Rick Gallaher's MPLS Training Guide

September 10, 2001

In this article, we will examine how an MPLS network is constructed and how MPLS data flows.  In future MPLS Tutorials, we will examine:

• Introductory MPLS Label Distribution and Signaling
• Advanced MPLS Signaling
• MPLS Network Reliance and Recovery
• Traffic Engineering, MPLambdaS and GMPLS

In order to assist your further study, I have provided an acronym list and a list of related URLs to accompany each article.  

INTRODUCTION

What is this new protocol that leading telecommunication experts claim “will take over the world”?  Well, you can rest your worried mind – IP and ATM are not on death row.  In fact, it is my belief that MPLS will breathe new life into the marriage of IP and ATM.

The best way to describe the function of MPLS is by using an analogy of a large national firm with campuses located throughout the United States.  Each campus has a central mail-processing point through which mail is sent around the world, as well as to its other campuses.  Since its beginning, the mailroom has been under orders to send all intercampus correspondence via standard first-class mail.  The cost of this postage is calculated into the company’s operational budget.

KEY ACRONYMS
MPLS	Multiple Protocol Label Switching; also, Multiple Protocol Lambda Switching
LER	Label Edge Router
LSR	Label Switch Router
LIB	Label Information Base
LSP	Label Switch Path
FEC	Forward Equivalence Class; also, Functional Equivalent Class

 

MPLS HIGHLIGHTS MPLS allows for the marriage of IP to layer 2 technologies (such as ATM) by overlaying a protocol on top of IP networks.    Network routers equipped with special MPLS software process MPLS labels contained in the Shim Header.   Raw IP traffic is presented to the LER, where labels are pushed; these packets are forwarded over LSP to LSR where labels are swapped.   At the egress to the network, the LER removes the MPLS labels and marks the IP packets for delivery.    If traffic crosses several networks, it can be tunneled across the networks by using stacked labels.

However, for months now, some departments have been complaining that they require overnight delivery and package-tracking services.  As a manager, you set up a system to send three levels of mail between campuses – first class, priority, and express mail.  In order to offset the increased expense of the new services, you bill the departments that use these premium services at the regular USPS rate plus 10%.

Priority and express mail are processed by placing the package into a special envelope with a distinctive label.  These special packets with distinctive labels assure the package priority handling and tracking capability within the postal network.  In order to avoid slowdowns and bottlenecks, the postal facilities in the network created a system that uses sorting tables or sorting databases to expedite these special packets.  

The Construction of an MPLS Network

In an IP network, you can think of routers as post offices or postal sorting stations.  Without a means to mark, classify, and monitor mail, there would be no way to process different classes of mail.  In IP networks, you find a similar situation.  Figure 1 below shows a typical IP network with traffic having no specified route.

Figure 1: An IP Network

In order to designate different classes of service or service priorities, traffic must be marked with special labels as it enters the network.  Special routers called LER (Label Edge Routers) provide this labeling function (Figure 2).  The LER converts IP packets into MPLS packets, and MPLS packets into IP packets.  On the ingress side, the LER examines the incoming packet to determine whether the packet should be labeled.  A special database in the LER matches the destination address to the label.  An MPLS shim header (Figure 3) is attached and the packet is sent on its way.

Figure 2: IP Network with LERs and an IP packet with Shim header attached

To further explain the MPLS shim header, let's look at the OSI model.  Figure 3 (a) shows OSI layers layer 7 through layer 3 (L7-L3) in red and layer 2 (L2) in yellow.  When an IP packet (layers 2-7) is presented to the LER, it pushes the shim header (b) between layers 2 and 3.  Note that the shim header is neither a part of layer 2 or layer 3; however, it provides a means to relate both layer 2 and layer 3 information.

The Shim Header (c) consists of 32 bits in four parts – twenty bits are used for the label, three bits for experimental functions, one bit for stack function, and eight bits for time to live (TTL).  It allows for the marriage of ATM (a layer-2 protocol) and IP (a layer-3 protocol).

Figure 3: The MPLS Shim Header and Format

A shim header is a special header placed between layer two and layer 3 of the OSI model. The shim header contains the label used to forward the MPLS packets.

In order to route traffic across the network once labels have been attached, the non-edge routers serve as LSR (Label Switch Routers).  Note that these devices are still routers.  Packet analysis determines whether they serve as MPLS switches or routers.

The function of LSR is to examine incoming packets.  Providing that a label is present, the LSR will look up and follow the label instructions, and then forward the packet according to the instructions.  In general, the LSR performs a label swapping function.  Figure 4 shows LSR within a network. 

Figure 4: LSR (Label Switch Routers)

Paths are established between the LER and the LSR.  These paths are called LSP (Label Switch Paths).  The paths are designed for their traffic characteristics; as such, they are very similar to ATM path engineering.  The traffic-handling capability of each path is calculated.  These characteristics can include peak traffic load, inter-packet variation, and dropped packet percentage calculation.

Figure 5 shows the LSP established between MPLS-aware devices.  Because MPLS works as an overlay protocol to IP, the two protocols can co-exist in the same cloud without interference.

Figure 5: LSP (Label Switch Paths)

BRIEF REVIEW

To review the construction of an MPLS network, the LER adds and/or removes (pops or pushes) labels.  The LSR examines packets, swaps labels, and forwards packets, while the LSP are the pre-assigned, pre-engineered paths that MPLS packets could take.

Right about now, you may be asking whether the advantages of MPLS are worth the extra effort.  Consider for yourself:

Your company uses a database application that is intolerant of packet loss or jitter.  In order to ensure that your prime traffic will get through, you have secured a high-cost circuit, and you have over-provisioned the circuit by 60%.  In other words, you are sending all of your mail as “express mail” for $13.50.

With MPLS, you can have the LER sort your packets and place only your highest priority traffic on the most expensive circuits, while allowing your routine traffic to take other paths.  You have the ability to classify traffic in MPLS terms, and your LER sorts traffic into FECs (Forward Equivalence Classes).  Figure 6 shows the network now broken down into FECs.

Figure 6: An MPLS Network with Two FECs

Data Flow in an MPLS Network

The simplest form of data “flow” occurs when IP packets are presented to the ingress router (acting as the LER)

(Figure 7). 

Figure 7: Ingress LER Attaches a Shim Header

Much like the mail room that classifies mail to your branch location into routine, priority and overnight mail, the Label Edge Router classifies traffic. In MPLS, this classification process is called forward equivalence class, or FEC for short.

The LER are the big decision points. LER are responsible for classifying incoming IP traffic and relating the traffic to the appropriate label.  This traffic classification process is called the FEC (Forward Equivalence Class).

LER use several different modes to label traffic.  In the simplest example, the IP packets are “nailed up” to a label and an FEC using preprogrammed tables such as the example shown in Table 1.

Destination / IP	Port Number	FEC	Next Hop	Label	Instruction
199.50.5.1	80	B	x.x.x.x.	80	Push
199.50.5.1	443	A	y.y.y.y	17	Push
199.50.5.1	25	IP	z.z.z.z		(Do nothing; native IP)

Table 1: LER Instruction Set

When the MPLS packets leave the LER, they are destined for LSR where they are examined for the presence of labels.  The LSR looks to its forwarding table (called a Label Information Base [LIB] or a connectivity table) for instructions.  The LSR will swap labels according to the LIB instructions.  Table 2 shows an example of a Label Information Base.

Label/In	Port In	Label/Out	Port/Out	FEC	Instruction Next Hop
80	B	40	B	B	Swap
17	A	18	C	A	Swap

Table 2: A Label Switch Router’s Label Information Base (LIB)

Figure 8 demonstrates the LSR performing its label-swapping functions.

At the egress of the network, the LER removes the MPLS header and forwards the packet to an IP network.  Label swapping greatly simplifies MPLS packet flow.

The LER performs many packet analysis functions:  mapping layer 2 to MPLS; mapping MPLS to layer 3; and classifying traffic with great granularity.  In addition, the LER decides what traffic becomes an MPLS packet. One decision-making method is called “triggered mode.” Using this method, when a predetermined number of packets are addressed to a single location within a specified time window, the router will determine that there is a "traffic stream," and will reroute the stream of traffic for MPLS processing.

Even further enhancements and flexibility are available to MPLS by using the label-stacking method, as shown in figure 9.

Consider this scenario:  You own Network 1; however, your traffic must proceed across a network that is not owned by your company (Network 2). You must ensure that Network 2 handles your traffic according to your service-level agreements (SLA), but they are not using the same label criteria as your company. 

In this case, you would stack labels and build a tunnel across Network 2. This configuration would preserve the integrity of your network's labels while allowing the other network to operate independently.

Figure 9 Stacked Labels with Tunneled Network

IN SUMMARY

The concept of processing by labels is not new; it has been implemented successfully for the US Postal Service, Federal Express, and many other package-handling systems. In networking, this process has been used in Frame Relay and ATM. What is new is that the ubiquitous, uncontrolled Internet Protocol (IP) is now under a new set of rules where it can be classified, managed, and policed across any type of network.  

A nice feature about MPLS is that it is not a fork lift modification.  In some cases it only requires software modifications to existing IP routers.  For a fraction of the expense of installing a dedicated network, MPLS allows IP traffic to be classified, marked and policed while providing a method of layers two and layers 3 exchanging data.

MPLS does not replace IP – it supplements IP so that traffic and be marked, classified and policed.  With the use of MPLS, end-to-end quality of service can finally be achieved.

More on MPLS

The next MPLS Tutorial in our series: MPLS Label Distribution and Signaling

Rick Gallaher, CISSP, is owner of Dragonfly Associates LLC http://dragonfly-associates.com and author of  Rick Gallaher's MPLS Training Guide

Read More