PUBLIC DOCUMENT                                                 James R. LeuMay 24 2000                          MPLS Forwarding Basics1. MPLS SummaryThe goal of Multi-Protocol Label Switching (MPLS) is to remove the process oflayer three lookups at each hop of a network.  This has many direct affects.MPLS forwarding makes traffic engineering a more viable solution for networkcongestion.  MPLS forwarding _may_ enable wire speed routing (switching).MPLS forward _could_ allow network hardware vendors to make cheaper trunkcards that ONLY understand labeled packets.  MPLS abstracts the media specificqualities away from more complex network engineering (QoS, CoS, DiffServ).MPLS forwarding can be used to make VPN service more flexible and deployablewithout compromising the performance of your edge routers (switches).  Inaddition to the above, the concepts used to to setup MPLS forwarding arethe first step towards creating completely optical networks.As a packet traverses an MPLS enabled network it must make three transitions.First, is that it must go from it's native layer 3 forwarding intolabeled MPLS forwarding.  This process entails the adding of a label to thehead of the packet.  Second, a (now labeled) packet much be able to traversean MPLS path.  This path consist of all the devices that know how thisparticular packet (and packets like it) need to traverse a network.  Thispath is called a Label Switch Path (LSP).  It is a connection oriented paththat is setup ahead of the forwarding of any packets.  Finally a packet mustmake its way back into layer 3 forwarding.  This process consists of removingthe label from the head of the packet and then sending it to the appropriatelayer 3 protocol for additional handling.  In an MPLS enabled network, layer3 forwarding is used by the edges of the network, and MPLS forwarding is usedin the core of the network.A network device that acts as the boundary between layer 3 forwarding andMPLS forwarding is called a Label Edge Router (LER).  An LER has the abilityto add a label to a unlabeled packet, and remove the labels from a labeledpacket. An LER that adds a label to a packet, is called an ingress LER andan LER that removes the label from a packet is a egress LER.  A network devicethat can forward a labeled packet (still labeled with possibly a differentlabel) is called a Label Switch Router.  The process of forwarding a labeledpacket is commonly referred to a Label Switching, because it mimics the ideasof Ethernet or ATM switching.  Sometimes this is also called Label Swappingbecause the value of the label may change at each hop in a LSP.  So the LSRis "swapping" the labels in the packet.2. MPLS LabelsWhen a label is added to a packet this means that at minimum a 4 byte "shim"has been added to the packet.  This shim is added between the layer 3 headerand layer 2 header.  Therefore an IP packet on Ethernet would add the shimbefore the IP header but after the Ethernet header.  MPLS forwarding iscurrently defined for the following layer 2 implementation:  Ethernet, packetover SONET, ATM, frame-relay.  MPLS has also been defined for any medium thatPPP runs on top of.  On _most_ of these layer 2 implementation a label consistsof a 20 bit number.The shim that is added to the packet contains more then just a label.  Hereis a diagram of a MPLS shim:  0                     1                   2                   3  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |                Label                  | Exp |S|       TTL     | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+As you can see the label is 20 bits.  This value is used to determine how apacket will be label switched.  The next 3 bits are called the EXP bits.  Theyare currently reserved for experimental purposes.  (although DiffServ overMPLS has claimed these 3 bits for its use).  The next bit is referred to as the"bottom of stack bit" (S bit).  Due to the fact that MPLS _adds_ a shim tothe packet a LSR needs to know if what follows this top shim is the layer3 header or another shim (Multiple shims are called a label stack.  The purposeof a label stack will be explained later).  The S bit signifies that whatfollows this shim is the layer 3 header.  For typical single shim MPLS forwarding the S bit is on.  Finally the shim contains the Time To Live (TTL)counter.  This is used to allow current layer 3 functions to occur even thoughan LSR cannot use the layer 3 header.  Some examples of these are traceroute,loop detection, and multicast domains.2.1 MPLS Label StackingWhen an LER adds a shim to a packet, it is feasible that is can add more thenone shim.  This concept is called Label Stacking.  The _stack_ of shims istreated just as it's name sake data structure.  A POP means that the top shimis removed, exposing either another shim or the layer 3 header (determinedby the S bit).  A PUSH adds a new shim to the top of the stack or on topof the layer 3 header. So standard label swapping is defined as a POPfollowed by a PUSH.  In some cases a labeled packet may need to be tunneledacross another MPLS network.  In the case the labeled packet gets anothershim pushed on top without POPing the original shim off.  This results in alabel stack of size 2.  This operation can occur multiple time by separateLSRs or a single LSR could add more then one shim. In general any labeledpacket has a label stack, although most have a label stack of size 1. As onemay expect a packet with a label stack greater then 1 may _shrink_ in sizeas well.  This operation would be defined by a POP without a PUSH.  The exactdetails of how this occurs will be explained later.3 MPLS Data StructuresFor MPLS forwarding to occur correctly some data structures need to existto assist in the interpretation of labels and the processing of them.In general there exists three data structure. One data structure to helpinterpret incoming labels (labels from packets that are entering an LSR oregress LER).  A second data structure to assist in adding out going labels(labels on packets that are leaving a LSR or ingress LER).  A third datastructure is used by ingress LERs to figure out what label to add to a packet.The common name for the data structure used to interpret incominglabels is called the Incoming Label Map (ILM).  The ILM table consistsof all the incoming labels that an LSR or egress LER will recognize.The contents of each ILM entry are: label, opcode, FEC, and an optional link toan outgoing data structure.  The general order of operation for incoming labelprocessing is:-extract label from top shim-lookup the label in the ILM table-further processing on the packet based on the opcode stored with the labelDetail ILM processing will be explained later.As stated earlier there also exists a data structure to assist with outgoinglabeling.  The common name for this data structure is the Next Hop LabelEntry (NHLFE).  The NHLFE table consists of all the labels which can be pushonto packets.  Each NHLFE entry contains: label, outgoing interface, and nexthopinformation.  The general processing that occurs when a packet reaches theNHLFE table is:-form new shim that contains the label-push the shim onto the packet-forward the packet to the nexthop via the outgoing interfaceDetails of NHLFE processing will be explained later.A third data structure exists for the sole purpose of helping ingress LERs decidewhat labels to add to a packet.  For the explanation of this data structure weneed to take one step back and introduce the term Forwarding Equivalence Class(FEC).  Up until now we have referred to individual packet in terms of addingand removing labels.  How do we know what label to add to a packet?  How do weknow what type of packet I have after removing a label?In general packets are labeled according to which FEC they belong to.  Forexample I am defined FEC A to be the class of packet that are heading tothe host with IP address 1.1.1.1.  Therefore all packets that have a destinationIP address 1.1.1.1 belong to FEC A.  In MPLS we assign each FEC a label andeach label refers to a FEC (1:1 mapping).  The definitions of FECs may changebut the 1:1 mapping should always stay constant.  The data structure used tomap FECs to labels is called a FEC To NHLFE (FTN).  An FTN table consists ofall FECs which we know how to add labels too.  An FTN entry consists of:FEC, NHLFE entry.  The general order of operation for FTN processing is:-decide what FEC a packet belongs to-find the FEC in the FTN table-forward the packet to he NHLFE entry that corresponds to the FTNDetail FTN processing will be explained later.4. MPLS over ATMEarlier the statement was made that labels are 20 bits values for _most_layer 2 implementations.  ATM is one of the exceptions (Frame relay is theother).  Since ATM is already built upon switching technology it can takeadvantage of this.  If the definition of a label is changed to a VPI,VCI pair,we now would do label switching based on VPI,VCI which is what ATM alreadydoes.  This provides a nice optimization, but introduces problems andcomplexity.  In "normal" MPLS forwarding we look inside to the top shimto get the label, on ATM we do not need to look in the shim, nor CAN we.But what about the other fields in the shim?  Do we just loose the functionalitythey provide when running MPLS over ATM?  To retain the functionality we needto make a couple of compromises.  First, even though we can do MPLS forwardvia VPI,VCI pairs and we do not need the shim to store the label, we will stillkeep a place holder shim at the top of the stack.  This is called the NULL shim.The NULL shim is added after the ATM header in the first cell of a AAL5 frame.The NULL shim will hold the EXP, TTL and S bit that would have been added ifwe doing "normal" MPLS forwarding.  Due to the nature of ATM switching, thesevalues will pass through the ATM network untouched.  When the packet leavesthe ATM network and either goes back to layer 3, or move on to "normal" MPLSforwarding these values will be available for use at that time.  MPLS forwardingover ATM has 5 transition it can go through:-Layer 3 forwarding to MPLS over ATM forwarding (ingress LER)-MPLS forwarding to MPLS over ATM forwarding (LSR)-MPLS over ATM forwarding to MPLS over ATM forwarding (LSR)-MPLS over ATM forwarding to MPLS forwarding (LSR)-MPLS over ATM forwarding to Layer 3 forwarding (egress LER)5. MPLS Detailsstruct mpls_label {  u32 label_res:1,      label_value:28,      label_type:3:#define MPLS_LABEL_VPI		((label_value>>16)&0xFFF)#define MPLS_LABEL_VCI		(label_value&0xFFFF)#define MPLS_LABEL_GEN		(label_value&0xFFFFF)#define MPLS_LABEL_DLCI_10	(label_value&0x3FF)#define MPLS_LABEL_DLCI_17	(label_value&0x1FFFF)#define MPLS_LABEL_DLCI_23	(label_value&0x7FFFFF)};#define MPLS_GEN_LABEL		0x01#define MPLS_VPIVCI_LABEL	0x02#define MPLS_VPI_LABEL		0x03#define MPLS_VCI_LABEL		0x04#define MPLS_FR10_LABEL		0x05#define MPLS_FR17_LABEL		0x06#define MPLS_FR23_LABEL		0x075.1 MPLS ILM Details-ILM structure:struct ilm_ent {  struct mpls_label label;  struct route_ent* outgoing_rt;  u16 protocol;  u8 opcode;}; (more detailed processing can be found in the MPLS reference code)-Each logical interface needs to stores it's own ILM table.  MPLS packets that arrive via that interface will do label lookups into that interfaces ILM table.-The full list of opcodes that can be stored in a ILM entry: POP_AND_LOOKUP   If the top shim has the S bit on:     Extract the protocol type from the ILM     POP the top shim     Copy the TTL to the layer 3 header     Using the protocol type, do a lookup on       the layer 3 header that is exposed   Else     POP the top shim     Extract the label from the shim that is       exposed     Extract the S bit     Extract the EXP     Extract label and create ILM Index     Using the ILM Index Lookup the ILM Entry     Execute the opcode in the ILM Entry   End POP_AND_FORWARD   Extract the outgoing route entry from the ILM   POP the top shim   If the outgoing route entry is a layer 3 route entry     copy TTL to layer 3 header   Using the outgoing route entry forward the     packet to the outgoing interface                   NO_POP_AND_FORWARD   Extract the outgoing route entry from the ILM   Using the outgoing route entry forward the     packet to the outgoing interface SEND_TO_RP   Send the entire packet to the Route Processor5.2 MPLS Receive Processing If interface is of type ATM and VCC is of type MPLS_ENC     Use VPI,VCI to create ILM Index Else   Extract generic label from shim and create ILM Index End Extract TTL from top shim Extract EXP from top shim Extract S bit from top shim Decrement TTL If TTL <= 0 Execute opcode SEND_RP Using ILM Index to lookup ILM Entry Execute opcode from ILM Entry5.3 MPLS FTN Detailsstruct mpls_ftn {  struct mpls_nhlfe *nhlfe;  };5.4 MPLS NHLFE Details-The NHLFE is located on the tx interface.  Therefor the NHLFE Entry doesn't need to store the outgoing interface. struct mpls_nhlfe {  struct mpls_label **label;  u8 number_of_label;  struct sockaddr_un next_hop;  u8 exp;};5.5 MPLS Transmit Processing If the route entry that the FTN point to is a NHLFE or the ILM refers to a NHLFE then the following processing pertains.  If the shim with an S bit on was POPed on ingress then    make sure to add an S bit to the bottom shim  For each label in the NHLFE    If more labels can be added      If the label is of type ATM then        create a NULL shim and add it to the packet        make sure the shim with the S bit is on the bottom of the stack        extract VCC info from the ATM label        mark this packet will leave via this ATM VCC        mark that no more labels can be added.      Else        create a shim from the generic label and add it to the packet        make sure the shim with the S bit is on the bottom of the stack      End    End  End  Forward the packet to the next hop stored in the NHLFE