Prev TOP NEXT
Network Layer Routing
Basic Movement in Conventional IP Paradigm
Introduction to MPLS
MPLS forms an intermediate layer between the network layer and the data link layer i.e. it hypothetically resides between Layer 2 and Layer 3 of the OSI Reference Model. It is multiprotocol as it is independent of overlaying network layer and underlying link layer protocols.
Enhanced to interoperate with MPLS shim.
MPLS Shim Layer
Fig2.1 OSI Model and MPLS
MPLS is a packet forwarding mechanism independent of routing protocol, thus conveniently isolating the data plane from the control plane.
2.1 Network Layer Routing
The network layer routing can be functionally decomposed into the data plane and the control plane. The data plane (forwarding component) is responsible for the actual forwarding of packets from input to output across a switch or router, whereas the forwarding table maintained by router and information carried in packet header is used to forward the packets to the next hop. It consists of a set of procedures/algorithms that a router uses to make a forwarding decision on the packet. The algorithms used, define the information from the packet that a router uses to find a particular entry in its forwarding table and also the exact procedures to be followed to find that entry.
The control component is responsible for the construction and maintenance of the forwarding table. It consists of one or more routing protocols that provide exchange of information amongst routers and also the procedures used by the router to convert that information into a forwarding table.
2.2 Basic Packet Movement in Conventional IP Paradigm
In the normal connectionless network layer protocol like IP, a packet travels from one router to the next. When a packet arrives at a router, it analyzes the packet header and runs some algorithms so as to make the next hop forwarding decision for the packet. This selection of next hop can be thought of as the composition of 2 functions.
1) Partitioning the entire set of possible packets that the router can forward into a set of Forwarding Equivalence Classes (FECs)
2) Mapping each FEC to a next hop
FEC can be defined as the partitioning the set of all possible packets that a router can forward into a finite number of disjoint subsets, where the packets within each subset are forwarded to the same next hop i.e. FEC is a group of packets sharing the same requirements for their transport.
So it can be said that if for any two packets arriving at a router, the router takes identical forwarding decisions for them, then the two packets can be said to be belonging to the same FEC. The router will usually take identical forwarding decisions for them if there exists some address prefix 'X' in that router's routing tables, such that 'X' is the "longest match" for each packet's destination address. In this way, as a packet traverses the network, each hop in turn will examine the packet header and assign it to a FEC. This implies a redundant mechanism.
2.3 Introduction to MPLS
Now if we bind a label with every FEC and forward the packets along the path using labels, we eliminate the redundancy of performing the same operation of network layer header lookup for each and every packet at each consecutive hop within the network. And this is precisely the basic principle/model over which MPLS has been developed.
LSR (Label Switching Router):
A router which performs label switching is known as a Label Switching Router (LSR). An MPLS node that is capable of forwarding native L3 packets.
LSP (Label Switching Path):
The path through one or more LSRs at one level of hierarchy followed by a packets in a particular FEC is known as Label Switched Path (LSP)
A label is a short, fixed length, locally significant identifier used to identify a FEC
FEC (Forwarding Equivalence Class):
A group of IP packets which are forwarded in the same manner (e.g. over the same path, with the same forwarding treatment). Subsets of packets are treated the same way if they belong to the same FEC. The concept of FEC provides a great deal of flexibility and scalability. In conventional routing, the packets are assigned a FEC at each hop (i.e. L3 lookup), in MPLS it is done only once at the network ingress.
LDP (Label Distribution Protocol):
The MPLS architecture defines a LDP as a set of procedures by which one LSR informs another of the meaning of labels used to forward traffic between and through them.
Two LSRs that exchange LDP messages amongst themselves.
MPLS Ingress LSR:
An LSR in it’s role as an entry point for a packet into the MPLS domain. The important task of Ingress LSR is to map the packet to a unique FEC (if one exists).
MPLS Egress LSR:
An LSR in it’s role as an exit point for a packet from the MPLS domain All the MPLS related layering information is removed at this stage.
E-LSR (Edge LSR):
An LSR that is either an ingress or egress LSR.
MultiProtocol Label Swtiching:
An IETF working group and the effort associated with the working group.
A contiguous set of nodes which operates MPLS routing and forwarding and which are also in one Routing or Administrative domain.
A node that is running MPLS. An MPLS node will be aware of MPLS control protocols, will operate one or more L3 routing protocols, and will be capable of forwarding packets based on labels. An MPLS node may optionally be also capable of forwarding native L3 packets.
Upstream and Downstream LSRs:
Suppose Ru and Rd have agreed to bind label L to FEC F, for packets sent from Ru to Rd. Then with respect to this binding, Ru is the “upstream LSR”, and Rd is the “downstream LSR”.
2.4 MPLS - Basics
MPLS uses the "label swapping" algorithm to forward packets. The packet forwarding in MPLS domain can be thought of as consisting of the following functions
1) Label creation and distribution
2) Table creation at each router
3) LSP creation
4) Label insertion and table lookup
5) Packet forwarding
Consider two LSRs Ru & Rd. Let them agree on a label binding of moving for FEC F for packets moving from Ru to Rd. When Ru receives packets belonging to FEC F, then it labels them with label L and sends the labeled packets to Rd.
Here Ru is called the upstream LSR and Rd is called the downstream LSR with respect to binding of label L to FEC F.
A label as defined in previous section is a locally significant identifier used to a FEC. The label which is put on a particular packet represents the FEC to which the packet is assigned. Usually a packet is assigned to a FEC based on its network layer destination address. However, the label is never an encoding of that address.
Fig2.3 Format of Label
2.4.2 Label Stack
Labels can be organized as a stack known as label stack. Thus instead of encoding a single label onto a packet, we can encode a label stack, which can contain more than a single label. This is useful in hierarchical operation and traffic engineering. The encoding technique to be used whether for a single label or a label stack must be agreed by both, the LSR that encodes the label and the label that decodes the label.
Actions to be performed on the Label
An LSR receives labeled traffic and forwards it after performing some action on the label. The different actions that can be performed on the label on receipt of a labeled packet are:
1) PUSH a label or a label stack onto the existing one.
2) POP a label from the label stack and forward the packet using the label underneath.
3) SWAP a label (i.e. replace the existing label with a new label by performing POP and PUSH operations respectively) and forward the packet using a new label.
2.4.3 Label Assignment and Distribution
The decision to bind a particular label to a particular FEC is made by the LSR, which is "downstream" with respect to that binding. Thus labels are "downstream assigned" and label bindings are distributed in the "downstream to upstream" direction.
Labels/Label bindings can be distributed by extending the existing routing protocols so that label distribution can be piggybacked on them. Or we can use Label Distribution Protocols (LDP), which have been defined solely for the purpose of label distribution. LDP is used to establish and maintain the label bindings between the LSRs. MPLS architecture does not assume a single label distribution protocol and a number of label distribution protocols are being standardized.
For our implementation we will be using LDP for label distribution and propagating route changes.
Labels distribution can be expedited in two fashions namely
1) downstream on demand
-where an LSR explicitly requests, from its next hop for a particular FEC, a label binding for that FEC.
2) Unsolicited downstream
- where an LSR is allowed to distribute label bindings to LSRs that have not explicitly requested them.
Both of these techniques may be used in the network at the same time. However, on any given label distribution adjacency, the upstream LSR must agree on which technique to be used.
In our implementation we’ll be using downstream on demand mode of operation.
2.4.4 Label Retention Mode
Any upstream LSR Ru may receive (or may have received) a label binding for a particular FEC from a downstream LSR Rd, even though Rd is not Ru's next hop ( or is no longer Ru's next hop ) for that FEC.
Ru then has the choice of whether to keep track the choice of whether to keep track of such bindings, or whether to discard such bindings. If Ru keeps track of such bindings, then it may immediately begin using the binding again if Rd eventually becomes its next hop for the FEC in question.
If Ru discards such bindings, then if Ru discards such bindings, then if Rd later becomes the next hop, the label binding will have to be required.
If LSR Ru maintains the bindings between the label and FEC, which it received from LSR Rd, then it is said to support " Liberal Label Retention Mode". If LSR Rd discards the bindings between the label and the FEC, which it received from LSR Rd, then it is said to support "Conservative Label Retention Mode"
Liberal Label Retention mode allows for quicker adaptation to routing changes. Conservative Label Retention mode requires an LSR to maintain fewer label bindings.
2.4.5 Label Switching Forwarding Table
Every LSR maintains an information base for keeping track of FEC-to -label bindings it receives from downstream LSRs. There are 2 such information bases maintained by the LSR, namely the Label Information Base (LIB) which is maintained in the control plane of a LSR and the Label Forwarding Information Base (LFIB) which is
maintained in the data plane of an LSR.
The LFIB maintains the list of label bindings it receives from downstream LSRs, which are currently the next hops for various respective FECs.
Likewise, the LIB also maintains the same list as maintained in the LFIB, in addition it may also maintains label bindings for FECs it receives from downstream LSRs and which may currently no longer be the next hops the LSR.
2.4.6 Invalid Incoming Labels
In the event that an LSR receives a labeled packet and still be unable to recognize the same, i.e. it has no binding for the label to a FEC, then the different scenarios that can be considered as to how the LSR will react would be as follows:
1) Firstly the label can be removed and the packet can be forwarded as an unlabeled IP packet. But doing so in some cases would cause a loop. If the upstream LSR thinks the label is bound to an explicit route, and the downstream LSR doesn't think the label is bound to anything and thus forwards it as an unlabeled IP packet, then if the routing of the unlabeled packet brings it back to the upstream LSR, then a loop is formed. ( In MPLS the next hop is obtained from the label switching information base, but, the next hop may be different if MPLS were not in use.)
2) Secondly, it is also possible that the label was intended to represent a route which cannot be inferred from the IP header.
3) And lastly, when a labeled packet is received with an invalid label, it must be discarded, unless it can be determined that forwarding it unlabeled cannot cause any harm.
Of all the above mentioned options, the last option is the safest. Thus if an invalid labeled packet is received by an LSR, it is discarded.
2.4.7 LSP Control
Labeled packets are forwarded through LSPs that have been set up from ingress LSR to egress LSR. The setup of these LSPs can be achieved either through
1) Independent LSP Control or
2) Ordered LSP Control
Independent LSP Control corresponds to the way that conventional IP routing works. Each LSR when it recognizes an FEC, makes an independent decision to bind a label to that FEC and distributes that binding to its label distribution peers. It then relies on the routing algorithm to converge rapidly so as to ensure that each datagram is correctly delivered.
In ordered LSP control, an LSR only binds a label to a particular FEC if it is an egress LSR for that FEC or has already received label binding for that FEC from its next hop for that FEC.
2.4.8 Route Selection
Selecting the route/LSP for a particular FEC can be done in either of the 2 ways
1) hop-by-hop routing
2) Explicit routing
In hop-by-hop routing, each node independently chooses the next hop for each FEC. This is similar to the manner in which existing IP networks select their next hop.
In explicit routing, the ingress LSR, i.e. the LSP ingress or the egress LSR, i.e. the LSP egress, specify the LSRs in the LSP. The LSP ingress or LSP egress may specify several or all of the LSRs in the LSP. If all the LSRs are specified, the LSP is a "strictly" explicitly routed LSP. If some LSRs are not specified, the LSP as a "loosely" explicitly routed LSP.
2.4.9 Time to Live (TTL)
In conventional IP forwarding, each packet carries a “Time To Live” (TTL) value in its header. Whenever a packet passes through a router, its TTL gets decremented by 1; if the TTL reaches 0 before the packet has reached its destination, the packet gets discarded. This provides some level of protection against forwarding loops that say exist due to misconfigurations, or due to failure or slow convergence of the routing algorithm. TTL is sometimes used for other functions as well, such as multicast scooping, and supporting the “traceroute” command. This implies that there are two TTL related issues that MPLS needs to deal with:
1) TTL as a way to suppress loops
2) TTL as a way to accomplish other functions, such as limiting the scope of a packet.
When a packet travels along an LSP, it SHOULD emerge with the same TTL value that it would have had if it had traversed the same sequence of routers without having been label switched. If the packet travels along a hierarchy of LSPs, the total number of LSR-hops traversed SHOULD be reflected in its TTL value when it emerges from the hierarchy of LSPs.
The label values are encoded in a “shim” that sits between the data link and network layer headers, then this shim MUST have a TTL field that SHOULD be initially loaded from the network layer header TTL field, SHOULD be decremented at each LSR-hop, and SHOULD be copied into the network layer header TTL field when the packet emerges from its LSP.
Prev TOP NEXT