You may be interested in this book because you are a Network Engineer, a Network Planner or Architect, or other person thinking about deploying MPLS in your own network. You may find this book interesting if you are a technical manager or an engineer thinking of implementing the technology in your products. You might be a student who has volunteered your time and energy to study another tough subject. Or you may simply have heard of the technology and are interested in seeing where reading up on it might take you.

It is possible that a person might pick this book off of a shelf - either at a bookstore, or in a technical library - with out ever having heard of the technology, but it is not very likely. MPLS is, after all, yet another member of the new generation of four-letter acronyms (ATM having fairly demonstrated that the age of original three-letter acronyms has passed) and will - therefore - not be of urgent interest to someone who has not even heard of it.

Finally, at the time that I am writing this book, there are no reasonably up to date detailed technical books on the subject and yet there are a lot of questions and general interest in this exciting new technology. The fact that you've read this far, indicates that you are one of the many people with questions about this new technology.

Hence, unless you're still convinced that MPLS is the abbreviation for Minneapolis, the fact that you still have this book in front of you indicates that you are likely to be someone who should read it.
 
 

    Jhilmil Kochar
    Loa Andersson
    Muckai K Girish of SBC Technology Resources, Inc.
    Radia Perlman
    Randal T. Abler of the Georgia Institute of Technology
    Rob Blais of the University of New Hampshire InterOperability Lab
    Ron Bonica
    Ross W. Callon
    Thomas D. Nadeau of Cisco Systems, Inc.
    Tom Herbert
    Walt Wimer of Marconi Communications

Their efforts did much to encourage me and help to improve the readability and accuracy of the work.

I also wish to thank co-workers who offered encouragement and support throughout the time I spent working on the book. I particularly want to thank Barbara Fox, Pramod Kalyanasundaram and Vasanthi Thirumalai (then of Lucent Technologies) and people I worked with at Zaffire, including Fong Liaw, George Frank, John Yu and Michael Yao.

Nobody helped quite as much as those closest to me. I offer a very special thanks to the members of my family who bore with me during the many crunch periods.

Finally, I wish to acknowledge the help and patience of the staff at Addison Wesley Longman, in particular: Karen Gettman, Mary Hart, Emily Frey and Marcy Barnes.

The most important example of a routing problem MPLS deals with today is Traffic Engineering. Traffic Engineering is the approach network operators typically use to equalize traffic loads across all devices in their network. Traffic Engineering may be done more easily using MPLS than it was being done previously.

The second most important routing problem that MPLS offers a solution to is support for Virtual Private Networks. MPLS may be used in a number of ways to provide for tunneling private network traffic across a public or backbone infrastructure.

The simplicity of the forwarding process offered by MPLS, however, makes it highly likely that there will be other - perhaps more important - applications for this technology in the future. In general, if one of the alternatives that is being considered in solving a network (or routing) problem is using a packet tunneling approach, MPLS is likely to be a useful solution for that problem.

I intended for this book to be a self-contained reference for MPLS technology. However, MPLS as a technology interacts with a large number of other technologies. Included in these interactions are various routing protocols, link-layer and - in theory at least - network layer technologies. I do not, for example, describe in this book the specifics of individual routing protocols except as they directly relate to MPLS. There are many good reference books on routing, network and link layer technologies.

This book provides an overview of the various technologies that led to the development of MPLS. A relatively high-level summary of the history of the development process is useful in understanding some of the choices made in that process. However, the goal in this book is to make the protocol itself understandable, so the focus is on the protocol details that resulted from the process of merging the various proposals; it does not perform a detailed analysis and comparison of each one. There are already books that do a good job of comparing at least the early proposals.

I based the material in this book on publicly available information. Statements made in this book can be verified by anyone wishing to do so. Of course, not all of the public information is consistent. In particular, for several topics that are completely unavoidable in a serious attempt to talk about label switching, it is not actually possible to distill a common conclusion from the available information - or, at least, it is not possible to do so objectively. Information presented by the various participants often contains obscure references to information that might or might not be well known - even if not publicly available - and was often starkly at odds with related information provided by others. An example of this would be the continuing debate over which signaling protocol is most useful under what circumstances.

Consequently, the goal of trying to make the multi-protocol label switching technology easily understandable (or - at least - more easily understandable) is slightly at odds with the goal of being fair and objective in discussing the results of the development of the technology standard. Too much fairness and objectivity would result in too much ambiguity.

I hope I've done a reasonably good job of achieving the understandability goal without compromising too much on fairness and objectivity.

As another example, I have used footnotes extensively. My hope - in so doing - is to make it possible for a reader to simply ignore the footnotes if they are not interested in a background or sidebar discussion, or where a particular comment or observation came from. Using footnotes in this way allows many readers somewhat greater ease in following the flow of the ideas being discussed. I know that some people are incapable of ignoring footnotes and other references and - for those people - I offer my heartfelt sympathy.

I have also tried to organize the chapters in such a way as to let each stand on its own in addressing a particular subset of MPLS functionality that might be of interest to people who are not as interested in other chapters. For example, people who are not interested in the history of MPLS, may skip chapter 2 entirely with little loss in understanding of - say - usefulness of MPLS for a specific network application. Of course, there will be people who are interested in all aspects of the technology, and - for those people - it is necessary to provide references that tie all of the pieces together. Therefore, I have set out with the dual goal of:

• making each chapter an integral whole and
• providing cross references to tie all of the material together for those people who are interested in the whole picture.

Chapter 1 describes the basics of the technology, using examples and providing an overview of the technical details. The main concepts discussed include what label switching and label swapping are and how they compare to routing, and what is required to signal labels.

Chapter 2 goes through the evolutionary process in which these revolutionary concepts developed. This brief history starts with a prehistory that touches on some of the problems people were trying to solve, some of the earlier proposals to deal with those problems and the way in which the problems themselves were evolving. Then the Chapter discusses the major proposals that actually drove the industry to develop one standard solution. Finally, the chapter provides a summary of the process of getting the standard to where it is now. Throughout this chapter, I provide time-lines and other charts in an effort to show how various efforts influenced each other.

Chapters 3, 4 and 5 take the reader a little closer to the technology and its relationship to the networking world. Chapter 3 explains how MPLS must interact with routing and the network and link layers in order to provide forwarding services at least as good as those that currently exist and the benefits MPLS is expected to provide within this framework. Chapter 4 details MPLS system architecture, including components, functions and operating modes. Chapter 5 shows where specific MPLS encapsulation and signaling approaches are most applicable. These chapters provide the ground work for more detailed discussion in the remaining chapters.

Chapter 6 provides detailed comparisons of MPLS and alternative approaches to solving the same problems. The reader should find out in this chapter how MPLS differs from other approaches and what the benefits are in using MPLS. In providing detailed comparison of alternatives, chapter 6 also shows how MPLS is supported over various technologies, including ATM, Frame Relay, Packet-On-SONET (POS) and Ethernet.

Finally Chapter 7 describes how services - such as QoS, Traffic Engineering and Virtual Private Networks - may be supported using MPLS.

Chapters 1-5 provide an overview of the technology while chapters 6 and 7 dig into the details.

Finally, an extensive glossary is provided with both acronym expansions and definitions of terms and phrases used in this book.

Currently, the two most important uses of MPLS are Traffic Engineering and Virtual Private Networks (in order of current importance). Although both can and are done currently using existing standard protocols, MPLS makes this simpler because it possible to take advantage of the separation of routing and forwarding to reduce or eliminate some of the limitations of routing.

In Traffic Engineering, for example, it is possible to specify explicit routes during the process of setting up a path such that data may be re-routed around network hot spots. Network hot spots (congestion points) develop as a result of the fact that routing tends to converge on selection of a single least cost path to each possible (aggregate) destination. Using an explicit route to direct significant portions of this traffic to parts of the network that are not selected by the routing process allows packets to bypass network trouble spots by (partially) ignoring routing.

It is also relatively simple to establish MPLS tunnels to allow transport of packets that would not otherwise be correctly routed across a backbone network - as is often necessary in support of Virtual Private Networks. A network operator can use MPLS to tunnel packets across their backbone between VPN sites making address translation and more costly tunneling approaches unnecessary.

MPLS is potentially useful for other applications. For example, MPLS is likely to be fully supported on Linux platforms used at small ISPs, businesses and residences to provide network access for multiple computers. Use of MPLS in forwarding packets using a software router may make a noticeable difference in the performance of the host being used as a router - for example allowing the Linux station to be used for network management, administrative and accounting applications and other purposes (such as playing Civilization or Pod Racer).

MPLS does not represent a merger of the link and network layers. Instead, MPLS interacts with both in a role as the arbitrator of layer two and layer three technologies. MPLS defines an encapsulation that resides between the network layer and link layer encapsulations, but - in some cases - it also defines values for significant field positions in the link layer encapsulation itself. This is the case for ATM and Frame Relay, for example. Thus the desirable features of link layer behavior may be achieved by:

• assigning values to fields in the link layer encapsulation (VPI/VCI or DLCI, for example),
• using a shim layer encapsulation residing between the link layer and network layer encapsulations or
• embedding a fixed length value within the network layer encapsulation.

MPLS is not expected to be an end-to-end solution. There is relatively little to gain from having host involvement in MPLS label allocation and use. In addition, MPLS scalability depends in part on limiting the scope of MPLS domains. Merging of labels becomes essential as the size of an MPLS domain increases and yet merging cannot extend all the way to end points - unless, for example, there is only one receiver for traffic in the Internet. Finally, use of labels in forwarding implies a strong trust relationship between systems allocating labels and other systems using them. Things being the way they are, that level of trust relationship does not currently exist end-to-end in the Internet.

Basic MPLS concepts expanded on in the first chapters are as follows:

• Use of fixed length labels to represent arbitrary information about packets. This might be information normally included with the packet, or it might be information known about a stream of packets that would not normally be included with each packet.
• A label is used to locally represent forwarding of packets.
• This fixed length label representation of forwarding information simplifies decisions based on use an exact match algorithm. This simplified forwarding paradigm is called label switching.
• A router that participates in label switching is a Label Switching Router (LSR).
• Labels are added at an MPLS ingress point, swapped at intermediate LSRs and removed at an MPLS egress point. The path along which this occurs for any particular starting label is called a Label Switched Path (LSP).

1.1 - Label Switching

Switching

Of course, the lead car may use an arbitrarily complex code. The code may include where each car came from, where it is going, what it contains and how it is to be routed at each switching station. It may also describe who owns each item contained and whether or not those items have been inspected, have cleared customs or are insured. I'm sure you get the idea.

Much of this information may be needed if each switching station has to make an independent routing decision. For example, if there are goods on board that have not cleared customs, or otherwise been inspected, it is possible that some switching stations may be required to divert the railway cars to a location where this can take place. However, for more mundane railway cars and at many switching stations, the routing options are not so complicated and it is likely that many similar trains can be grouped into a class in which all class members are switched in the same way.

In fact, such a switching system can realize substantial savings in storage if it stores exactly that information about each class that it needs to identify members of that class. The system then determines class membership by examining the code provided by the lead car and searching for a "best fit" among the routing information it has stored.

To understand why this may be important, imagine that the automated switching system supports well over a hundred million (10⁸) railway terminal stations. That would mean that storing routing information based solely on source and destination would require over 10¹⁶ route entries. Additional information that might be required to identify an individual route would further compound this complexity.

However, performing a "best fit" (or longest match, in routing parlance) search at every switching station and for every set of railway cars has its own costs. The code used by the lead car must be successively compared with code fragments (following a decision tree) looking for the first point at which it does not match a code fragment on any sub-branch (of the decision tree). In practical usage, multiple comparisons are required in every case.

To put this cost in perspective, imagine that I'm thinking of upgrading the automated switching system such that it can switch 20 million cars a second and I don't want to have cars side-tracked for an appreciable amount of time at every station.

In this case, I would want to reduce the time it takes to match the code for the lead car with a routing entry by as much as possible. One way to do that would be to replace the complex code we've been using with a shorter one that exactly matches a code associated with an individual route entry at each switching station. This is, in essence, what MPLS does.

Let's examine this analogy now and see how it compares to the general concept of routing and switching data packets.

In the analogy:

• switching stations compare to routers and switches,
• trains compare to data packets and
• tracks compare to links and interfaces.

Most network layer data packets are pretty mundane, however, and are routed based on a network layer destination address at most network devices. This is a good thing because there are something like 100 million IP end stations in the Internet and thus there is a need to be able to group destination addresses into classes.

Aggregating route information using destination-based routing produces forwarding classes based on a network layer address prefix. Because not all prefixes will be the same length, routing decisions are typically based on a longest match ("best fit") algorithm. The need to perform multiple comparisons establishes the maximum speed at which routing decisions can be made and thus sets the maximum rate at which a given routing device can forward packets, for any particular device's processing speed.

The maximum speed at which I can forward packets determines the efficiency of my utilization of a particular line speed. For example, if my interface line speed is roughly 2.5 gigabits/second (corresponding to OC-48 SONET) and my packet size distribution is 64/200/1500 (minimum/average/maximum) bytes/packet, I can compute the approximate required packet-processing speed (for ~100 % utilization) as follows:

If I now want to introduce 10 gigabit/second line rates (corresponding to OC-192) into my network, I need to be able to increase my packet-processing rate to roughly 20 million packets per second (in order to handle a continuous stream of minimal packets).

In order to distinguish between forwarding based on longest match and forwarding based on exact match, many people refer to the former as routing and the latter as switching. That is a key distinction in the way I use these terms in this book.

This comparison is useful to many people who are familiar with the differences in complexity in bridging and routing because it can help them to understand advantages that switching has to offer in comparison to routing.

In addition, there are technologies that have always been referred to as switching - for example, circuit-switching, ATM and Frame Relay. People familiar with these switching technologies generally associate switching with the idea of higher forwarding speeds. The higher forwarding speeds these technologies offer are, at least in part, due to the simplified forwarding made possible by using an exact match on a fixed length field. Unlike bridging and some other switching technologies, however, ATM and Frame Relay may exchange the values on which forwarding is based. For example, a Frame Relay DLCI is used in conjunction with an input interface to determine both the output interface and the new DLCI.

If a network device is able consistently to make forwarding decisions based on well-known bit positions in message headers, the process of making the decision is very simple. This is true regardless of the header to which this applies (whether it is a layer 2, layer 3 or higher layer). Values in these bit positions may be used as a control word that sets up a temporary channel from the interface on which the packet was received to the interface on which the packet is to be re-transmitted - thus switching the packet. A common approach for doing this is through the use of content addressable memory - the significant header data is used to access a data-record in high-speed memory that is then used to switch the data to the appropriate output interface. The data-record may also include replacement header information.

Switching is based on the ability to consistently determine how to forward packets from well-known bit positions in message headers.

Forwarding Complexity

Prior to the introduction of MPLS (and related proposals), the forwarding decision was a great deal more complicated for routing than it was for any switching technology. From the earliest generations, routers have been tasked with dealing with multiple paths across a network and, over time, multiple network layers and corresponding packet formats. Routing is also required to provide access to the global Internet (Internet) - i.e. to act as a gateway between a private network (intranet) and any and all other networks (extranets) - including the Internet. The Internet is orders of magnitude larger and more complicated than any currently existing bridged network segment.

Of course, there is a direct relationship between complexity of any task and the cost of acquiring and maintaining the equipment necessary in performing the task, i.e. -

From this, we can make an inference about the relative costs of bridging (or switching) and analogous routing functions. If the complexity of a routing function is orders of magnitude greater than the complexity of a bridging function, then the cost of the routing function (in terms of initial outlay and continuing operating costs) should be orders of magnitude greater than the cost of an analogous bridging function. That this is not always reflected in equipment prices is a fact that is attributable to at least some of the following factors:

• equipment manufacturers use proprietary techniques to eliminate as much of the additional complexity as possible,
• the cost of routing, bridging and switching functions is only a part of the total cost of the devices used to provide these functions and
• part of the initial outlay may be hidden in indirect expenses relating to the cost of maintenance agreements, service contracts and upgrades.

Hence, routers and routing protocols have evolved - and continue to evolve - mechanisms for continuing to forward data. Most such mechanisms are based on using distributed route computation. At any given instance in time, a router is likely to believe it knows the right thing to do with a packet (thus avoiding dropping it as much as possible). However the "right thing to do" (as determined using route table information) is:

• subject to change and
• a result of information that may not be in synchronization with that being used by other network devices making similar forwarding decisions for the same packets in the same network.

Since it is possible that the information used to make forwarding decisions is not consistent at all routers in any portion of the network, it is certain that data packets may take the wrong path and even loop. Some part of the forwarding decision process must be to determine if data is looping too much (consuming too many network resources) - and this typically is done on a packet by packet basis (using TTL for example).

Routing technologies, consequently, rely on loop mitigation approaches. Use of TTL, for example, prevents packets from consuming more than a fixed amount of network resources (on a per-packet basis that is).

Switching technologies construct a simplified network topology that restricts the paths available for forwarding thus making looping impossible. Prior to constructing (or restricting) forwarding paths, switching technologies typically do not forward data packets. Consequently, a transient in a switched network will usually result in a total loss of use of the network until the new topology is completely determined.

Bridging technologies, for example, use the spanning tree algorithm to construct a connected, loop free, forwarding tree. This is accomplished by disabling forwarding using certain interfaces at each bridge. Hence, looping data is avoided by choosing not to use some network resources.

Other switching technologies use a connection-oriented approach based on virtual circuits that are similarly loop free. Consequently, switches do not have to check to see if packets are looping since packets follow a path that has been determined to be loop free during the setup process. Use of virtual circuits does not necessarily guarantee equal use of network resources, however, and it is disruptive to move a virtual circuit from one path to another in an attempt to redistribute traffic.

Routers generally attempt to detect that a loop exists during the process of forwarding data, while switches generally attempt to eliminate loops prior to forwarding data.

Until very recently, routers in enterprise (private) networks were required to support several network (or higher) layer protocols. In particular, IPv4, IPX and Appletalk were in use in many corporate networks. Recent trends have been toward exclusive use of IPv4. Ideally, all networks would eventually switch to exclusive use of IPv4, however, IPv6 is looming on the horizon.

One solution used in the past relied on a simplistic optimization approach - optimize for the dominant (or normal) case only. This meant that forwarding of IPv4 packets, with no IP options in use, would be optimized while forwarding of other network layer packets, or IP packets with options specified, might be performed in a substantially sub-optimal way. Because of the possibility of network layer transitioning from IPv4 to IPv6 at some point in the future it is very likely that many routers will need to support both versions of the Internet Protocol. Consequently, people who build routers are less willing to assume that it is sufficient to optimize packet processing for only one network layer protocol.

An efficient switching solution to the problem of having a variety of network layer protocols is to perform a forwarding decision on the basis of information that is not dependent on the network layer - at least on a per-packet basis. For instance, switches that use virtual circuits can establish virtual circuits for the purpose of switching specific sets of network layer packets along a path. If the path is determined during virtual circuit setup, using the same route determination process that would otherwise be applied on a per-packet basis, then these switches only need optimize the process of forwarding along the virtual circuit. The actual forwarding process is thus independent of the network layer used in making a route determination.

Routers decide how to forward each packet by determining the route for the packet from the L3 (network layer) header and the router's route table. Switches decide how to forward each packet using a function that is separate from the process of determining the route for packets having any particular L3 header.

In addition, routers frequently serve as "gateways" between network domains - imposing filtering, security and other complicating factors on the already complex routing task. The gateway function is an essential part of access to the Internet.

The additional complexity associated with domain boundaries affects both the process of forwarding data and the process of computing routes. Data forwarding is impacted since filtering, address translation or header manipulation impose requirements to look more closely at the packets being forwarded. The process of computing routes is affected because the information shared across domain boundaries by routing protocols may be limited by policy considerations or limitations in the ability to import routes and these limitations may lead to inaccurate data affecting route computation.

The net effect of the combination of these two complicating factors is that it is possible for the policies affecting forwarding and route computation to be inconsistent. This increases the likelihood of incorrectly forwarding data packets - leading to packet loss and potentially lost network connectivity.

A New Switching Paradigm

Switching technologies such as Frame Relay and ATM had a significant impact on the distinction between bridging and routing. ATM, for example, uses routing for Virtual Circuit (VC) setup and switching of actual data packets. These switching technologies represented the first industry-wide attempt to uniformly separate route determination from forwarding in data networks.

The general approach, suggested by the ATM specific paradigm, is to use routing protocol exchanges, router configuration information and routing decisions to setup virtual connections for streams of data. In the MPLS analog, a virtual connection for a specific data stream is established across some subset of network devices based on the routing decisions these devices would make for the actual data in those streams. Labels corresponding to ATM Virtual Path and Channel Identifiers (VPI/VCI or VPCI) locally identify the virtual connection. Once a virtual connection is thus established, the data packets may be forwarded based on the labels assigned - allowing for a high-speed forwarding implementation similar to ATM.

Unlike ATM, however, the label-switching approach is generally applicable to a number of network technologies, does not always require fragmentation of data packets into cells and allows direct use of native routing information and technology. Label Switching is the process of making a simplified forwarding decision based on a fixed length label and this label can be included in a Frame Relay DLCI, an ATM VPI/VCI or at the head of an MPLS shim header in other technologies.

1.2 - Label Swapping

Not all switching technologies modify the value used in making a forwarding decision. Circuit switching (for example, in voice telephony) and transparent bridging (in data networking) are instances that do not modify the value used to decide how to forward information. The trouble with approaches like these is that the values used have to be established as unique for all members of a network using this common technology. In other words, the labels used are more than locally significant.

Label Switching relies on Label Swapping to preserve the local significance of a label. In addition to enabling the switching function, the label in a label-encapsulated data packet received on an input interface is used to determine the label that will be used in transmitting the altered data packet on an output interface. This is highly analogous to VPI/VCI switching in ATM, for example, in which the input interface and VPI/VCI determines the output interface and VPI/VCI. Local significance is important in reducing the complexity of the process of negotiating labels since it is only necessary to know that the label is locally unique and the label does not have any non-local meaning.

In addition to possibly swapping the input label with an output label, one or more labels may be popped from the label stack of the received data packet and one or more labels may be pushed on to the label stack for the packet to be transmitted. In fact, label swapping itself may be logically generalized as the degenerate case of a pop (one or more labels) and push (one or more labels) in which exactly one label is popped and exactly one pushed. Pushing and popping of labels (adding/removing one or more labels) is discussed in greater detail in the Label Stack Manipulation portion of section 4.2 - MPLS System Functions.

Label swapping effectively establishes the Label Switching Router (AKA Label Switch Router or LSR) as a media end-point, defining the local scope of the label being swapped and, thus, the domain within which the label is significant and must be unique. This limitation in the scope of a label greatly increases the scalability of label switching since any label need only be unique between the LSR that allocates it and the LSR that prepends it to a packet.

1.3 - Signaling Labels

The significance of a label received at an input interface is that it is used to:

• determine what output interface will be used, if any, in forwarding data,
• determine what label operations (push, pop, swap) are to be performed and
• determine what label is to be used on transmission at the output interface.

Although the significance of a label might be established via configuration (or provisioning), this will prove to be an onerous task if large numbers of Label Switched Paths (LSPs) are required. In addition, this will not allow for the dynamic changes in routes currently supported in routed networks. Finally, as the amount of configuration increases, the probability of configuration error approaches certainty.

Consequently, label switching requires mechanisms for signaling, or distributing, labels within a domain of label significance. In general, LSRs that share knowledge of the significance of a set of labels are adjacent - at least within the context of the signaling mechanisms used to distribute those labels. These mechanisms must ensure that label significance is consistent both among various adjacent LSRs and with respect to each label's meaning at each LSR.

Consistency relative to a label's meaning is slightly different from simply keeping each adjacent LSR on the same page with label and forwarding information. The information used by the routing function at each LSR is subject to constant change - not only in terms of how a particular stream of data is forwarded, but also in terms of whether or not a particular message is part of that stream. Because of this it is necessary that adjacent LSRs be able to negotiate more or less labels as needed to support changing forwarding requirements.

An example of this is when routes are aggregated and the aggregate is associated with a single label. If a subset of the routes thus aggregated subsequently change (such that they diverge from the remaining routes associated with the aggregate label), the LSRs will need to negotiate one or more new labels.

The simplest way to ensure that any label is consistent among adjacent LSRs and consistent with its meaning relative to specific forwarding, is to piggy-back the labels being distributed using the same messages the routing function at each LSR uses to establish forwarding. In order to piggyback labels, however, it is necessary that forwarding information be shared between routers via protocols meeting these conditions:

• the protocol consists of message exchanges between adjacent protocol peers;
• there is an exact mapping between effectively adjacent peers with respect to the protocol itself and adjacent LSRs within the label switching context among all adjacent LSRs;

To illustrate the first point, imagine a protocol consisting of message exchanges between LSRs that may or may not be adjacent. Labels attached to such messages will not be useful in cases where the LSRs are not adjacent as the label negotiated in this way will need to be interpreted or assigned by devices not participating in the negotiation.

Note that the adjacency here is in terms of how the labeled messages are transported from one LSR to another. If the labeled packets are L2 encapsulated, the presence of one or more transparent bridges between two LSRs does not affect their adjacency. In the same way, an LSP may be used to provide adjacency, as may any of several other tunneling approaches which allow transparent packet transport.

In Figure 2 above, if LSRs 2, 3 and 4 are using protocol XYZ and LSR 1 is not, protocol XYZ cannot be used to piggy-back labels between LSRs 2 and 4 unless a more direct adjacency is established between these two devices.

Similarly, there must be a contextual mapping between the logically adjacent peers in both the piggyback protocol candidate and MPLS contexts. If routers are adjacent with respect to a piggy-back candidate protocol but not adjacent with respect to MPLS, the labels which might be piggy-backed on the candidate protocol would be meaningless in the MPLS context since intervening LSRs would be unable to interpret (and properly forward packets using) these labels. In the same way, adjacent LSRs can only piggyback label distribution on protocols in which all adjacent LSRs participate and are logically adjacent. Otherwise, some of the adjacent LSRs would not be aware of the labels being distributed.

Let's use BGP as an example to illustrate this. Labels may be negotiated using BGP messages to piggy-back label assignments from one BGP peer to another. But for these labels to be useful, the peers participating in the negotiation must be either physically adjacent, or they must be logically adjacent via an LSP between them. If they are not directly adjacent, and there is not a continuous LSP between them, any labels negotiated between them will have no meaning at some point between the two peers. In this example, two adjacent BGP speakers are not logically adjacent LSRs.

The protocol being considered as a candidate for piggy-back distribution of MPLS labels should have defined mechanisms or protocol extensions to allow the labels to be transported via intervening devices in the event that protocol peers are not physically adjacent. It would not do, for instance, if the messages carrying MPLS labels were being discarded as incompatible with the base protocol in intermediate systems.

Protocol extensions used to carry labels must be defined for carrying the appropriate type of label as well. For example, a candidate piggy-back protocol needs to be able to include an ATM VPI/VCI in order to establish LSPs for use with ATM links.

Under circumstances in which no candidate protocol for piggyback distribution exists and is acceptable, labels must be distributed using a protocol specifically provided for that purpose. A specific label distribution protocol is also needed to permit negotiation of label parameters and provide ACK/NAK responses to label assignments where piggy-back protocols do not themselves provide mechanisms for doing these things.

What MPLS buys us is the ability to make a routing decision one time and a series of switching decisions along an LSP.
 
 

In the simplest case, this is what MPLS allows routers to do - via signaling.

1.4 - References

[3^rd Computer Networks] - Third Edition, Computer Networks, Andrew S. Tanenbaum, Prentice Hall, 1996.

[BGP REFLECTORS] - BGP Route Reflection An alternative to full mesh IBGP, Tony Bates and Ravishanker Chandrasekeran, RFC 1966

[Interconnections] - Interconnections, Bridges and Routers, Radia Perlman, Addison Wesley, 1992.

[MPLS-Drafts] - Various, http://www.ietf.cnri.reston.va.us/ids.by.wg/mpls.html

[OSI] - OSI, A Model for Computer Communications Standards, Uyless Black, Prentice Hall, 1991.

[OSPF] - OSPF, Anatomy of an Internet Routing Protocol, John T. Moy, Addison Wesley Longman, 1998

[SONET] - SONET/SDH - A Sourcebook of Synchronous Networking, C. Siller and M. Shafi, editors, IEEE Press, 1996.

A thorough discussion of a technology is not truly complete without at least a summary of the history that went into making it. However, this chapter is essentially parenthetical. If you are not interested in the history of MPLS and how it developed out of a miasma of related technologies, skipping this chapter entirely will not prevent you from understanding the remaining chapters of this book.

2.1 - Early Notions

In retrospect, there were disconnects in the process of defining both Switched Virtual Circuits (SVCs) and Traffic Management in ATM and the possibility of using these services in IP. These disconnects are not hard to understand for those people who were involved in the process. They were largely because of changes in market and product development directions stemming from the chaotic influence of market feedback. Similar feedback processes were involved in the standardization process as well. Where things ended up is not where things looked like they were going to end up at various stages in the process.

LAN Emulation

For example, LAN Emulation ([LANE]) was developed because of a then widespread belief that ATM to the desktop was the future technology direction. LANE defined a client-server architecture and service implementation to support use of ATM switches in a bridged network. Focus for LANE was on interworking with the dominant L2 technologies - specifically IEEE standards 802.5 (Token Ring) and 802.3 (nearly identical to, and usually thought to include, Ethernet) - in order to support L2 technologies generally. Work in developing LANE was coordinated with continuing efforts in the IEEE through the occasionally heroic efforts of people participating in both efforts.

Multi-Protocol Over ATM

Multi-Protocol Over ATM (MPOA) was developed in turn as an effort to extend the thinking (if not at all times the technology) used in developing LANE to be useful in a routed ATM network. MPOA also defined a client-server architecture and service implementation - however MPOA applies to routing in all-ATM networks. MPOA focused on use of the Next Hop Resolution Protocol (NHRP), then being defined in the IETF working group Routing Over Large Clouds (ROLC). NHRP was intended to solve some of the problems then known to exist with Classical IP and ARP over ATM (CLIP) and - for this reason - was regarded by some to be the next generation CLIP version. Work in developing MPOA was coordinated with ongoing efforts in the IETF in the same way that similar coordination occurred in LANE.

While MPOA represented a major attempt to reconcile differences between what had developed as two separate routing models, one for ATM and one for IP, its proponents were not at all in agreement about what the target model should be. Many people saw that the NHRP architecture offered a well understood way to separate the route determination and forwarding functions, but the effort within the MPOA was split on how best to take advantage of this. Part of the effort centered around use of NHRP's client-server architecture to develop a virtual router architecture while part of the effort centered around trying to define extensions to the NHRP protocol specific to ATM that would allow ATM-native traffic management features to be used in forwarding IP packets.

Of course, if the routing overhead in any particular implementation is negligible, this aspect of the use of NHRP (and, consequently, MPOA) is not as important. However, implementations in which this was the case tended to be regarded as either largely theoretical or prohibitively expensive at the time these considerations were being made.

The value of this approach is sensitive to the number of ATM switches that are not also routers. Obviously, if every ATM switch is a router, then there will be no mismatch between ATM physical connectivity and the routing topology. If only one out of every ten ATM switches is also a router, then some degree of topological mismatch may be unavoidable. At the time these things were being considered, it was generally accepted that adding routing function to every ATM switch would be expensive - especially if one is trying to avoid the routing overhead at the same time.

NHRP - by itself - does nothing to address this problem. Unless the protocol's usage is restricted in some way, NHRP cannot provide connectivity between ATM end-stations in a cloud larger than was the case with a LIS in CLIP. Thus NHRP (and MPOA) is effective only when it is used to establish connectivity to a restricted subset of all end-stations in any one ATM cloud. Such a restriction could be based on whether or not the connection is associated with some level of service assurance, whether or not there is a topological mismatch associated with the normally routed path, or both.

Neither the ROLC group (and its successor - ION) nor the MPOA working group embarked on an effort to define signaling mechanisms and mappings between either IntServ or DiffServ like Quality of Service (QoS) and ATM signaling parameters. This effort was the responsibility of the corresponding work groups within the IETF. While a lot has been done in this area to date, the lack of progress at the time that NHRP was approaching becoming a Proposed Standard in the IETF made it hard for implementers to provide for inclusion of QoS parameters in NHRP messages.

Another issue with CLIP was the delay caused by the need to perform address resolution in order to determine the address of the ATM local destination for any particular IP destination address. This issue exists also when using NHRP - and is potentially worse because resolution requests may be forwarded multiple hops before an appropriate address resolution response can be returned. Implementations that attempt to compensate for this factor by "learning" ATM address associations would interfere with the efficacy of those implementations trying to restrict ATM connectivity.

Cell Switching Router

The routing decision on a per-packet basis can be avoided - in ATM switches - if there is some way to associate the input interface and VPI/VCI of ATM cells received with output interface and VPI/VCI to be used on forwarding them. Typically this cannot be done in any interesting ATM switch router because VPI/VCI values on an incoming and outgoing interfaces will correspond to the end-stations or routers connected to this interface - rather than the source or destination of the IP packets being carried in the cells.

Folks at Toshiba recognized that - if a signaling protocol is used to establish new VPI/VCI values for specific flows of IP packets arriving at an input interface - then these special values could be bound to corresponding VPI/VCI values at an output interface. In this way a cell arriving with one VPI/VCI value would be switched at the ATM layer to the appropriate output interface and would be assigned the correct VPI/VCI for forwarding to the next hop router or end-station. Yasuhiro Katsube, Ken-ichi Nagami and Hiroshi Esaki submitted their Internet Draft "Router Architecture Extensions for ATM: Overview" to the IETF describing this idea at that time. In their draft, they proposed alternative signaling protocols for use and described how a Cell-Switching Router (CSR - [CSR-T]) would interwork with ATM switches, other types of ATM-switch routers and end-stations.

The basic idea was that the majority of packet flows would still be processed using the routing function but that specific flows would be forwarded at the ATM layer based on use of an additional signaling protocol. Flows involving special handling and flows consuming higher numbers of VCs would fall in two categories: default or dedicated VCs. Default VCs could be setup - for example - by using CLIP. Dedicated VCs would be setup using some other (in-band or out-of-band) signaling protocol. Protocols initially proposed included STII and RSVP (ReSerVation Protocol). Subsequently, the same authors, along with four of their colleagues at Toshiba Research, proposed a specific protocol - Flow Attribute Notification Protocol ([FANP]).

Kenji Fujikawa, of Kyoto University, published an Internet Draft [IP-SVC] in May 1996, proposing a lightweight ATM signaling replacement for use within an ATM LIS. This was intended to replace CLIP as a complement to - and thus an extension of - the earlier CSR proposal. While interest in this proposal continued for some time (it later became know as [PLASMA]), it has not become part of the mainstream effort in later MPLS standardization and signaling protocol development.

Ipsilon's IP Switching

Up to this point, existing proposals relied on use of native ATM signaling to establish at least default ATM virtual circuits. Ipsilon Networks, Inc. suggested a new approach - abandon the currently defined signaling in ATM and introduce a new signaling protocol to be used to manage IP flows. Ipsilon proposed a flow management protocol (Ipsilon's Flow Management Protocol - [IFMP]) for use in establishing (for example) VPI/VCI values to be used by neighboring ATM switches for specific IP flows. The assumption in this approach is that IP switches would forward IP packets between IP hosts and routers using default encapsulation until a flow is detected and a redirection message sent. Once an IP switch sent a redirection message - including a new encapsulation value (VPI/VCI in ATM) - the neighboring host, router or IP Switch would forward packets belonging to the defined flow using the newly defined encapsulation. Use of the new data-link layer encapsulation - which would be locally unique to a specific flow - would allow a neighboring router to forward IP packets associated with that flow at the data-link layer.

The Ipsilon approach had the advantage - relative to Toshiba's CSR proposal - of being potentially able to reduce the default forwarding load by a larger percentage of all IP packets being forwarded at any particular IP router. Unlike CSR, however, IFMP depended to a large degree on flow detection at each IP routing node in a network composed of IFMP-participating IP routers. This could result in significant overhead in IP packet processing in the default-forwarding mode and required implementations to pay attention to the activity of IP packets even in redirected flows.

In order to avoid scale issues associated with both CLIP and NHRP, IFMP-participating implementations would need to use flow detection algorithms aimed at detecting a relatively small percentages of the total number of IP flows. In order to minimize the over-all impact on IP forwarding, however, this small percentage of flows would need to carry a significant majority of the traffic. Based on data available from researchers at FIX-WEST, folks at Ipsilon proposed several approaches for detecting flow that would result in low flow count to redirected packet ratios.

Issues discussed relative to the Ipsilon approach were similar to those raised with CLIP and NHRP earlier:

• packet latency associated with protocol activity initiated by the prior existence of a flow of packets and
• scalability of the resulting virtual circuits in an ATM network of any appreciable size.

In late March, 1996, Greg Minshall (of Ipsilon Networks, Inc.) observed that greater scalability was achievable through the use of ATM switches that could merge ATM cells at the frame level from multiple input VPI/VCIs onto a single output VPI/VCI. This would have to be done without interleaving the cells associated with any particular frame with cells from other frames in the same output VPI/VCI. But it could be accomplished using a state variable - thus eliminating the need to actually assemble the frame at the IP layer. This simple observation may have led to the most significant contribution in many of the ensuing IP switching proposals.

2.2 - TAG, ARIS and Other Proposals

In the last few months of 1996, several new proposals popped up either on the ROLC and ION mailing lists, or on the tag-switching mailing list set up by Cisco Systems, Inc. to discuss their proposal or on the ION mailing list. Included among these were the following:

• TAG - from Cisco Systems, Inc.
• SITA - from Telecom Finland.
• ARIS - from IBM Corp.

Cisco Systems, Inc. and IBM Corporation each publicly announced their own versions of IP Switching late in 1996. Cisco announced the formation of a tag-switching discussion list and availability of tag-switching architecture [TAG-ARCH] and tag distribution protocol specification [TDP] documents in September. IBM posted an Internet draft - Aggregate Route-based IP Switching [ARIS] - in November. Cisco posted their first versions of tag switching over ATM and tag encapsulation in time for presentation at December Birds Of a Feather (BOF) meeting [IETF-37].

Essential differences between the TAG and ARIS proposals were:

• [ARIS] - although intended to apply to multiple media - focused on ATM and devoted an entire section to discussion of VC-Merging while [TAG-ARCH] was written to apply generally (VC-Merging was implied by the assumption that the solution was scalable in the number of routes supported by the proposed architecture);
• [ARIS] introduced the concept of VP-merging and the term label;
• [TAG-ARCH] and [TDP] tied the assignment and advertisement of tags to local determination of a new route availability while [ARIS] only allowed this to occur at an egress from a switching cloud;
• [TAG-ARCH] included alternative schemes for allocation of tags.

Between the TAG and ARIS proposals, another proposal was discussed on the Internetworking Over NBMA (ION) mailing list. This proposal - referred to at the time as Switching IP Through ATM ([SITA]) - suggested a simplistic configuration based approach to supporting IP packet switching over ATM. It also suggested a variant of VP merging as later proposed in ARIS. In this proposal, ATM VCIs would be configured based on the egress for a specific class of packets while VPIs would be configured based on the ATM ingress that first classified each packet. This proposal was updated in early November, but was subsequently dropped by its author.

While there had been an earlier attempt to establish a tag-switching forum, with the advent of TAG, ARIS and other proposals, it was clear that the possibility of developing a standard packet switching approach needed to be considered. Hence there was a Birds Of a Feather (BOF) meeting in December 1996. The result of this meeting was the decision to form an IETF working group - which would later come to be called Multi-Protocol Label Switching (MPLS).

2.3 - A Working Group

While the decision was made - in December 1996 - to form a working group to develop a standard approach for Switching IP, the MPLS working group was not actually formed until March 3, 1997.
 
 

Figure 4 above shows both the projected and the actual schedule for delivery of MPLS specifications. In this figure, it is apparent that original projections were based on unbridled optimism in most cases. On average, the delay between hoped for and actual delivery was more than a year.

To describe in detail how each of the various drafts developed by the MPLS working group evolved would take perhaps hundreds of pages and would - therefore - not be of use to most people. In subsections of this chapter, however, I have attempted to capture pictorially how the numerous drafts were interrelated and provide a very topical summary of the evolution process.

One general qualification must be made on this effort - I have tried to show reasonably strong links between drafts on related topics, based on specific acknowledgement, consensus of the working group (both on the mailing list and in working group meetings) or from participants in the process. It is necessary to acknowledge that other associations probably exist and it is fair to admit that all drafts publicly issued at any given point may have had direct or indirect impact on the ideas and material that is included in subsequent drafts.

In addition, many of the drafts associated with development of MPLS signaling protocols were put forward by individual contributors or multiple contributors from individual organizations. Each section lists any design teams that are notable exceptions to this rule (where members of more than one organization cooperated to develop one or more drafts).

Note that the tables represent the affiliations of individuals contributing to each effort during the period of active work. For that reason, many of the individuals listed may be listed as having different affiliations in different efforts. Many have different affiliations now than during any part of the MPLS protocol development effort.

Signaling Draft Development

Signaling Evolution Figure 5 - Signaling LDP and CRLDP

At this same time, a concern was raised about potential confusion of state machine interactions between LDP implementations using different control and label allocation modes in setting up LSPs. This was of particular concern because of the separation of signaling of explicit routes from the base Label Distribution Protocol specification. The working group established a draft ([LDP-State]) on LDP state machines for LSP setup to provide information on these interactions.

Both LDP and CRLDP drafts reached a state of relative completion in late 1999 and [LDP-State] entered working group last call toward the end of 1999. With the exception of modifying the procedures in appendices (to support non-merging LSPs) in the LDP specification, all LDP related drafts received only minor editing changes through out the year 2000.

Encapsulation and Related Draft Development

Encapsulation Evolution

Figure 6 - Encapsulation document

Two exceptions - shown in Figure 6 - are:

• separation of LAN encapsulation from the generic and PPP encapsulation draft ([Encapsulation]) and subsequent merging of the two separate resulting drafts ([MPLS-LAN-R] and [Encapsulation]);
• separation of specification of ATM and Frame Relay differentiated services from PPP differentiated services. Two PPP differentiated service drafts were proposed separately ([MPLS-Diff-PPP-L] and [MPLS-Diff-PPP-D]) and both were combined back into the mainstream differentiated service draft ([MPLS-Diff]) (major influence came from [MPLS-Diff-PPP-L] rather than [MPLS-Diff-PPP-D]).

Framework, Architecture and Other General Draft Development

Evolution
Figure 7 - Architecture, framework and issues document road map

MPLS Architecture, Framework and three applicability statements ([CR-LDP-App], [LDP-App] and [RSVP-TE-App] reached effective completion in the second half of 1999.

VPN, TE and OMP Draft Development

Figure 8 - VPN, TE and OMP document roadmap

There were a number of attempts to kick-start an effort to include standardization of a Virtual Private Network (VPN) support approach in the MPLS working group as well as in the IETF in general. The main reason why the majority of the VPN proposals that came forward were tabled is that it was felt that the requirements for VPN functionality were a subset of the requirements for Traffic Engineering (TE). Exceptions were a proposal to support VPNs over MPLS using BGP ([BGP-MPLS-VPN]) and a proposal for a standard VPN identifier format ([VPN-ID]). Both of these proposals are now RFCs.

Traffic Engineering requirements ([TER]) was the draft that energized much of the work in the MPLS working group from mid 1998 through late 1999. This draft - endorsed as it was by a major user of networking equipment - very quickly became the center-piece for virtually all efforts in signaling and other areas of MPLS development. This draft became an RFC in the second half of 1999.

Though there was genuine interest in it from several IETF working groups, the author of the work on Optimized Multipath was its primary driver in the MPLS working group. However, there was no consensus that there was a need to define anything in an MPLS context and this draft was allowed to expire.

2.4 - Reference Key and References

A note on the following references: the references listed in this section are divided into two categories:

• a section (provided as a table) that includes Internet Drafts which have expired or been replaced by subsequent drafts and or RFCs, as well as other historical documents as referred to by figures in this chapter and
• the usual references to current and available publications.

Reference Key for Figures in this Chapter

Table 4, below, provides Key expansion for reference keys used in this chapter. Note that Internet Drafts are by nature "work in progress". Listing Internet Drafts here is for historical purposes and is not intended to indicate that the listed Internet Drafts are useful as reference material in determining how these ideas are actually implemented or should be implemented.

References

[CLIP] - Classical IP and ARP over ATM, M. Laubach, RFC1577, January 1994. Subsequently superceded by RFC2225 (same title), April 1998

[Complexity] - Complexity, the Emerging Science at the Edge of Order and Chaos, M. Mitchell Waldrop, Simon and Schuster Inc. 1992.

[CSR] - Toshiba's Router Architecture Extensions for ATM: Overview, Y. Katsube, K. Nagami, H. Esaki, RFC 2098, February 1997

[FANP] - Toshiba's Flow Attribute Notification Protocol (FANP) Specification, K. Nagami, Y. Katsube, Y. Shobatake, A. Mogi, S. Matsuzawa, T. Jinmei, H. Esaki, RFC 2129, November 1996

[FLIP] - Transmission of Flow Labelled IPv4 on ATM Data Links Ipsilon Version 1.0, P. Newman, W. L. Edwards, R. Hinden, E. Hoffman, F. Ching Liaw, T. Lyon, G. Minshall, RFC1954, May 1996

[IETF-37] - Proceedings of the Thirty-seventh Internet Engineering Task Force, December 9-13, 1996.

[IETF-38] - Proceedings of the Thirty-eighth Internet Engineering Task Force, April 7-11, 1997.

[IETF-39] - Proceedings of the Thirty-ninth Internet Engineering Task Force, August 11-15, 1997.

[IETF-40] - Proceedings of the Fortieth Internet Engineering Task Force, December 8-12, 1997.

[IETF-41] - Proceedings of the Forty-first Internet Engineering Task Force, March 30 - April 3, 1998.

[IETF-42] - Proceedings of the Forty-second Internet Engineering Task Force, August 23-28, 1998.

[IETF-43] - Proceedings of the Forty-third Internet Engineering Task Force, December 7-11, 1998.

[IETF-44] - Proceedings of the Forty-fourth Internet Engineering Task Force, March 15-19, 1999.

[IETF-45] - Proceedings of the Forty-fifth Internet Engineering Task Force, July 11-16, 1999.

[IETF-46] - Proceedings of the Forty-sixth Internet Engineering Task Force, November 7-12, 1999.

[IETF-47] - Proceedings of the Forty-seventh Internet Engineering Task Force, March 26-31, 2000.

[IFMP] - Ipsilon Flow Management Protocol Specification for IPv4 Version 1.0, P. Newman, W. L. Edwards, R. Hinden, E. Hoffman, F. Ching Liaw, T. Lyon, G. Minshall, RFC 1953, May 1996

[LANE] - LAN Emulation Over ATM, Version 2 - LUNI Specification, ATM Forum Technical Committee, J. Keene (editor), 1997.

[MPOA] - Multi-Protocol Over ATM, Version 1.0, ATM Forum Technical Committee, A. Fredette (editor), 1997.

[NHRP] - NBMA Next Hop Resolution Protocol (NHRP), J. Luciani, D. Katz, D. Piscitello, B. Cole, N. Doraswamy, RFC2332, April 1998

[RFC1483] - Multiprotocol Encapsulation over ATM Adaptation Layer 5, J. Heinanen, RFC1483, July 1993. Superceded by RFC2684

[RFC1755] - ATM Signaling Support for IP over ATM, M. Perez, F. Liaw, A. Mankin, E. Hoffman, D. Grossman and A. Malis, RFC1755, February 1995. Further augmented by RFC2331

[RFC2105] - Cisco Systems' Tag Switching Architecture Overview, Y. Rekhter, B. Davie, D. Katz, E. Rosen and G. Swallow, RFC2105, February 1997

[RFC2331] - ATM Signaling Support for IP over ATM - UNI Signalling 4.0 Update, M. Maher, RFC2331, April 1998.

[RFC2547] - BGP/MPLS VPNs, E. Rosen and Y. Rekhter, RFC2547, March 1999

[RFC2684] - Multiprotocol Encapsulation over ATM Adaptation Layer 5, J. Heinanen, RFC2684, September 1999

[RFC2685] - Virtual Private Networks Identifier, B. Fox and B. Gleeson, RFC2685, September 1999

[RFC2702] - Requirements For Traffic Engineering Over MPLS, D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell and J. McManus, RFC2702, September 1999

[RFC2764] - A Framework for IP Based Virtual Private Networks, B. Gleeson, A. Lin, J. Heinanen, G. Armitage and A. Malis, RFC2764, February 2000

3.1 - Requirements

There are 3 broad requirement categories discussed below:

• Relationship to Routing,
• Relationship to Network Layer Protocols and
• Relationship to Link Layer Protocols.

MPLS forwarding mechanisms operate independently of routing. To maximize the compatibility of the MPLS packet forwarding technology with route determination mechanisms it is highly desirable that the basic forwarding technology is defined in such a way as to be as decoupled from the route determination process as possible.

Figure 9 shows a typical interface arrangement between Route Determination functions (routing protocol engine, policy management, filtering, etc.) and packet forwarding mechanisms. MPLS should minimize the complexity of the required interface in terms of the quantity of information exchange required in setting up to forward packets and in actually forwarding packets.

In general, a route determination function may off-load a subset of its tasks allowing a corresponding subset of packets to be forwarded without querying the route determination function for each packet processed. Alternatively, the information provided to the forwarding function may allow this function to perform some portion of the routing decision, reducing the burden on the route determination function and possibly allowing for pipelining and/or parallel processing of the remaining routing decision process. Off-loading the entire route determination process to the forwarding function may not be practical when the forwarding decision may be based on arbitrary bit locations in the data packets being forwarded. When this is the case, some subset of the decision making process would still need to be done by the route determination function directly.

This process involves an engineering trade-off between:

• amount of packet forwarding that can be done by the forwarding function without direct involvement of the route determination function, and
• complexity of the forwarding function itself.

By defining mechanisms by which the data that is significant to the route determination process can be abbreviated using a fixed-length label, MPLS makes it possible for any individual implementation to realize an optimal trade-off with considerably more of the forwarding decisions being made in a relatively uncomplicated forwarding function - often with minimal change in the implementation's architecture.

Note that MPLS does not excuse the entire networking system from ever having to make a route determination based on the potentially complex route determination function (using arbitrary bit positions in received data). The process of negotiating (or distributing) labels pushes this task to the MPLS implementation(s) that will serve as ingress for a particular stream of data packets (matching the criteria that would have been used to make the route determination at each router in the absence of MPLS). However, only the ingress will typically need to make this determination once an LSP has been established.

The normal mode for MPLS is to forward packets following the path determined by routing. The wording settled on by the members of the MPLS working group responsible for defining an MPLS framework was to the effect that MPLS integrates label switching and routing at the network layer. In an interesting twist of meaning, this equates to decoupling (dis-integration) of the binding between route determination and forwarding, since MPLS - and the label-switching paradigm in particular - is expected to make it easier to extend the route determination process by providing this decoupling effect.

As shown in Figure 9, routing protocols (and other routing functions - i.e. - static routes, policies, filtering, etc.) drive the route determination process. While some internetworking features may be a great deal more practical in using MPLS, the essential orientation of the route determination process remains the same when using MPLS as it is using routers without MPLS - that is to say, routing still drives the route determination process.

Where route determination might be performed on a per-packet basis for a significant subset of all packets forwarded in a non-MPLS router, MPLS allows the determination to be made at the time labels are being negotiated between MPLS implementations. The route determination function drives both the process of associating labels with a Forwarding Equivalence Class (FEC) and injecting label associations into the Forwarding Information Base (FIB). The route determination function also drives the process of removing label associations.

MPLS should perform better and in a larger network environment than an equivalent routing solution. This is expected to come about as an evolutionary process and the degree to which this actually occurs depends on a number of factors including:

• the extent to which the ability of routing devices to make routing decisions gains on dominant wire-speeds in the Internet in over-all deployment, without MPLS;
• the extent to which MPLS capabilities become ubiquitous in routing and/or administrative domains;
• the extent to which MPLS supports, and is used for, tunneling applications.

The extent to which MPLS is not needed or may add costs and delays (as a result of additional complexity in the product) in providing packet processing at wire speeds also effects the degree to which MPLS might become ubiquitous in a network routing or administrative domain.

Figure 10 - Partial deployment of Label Switching Routers

Figure 10 shows a partial MPLS deployment in a relatively simplistic network. In this network, isolated MPLS devices are unable to realize any advantage over standard routing because they are effectively the ingress and egress for every LSP which might be established through them. With small cliches of MPLS devices - consisting of 2 or 3 LSRs - the benefit from using MPLS over the relatively small number of links and the relative small percentage of total recognizable FECs which can be assigned to an LSP, may not outweigh the costs associated with signaling and processing labels. It is not until relatively large cut-sections of a network are entirely populated with LSRs that you're likely to see a reduction in the average amount of work done at each LSR. Note that - even under these circumstances - there may be no actual gain in performance in the network.

What does make this possible is that labels may be used - possibly in a hierarchical fashion - to establish tunnels (peer-to-peer, explicitly routed, etc.). Tunnels are already used as an approach to overcome addressing and scaling problems in the Internet today. MPLS labels consume less space in packet headers than many other tunneling approaches, may be established more easily (possibly using relatively complex instructions such as would be prohibitively difficult to implement in standard routing but are feasible in MPLS because of the separation of route determination and forwarding).

MPLS tunnels may be used to improve the utilization of the network through traffic engineering (7.3 - Traffic Engineering) for example - making it possible to build larger networks with fewer problems with network hot spots and under-utilization. MPLS tunnels may also be used to virtualize networks (7.4 - Virtual Private Networks) such that the route determination function is not required to peer with as many routers.

Relationship to Network Layer Protocols

MPLS will initially support IPv4 but be extensible for support of IPv6 and possibly other Network Layer protocols and addressing schemes. MPLS is intended to be able to support multiple Layer 3 (L3 or Network Layer) protocols (hence Multiprotocol Label Switching). Initially, however, the focus of the effort is on defining system components and functions required to support IPv4.

Support for additional network layer protocols requires specification of protocol specific FECs and required extensions to MPLS protocols for associating labels with these new FECs. The specification would need to include additional messages, message contents and processing behaviors and would need to account for behaviors relating to looping data and control messages, interactions with routing, etc. The existing specifications already define FECs for IPv6 network layer addressing, for example, but do not address interactions between MPLS and IPv6 routing (for good reasons - these interactions are not yet fully defined).

Note that - again, because of the separation of route determination and forwarding - these additional specification requirements do not affect implementations of the MPLS forwarding function. This is a highly significant factor in potential MPLS support of additional network layer protocols because reducing impact on highly optimized forwarding functions increases the ease with which additional support can be provided.

Relationship to Link Layer Protocols

MPLS should not be restricted to any particular Link Layer. Specification of MPLS operation over various media is required in order to realize many of the intended benefits of MPLS. Currently specified media support includes ATM, Frame Relay and generic MPLS shim (for PPP and Ethernet).

3.2 - Benefits

This section discusses the benefits of using MPLS as a forwarding paradigm. Not all of the benefits apply in every case. It has even been argued that several of these benefits have been overcome by technological developments.

Simple Forwarding Paradigm

Forwarding is based on exact match of a relatively small, fixed length field as opposed to (for example) a longest match on a similar length field, or a complicated evaluation of arbitrary bit positions in an arbitrary length portion of data packets being forwarded.

The actual length of the label is media and session specific.

Explicitly Routed LSPs

Explicit routes are established as LSPs. It is not necessary to include and evaluate an explicit route with each packet forwarded.

Traffic Engineering

The ability to explicitly route a portion of the data traffic along paths not normally used by standard routing (e.g. - not the optimal path chosen by an IGP) makes it possible to realize greater control in engineering traffic flow across a network. Mechanisms for accomplishing this function in the absence of MPLS involve configuration of routing metric values, static routes and - using for example ATM or Frame Relay - permanent virtual circuits. This would typically be done either manually or under the control of a management system. Determination of the traffic that will be re-routed is typically done using an off-line path and resource computation on a weekly or possibly daily basis. This is frequently referred to as off-line Traffic Engineering (TE). TE based on use of explicit routes allows the network administrator to use arbitrary flow granularity and potentially a much smaller time scale to obtain more efficient utilization and minimize congestion in the network.

QoS

Allocation of special treatment facilities for packets associated with a FEC that is to receive some form of preferential treatment is done at LSP setup. In addition, it is possible to perform policing and/or traffic shaping at ingress to an LSP (as opposed to at each hop).

Even if it is desirable to support a less state-full QoS model - such as that defined for Differentiated Services - use of an essentially connection oriented signaling model allows the network to perform sanity checks in determining if the capacity to provide a service exists prior to committing to provide that service.

Work Partitioning

The process of assigning packets of a particular FEC to an LSP is done once at the ingress of the LSP, rather than performing a similar function at each hop. The process of signaling, or negotiating, label and FEC associations allows core network devices to push the task of packet classification toward the edge of the network.

Where edge-ward devices have substantial packet forwarding capability using L3 as well as MPLS, it is even possible to share the packet classification task among edge-ward LSRs by forwarding a portion of the traffic at L3 to be classified by LSRs further downstream.

The packet classification process is easily partitioned using hierarchical LSPs as well. An example of where this is useful is when an edge-to-edge service requires LSPs to classify and process packets as individual streams. By aggregating tributary streams as they progress toward the core of the network, and de-aggregating them as they progress away from the core, it is possible to classify and treat individual packet streams on the basis of an extremely fine granularity. This is possible because higher-level LSPs may be treated as fixed capacity pipes allowing fine-grained treatment of individual packet streams in lower-level LSPs.

Routing Protocol Scalability

MPLS offers increased scalability of routing protocols by reducing the number of peer relationships that a routing entity is required to maintain. MPLS provides mechanisms for virtualizing network topology, thus allowing routers in virtual networks to peer only with routers in that same virtual network. In addition, MPLS defines system behavior in such a way that it is not necessary to have full mesh peer relationships in a hybrid switching and routing network environment.

This requires some more explanation. Intuitively, tunneling between routing peers typically results in more peer relationships. This is a commonly recurring theme in discussion of overlay and peer routing models. However, it is possible to partition an implementation into separate routing instances such that one routing instance deals with local peers to - for example - route tunnels to remote peers while another routing instance deals with a set of remote peers. Partitioning the overall routing problem in this way is a good way to reduce the complexity associated with the need to deal with local and remote peers. This partitioning is very similar to that used in gateway routers that need to deal with remote EGP and local IGP peers.

Common Signaling

The same label distribution techniques are usable over ATM, Frame Relay, Ethernet, PPP, and other media. This makes deployment of MPLS applications (such as Traffic Engineering or VPNs) across multiple media types, using common signaling, possible.

Simplified Management

Because MPLS allows applications to be deployed over multiple media using common signaling and forwarding mechanisms, management of the network in support of these applications is greatly simplified.

Reduced Latency

Using a topology-driven approach to establish LSPs for normal, best-effort, forwarding of data packets virtually eliminates latency in packet transport. Setup of LSPs driven directly by routing transactions should result in availability of an LSP nearly as quickly as a route is available. Because packets would not be deliverable in the absence of an available route, the additional latency is very small generally or - in the case where a piggyback label distribution mechanism is used - non-existent.

3.3 - References

[IPv4] - Internet Protocol, RFC 791, Jon Postel (Editor), September 1981

4.1 - MPLS System Components