draft-deoliveira-diff-te-preemption-00.txt                  February, 2003

                                                  Jaudelice C. de Oliveira
                                                          Leonardo C. Chen
                                                          Caterina Scoglio
                                                           Ian F. Akyildiz
                                           Georgia Institute of Technology

IETF Internet Draft
Expires: August, 2003
February, 2003


                        LSP Preemption policies for
                 Diff-Serv-aware MPLS Traffic Engineering

Status of this Memo

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026. Internet-Drafts are
Working documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups.  Note that other groups may also
distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
The list of Internet-Draft Shadow Directories can be accessed at


When the establishment of a higher priority LSP requires the preemption
of a set of lower priority LSPs, the node has to make a local decision
on the set of preemptable LSPs and select which LSPs will be preempted,
based on a certain objective, in order to accomodate the newly signaled
high priority LSP. The preempted LSPs are then rerouted. This draft
documents a preemption policy which can be modified in order to stress
different objectives: preempt the lowest priority LSPs, preempt the
minimum number of LSPs, preempt the exact required bandwidth in order
to fit the new LSP.

 de Oliveira, Chen, Scoglio, and Akyildiz                                1

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

1. Motivation

Work is currently ongoing in the IETF Traffic Engineering Working Group to
define the requirements and protocol extensions for DiffServ-aware MPLS
Traffic Engineering (DS-TE) [DSTE-REQ,DSTE-PROTO]. Several Bandwidth
Constraint models for use with DS-TE have been proposed [BC-RD,BC-MAM,
BC-MAR] and their performance was analized with respect to the use of
preemption. Recently, a non-disruptive rerouting mechanism for preempted
TE LSPs was proposed in [SOFT-PREPT].

Preemption can be used to assure that high priority LSPs can be always
routed through relatively favorable paths within a differentiated services
environment. In the same context, preemption can be used to implement
various prioritized access policies as well as restoration policies
following fault events [TE-REQ].

Although not a mandatory attribute in the traditional IP world, preemption
becomes indeed a more attractive strategy in a Differentiated Services
scenario [DEC-PREP,ATM-PREP]. Nevertheless, in the DS-TE approach, whose
issues and requirements are discussed in [DSTE-REQ], the preemption policy
is considered an important piece on the bandwidth reservation and
management puzzle, but no preemption strategy is defined.

This draft proposes a flexible preemption policy that can be adjusted in
order to stress the desired preemption criteria: priority of LSPs to be
preempted, number of LSPs to be preempted, and amount of bandwidth
preempted. The implications (cascading effect, bandwidth wastage, priority
of preempted LSPs) of selecting a certain order of importance for the
criteria are discussed.

2. Introduction

In [TE-REQ], issues and requirements for Traffic Engineering in an MPLS
network are highlighted. In order to address both traffic oriented and
resource oriented performance objectives, the authors point out the need
for *priority* and *preemption* parameters as Traffic Engineering
attributes of traffic trunks. The notion of preemption and preemption
priority is defined in [TEWG-FW], and preemption attributes are defined in

A *traffic trunk* is defined as an aggregate of traffic flows belonging to
the same class which are placed inside an LSP [DSTE-REQ]. In this context,
preemption is the act of selecting an LSP which will be removed from a
given path in order to give room to another LSP with a higher priority.
More specifically, the *preemption attributes* determine whether an LSP
with a certain *setup preemption priority* can preempt another LSP with a
lower *holding preemption priority* from a given path, when there is a
competition for available resources.  The preempted LSP may then be
rerouted and soft preemption [SOFT-PREPT] can be used to avoid service

For readability a number of definitions from [DSTE-REQ] are repeated here:

 de Oliveira, Chen, Scoglio, and Akyildiz                                2

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

Class-Type (CT): the set of Traffic Trunks crossing a link that is
governed by a specific set of Bandwidth constraints. CT is used for the
purposes of link bandwidth allocation, constraint based routing and
admission control. A given Traffic Trunk belongs to the same CT on all

TE-Class: A pair of:
           i. a Class-Type
          ii. a preemption priority allowed for that Class-Type. This
              means that an LSP transporting a Traffic Trunk from
              that Class-Type can use that preemption priority as the
              set-up priority, as the holding priority or both.

By definition there may be more than one TE-Class using the same CT, as
long as each TE-Class uses a different preemption priority. Also, there
may be more than one TE-Class with the same preemption priority, provided
that each TE-Class uses a different CT. The network administrator may
define the TE-Classes in order to support preemption across CTs, to avoid
preemption within a certain CT, or to avoid preemption completely, when so
desired.  To ensure coherent operation, the same TE-Classes must be
configured in every Label Switched Router (LSR) in the DS-TE domain.

As a consequence of a per-TE-Class treatment, the Interior Gateway
Protocol (IGP) needs to advertise separate Traffic Engineering information
for each TE-Class, which consists of the *Unreserved Bandwidth* (UB)
information [DSTE-PROTO]. The UB information will be used by the routers,
checking against the bandwidth constraint model parameters, to decide
whether preemption is needed. Details on how to calculate the UB are given

3. LSP Setup Procedure and Preemption

A new LSP setup request has two important parameters: bandwidth and
preemption priority. In order to minimize wastage, the set of LSPs to be
preempted can be selected by optimizing an objective function that
represents these two parameters, and the number of LSPs to be preempted.
More specifically, the objective function could be any or a combination of
the following [DEC-PREP,ATM-PREP]:

* Preempt the connections that have the least priority (preemption
priority). The QoS of high priority traffics would be better satisfied.
* Preempt the least number of LSPs. The number of LSPs that need to be
rerouted would be lower.
* Preempt the least amount of bandwidth that still satisfies the request.
Resource utilization would be better.

After the preemption selection phase is finished, the selected LSPs must
be torn down (and possibly rerouted), releasing the reserved bandwidth.
The new LSP is established, using the currently available bandwidth. The
UB information is then updated. Fig. 1 shows a flowchart that summarizes
how each LSP setup request is treated in a preemption enabled scenario.

 de Oliveira, Chen, Scoglio, and Akyildiz                                3

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

  LSP Setup Request
  (TE-Class i, bw=r)

          v            NO
UB[TE-Class i] >= r ? ----> Reject LSP
          v            NO
 Preemption Needed ?  ----> Setup LSP/
                           Reroute LSPs
          |                 Update UB
          |YES                 ^
          |                    |
          v                    |
      Preemption ---------------

Fig. 1: Flowchart for LSP setup procedure.

In [DEC-PREP], the authors propose connection preemption policies that
optimize the discussed criteria in a given order of importance:  number of
connections, bandwidth, and priority; and bandwidth, priority, and number
of connections. The novelty in our approach is to propose an objective
function that can be adjusted by the service provider in order to stress
the desired criteria. No particular criteria order is enforced.

4. Preemption Policy

4.1. Preempting Resources on a Path

It is important to note that once a request for an LSP setup arrives, the
routers on the path to be taken by the new LSP need to check for bandwidth
availability in all links that compose the path. For the links in which
the available bandwidth is not enough, the preemption policy needs to be
activated in order to guarantee the end-to-end bandwidth reservation for
the new LSP. This is a decentralized approach, in which every node on the
path would be responsible to run the preemption algorithm and determine
which LSPs would be preempted in order to fit the new request. A
decentralized approach may sometimes not lead to an optimal solution.

In another approach, a *manager entity* runs the preemption policy and
determines the best LSPs to be preempted in order to free the required
bandwidth in all the links that compose the path. A unique LSP may be
already set in between several nodes on that path, and the preemption of
that LSP would free the required bandwidth in many links that compose the

 de Oliveira, Chen, Scoglio, and Akyildiz                                4

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

Both centralized and decentralized approaches have its advantages and
drawbacks. A centralized approach would be more precise, but requires that
the whole network state be stored and updated accordingly, which raises
scalability issues. In a network where LSPs are mostly static, an off-line
decision can be made to reroute LSPs and the centralized approach could be
appropriate. However, in a dynamic network in which LSPs are setup and
torn down in a frequent manner, the correctness of the stored network
state could be questionable. In this scenario, the decentralized approach
would bring more benefits, even when resulting in a non-optimal solution.
A distributed approach is also easier to be implemented due to the
distributed nature of the current Internet protocols.

Since the current Internet routing protocols are essentially distributed,
a decentralized approach was selected for the LSP preemption policy.  The
parameters required by the new preemption policies are currently available
for protocols such as OSPF or are easy to be determined.

4.2. Preemption Algorithm (Heuristic)

Consider a request for a new LSP setup with bandwidth b and setup
preemption priority p. When preemption is needed, due to lack of available
resources, the preemptable LSPs will be chosen among the ones with lower
holding preemption priority (higher numerical value) in order to fit
r=b-Abw(l).  The constant r represents the actual bandwidth that needs to
be preempted (the requested, b, minus the available bandwidth on link l:

Without loss of generality, we assume that bandwidth is available in
bandwidth modules, which implies that variables such as r and b are

Define L as the set of active LSPs having a holding preemption priority
lower (numerically higher) than p.
b(l) is the bandwidth reserved by LSP l in L, expressed in bandwidth
modules and p(l) is the holding preemption priority of LSP l.

In order to represent a cost for each preemption priority, we define an
associated cost y(l) inversely related to the holding preemption priority
p(l). For simplicity, we choose a linear relation y(l)=8-p(l). We define y
as a cost vector with L components, y(l). We also define b as a reserved
bandwidth vector with dimension L, and components b(l).

Concerning the objective function, as reported in the previous section,
three main objectives can be reached in the selection of preempted LSPs:

* minimize the priority of preempted LSPs,
* minimize the number of preempted LSPs,
* minimize the preempted bandwidth.

To have the widest choice on the overall objective that each service
provider needs to achieve, we define the following equation,
which for simplicity is chosen as a weighted sum of the above mentioned

H(l)= alpha y(l) + beta + gamma (b(l)-r)^2

 de Oliveira, Chen, Scoglio, and Akyildiz                                5

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

In this equation, alpha y(l) represents the cost of preempting LSP l, beta
represents the choice of a minimum number of LSPs to be preempted in order
to fit the request r, and gamma (b(l)-r)^2 penalizes a choice of an LSP to
be preempted that would result in high bandwidth wastage. Coefficients
alpha, beta, and gamma are suitable weights that can be configured in
order to stress the importance of each component in H.

In the heuristic, H is calculated for each LSP. The LSPs to be preempted
are chosen as the ones with smaller H that add enough bandwidth to
accommodate r. The respective components in the vector z are made equal
to one for the selected LSPs.

In case H contained repeated values, the sequence of choice follows the
bandwidth b reserved for each of the regarded LSPs, in increasing order.
For each LSP with repeated H, we test whether the bandwidth b assigned to
that LSP only is enough to satisfy r. If there is no such LSP, we test
whether the bandwidth of each of those LSPs, added to the previously
preempted LSPs' bandwidth is enough to satisfy r. If that is not true for
any LSP in that repeated H value sequence, we preempt the LSP that has the
larger amount of bandwidth in the sequence, and keep preempting in
decreasing order of b until r is satisfied or the sequence is finished. If
the sequence is finished and r is not satisfied, we again select LSPs to
be preempted based on an increasing order of H. More details on the
algorithm to implement the policy's heuristic are given in [PREEMPTION].

After finishing, the algorithm contains the information about which LSPs
are to be preempted and the amount of bandwidth

5. Examples

5.1. Static Case

Consider a link with 16 LSPs with reserved bandwidth b in Mbps, preemption
holding priority p, and cost y, as shown in Table 1. In this example,
8 TE-Classes are active. The preemption here is being performed in a single
link as an illustrative example.

LSP              l1   l2   l3   l4   l5   l6   l7   l8
Bandwidth (b)    20   10   60   25   20    1   75   45
Priority  (p)     1    2    3    4    5    6    7    5
Cost      (y)     7    6    5    4    3    2    1    3
LSP              l9  l10  l11  l12  l13  l14  l15  l16
Bandwidth (b)   100    5   40   85   50   20   70   25
Priority  (p)     3    6   4     5    2    3    4    7
Cost      (y)     5    2   4     3    6    5    4    1
Table 1: LSPs for static case.

 de Oliveira, Chen, Scoglio, and Akyildiz                                7

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

Suppose the network operator decides to configure beta=0, indicating that
the number of LSPs preempted is not important (rerouting is allowed and
not expensive: small topology), alpha=1 and gamma=1, indicating that
preemption priority and preempted bandwidth are more important.

A request for an LSP establishment arrives with r=155 Mbps and p=0
(highest possible priority, which implies that all LSPs with p>0 in Table
1 will be considered when running the algorithms). Using an optimization
tool to solve the above optimization problem, one will find that LSPs l8,
l12, and l16 are selected for preemption.

Suppose the network operator decides that it is more appropriate to
configure alpha=1, beta=1, and gamma=0, because in this network rerouting
is now cheaper, LSP priority is again very important, but bandwidth is not
a critical issue. In this case, LSPs l7 and l12 are selected for

To take into account the number of LSPs preempted, the preemption
priority, and the amount of bandwidth preempted, the network operator may
set alpha=beta=gamma=1. In that case, LSPs l12 and l15 are selected.

From the above example, it can be observed that when the number of LSPs
preempted was not an issue, 3 LSPs adding exactly the requested bandwidth,
and with the lowest priority were selected. When a possible waste of
bandwidth was not an issue, 2 LSPs were selected, adding more bandwidth
than requested, but with lower preemption priority.  Considering the three
factors as crucial, 2 LSPs are preempted, and in this case adding exactly
155 Mbps with the lowest possible preemption priorities.

If a balance amongst the three objectives is sought, the coefficients
alpha, beta, and gamma need to be configured in a proper manner. In the
example, alpha is multiplying a term that could be any value between 1 and
sum(y) (1 and 60), beta is multiplying a number between 1 and L (total
number of LSPs in the link:  1 and 16), and gamma is multiplying a number
between min(b) and sum(b) (1 and 651). It is very likely that neither the
number multiplied by alpha nor the number multiplied by beta will be large
when compared to the number multiplied by gamma, which will be of the
order of r.  Depending on the value of r, the gamma factor in the
objective function can be quite large when compared to the other two
terms. As an example, assume a request arrives for an LSP requesting r=90.
If only priority is selected as the most important criteria (alpha=1,
beta=gamma=0), LSPs l7 and l16 would be selected for preemption.

When number of preempted LSPs would be the criteria of consideration (beta=1,
alpha=gamma=0), LSP l9 would be selected, releasing 100 Mbps. If bandwidth
is the only important criteria, LSPs l5 and l15 could be selected, adding
exactly 90 Mbps. Following our previous analysis, the coefficients could
be selected as follows, when a balance is sought: alpha=1, beta=1 and
gamma=0.01. In that case, two LSPs would be selected for preemption, LSPs
l7 and l16, adding 100 Mbps, but both with the least priority. The
sensitivity of the objective function to the coefficients was analyzed,
and it was determined that, in this case, the same LSPs were selected for
preemption when alpha >= 0.35, beta leq 3, and gamma leq 0.3.

 de Oliveira, Chen, Scoglio, and Akyildiz                                8

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

5.2. Dynamic Case

 |          | \          |
 |          |  \         |
 |          |   \        |
 |          |    \       |
 |  R08----R09---R06----R02
 |          |     | \    |
 |          |     |  \   |
 |          |     |   \  |
 |          |     |    \ |

Fig 2. Network topology for the examples.

In the network depicted above in figure 2, suppose:  Each link has 100Mbps
of bandwidth. Source and destination for each LSP setup request
are selected randomly (uniform distribution).  Bandwidth request for each
LSP is randomly selected from 2, 4, 6, 8, or 10 Mbps. LSP setup requests
have 50% chance of being of priority 7 (lower), 20% of being 6, and 6%
each of being priorities 1-5. LSP setup requests arrive according to a
Poisson process with interarrival average rate 2 seconds and holding time
exponentially distributed with mean 500 seconds.

Experiments were run for the preemption policy with different values of
alpha, beta, and gamma, and for a total of 3980 LSP setup requests.

The cascading effect is defined in the following manner: when an LSP is
preempted and rerouted without causing any further preemption, the cascading
is said to be of level 0. However, when a preempted LSP is rerouted and
in order to be established in the new route it also causes the preemption
of other LSPs, the cascading is said to be of level 1, and so on.

Considering the priority of LSPs as the most important parameter (alpha=1,
beta=gamma=0), 7% of the LSP setup requests were immediately rejected.
8% of the LSPs were preempted and 74% of those were succesfully rerouted.
Cascading did not exceed level 1. 83.8% of the preemption affected only a single
LSP, 12.5% affected 2, 3.4% affected 3 LSPs, and 0.3% preempted 4 LSPs.

With number of preempted LSPs as the criteria of most importance
(alpha=0,beta=1,gamma=0), 7% of the LSP setup requests were immediately rejected.
10% of the LSPs were preempted and 80% of those were succesfully rerouted.
Cascading did not exceed level 2. 84.4% of the preemption affected only a single
LSP, 14.4% affected 2, and 1.2% affected 3 LSPs.

When wasted bandwidth was the considered criterion (alpha=beta=0,
gamma=1), 7% of the LSP setup requests were immediately rejected.
10% of the LSPs were preempted and 78% of those were succesfully rerouted.
Cascading did not exceed level 2. 84.1% of the preemption affected only a
single LSP, 14.1% affected 2, and 1.8% affected 3 LSPs.

 de Oliveira, Chen, Scoglio, and Akyildiz                                9

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003

Combining the parameters to build more complex policies is also being
studied. When the priority and the number of LSPs are considered
(alpha=beta=1, gamma=0), the same results as the first case were obtained
(alpha=1, beta=gamma=0).

If priority and wasted bandwidth were considered the most important
(alpha=1, beta=0, gamma=1), 8% of the LSP setup requests were immediately
rejected.  9% of the LSPs were preempted and 78% of those were succesfully
rerouted.  Cascading did not exceed level 2. 84.1% of the preemption
affected only a single LSP, 14.0% affected 2, 1.6% affected 3 LSPs and
0.3% affected 5 LSPs.

Finally, when the number of LSPs and the wasted bandwidth were the
considered criterion (alpha=0. beta=gamma=1), 7% of the LSP setup requests
were immediately rejected.  10% of the LSPs were preempted and 78% of
those were succesfully rerouted.  Cascading did not exceed level 2. 84.1%
of the preemption affected only a single LSP, 14.1% affected 2 and 1.8%
affected 3 LSPs.

9. Security Considerations

The practice described in this draft does not raise specific security
issues beyond those of existing TE.

10. Acknowledgment

The authors would like to thank George Uhl (Swales Aerospace) and
Jeff Smith (NASA Goddard) for their valuable comments.

 de Oliveira, Chen, Scoglio, and Akyildiz                               10

draft-deOliveira-diff-te-preemption-00.txt                  February, 2003


[DSTE-REQ] F. Le Faucheur and W. Lai, "Requirements for support of
Diff-Serv-aware MPLS Traffic Engineering," draft-ietf-tewg-diff-te-
reqts-06.txt, September 2002.

[DSTE-PROTO] F. Le Faucheur, "Protocol extensions for support of
Diff-Serv-aware MPLS Traffic Engineering," draft-ietf-tewg-diff-te-
proto-02.txt, October 2002.

[BC-RD] F. Le Faucheur, "Russian Dolls Bandwidth Constraints Model for
Diff-Serv-aware MPLS Traffic Engineering," draft-ietf-tewg-diff-te-
russian-00.txt, October 2002.

[BC-MAM] W. Lai, "Bandwidth Constraint Models for Diffserv-aware MPLS
Traffic Engineering," draft-wlai-tewg-bcmodel-00.txt, June 2002.

[BC-MAR] J. Ash, "Max Allocation with Reservation BW Constraint Model for
MPLS/DiffServ TE," draft-ash-mpls-dste-bcmodel-max-alloc-resv-00.txt,
November, 2002.

[SOFT-PREPT] M. R. Meyer, D. Maddux, and J.-P. Vasseur, "MPLS Traffic
Engineering Soft preemption," draft-meyer-mpls-soft-preemption-00.txt,
February, 2003.

[TEWG-FW] Awduche et al, "Overview and Principles of Internet Traffic
Engineering," RFC3272, May 2002.

[TE-REQ] Awduche et al, "Requirements for Traffic Engineering over MPLS,"
RFC2702, September 1999.

[DEC-PREP] M. Peyravian and A. D. Kshemkalyani, "Decentralized Network
Connection Preemption Algorithms," Computer Networks and ISDN Systems,
vol. 30 (11), pp. 1029-1043, June 1998.

[ATM-PREP] S. Poretsky and T. Gannon, "An Algorithm for Connection
Precedence and Preemption in Asynchronous Transfer Mode (ATM) Networks,"
Proceedings of IEEE ICC 1998.

[PREEMPTION] J. C. de Oliveira et al, "A New Preemption Policy for
DiffServ-Aware Traffic Engineering to Minimize Rerouting," Proceedings
of INFOCOM 2002.

Jaudelice C. de Oliveira
Broadband & Wireless Networking Laboratory
Georgia Institute of Technology
250 14th St. NW Room 556
Atlanta, GA 30318
Email: jau@ece.gatech.edu

Leonardo C. Chen
Broadband & Wireless Networking Laboratory
Georgia Institute of Technology
250 14th St. NW Room 556
Atlanta, GA 30318
Email: leochen@ece.gatech.edu

Caterina Scoglio
Broadband & Wireless Networking Laboratory
Georgia Institute of Technology
250 14th St. NW Room 556
Atlanta, GA 30318
Email: caterina@ece.gatech.edu

Ian F. Akyildiz
Broadband & Wireless Networking Laboratory
Georgia Institute of Technology
250 14th St. NW Room 556
Atlanta, GA 30318
Email: ian@ece.gatech.edu

Full Copyright Statement

   Copyright (C) The Internet Society (2002). All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain
   it or assist in its implementation may be prepared, copied,
   published and distributed, in whole or in part, without restriction
   of any kind, provided that the above copyright notice and this
   paragraph are included on all such copies and derivative
   works. However, this document itself may not be modified in any
   way, such as by removing the copyright notice or references to the
   Internet Society or other Internet organizations, except as needed
   for the purpose of developing Internet standards in which case the
   procedures for copyrights defined in the Internet Standards process
   must be followed, or as required to translate it into languages
   other than English. The limited permissions granted above are
   perpetual and will not be revoked by the Internet Society or its
   successors or assigns.
   This document and the information contained herein is provided on an