mpls-forwarding-basics-00.txt

基于linux内核2.6.9的mpls补丁

PUBLIC DOCUMENT                                                 James R. Leu
May 24 2000

                          MPLS Forwarding Basics

1. MPLS Summary

The goal of Multi-Protocol Label Switching (MPLS) is to remove the process of
layer three lookups at each hop of a network.  This has many direct affects.
MPLS forwarding makes traffic engineering a more viable solution for network
congestion.  MPLS forwarding _may_ enable wire speed routing (switching).
MPLS forward _could_ allow network hardware vendors to make cheaper trunk
cards that ONLY understand labeled packets.  MPLS abstracts the media specific
qualities away from more complex network engineering (QoS, CoS, DiffServ).
MPLS forwarding can be used to make VPN service more flexible and deployable
without compromising the performance of your edge routers (switches).  In
addition to the above, the concepts used to to setup MPLS forwarding are
the 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 into
labeled MPLS forwarding.  This process entails the adding of a label to the
head of the packet.  Second, a (now labeled) packet much be able to traverse
an MPLS path.  This path consist of all the devices that know how this
particular packet (and packets like it) need to traverse a network.  This
path is called a Label Switch Path (LSP).  It is a connection oriented path
that is setup ahead of the forwarding of any packets.  Finally a packet must
make its way back into layer 3 forwarding.  This process consists of removing
the label from the head of the packet and then sending it to the appropriate
layer 3 protocol for additional handling.  In an MPLS enabled network, layer
3 forwarding is used by the edges of the network, and MPLS forwarding is used
in the core of the network.

A network device that acts as the boundary between layer 3 forwarding and
MPLS forwarding is called a Label Edge Router (LER).  An LER has the ability
to add a label to a unlabeled packet, and remove the labels from a labeled
packet. An LER that adds a label to a packet, is called an ingress LER and
an LER that removes the label from a packet is a egress LER.  A network device
that can forward a labeled packet (still labeled with possibly a different
label) is called a Label Switch Router.  The process of forwarding a labeled
packet is commonly referred to a Label Switching, because it mimics the ideas
of Ethernet or ATM switching.  Sometimes this is also called Label Swapping
because the value of the label may change at each hop in a LSP.  So the LSR
is "swapping" the labels in the packet.

2. MPLS Labels

When 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 header
and layer 2 header.  Therefore an IP packet on Ethernet would add the shim
before the IP header but after the Ethernet header.  MPLS forwarding is
currently defined for the following layer 2 implementation:  Ethernet, packet
over SONET, ATM, frame-relay.  MPLS has also been defined for any medium that
PPP runs on top of.  On _most_ of these layer 2 implementation a label consists
of a 20 bit number.

The shim that is added to the packet contains more then just a label.  Here
is 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 a
packet will be label switched.  The next 3 bits are called the EXP bits.  They
are currently reserved for experimental purposes.  (although DiffServ over
MPLS 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 to
the packet a LSR needs to know if what follows this top shim is the layer
3 header or another shim (Multiple shims are called a label stack.  The purpose
of a label stack will be explained later).  The S bit signifies that what
follows 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 though
an LSR cannot use the layer 3 header.  Some examples of these are traceroute,
loop detection, and multicast domains.

2.1 MPLS Label Stacking

When an LER adds a shim to a packet, it is feasible that is can add more then
one shim.  This concept is called Label Stacking.  The _stack_ of shims is
treated just as it's name sake data structure.  A POP means that the top shim
is removed, exposing either another shim or the layer 3 header (determined
by the S bit).  A PUSH adds a new shim to the top of the stack or on top
of the layer 3 header. So standard label swapping is defined as a POP
followed by a PUSH.  In some cases a labeled packet may need to be tunneled
across another MPLS network.  In the case the labeled packet gets another
shim pushed on top without POPing the original shim off.  This results in a
label stack of size 2.  This operation can occur multiple time by separate
LSRs or a single LSR could add more then one shim. In general any labeled
packet has a label stack, although most have a label stack of size 1. As one
may expect a packet with a label stack greater then 1 may _shrink_ in size
as well.  This operation would be defined by a POP without a PUSH.  The exact
details of how this occurs will be explained later.

3 MPLS Data Structures

For MPLS forwarding to occur correctly some data structures need to exist
to assist in the interpretation of labels and the processing of them.
In general there exists three data structure. One data structure to help
interpret incoming labels (labels from packets that are entering an LSR or
egress 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 data
structure 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 incoming
labels is called the Incoming Label Map (ILM).  The ILM table consists
of 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 to
an outgoing data structure.  The general order of operation for incoming label
processing 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 label

Detail ILM processing will be explained later.

As stated earlier there also exists a data structure to assist with outgoing
labeling.  The common name for this data structure is the Next Hop Label
Entry (NHLFE).  The NHLFE table consists of all the labels which can be push
onto packets.  Each NHLFE entry contains: label, outgoing interface, and nexthop
information.  The general processing that occurs when a packet reaches the
NHLFE table is:

-form new shim that contains the label
-push the shim onto the packet
-forward the packet to the nexthop via the
 outgoing interface

Details of NHLFE processing will be explained later.

A third data structure exists for the sole purpose of helping ingress LERs decide
what labels to add to a packet.  For the explanation of this data structure we
need 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 adding
and removing labels.  How do we know what label to add to a packet?  How do we
know what type of packet I have after removing a label?

In general packets are labeled according to which FEC they belong to.  For
example I am defined FEC A to be the class of packet that are heading to
the host with IP address 1.1.1.1.  Therefore all packets that have a destination
IP address 1.1.1.1 belong to FEC A.  In MPLS we assign each FEC a label and
each label refers to a FEC (1:1 mapping).  The definitions of FECs may change
but the 1:1 mapping should always stay constant.  The data structure used to
map FECs to labels is called a FEC To NHLFE (FTN).  An FTN table consists of
all 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 FTN

Detail FTN processing will be explained later.

4. MPLS over ATM

Earlier the statement was made that labels are 20 bits values for _most_
layer 2 implementations.  ATM is one of the exceptions (Frame relay is the
other).  Since ATM is already built upon switching technology it can take
advantage 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 already
does.  This provides a nice optimization, but introduces problems and
complexity.  In "normal" MPLS forwarding we look inside to the top shim
to 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 functionality
they provide when running MPLS over ATM?  To retain the functionality we need
to make a couple of compromises.  First, even though we can do MPLS forward
via VPI,VCI pairs and we do not need the shim to store the label, we will still
keep 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 if
we doing "normal" MPLS forwarding.  Due to the nature of ATM switching, these
values will pass through the ATM network untouched.  When the packet leaves
the ATM network and either goes back to layer 3, or move on to "normal" MPLS
forwarding these values will be available for use at that time.  MPLS forwarding
over 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 Details

struct 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		0x07


5.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 Processor

5.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 Entry

5.3 MPLS FTN Details

struct 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