Virtual circuit packet switching with IP

Protocols which route data from a node or hop to another hop between two end hosts in a network are called network-layer or L3 protocols. In the Internet, the only currently available network-layer protocol is IP, which comes in two flavors: IPv4 [59] makes use of 32-bit long addresses and IPv6 [22] uses 128-bit long addresses. We will mostly focus on IPv4 as IPv4 is the currently deployed version of IP in the Internet. Because of the advantages of virtual circuit packet switching and the growing popularity of IP, many Internet service providers send IP packets over virtual circuits. Virtual circuit packet switching technologies that have been used in the Internet backbones are ATM and, more recently, MPLS.

IP-over-ATM

ATM is a VC-switching technology which was standardized starting in the late 1980s. ATM uses fixed-length payloads with a length of 48 bytes and a 5-byte header, yielding 53-byte long ATM cells. Among the 40 header bits of a cell, 28 are reserved to identify the virtual circuit to which the cell belongs. The corresponding fields are called VCI/VPI (Virtual Circuit Identifier/Virtual Path Identifier). The VCI/VPI fields are updated at each switch.

A first issue that arises when trying to send IP packets over ATM virtual circuits is the need for a definition of an encapsulation of IP packets in ATM cells, i.e., how to put IP data inside ATM cells. Encapsulation is performed by an adaptation layer (AAL) as defined in [6]. Moreover, most IP packets are too large to fit in a 53-byte ATM cell. An IP header is at least 20 bytes long, and hosts cannot be coerced to send IP packets of at most 53 bytes. Therefore, IP packets must be cut into smaller pieces in a process called segmentation before they can be encapsulated and put in ATM cells. The last router on the path of IP packets must reassemble the fragments to reconstitute the original IP packets. Segmentation and Reassembly (SAR) is a complex and time consuming process.

Sending IP traffic over an ATM infrastructure proves to be complex [19]. Far from solving the circuit interruption problem that arises on link failure with VC-switching, IP over ATM introduces the aforementioned issues and requires additional hardware as combined IP routers/ATM switches do not exist.

MPLS

Multiprotocol Label Switching (MPLS) is a comprehensive IP over virtual circuits technology which has been specifically engineered to interface better with IP than ATM. MPLS runs over many existing network hardware like Ethernet [38] or even ATM and supports the forwarding of IP packets over virtual circuits. MPLS can be implemented in IP routers.

In MPLS, each packet carries a virtual circuit identifier, called label, as a field of a shim header inserted between the IP header and the MAC/link layer header of a packet. A single packet can carry more than one shim header. The set of all headers carried by a packet is called an MPLS stack. Figure 1.4 depicts a stack of MPLS headers, and the position of the MPLS stack in the headers of a packet.

Figure 1.4: Position of the MPLS stack in the network protocol stack. Shim headers are inserted between the IP layer and the MAC or link layer. Each shim header consists of four fields.

MPLS handles labels just like all other virtual circuit identifiers are handled in other virtual circuit switching technologies. Consider an IP packet sent by host $A$ to host $B$ in Figure 1.5. The packet is forwarded through an MPLS network or domain between $A$ and $B$. When a packet arrives at the first MPLS router, also called ingress Label Edge Router (ingress LER) of the MPLS domain, the source and destination IP addresses of the packet are analyzed and the packet is classified in a Forwarding Equivalence Class (FEC). All packets within the same FEC use the same virtual circuit, called Label Switched Path or LSP. Suppose a virtual circuit has already been established for the FEC of the packet sent by $A$ to $B$: then, the ingress LER inserts or pushes an MPLS header on the packet (L1 in the Figure). Subsequent routers of the MPLS domain update the MPLS header by swapping the label (L1 against L2, L2 against L3). Finally, the last router of the LSP, called egress LER, removes or pops the MPLS header (L3 in the Figure), so that the packet can be handled by subsequent MPLS-unaware IP routers or hosts.

Figure 1.5: MPLS forwarding. The ingress LER determines the FEC of packets sent by $A$ to $B$ and pushes a label on the packets. Subsequent LERs swap labels. The egress LER pops the label and outputs an IP packet with no MPLS header.

MPLS routers push, swap and pop MPLS headers according to rules contained in a forwarding table called Forwarding Information Base (FIB) that is distinct for each MPLS router. The FIB can contain three different types of entries. A Next Hop Label Forwarding Entry (NHLFE) contains the information necessary to forward a packet for which a label has already been assigned. A NHLFE contains two pieces of information: the packet's next hop address, and whether the MPLS header of the packet must be swapped or popped. If the MPLS header of the packet must be swapped, then the NHLFE also contains the new label of the packet. The Incoming Label Map (ILM) contains the mappings between labels carried by incoming packets and NHLFE entries. Last, the FEC-to-NHLFE (FTN) contains the mappings between incoming packet FECs and NHLFE entries. MPLS routers use their FIB as follows. Suppose a packet with no label arrives at an MPLS router. The MPLS router first determines the FEC for the packet, then looks up in the FIB for the FTN that matches the FEC of the packet. This FTN contains a label and a NHLFE which in turn contains the next hop for the packet. The MPLS router pushes an MPLS header that contains the label read in the FTN and forwards the packet according to the information contained in the NHLFE. Now suppose that a labeled packet arrives at an MPLS router. The MPLS router searches in the FIB for an ILM that matches the label of the packet and reads the associated NHLFE. The NHLFE can either indicate that the MPLS header must be swapped against a new label, or popped. In the former case, the MPLS router swaps the MPLS header and forwards the packet to the next hop specified in the NHLFE. In the latter case, the MPLS router pops the label and forwards the packet to the next hop specified in the NHLFE.

MPLS headers are 32 bits long and labels take only twenty bits out of these thirty-two bits, therefore leaving room for further information inside the header. The twelve remaining bits are used as follows. First, MPLS is designed to be able to take into account Quality of Service (QoS), and three experimental (exp) bits have been allocated to handle up to eight QoS classes. Second, MPLS allows hierarchical domain nesting: when a packet enters an MPLS domain which is contained in another MPLS domain, a new label is appended to the packet, which was already carrying one label. This is referred to as label stacking. For instance, Figure 1.6 shows two nested MPLS domains. A bottom of stack (bos) bit indicates whether a label is the last in the stack or not. Finally, each MPLS router decrements an 8-bit Time To Live (TTL) field and discards packets when the value of this field initially set by the ingress LER reaches zero. The reason for this mechanism is to avoid packets from indefinitely looping in case a circular virtual circuit is mistakenly created. The division of an MPLS header into the four fields we have just described is summed up in Figure 1.4.

Figure 1.6: Nested MPLS domains. In the inner MPLS domain, two labels are stacked.

A main point of interest with FECs in a traffic engineering context is that they support aggregation. All packets from different sources but entering the MPLS domain through the same LER, and bound to the same egress LER, can be assigned to the same FEC and therefore the same virtual circuit. In other words, there is no need to establish a new virtual circuit for each (source, destination) pair read in the headers of incoming packets. Once an ingress LER has determined the FEC of a packet, the ingress LER assigns a virtual circuit to the packet via a label number. Also, FEC definitions can take into consideration IP packet sources in addition to destinations. Two packets that enter the MPLS domain through the same LER and going to the same destination can use different sets of links so as to achieve load balancing, that is, put the same amount of traffic on all links hereby distributing the load of traffic on each link. A FEC can also depend on additional parameters such as the Type of Service bits of the IP header to provide differentiated services to IP traffic [23].

Establishing virtual circuits and mappings or bindings between FECs and labels and building the FIB at each MPLS router is the responsibility of a signaling protocol. The MPLS architecture [62] does not impose to use any specific signaling protocol. The only requirement is that, on a given link and for a given LSP, labels are assigned by the downstream node and advertised to the upstream node. Two refinements have been devised from this requirement, as shown in Figure 1.7. In downstream unsolicited label distribution mode, a node recognizes that it is a downstream node for a FEC and sends a label binding message to the upstream node for that FEC. The downstream node decides by itself to send the binding message without any trigger from the upstream node. Conversely, in downstream on demand mode, the upstream node identifies that it needs a label binding message for a particular FEC and requests that the downstream node sends this label binding message.

Figure 1.7: Label distribution modes. Downstream unsolicited and downstream on demand label distribution modes.

Although no label signaling protocol is imposed by the MPLS standards, only two signaling protocols for MPLS have been developed. RSVP-TE [8] is based on a resource reservation protocol for the Internet, RSVP [13], to which it adds the capability to advertise LSPs. Another protocol, LDP (Label Distribution Protocol [3]), has been defined from scratch as a part of the MPLS design effort. An extension to LDP, namely CR-LDP (Constraint Routing LDP [41]), adds important features to LDP with respect to traffic engineering. One of the main improvements of CR-LDP is the support of Explicit Routing, where a single node or an offline server which precomputes paths can fully define and advertise LSPs. The differences between these two signaling protocols are examined in [14].

MPLS is still a new technology. The need for a new VC-switching technology with IP packets to replace IP over ATM has been identified in 1996 and standardization of MPLS commenced in 1997 [62]. The standardization process is still continuing at the time of this writing, and one of the big pieces of work that remains to be added to this effort is multicasting.