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 http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract 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 [TE-REQ]. 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 disruption. 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 links. 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 in [DSTE-PROTO]. 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 Setup | |YES | v NO Preemption Needed ? ----> Setup LSP/ Reroute LSPs | Update UB |YES ^ | | v | Preemption --------------- Algorithm 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 path. 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: Abw(l)). Without loss of generality, we assume that bandwidth is available in bandwidth modules, which implies that variables such as r and b are integers. 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 criteria: 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 preempted. 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 preemption. 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 R04--------R05----------R01 | | \ | | | \ | | | \ | | | \ | | R08----R09---R06----R02 | | | \ | | | | \ | | | | \ | | | | \ | R11--------R10---R07----R03 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 References [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 USA 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 USA Email: leochen@ece.gatech.edu Caterina Scoglio Broadband & Wireless Networking Laboratory Georgia Institute of Technology 250 14th St. NW Room 556 Atlanta, GA 30318 USA 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 USA 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 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.