MPLS
Multi-Protocol Label Switching
By Robert Nagy
Draft Date:12/13/2000
Final Paper will be available by Friday Dec. 15th
please send any comments to nagy@hawaii.edu
The purpose of this paper is to give an understanding of the emerging technology of MPLS. MPLS is a technology designed to improve upon and in some cases replace currently deployed Layer 3 packet forwarding. As an emerging technology, MPLS has many different entities are working on developing and implementing it. Because different hardware vendors are making choices to best suit their hardware, discrepancies in implementation still exist. This paper will focus on what the IETF working group on MPLS has proposed and what the theoretical implementations should be and not on vendor specific decisions wherever possible. To explain how this technology improves upon currently deployed systems, will require a basic understanding of how today’s Layer 3 forwarding operates. Section I will touch on some basic principles of Layer 3 packet forwarding and routing to establish a basis for discussing MPLS. This paper will not give a definitive explanation of Layer 3 forwarding and routing, but instead will touch on some basic concepts that will be expanded on to give an understanding of MPLS technologies. Section II will then show how MPLS operates by first touching on its current uses. This paper will then explain how the MPLS process happens and what the different options are for each stage. The paper will then look at how MPLS relates to IP, IP over ATM (IP/ATM) and mixed IP and ATM networks. To see how this technology improves on currently employed technologies the paper will examine how MPLS will impact Traffic Engineering, ATM/IP merging, and Virtual Private Networks (VPN).
For your convenience, there is a list of commonly used terms and acronyms at the end of this paper.
. (For the reader who has a solid background in IP forwarding you may want to skip ahead to Section II.)
SECTION I
In order to understand how packet forwarding takes place it is necessary to have a basic understanding of Layers 2 and 3 of the OSI model. After getting an understanding of theses Layers and the protocols associated with them, this section will cover the fundamentals of IP based routing and the protocols associated with it.
Layer 2 is the Data Link Layer. This layer is the format through which Layer 3 will forward its packets. Examples of this are Ethernet, Token Ring, 802.3, and FDDI. It will not have a huge impact on our choices for MPLS, but it is important to note that some Layer 2 protocols have different Maximum Transfer Units(MTU). This is the maximum number of bytes that may be put into one packet. We will see in Section II that this impacts the labeling of packets as there may be multiple MTUs along a given path, and the label itself can have an effect on the size of these packets.
Layer 3 is the Network Layer. It is the Layer at which routing decisions are made. Layer 3 includes addressing information and information on how the packet should be handled along the way. This will be the layer that MPLS will operate at and therefore most effect the implementation decisions of MPLS. There are two major schools of thought on how the Layer 3 protocol should act. These are split down an ideological barrier.
Connectionless
Service
The first ideology is to offer a connectionless service. This offers no guarantees of delivery, but is very efficient in terms of processor workload and bandwidth. Connectionless service is premised on the belief that reliability issues will be left up to Layer 4 and higher protocols. This means that the only thing a Layer 3 device does is accept a packet and forward it based on its destination address. IP is the protocol we look at when we examine connectionless Layer 3 service. It is the most widely used of any Layer 3 protocol.
Connection-Oriented Service
The other ideology is to have a connection-oriented service. This ideology is based around the idea that the network layer should be a more reliable level of service. Under this premise connections are established before any packets are forwarded, and then closed after transmission. This increased reliability does come at a cost. Creating a connection and closing it utilize both bandwidth and processing power. The technology that will be discussed from the connection-oriented ideology is Asynchronous Transfer Mode (ATM). ATM is a widely distributed technology that is found in many networks. It requires different hardware and speaks different protocols than IP. One of the main objectives of MPLS is to better integrate IP and ATM sections of a given network.
The other technology this paper will address, is passing IP over ATM. It is a little more complicated as it is a hybrid of both schools. In this technology IP views ATM as a Layer 2 protocol in that it is looking at ATM as a lower Layer. But to the network, ATM is still functioning as a Layer 3 protocol and it operates as such. It is important here to understand that from the perspective of the rest of the network and other routers that once the IP has been put into ATM, it is viewed as an ATM Layer 3 protocol until it is turned back into an IP packet(s) at the edge of the ATM section of a network or until it is delivered.
The second main issue that we need to explore is how paths are chosen within a network. The Internet itself is a series of networks that are all interconnected. Each network that is functional as its own network is called an Autonomous System (AS). The easiest way to explain the way routing choices are made is to split the task in two. First we look at how routing choices are made within the AS and then at how it is done between different Autonomous Systems.
Within an Autonomous system every router must speak a common routing algorithm. By using a common algorithm, all routers can fairly reliably compute tables that will allow proper packet forwarding. To make this truly reliable takes a little more work, but the details of that are not important to the concepts we will examine for MPLS. The process of passing information for the calculation of a common algorithm is called an Interior Gateway Protocol (IGP). The IGP spoken allows each router to build a routing database that is agreed upon by all the routers within the AS. The most commonly used of these protocols are OSPF, RIP, and IS-IS. For the purposes of this paper it will not matter which IGP is spoken. Once we have an IGP we have packet forwarding between the routers within the AS, now the question is how to get them from one AS to another.
The process of passing packets from one AS to another is called an Exterior Gateway Protocol (EGP). This is a very hard coded (as opposed to algorithmic) process that allows different AS to pass packets in a logical direction. The most common Protocol used for EGP is Border Gateway Protocol (BGP). The rest of this paper will refer to BGP when discussing EGP. This concept of Autonomous Systems and the division of routing computations is an important part of both MPLS’s advantages and limitations. It is important to understand that in traditional networks, routers internal to the AS, do need to compute BGP routes so that they understand which Edge Router they need to forward to for any given destination address outside of the AS. They will use IGP paths to get to it, but they need to know which edge to forward it to.
SECTION II
MPLS is currently used primarily by Tier-1 ISP’s for Traffic Engineering purposes in their core routers. MPLS can be thought of primarily as a tunneling mechanism that allows better management of core routers within an Autonomous System (AS). It takes the bulk of the workload to the edge of an AS, and frees up the internal routers. In MPLS edge routers are referred to as Label Edge Routers (LERs) and internal routers are referred to as Label Switch Routers (LSRs).(see diagram 1.1)
Figure 1.1
Because MPLS cannot currently cross between different AS it is primarily used to lighten and distribute the load within an AS. MPLS allows all the internal routers to speak only Internal Gateway Protocols (IGP). By removing the need for Border Gateway Protocol (BGP), you reduce the table size each internal router must maintain and remove the need for internal routers to recomputed their tables when the BGP is altered. This allows tier 1 ISP’s to alleviate a fair amount of workload from the internal routers. The other benefit that ISPs can realize is a more even distribution of packets over all routes within the AS. Because IGP paths often completely circumvent particular paths, MPLS can redistribute the traffic through the AS more evenly. To better understand how this is done, let’s look at the process of implementing MPLS into a network. There are many options within the process and we will look mainly at the ones that are not vendor specific.
The first step is to identify a set of packets with common attributes that will be forwarded in the same manner. This is called a Forward Equivalence Class (FEC). These packets can have IP destinations leading to the same egress router and possibly be limited to packets having similar Quality of Service (QoS) characteristics. QoS will be examined in more detail after we see how it is incorporated into MPLS. Once the FEC has been identified the next step in the process is the creation of Label Switch Paths (LSP). The Label Switch Path(‘s) is the route that all packets of a given FEC will travel in the MPLS environment. I bring up the option of multiple paths since, the option of having multiple LSPs for a given FEC would allow for load balancing. This is not currently implemented but is being looked at.
The process in which LSPs are created is called Label Distribution Protocol .The abbreviation (LDP) gets a little tricky here. It is often used in the context of Label Distribution Protocol, which refers to the overall distribution of Labels in general. Unfortunately it is also used to refer to a specific Label Distribution Protocol. I will use LDP to refer to the specific example of a Label Distribution Protocol. All of the Label Distribution Protocol signaling, that I will discuss runs over TCP and UDP. There are many options on how an LSP is created. Each having advantages and disadvantages in terms of convergence, number of control messages, and simplicity of set-up. The 3 major areas we need to decide on are: Solicitation method, Label retention, and Distribution control. All of these are choices one must make when setting up their LDP. It is not necessary to have each adjacency in the network make all of the same choices, but each two adjacent routers must agree on all three choices. LDP is not concerned with traffic engineering. It will assign LSP’s along IGP routes and will therefore follow the same path as non-Labeled packets. It will decrease the workload of the LSRs and will eliminate the need for them to keep BGP tables. I will introduce traffic engineering in the next two examples.
Looking first at Solicitation we identify 2 choices. We can use Downstream-on-Demand or Downstream-Unsolicited.
Downstream on Demand: operates on the principle that a Label is only issued to an upstream LSR when requested. If an upstream LSR requests a binding between a given FEC and a Label, and the downstream LSR recognizes that FEC and has a next hop for it then it requests a Label from it’s own downstream LSR. This process goes on until it reaches the appropriate LSR or the egress LER for that FEC. At which point that router binds a Label to the given FEC and returns a Label to its upstream LSR that issued the request. This process continues to cascade back to the ingress LER or the LSR that first requested the Label. It is important to note that each Label is
unique to each hop in the path of the LSP.
Downstream Unsolicited: A downstream LSR recognizes a FEC and sends a binding of a Label to a given FEC, to an adjacent upstream LSR. The upstream LSR inputs the label into its table, and is then able to use it to forward packets of that FEC. This happens for every LSR and LER.
The next choice in setting up a Label Switch Path is Label Retention. Label retention determines how long labels are saved in its table. We can use either Liberal Label Retention or Conservative Label Retention.
Liberal Label Retention: Means that a given router will keep Labels in its table that are from downstream routers other than its valid next hop for the given FEC. This can happen as a result of Downstream-Unsolicited label distribution or when IGP tables change due to changes in network topology. Resulting a new Label being added to the table for a given FEC.
Conservative Label Retention: The Conservative approach means that the router only maintains Label-FEC bindings from its current valid next hop. If IGP tables change and a new Label is bound to a FEC then the old Label-FEC binding is purged from the table.
The last choice we need to make is how to decide when Labels are created. This is called Distribution Control. The two main choices are Independent and Ordered.
Independent LSP Control: Each router makes its own decision to send a Label-FEC binding when it finds a next hop for that FEC. It does this based on its current IGP table.
Ordered LSP Control: a router only sends a Label-FEC binding if it is either the egress router for that FEC or if it receives a Label from a downstream router for that given FEC.
It is easy to see that there are trade offs for each choice. And the mix gets more complex as you mix and match. For instance, when you have Downstream-Unsolicited / Liberal Label Retention / Independent Distribution Control, and your network topology is subject to frequent changes, you will create relatively large tables and a large number of control messages but will have very quick convergence. Whereas if you have Downstream-on-Demand / Conservative Label Retention / Ordered Distribution Control you will have relatively slow convergence when changes in topology occur, but will have small table sizes and small number of control messages and Labels assigned. Each mix has its trade offs and it would be important to match the requirements of the network to be implemented with the choices you make.
The next two Label Distribution Protocols to look at are Constraint Based-LDP with Traffic Engineering (CR-LDP-TE) and ReSerVation Protocol for Traffic Engineering with Traffic Engineering (RSVP-TE). Both of these technologies build LSPs that incorporate traffic engineering functionality. They have more similarities than differences. They both operate in Downstream-on-Demand/Conservative Label Retention/Ordered Distribution Control. As mentioned earlier in this paper, this set of options is easier on resources but a little slower to converge during topology changes. Both allow for routes based on traffic engineering concerns and/or on QoS specifications. Both can have explicit routes set either strictly or loosely. Strict routes refer to paths where every router in the path is specified, and loose routes refer to paths where some of the intermediate routers are specified but paths between those are open. Both technologies require explicit set-up to define LSP requirements. The two technologies differ more in implementation then in functionality, with a few exceptions.
CR-LDP-TE Creates constraint based routes based on IGP information and on Type, Length, Value(TLV) messages that are used for the purposes of traffic engineering. There are 2 main TLVs added to CR-LDP. It is sufficient for the purposes of this paper to say that these operate as control messages that supply information on the hops that we are attempting to set up our LSP. In CR-LDP, the two messages being added are notification, and withdraw messages. These messages carry 8 different bandwidth parameters for the hop in question. With this information the network administrator can specify certain criteria that must be met for the LSP to be created. Some of the 8 parameters that can be used are minimum bandwidth, allowable delay, and relative share of bandwidth. By using these criteria and explicit routes the network manager can make decisions in setting up LSPs for any need. Whether it be to ensure prompt reliable packet delivery for a certain IP range, or to better distribute workload over all sections of the network.
RSVP-TE: runs over IP and uses messages from classic RSVP but adding new objects to them that add new information to allow for QoS decisions similar to CR-LDP. The first message is the Path message, which is used as a label request. The other is the Resv message, which is used for label mapping. In RSVP-TE the new objects are factored in to allow for traffic engineering in the same way as TLV messages were used in CR-LDP.
The few exceptions to their similarities in functionality are primarily in their impact on the network and their respective needs for messaging. Because the messaging structure for each of these protocols varies, the choice of protocol cannot help but impact the network in different ways. Because CR-LDP is a hard-state it does not need to have refresh message sent. That does however mean that LSP’s must be explicitly torn down, even when they are no longer valid. On the opposite end of the spectrum we have RSVP-TE, which is soft-state protocol. It therefore must have constant refresh messages flowing on the network, which utilize valuable bandwidth. It does mean that out of date LSP’s will automatically be destroyed at the first refresh message that shows it as invalid. Because we can reserve bandwidth for these LSPs this could also be detrimental to bandwidth usage.
Now that we have an understanding of how LSPs are created lets look at one of the more powerful tools that MPLS offers. This is the ability to create LSPs within LSPs. This is incredibly useful, especially when looked at in conjunction with bandwidth reservation. You have the power to engineer multiple FECs on the same intermediate path without losing their separate long range path. This is accomplished by creating a label stack. At the point where a packet being routed by one series of labels reaches an intermediate router with an LSP, it has a new label pushed on to the label stack. The packet is then routed through the intermediate LSP based on its top label. When it reaches the end of that LSP the outer label is popped off and MPLS routing continues based on the inner label. At the point where it reaches its bottom label it is then forwarded based on IP or ATM packet information.
Having an understanding of how FECs are forwarded through LSPs and how LSPs are created, lets look at how the labels are encapsulated into the packets. There are three ways that this is accomplished with IP and ATM. All rely on adding the 4-byte label stack entry to the packet headers (see Figure 1).
Figure 1.(graphic object here)
32 bits total size (20bits) (3bits) (1bit) (8bits)
Before examining at the components of the Label, we should consider its impact on the packet. Because we have increased the size of the packet by 32 bits (or 4 unsigned bytes), we need to examine its impact on Maximum Transmission Units (MTU). Maximum Transmission Unit is the largest frame that can be passed along a given hop. Because different hops will have different MTU limits its is necessary to understand that MPLS encapsulation can lead to a packet becoming larger than an allowable MTU for its path. One way this is overcome is the fact that many hosts today allow for IP MTU path discovery (RFC 1191). A host sends a packet with DF (do not fragment) set and relies on ICMP messages from subsequent routers to let it bring its MTU down to a small enough size. If the host does not utilize the MTU Path Discovery option then an LSR can fragment the packets(labeled or unlabeled) if the DF bit is not set or return an ICMP message if it is. This message will alert the source that it is sending packets that are too large. While this should resolve most problems it is important to note that these solutions do not cover all situations and more work will need to be done to deal with the issue of label encapsulation and MTU. Firewalls that do not allow ICMP messages through are just one example of how this process can fall apart.
Now looking at the different parts of the Label itself, we see 4 distinct parts.
Label is a 20-bit value showing the top most label.
Exp portion is 3 bits and is currently unused although , it was once intended to be used as a class of service field it has been left for future modifications.
S field is an indicator for bottom of Stack. It is set to 1 if the current label is the bottom of the stack and 0 otherwise.
-
TTL is the Time To Live and is 8 bits. It is decremented on a per hop basis like most technologies implementing TTL. This structure is used differently based on the type of network that MPLS is being implemented on.
In best effort networks such as Ethernet or 802.3, the label stack entry is placed as a shim header between the Layer 2 and Layer 3 headers. The label stack entry is created by the most upstream LSR or LER of the LSP. Then subsequent LSRs read the incoming label, look it up in their table, replace the label or push a new label onto the stack, and forward it according to their table.
IPoverATM (IP/ATM) on the other hand leads to a choice of implementations. One of the main shortcomings of ATM is that all routers need to be able to establish connections to every other router. This concept is called cross-connection. One of the goals of implementing MPLS across an ATM network is to minimize the number of cross connects and therefore reduce the control traffic that ATM creates. This will help with the problem of scalability in ATM networks. Because the number of cross connects grows at N2, where N is the number of routers in the AS, this is a major issue.
The first way to do Label encapsulation for ATM is with shim header much like we did in the case of Ethernet. In this case the VPI/VCI fields identify ATM VC, the LLC/SNAP field identifies the MPLS protocol and the ATM switches ignore the MPLS labels. This allows networks running both ATM and MPLS to utilize both technologies. This method does not solve the problem of ATM cross connects as the ATM portion of the network remains fundamentally unchanged. It does however allow a smoother flow between the ATM and pure IP (now MPLS) sections of a network. This technology was heavily used for the initial integration of MPLS into ATM networks, but is as of yet not officially documented. It is unlikely to be documented because most of the industry is moving away from it as MPLS is better understood and supported. The major exception to this that I have found is CISCO.
The technology that is replacing this method of label encapsulation in ATM is using the Virtual Path Interface (VPI) / Virtual Channel Interface (VCI) fields in the ATM header. This places the top most label(s) into the VPI/VCI fields in the ATM header. It can be one label in each field or one label across both fields. Either way the Label's S bit is set to 0. Subsequent labels are placed in a shim header with at least one entry and the bottom of the stack carrying a NULL value. This requires a modification to the hardware for it to know about MPLS. The advantage though is that you solve the exponential growth of cross connects. The concept of using your ATM switch as both an ATM router and an MPLS router simultaneously is called “Ships in the Night”. This allows a current ATM switch to have its control plane divided in two. One partition controls MPLS forwarding and the other controls ATM forwarding. For more detailed information on MPLS/ATM see
http://www.ietf.org/internet-drafts/draft-ietf-mpls-atm-04.txt
The last way that MPLS is beginning to impact the networking world is in the area of Virtual Private Networks(VPN). Because MPLS is such an efficient tunneling mechanism, it is ideal for VPNs. Because IP address are only used in determining FECS, an administrator of an AS can assign an LSP from the Ingress LER controlling one site of a business to the egress LER for another site of that business. This allows packets to cross from location to location without having to have real IP destinations. This allows you to maintain NAT or other private addressing schemes internal to our business. As long as all the traffic going to a certain address range are assigned to the FEC that corresponds to the MPLS tunnel to you’re other locations router, which also maintains the correct addressing. It essentially makes the AS you are crossing invisible to your internal routing choices. This is an area where MPLS is being utilized today. By controlling the guarantees offered on the LSP the AS (usually an ISP in this situation) can offer different grades of service and charge accordingly. This is a topic for a paper of its own, and is an exciting advancement. For more detailed information on MPLS and its use in VPN's see
http://www.ietf.org/internet-drafts/draft-kompella-mpls-l2vpn-02.txt
MPLS is coming onto the scene. Unlike many protocols that’s future is up for grabs, MPLS appears to be on track to have widespread usage. Its abilities to lighten the load for network cores, optimizing existing network links, and as a way to bridge existing ATM and IP hardware make an ideal standard to help with the issue of exponentially growing traffic across the internet. On both the theoretical and industrial sides MPLS is being constantly improved and fine-tuned. The IETF working group has continued to look at ways MPLS can be of increasing use. The two major developments that are looming on the horizon are bi-directional LSPs and MPLS across adjacent AS. These two functionalities will dramatically increase the scope of MPLS and its potential uses.
LIST OF MPLS TERMINOLOGY & COMMONLY USED ACRONYMS
FEC: Forward Equivalence Class. Refers to a group of packets sharing a common
attribute. This is usually the destination IP address directing it to the same
router. It can also refer to packets an engineer wants to give certain QoS
guarantees.
AS: Autonomous System: Is a network complete in and of itself, usually under one
entities control. It also usually shares routing protocols internally and a
separate protocol with the outside world.
LSP: Label Switched Path. This is the path set up within an Autonomous System that
packets of a given FEC will follow.
LER: Label Edge Router. Is an MPLS router at the edge of the AS. That talks both to
other routers in the AS, as well as to routers outside of the AS.
LSR: Label Switch Router: Refers to a Router within the AS that has connections
only to other routers within the AS.
LDP: Label Distribution Protocol. This is used in two ways. First to describe the process
of Labels being distributed down a path. It is used more frequently to describe a
specific methodology for distributing the labels.
Bibliography
PRESENTATIONS:
Presented by Bilel Jamoussi, Nortel Networks
Networld+InterOp Atlanta 2000
- Multiprotocol Label Switching(MPLS), Ilabs Tutorial
Presented by Jennifer Rasimas, Nortel Networks
Networld+InterOp Atlanta 2000
ON-LINE RESOURCES:
- IETF Working Group on MPLS
A Framework for Multiprotocol Label Switching
http://www.ietf.org/internet-drafts/draft-ietf-mpls-arch-07.txt
2. Light Reading- White Paper
TRAFFIC ENGINEERING WITH MPLS AND ATM
http://www.lightreading.com/document.asp?doc_id=613&page_number=5
3. TeleCommunications Online
IP + ATM = MPLS
http://www.telecoms-mag.com/issues/200002/tcs/ip.html
- IETF Working Group on MPLS
MPLS using LDP and ATM VC Switching
http://www.ietf.org/internet-drafts/draft-ietf-mpls-atm-04.txt
5. IETF Working Group on MPLS
Extensions to RSVP-TE for MPLS Path Protection
http://www.ietf.org/internet-drafts/draft-chang-mpls-rsvpte-path-protection-ext-00.txt
- MPLS Tutorial
By Peter Ashwood-Smith and Bilel Jamoussi
http://www.nanog.org/mtg-9905/ppt/mpls/