Multiprotocol Label Switching

Let us now look at a technology which aims at blending packet switching with circuit switching.

Today's Internet rely upon packet switching. We have sources (end hosts) dividing the data they want to across small packets. Each packet has a source and a destination address and is sent independently inside the network. Intermediate nodes (routers) forward these packets one-by-one, performing a longest-prefix match on every single one of them.

Circuit switching predates packet switching. It was used in the older days of the analogue telephone network. Back then, when people had to place a call they were calling an operator and ask "I would like to talk with Anna". The operator would then literally (physically) connect their cable with Anna's cable, creating a dedicated connection, a circuit, between both.

The cool thing about doing this is that, while it takes a little bit of time to establish the connection, once you have the circuit built, there is a dedicated connection between you and Anna. No one else is using this path, which gives you guarantees.

On the Internet, there is no guarantee whatsoever, everything is best effort. We can be 100,000s using the same path. And that means we could have a terrible Quality of Experience (QoE).

Of course, circuit switching is extremely wasteful if the communication is bursty, which most of the Internet traffic is (at least today). With bursty traffic, the overhead of setting up a circuit is not worth it. That's why circuit switching got torn down, and it's not used anymore in the Internet.

The big question is though: Can we combine the advantages of packet and circuit switching, with their drawbacks? Enters the idea of virtual circuits.

With Virtual Circuits (VCs), as the name indicates, we are not talking about physical circuits, but rather about logical ones. These logical circuits are then mapped to physical paths according to some logic. By mapping one logical circuit to exactly one physical path, we can emulate the isolation benefits provided by circuit switching. Likewise, by mapping many logical circuits to one physical path, we emulate IP-based forwarding. Essentially, how many logical circuits you associate to the same path gives you more or less isolation, more or less guarantees.

To implement logical circuit, we will add a bit of information to the header with the creation of a VC header. We'll then allow nodes to route traffic according to this VC header (and possibly also according to the IP destination).

MPLS, which stands for Multi Protocol Label Switching, is technology which blends IP with VCs. MPLS is used in many, many networks out there. The idea of MPLS is very basic: add a new header (known as a MPLS label) between the Ethernet header (layer 2) and the IP header (layer 3). Because of this, MPLS is often referred as a layer 2.5 protocol. You can then use this extra header to flexibly adapt how forwarding is done. It turns out that doing so has plenty of interesting applications such as Traffic Engineering (TE), QoS, etc.

Let us see how MPLS work in practice. As said, incoming packets will now carry a MPLS label (we'll see shortly that a packet can have more than one label attached to it). Upon receiving these labelled packets, the router will perform a lookup in a so-called label forwarding table (which is sometimes referred to as LFIB). This table lives alongside the IP forwarding table. So depending on whether the packet the enters a port is labelled or not, the router will use one forwarding table or the other.

Using its label forwarding table, the router decide where to send it next and whether it should change the label attached to it. In this simple example, you have packets with labels A and B entering the routers. In R1, the label forwarding table says that, when there is a labelled packet A that enters, then this packet should be forwarded on the right port, and then the out label should be set to X. So, A gets turned into X, and B gets turned into Y.

Let us now zoom out and look at what happens at the network level. Nowadays MPLS is typically used within a networks, not across them. That means that networks will receive IP packets from their neighbors. The ingress routers will be convert these packets into label packets (they will simply slap a label on them). Then, inside the network, the network will forward the packets according to their labels. As the packet gets out, the egress routers will remove all the labels, turning these packets into pure IP packets again. (This means that the IP packets you send on Internet will often turn into label packets as they cross different networks; you don't see it though as it is invisible to you.)

A little bit of terminology now. First, there are the ingress routers, aka labeling machines, if you wish. We call them ingress LERs. They receive IP packets and produce label packets. Then, you have a LSRs or switching routers. These routers are typically in the core of the network and only forward the packets according to their labels. You then have the opposite of labeling machines, stripdown machines if you wish, that remove any labels before the packets get out. We refer to those as ingress LERs.

Operationally-speaking, we need to solve three problems with MPLS. The first one is practical: What do we use as a label? As you'll see, it's very simple. The second one is what should be the behavior of a LSR. How do they forward labelled traffic? Then, finally, what is the behaviour of an LER, how do they map the IP world with the label world?

The MPLS headers are 32-bit long and place just in front of the IP header. Out of these 32 bits, 20 bits are reserved for the label itself while the remaining 12 bits are used for other things (we'll discuss about some in a second). 20 bits of label space, means $2^20$ distinct labels, which is plenty.

Let me now speak about the data-plane behavior of a LSR, i.e. the operations that these routers can perform on a labelled packet. As I said, a labeled packet can have multiple labels attached to it. The way to think about that is to consider that packets carry a stack of labels. As you know a stack is a data structure that supports three operations: PUSH, SWAP, and POP.

A push puts a new label in front of the packet. If the packet does not have a labeled yet (it's an IP packet), then it becomes a labelled packet. If it already has a label, then it gets another one, etc. (There are good reasons to carry more than one packet, as we shall see.).

A swap changes the value of the top label with another given one. If the top label is $k$ and you swap it to $x$, the next router on the path will see $x$ on top of the stack.

A pop removes the top label. If there is only one label left, a pop turns a labelled packet into a IP packet. In contrast, if you have more than one label and you do a pop, it still remains a labelled packet.

Looking at the picture, you would have pure IP packets entering. The ingress LERs perform pushes turning those into labelled packets, in green and red. The LSRs will then (typically) perform swap operations. While the egress LERs will perform pop operations.

So what does a labelled forwarding table contains? Well, of course, we have to match on the incoming label (InLabel). These matches packets will then be associated to outgoing interface (a next hop) alongside with the operations (PUSH, SWAP, POP) to perform on them (and their corresponding parameters).

Note that the next-hop will either be an outgoing interface or the router itself. The latter is useful when the destination of the labeled packet is the LSR itself.

Here are examples of label operations performed by a LSR according to its label forwarding table.

For the first label packet, the outer label is L3. According to the table, the LSR swap it with L0 and send it onto its North East interface. The resulting labeled packet is depicted in red. For the second labeled packet, the outer label is L4. The LSR pop it, and send it East, turning it into a labeled paket with L5 on top (in blue). Upon receiving a labeled packet with L5, the LSR pushes L1 send it South (in black).

The processing of the labeled packets with L6 on top is more interesting. As you can see, the operation is a POP and the NextHop is local. What happens here is that the router will remove L6 and essentially reprocess the packets according to the second label (which became the top label). This means that there are two lookups being done here, with the second lookup being done based on L3. What happens when the label is L3? We swap with L0 and we send to North East (in green).

Finally, for the incoming L9 label, the LSR will swap the outer label with L8, and then push L4 on top (see the resulting packet in magenta).

Now we have been looking at what happens on the single nodes. You can think about piecing these things together across the entire network and creating what are known as LSP. An LSP is a path followed by labelled packets throughout the network from an ingress LER to an egress LER. Of course an LSP is required for forwarding to work at all.

Let's look at a few examples of LSPs. The first LSP here (in red) is between L1 and L0. It crosses L5, L6, L7, and L4, following the content of the label respective forwarding tables. The ingress LER (L1) is performing a PUSH, L5 is doing a SWAP to L6, which gets to L6 which swaps it again to L5, etc.

There can (and will be) of course be multiple LSPs, in blue you can see another example goes from L3 to L2.

Let us now see how we can improve the scalability of our label forwarding tables by leveraging the stack and the fact that we can have more than one label on an packet. Doing so allows us to temporarily aggregate distinct LSPs (say the blue and red LSP in the example above) together by adding an extra outer label.

For instance, the blue and the red LSPs are sharing a common subset of the path. They both cross L5, L6, and L7 (in succession). If you look at the table of L6, L6 had two entries, one for the blue LSP, one for the red LSP. Here, we merge these two LSPs together by pushing L1 on top of both. One way to think of it is that I'm turning the blue and red LSPs into a green LSP. Doing so L6 only needs one forwarding entry for the green LSP. L6 then performs a POP and by doing so breaks down the LSP into two again. In this particular example, we could have had L6 not popping immediately and leaving the second label onto L7, and then have L7 break it down by popping. The slide didn't do that, but you could have done it.

Talking one second about the implementation of the stack. We need to give the LSRs a way to test whether there are more than one label on a packet. To do that, they simply rely on a single bit which is placed in the MPLS header. This bit (known as the S bit) indicates whether the label corresponds to the bottom of the stack or not. If the label is 0, it means that there is another label after.

Let us now talk about the behavior of ingress LERs. Again these are the routers that are sitting at the edge of the network. They receive pure IP packets on the one hand, and turn them into labelled packets on the other hand. This mapping from IP to labels needs to be done according to some logic.

This logic is rather simple, really. Ingress LERs do that by relying upon pre-defined Forwarding Equipment Classes, or FEC. A FEC maps IP prefixe(s) to labels. This mapping can be done in different ways, for instance, mapping each individual prefix to a distinct label, or mapping multiple prefixes (e.g. the ones leaving at a particular egress router) with the same label.

You can see several examples here. The ingress LER has a table which maps the IP world on the left to LSPs (and therefore, labels) on the right.

Figuring out the content of these mapping tables is either done manually, by the operators, or using various protocols that allow routers to exchange mappings between each other. We won't see these protocols in the lecture, but just in case you want to know more about them, LDP and RSVP-TE are the most used protocols there.

In the last two slides, I would like now to revisit how ISPs work in the light of MPLs and also justify why MPLS is so used in practice. On slide 24, you can see an example of a vanilla, IP-only ISP. It runs eBGP with its external neighbor, and has a full-mesh of iBGP sessions internally. This means that, for B3, B6, and B4, even if they do not have any external peering, they still need to carry 1.1 million prefixes inside theor forwarding table.

On slide 25, you see an alternative design which leverages MPLS. Using MPLS allows ISPs to build what is known as a "BGP-free" backbone. Concretely, the idea is to have the ingress routers attach a label on the packets they receive indicating the egress routers these packets should be forwarded to. That way, core routers can forward these packets to the egress based on the labels, and do not need to know anything about BGP. (They don't need to run BGP at all.) This means that B3, B4 and B6 will be BGP-agnostic.

So MPLS allows ISP to contain the cost of doing IP routing at the edge of their networks.