RFC 4829
Label Switched Path (LSP) Preemption Policies for MPLS Traffic Engineering
RFC 4829: Label Switched Path (LSP) Preemption Policies for MPLS Traffic Engineering 🎀
Okay bestie, this one is from April 2007 and it's an Informational RFC from the Network Working Group. That means it's sharing info with the Internet community, not setting a standard. The authors are J. de Oliveira (Ed., Drexel University), JP. Vasseur (Ed., Cisco Systems, Inc.), L. Chen (Verizon Laboratories), and C. Scoglio (Kansas State University). The header doesn't list anything it obsoletes or updates. 💅✨
Status of This Memo 🌸
This memo gives info to the Internet community. It is not an Internet standard of any kind, and the distribution of this memo is unlimited. 🦋
Copyright Notice 💜
Copyright (C) The IETF Trust (2007).
IESG Note 🙈
This RFC is not a candidate for any level of Internet Standard. The IETF disclaims any knowledge of the fitness of this RFC for any purpose and, in particular, notes that the decision to publish is not based on IETF review for such things as security, congestion control, or inappropriate interaction with deployed protocols. The RFC Editor has chosen to publish this document at its discretion. Readers of this document should exercise caution in evaluating its value for implementation and deployment. See RFC 3932 for more information.
Abstract ✨
Okay so here's the situation. When a higher priority TE LSP (Traffic Engineering Label Switched Path) needs room, and that means kicking out a bunch of lower priority TE LSPs, a node has to make a local decision about which ones get bumped. The preempted LSPs then get rerouted by their own Head-end Label Switch Router (LSR). 🔥
This doc offers a flexible policy that can chase different goals: preempt the lowest priority LSPs, preempt the fewest LSPs, pick the TE LSPs whose bandwidth is closest to what the preempting TE LSP actually needs (so less bandwidth gets wasted), or preempt the LSPs most likely to get rerouted successfully. It also includes simulation results and compares the policies on preemption cascading, number of preempted LSPs, priority, wasted bandwidth, and blocking probability. Very thorough, very iconic. 💅
Table of Contents 🧚
1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. LSP Setup Procedure and Preemption . . . . . . . . . . . . . . 5
4. Preemption Cascading . . . . . . . . . . . . . . . . . . . . . 6
5. Preemption Heuristic . . . . . . . . . . . . . . . . . . . . . 7
5.1. Preempting Resources on a Path . . . . . . . . . . . . . . 7
5.2. Preemption Heuristic Algorithm . . . . . . . . . . . . . . 8
6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1. Simple Case: Single Link . . . . . . . . . . . . . . . . . 10
6.2. Network Case . . . . . . . . . . . . . . . . . . . . . . . 12
7. Security Considerations . . . . . . . . . . . . . . . . . . . 16
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16
9. Informative References . . . . . . . . . . . . . . . . . . . . 171. Motivation 🦋
Okay so the IETF Traffic Engineering Working Group already defined the requirements and protocol extensions for DiffServ-aware MPLS Traffic Engineering (DS-TE) in [RFC3564] [RFC4124]. Several Bandwidth Constraint models for use with DS-TE have been proposed in [RFC4127] [RFC4128] [RFC4126], and people analyzed how they perform when preemption is involved. 📊
Preemption is a tool that helps make sure high priority LSPs can always go through relatively favorable paths. It can also support prioritized access policies and restoration policies after fault events, as described in [RFC2702]. 🔥
Now, preemption isn't a must-have attribute in traditional IP land. But it gets important in networks that use online, distributed Constrained Shortest Path First (CSPF) strategies to compute TE LSP paths, because it helps limit the damage from bandwidth fragmentation. ✨ It's also a really attractive strategy in MPLS networks where traffic is treated differently and high-importance traffic gets special treatment over lower-importance traffic [DEC-PREP, ATM-PREP]. Here's the tea though: in DS-TE, which [RFC3564] talks through, the preemption policy is recognized as a key piece of the bandwidth reservation and management puzzle, yet no preemption strategy is actually defined. 🙈 Also, preemption matters in regular MPLS Traffic Engineering environments too, the ones with a single pool of bandwidth.
So this document proposes a flexible preemption policy. You can tune it to weigh different criteria: the priority of the LSPs being preempted, the number of LSPs being preempted, the amount of bandwidth preempted, and blocking probability. The doc also talks through what happens (cascading effects, bandwidth wastage, priority of preempted LSPs) when you pick a certain order of importance for these criteria, using the examples given. 💖
2. Introduction 🌈
Okay, background time. [RFC2702] highlights the issues and requirements for Traffic Engineering in an MPLS network. To handle both traffic-oriented and resource-oriented performance objectives, the authors point out that priority and preemption parameters are needed as Traffic Engineering attributes of traffic trunks. The notion of preemption and preemption priority is defined in [RFC3272], and preemption attributes are defined in [RFC2702] and [RFC3209]. 🧠
A traffic trunk is an aggregate of traffic flows that belong to the same class and get placed inside an LSP [RFC3564]. In this context, preemption is when you pick an LSP to remove from a given path so another LSP with a higher priority (lower preemption number) gets the room. More precisely, the preemption attributes decide whether an LSP with a certain setup preemption priority can preempt another LSP with a lower holding preemption priority from a given path, when they're competing for available resources. Competing for resources is one situation that can trigger preemption, but other situations can exist too, and a policy controls those. 💅
For readability, here are a few definitions repeated from [RFC3564]:
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. 🫶
Okay so there can be more than one TE-Class using the same CT, as long as each TE-Class uses a different preemption priority. There can also be more than one TE-Class with the same preemption priority, as long as each one uses a different CT. The network administrator can define the TE-Classes to support preemption across CTs, to avoid preemption within a certain CT, or to avoid preemption completely, whenever that's what they want. For coherent operation, the same TE-Classes must be configured in every Label Switched Router (LSR) in the DS-TE domain. 🔥
Because of the per-TE-Class treatment, the Interior Gateway Protocol (IGP) needs to advertise separate Traffic Engineering information for each TE-Class. That info consists of the Unreserved Bandwidth (UB) information [RFC4124]. The routers use the UB information, checked against the bandwidth constraint model parameters, to decide whether preemption is needed. The details on how to calculate the UB are given in [RFC4124]. 📡
3. LSP Setup Procedure and Preemption 🎀
Every new LSP setup request has two important parameters: bandwidth and preemption priority. The set of LSPs to be preempted can be picked by optimizing an objective function that represents these two parameters along with the number of LSPs to be preempted. Specifically, the objective function can be any one of the following criteria, or a combination of them [DEC-PREP, ATM-PREP]:
- Preempt the LSPs with the least priority (preemption priority). This makes the QoS of high priority traffic better, and it can limit the cascading effect described below.
- Preempt the least number of LSPs. Fewer LSPs have to be rerouted.
- Preempt the least amount of bandwidth that still satisfies the request. Resource utilization could improve. Preempting larger TE LSPs (more than requested) with the newly signaled TE LSP means more bandwidth has to be rerouted, which is likely to raise the blocking probability (the inability to find a path for some TE LSPs). 😭
- Preempt the LSPs that minimize the blocking probability (the risk that a preempted TE LSP can't be rerouted).
Once the preemption selection phase is done, the selected LSPs get signaled as preempted, and the new LSP gets established (if a new path satisfying the constraints can be found). The UB information then gets updated, either by flooding an IGP-TE update, by pruning the link where preemption happened, or both. Figure 1 is a flowchart that sums up how each LSP setup request gets handled in a preemption-enabled scenario. 🗺️
LSP Setup Request
(TE-Class i, bw=r)
|
|
v NO
UB[TE-Class i] >= r ? -------> Reject LSP
Setup and flood an updated IGP-TE
| LSA/LSP
|YES
v NO
Preemption Needed ? -------> Setup LSP/Update UB if a threshold is
| crossed
| YES
v
Preemption ----> Setup LSP/Reroute Preempted LSPs
Algorithm Update UB
Figure 1: Flowchart for LSP setup procedure.Now, in [DEC-PREP], the authors propose connection preemption policies that optimize the criteria in a given order of importance: number of LSPs, bandwidth, and priority; or bandwidth, priority, and number of LSPs. What's new in this approach is an objective function the service provider can adjust to stress whichever criteria they care about. No particular criteria order is enforced. There's also a brand new criterion added to the objective function: optimizing the blocking probability, so there's less risk that an LSP isn't rerouted after being preempted. That's a whole main character moment. 👑
- Preemption Cascading ✨
So okay, preempting one LSP can set off a chain reaction of other preemptions across the network. That's the preemption cascading effect, bestie 💥, and a single preempted LSP can end up causing different cascading levels. Here's how the levels work 🎀: if a preempted LSP gets rerouted and doesn't cause any further preemption, that's cascading level zero. But if the preempted LSP gets rerouted and, to get established on its new route, it has to preempt other LSPs, that's cascading level 1, and it keeps going from there, level 2, level 3, and so on 🌸.
Preemption cascading is NOT desirable, so policies that minimize it are super important 😭. Honestly it can cause severe network instabilities, which is giving chaos 💀. In Section 5, a new versatile preemption heuristic will be presented 🦋. In Section 6, the preemption simulation results will be discussed and the cascading effect will be analyzed 📊.
5. Preemption Heuristic 💖
5.1. Preempting Resources on a Path 🛤️
Okay, so this is the key bit 🔑: once a request for an LSP setup arrives, each LSR along the TE LSP path checks the available bandwidth on its outgoing link. For the links where there isn't enough available bandwidth, the preemption policy has to kick in so the end-to-end bandwidth reservation for the new LSP can be guaranteed 🫶. This is a distributed approach, where every node on the path runs the preemption algorithm and decides which LSPs to preempt to fit the new request. Real talk, a distributed approach may not lead to an optimal solution 🙈.
Alternatively, there's a centralized approach, where a manager entity runs the preemption policy and figures out the best LSPs to preempt to free up the required bandwidth on all the links that make up the path. The policy would try to pick LSPs that overlap with the path being considered. So preempting one LSP that overlaps with the route beats preempting a single LSP on every link of the route 🧚.
Both approaches have pros and cons ⚖️. A centralized approach is more precise, BUT it needs the whole network state stored and updated, and that raises scalability issues 😬. In a network where LSPs are mostly static, an offline decision can be made to reroute LSPs, and the centralized approach could be appropriate 🌈. However, in a dynamic network where LSPs get set up and torn down frequently because of new TE LSPs, bandwidth increases, reroutes due to failure, and so on, the correctness of the stored network state could be questionable 🤔. Plus, setup time is generally longer than with a distributed solution. In this scenario, the distributed approach brings more benefits, even if it gives a non-optimal solution (how much more optimal a centralized approach is depends on lots of factors: network topology, traffic matrix, TE strategy, and so on) 💅. A distributed approach is also easier to implement, thanks to the distributed nature of current Internet protocols 🌸.
Since the current Internet routing protocols are basically distributed, a decentralized approach was picked for the LSP preemption policy 🦋. The parameters the new preemption policies need are already available for OSPF and Intermediate System to Intermediate System (IS-IS) ✨.
5.2. Preemption Heuristic Algorithm 🧮
Let's say there's a request for a new LSP setup with bandwidth b and setup preemption priority p. When preemption is needed because there aren't enough available resources, the preemptable LSPs get chosen from the ones with a lower holding preemption priority (higher numerical value), in order to fit r=b-Abw(l). The variable r is the actual bandwidth that needs to be preempted: the requested bandwidth, b, minus the available bandwidth on link l, Abw(l) 💜.
L is the set of active LSPs with a holding preemption priority lower (numerically higher) than p, so L is the set of candidates for preemption 👑. b(l) is the bandwidth reserved by LSP l in L, expressed in bandwidth units, and p(l) is the holding preemption priority of LSP l 🎀.
To represent a cost for each preemption priority, there's an associated cost y(l) that's inversely related to the holding preemption priority p(l). For simplicity, the linear relation y(l)=8-p(l) is chosen 🍓. y is a cost vector with L components, y(l), and b is a reserved bandwidth vector with dimension L, with components b(l) 📊.
For the objective function, four main objectives can be reached when selecting preempted LSPs 🔥:
- minimize the priority of preempted LSPs,
- minimize the number of preempted LSPs,
- minimize the preempted bandwidth,
- minimize the blocking probability.
So each service provider can hit whatever overall objective it needs, the following equation was defined. For simplicity, it's a weighted sum of the criteria above 💖:
H(l)= alpha y(l) + beta 1/b(l) + gamma (b(l)-r)^2 + theta b(l)
In this equation:
- alpha y(l) captures the cost of preempting high priority LSPs.
- beta 1/b(l) penalizes preempting low bandwidth LSPs, capturing the cost of preempting a large number of LSPs.
- gamma (b(l)-r)^2 captures the cost of preempting LSPs that are much larger or much smaller than r.
- theta b(l) captures the cost of preempting large LSPs.
The coefficients alpha, beta, gamma, and theta can be chosen to emphasize one or more components of H 🫧.
The coefficient theta is defined such that theta = 0 if gamma > 0. That's because when you're trying to minimize the blocking probability of preempted LSPs, the heuristic prefers preempting several small LSPs. So gamma, the weight for minimizing preempted bandwidth (which pushes the selection toward LSPs with about the same bandwidth as the requested amount), needs to be set to zero 🙅♀️. Selecting several small LSPs in a normally loaded part of the network increases the chance that those LSPs get rerouted successfully 🦋. Also, selecting several small LSPs may not mean preempting much more than the required bandwidth, which keeps low-bandwidth wastage down, as you'll see in the discussed examples 🌷. When preemption happens in a heavily loaded part of the network, the heuristic selects fewer LSPs for preemption to increase the chance of rerouting 🚀.
H is calculated for each LSP in L. The LSPs to be preempted are the ones with the smaller H values that together add enough bandwidth to accommodate r. When sorting LSPs by H, LSPs with the same H value are ordered by bandwidth b, in increasing order. For each LSP with a repeated H, the algorithm checks whether the bandwidth b of that LSP alone is enough to satisfy r. If no single LSP does it, the algorithm checks whether adding each of those LSPs' bandwidth to the bandwidth of the previously preempted LSPs is enough to satisfy r. If that isn't true for any LSP in that repeated H-value sequence, the algorithm preempts the LSP with the larger bandwidth in the sequence, and keeps preempting in decreasing order of b until r is satisfied or the sequence runs out. If the sequence runs out and r still isn't satisfied, the algorithm selects LSPs to preempt again, based on increasing order of H. More details on the algorithm are given in [PREEMPTION] 🧠.
When the objective is to minimize blocking, the heuristic follows two options for calculating H:
- If the link where preemption is happening is normally loaded, several small LSPs get selected for preemption using H(l)= alpha y(l) + theta b(l) 🌿.
- If the link is overloaded, few LSPs get selected using H(l)= alpha y(l) + beta 1/b(l) 🚨.
Part 2 of 5. More to come, so stay tuned, bestie 💕.
6.1. Simple Case: Single Link ✨
Okay bestie, let's start with the simplest case: a path with just a single hop 💅. The goal here is just to show how the heuristic works. In the next section we'll get into something more complex, where the preemption policies get tested on a whole network 🦋
Picture a link with 16 LSPs. Each one has a reserved bandwidth b in Mbps, a preemption holding priority p, and a cost y. You can see all of them in Table 1. There are 8 TE-Classes active in this example, and the preemption happens on that one link, just as an illustration 🎀
------------------------------------------------------------------
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 in the considered link.Now a new LSP establishment request shows up with r=175 Mbps and p=0. That's the highest possible priority, which means every LSP in Table 1 with p>0 gets considered when the algorithm runs 👑 We're also assuming Abw(l)=0.
Okay so, if priority is the only thing the network operator cares about, they set alpha=1, beta=gamma=theta=0. Then LSPs L6, L7, L10, L12, and L16 get picked for preemption, which frees up 191 bandwidth units to set up the high-priority LSP 🔥 The fun part is that 5 LSPs got preempted, but they all had a priority between 5 and 7. So it's a pretty chill outcome, no cap.
Now imagine a network where rerouting is super expensive, and you want the number of rerouted TE LSPs to be as small as possible. In that case the operator might go with beta=1 and alpha=gamma=theta=0. Then LSPs L9 and L12 get selected, adding up to 185 bandwidth units. That's less wastage than the last case, which is a W 🍓 The selected LSPs have priorities 3 and 5, so they might end up preempting some other LSPs of their own once they get rerouted. Wild, I know 🌀
Let's say the operator decides it's better to set alpha=1, beta=10, gamma=0, theta=0. The parameters were chosen to balance the weight of each component in the cost function, namely priority and number. The reasoning is that rerouting is very expensive here, LSP priority matters a lot, but bandwidth isn't a critical issue. With this setup, LSPs L7, L12, and L16 get selected. That gives a smaller number of preempted LSPs than the first case, and the priority levels stay between 5 and 7 💖
If the operator wants to account for the number of LSPs preempted, the preemption priority, and the amount of bandwidth preempted all at once, they can set alpha > 0, beta > 0, and gamma > 0. To get the three components balanced, the parameters need to be normalized. The aim is balance, so the parameters could be set to alpha=1, beta=10 (which brings the term 1/b(l) closer to the other parameters), and gamma=0.001 (which brings the value of the term (b(l)-r)^2 closer to the other parameters). With that, LSPs L7 and L9 get selected for preemption. They free up exactly 175 bandwidth units, with priorities 3 and 7. Notice that fewer LSPs got preempted, but they have a higher priority, which may lead to a cascading effect 🌈
Last one: if minimizing the blocking probability is the thing you care about most, you configure the cost function with theta=1, alpha=beta=gamma=0. Now a bunch of small LSPs get selected: L2, L4, L5, L6, L7, L10, L14, and L16. Preempting them frees 181 Mbps on this link. Since each selected LSP needs only a small amount of bandwidth, there's a good chance each one finds a new route in the network 🧚
So what do we learn from all this? When priority is the biggest concern and the number of preempted LSPs isn't an issue, the algorithm picks 5 LSPs with the lowest priority. When only the number of LSPs matters, the minimum is selected, which is 2 LSPs. Their priority is higher than in the previous case, though. When priority and number both matter and wasting some bandwidth isn't a problem, 3 LSPs get selected. That adds more bandwidth than requested, but the preemption priority is still low. When you consider all the parameters except blocking probability, the smallest set gets selected, which is 2 LSPs. They add just enough bandwidth, 175 Mbps, and their priority levels are 3 and 7 🫶
And when blocking probability is the criterion of interest, several small LSPs (8 of them) get preempted. The bandwidth wastage is low, but the number of rerouting events goes up. Given how small the bandwidth requirements are, the chances of finding a new route for each LSP are expected to be high 🌸
6.2. Network Case ✨
okay so bestie, for these experiments we're looking at a 150 node topology with an average network connectivity of 3 🕸️ 10% of the nodes have a degree of connectivity of 6, which is giving main character energy 💅 For the links, 10% are OC3, 70% are OC48, and 20% are OC192 🔥
There are two classes of TE LSPs in use: Voice LSPs and Data Internet/VPN LSPs 🎀 For each class, we need the set of preemptions (and the proportion of LSPs for each preemption) and the size distributions. Here's the full breakdown (a total of T LSPs is considered):
- T: total number of TE LSPs in the network (T = 18,306 LSPs) 🧚
Voice 💖
- Number: 20% of T
- Preemption: 0, 1 and 2
- Size: uniform distribution between 30M and 50M
Internet/VPN TE 🌈
- Number: 4% of T
- Preemption: 3
- Size: uniform distribution between 20M and 50M
- Number: 8% of T
- Preemption 4
- Size: uniform distribution between 15M and 40M
- Number: 8% of T
- Preemption 5
- Size: uniform distribution between 10M and 20M
- Number: 20% of T
- Preemption 6
- Size: uniform distribution between 1M and 20M
- Number: 40% of T
- Preemption 7
- Size: uniform distribution between 1K and 1M
LSPs are mostly set up because of network failure, like when a link or a node fails and the LSPs get rerouted 🦋
The network failure events were simulated with two functions:
- Constant: 1 failure chosen randomly among the set of links every 1 hour.
- Poisson process with interarrival average = 1 hour.
Table 2 shows the results for simulations with constant failure 📊 The simulations were run with the preemption heuristic configured to balance different criteria (left side of the table), and then with different preemption policies that consider the criteria in a given order of importance rather than balancing them (right side of the table) 🫶
The proposed heuristic was configured to balance the following criteria:
- HPB: The heuristic with priority and bandwidth wastage as the most important criteria (alpha=10, beta=0, gamma=0.001, theta=0).
- HBlock: The heuristic considering the minimization of blocking probability (normal load links: alpha=1, beta=0, gamma=0, theta=0.01) (heavy load links: alpha=1, beta=10).
- HNB: The heuristic with number of preemptions and wasted bandwidth in consideration (alpha=0, beta=10, gamma=0.001, theta=0).
Other algorithms that consider the criteria in a given order of importance:
- P: Sorts candidate LSPs by priority only.
- PN: Sorts the LSPs by priority, and for cases in which the priority is the same, orders those LSPs by decreasing bandwidth (selects larger LSPs for preemption in order to minimize number of preempted LSPs).
- PB: Sorts the LSPs by priority, and for LSPs with the same priority, sorts those by increasing bandwidth (select smaller LSPs in order to reduce bandwidth wastage).
-------------------------------------------------
| Heuristic | Other algorithms |
-------------------------------------------------
| HPB | HBlock| HNB | P | PN | PB |
-----------------------------------------------------------------
Need to be | 532 | 532 | 532 | 532 | 532 | 532 |
Rerouted | | | | | | |
-----------------------------------------------------------------
Preempted | 612 | 483 | 619 | 504 | 477 | 598 |
-----------------------------------------------------------------
Rerouted |467|76%|341|73%|475|77%|347|69%|335|70%|436|73%|
Blocked |145|24%|130|27%|144|23%|157|31%|142|30%|162|27%|
-----------------------------------------------------------------
Max Cascading | 4.5 | 2 | 5 | 2.75 | 2 | 2.75 |
-----------------------------------------------------------------
Wasted Bandwidth| | | | | | |
AVR (Mbps) | 6638 | 532 | 6479 | 8247 | 8955 | 6832 |
Worst Case(Mbps)| 35321 |26010 |36809 | 28501 | 31406 | 23449 |
-----------------------------------------------------------------
Priority | | | | | | |
Average | 6 | 6.5 | 5.8 | 6.6 | 6.6 | 6.6 |
Worst Case | 1.5 | 3.8 | 1.2 | 3.8 | 3.8 | 3.8 |
-----------------------------------------------------------------
Extra Hops | | | | | | |
Average | 0.23 | 0.25 | 0.22 | 0.25 | 0.25 | 0.23 |
Worst Case | 3.25 | 3 | 3.25 | 3 | 3 | 2.75 |
-----------------------------------------------------------------
Table 2: Simulation results for constant network failure:
1 random failure every hour.From Table 2, the takeaway is that among the heuristic results (HPB, HBlock, HNB), HBlock preempted the smallest number of LSPs 🏆 More importantly, it also had an overall smaller rejection rate and smaller average wasted bandwidth (and second overall smaller worst-case wasted bandwidth.) 💅
Okay, here's the funny part 🙈 Although HBlock doesn't try to minimize the number of preempted LSPs, it ends up doing so anyway, because it mostly preempts LSPs with lower priority, so it doesn't push cascading much further. Cascading was the overall lowest (preemption caused at most two levels of preemption, which was also the case for the policy PN). The average and worst preemption priority was very satisfactory, since it mostly preempted the lowest-priority LSPs, just like the other algorithms P, PN, and PB 🌸
When HPB was in use, more LSPs got preempted because of the higher cascading effect. That's because the heuristic likes to preempt LSPs that are very close in bandwidth size to the preemptor LSP, which can end up preempting a higher priority LSP and causing cascading 😭 Still, the wasted bandwidth was reduced compared to the other algorithms (P, PN, PB) ✨
When HNB was used, cascading was higher than in the other cases, since LSPs with higher priority could get preempted. Compared to P, PN, or PB, HNB preempted more LSPs (in fact, it preempted the largest number of LSPs overall, clearly showing the cascading effect), but its average wasted bandwidth was smaller, though not as small as HBlock's. HNB tries to preempt a single LSP, meaning it goes after LSPs whose reserved bandwidth is similar to the bandwidth actually needed. It's not always successful, because such a match may not exist, and in that case the wasted bandwidth could be high 🙃 The preempted priority was the highest on average and in the worst case, which also explains why the cascading level was the highest too (the heuristic picks LSPs for preemption without looking at their priority levels). In summary, this policy performed poorly 💀
Policy PN resulted in a small number of preempted LSPs overall and a small number of LSPs that weren't successfully rerouted. Cascading is low, but bandwidth wastage is very high (the overall highest bandwidth wastage) 😬 Also, in several cases where rerouting happened on parts of the network that were underloaded, HBlock preempted fewer LSPs than PN did 🍓
Policy P selects a larger number of LSPs (compared to PN) with low priority for preemption, so it was able to successfully reroute fewer LSPs compared to HBlock, HPB, HNB, or PN. Its bandwidth wastage is also higher than any of the heuristic results or PB, and it could be worse if the network had low priority LSPs with large bandwidth, which isn't the case here 🥀
Policy PB, compared to PN, resulted in a larger number of preempted LSPs and an overall larger number of blocked LSPs (not rerouted), due to preemption. Cascading was slightly higher. Since the selected LSPs have low priority, they can't preempt much further and get blocked when the links are congested. Bandwidth wastage was smaller because the policy tries to minimize wastage, and the preempted priority was about the same on average and in the worst case 🫧
The simulation results show that when preemption is based on priority, cascading isn't critical, since the preempted LSPs can't propagate preemption much further. When the number of LSPs is considered, fewer LSPs get preempted and the chances of rerouting go up. When bandwidth wastage is considered, smaller LSPs get preempted on each link and the wasted bandwidth stays low. The heuristic seems to combine these features, giving the best results, especially for blocking probability 🏅 When the heuristic was configured to minimize blocking probability (HBlock), small LSPs with low priority were selected for preemption on normally loaded links, and fewer (larger) LSPs with low priority were selected on congested links. Because their priority is low, cascading wasn't an issue. Several LSPs were selected for preemption, but the rate of LSPs that weren't successfully rerouted was the lowest. Since the LSPs are small, it's easier to find a new route for them in the network. When selecting LSPs on a congested link, fewer larger LSPs get selected, which improves load balance. On top of that, the bandwidth wastage was the overall lowest 🌈 In summary, the heuristic is very flexible and can be configured to suit the network provider's best interest regarding the criteria being considered 👑
For several cases, a link failure caused no preemption at all (all LSPs were able to find an alternate path in the network), or it caused preemption of very few LSPs, which were then successfully rerouted with no cascading effect 🧚
It's also important to note that for all policies in use, the number of extra hops when LSPs were rerouted wasn't critical. That shows preempted LSPs can be rerouted on a path with the same length or a path that is slightly longer in number of hops 🦋
7. Security Considerations 🔥
The practice described in this document does not raise specific security issues beyond those of existing TE. ✨
8. Acknowledgements 🫶
We would like to acknowledge the input and helpful comments from Francois Le Faucheur (Cisco Systems) and George Uhl (Swales Aerospace). 💖
9. Informative References ✨
Okay bestie, here's the reading list 📚 These are the background docs the RFC leans on. They're not requirements, just the good stuff if you want to go deeper 🧠
- [ATM-PREP] Poretsky, S. and Gannon, T., "An Algorithm for Connection Precedence and Preemption in Asynchronous Transfer Mode (ATM) Networks", Proceedings of IEEE ICC 1998.
- [DEC-PREP] Peyravian, M. and Kshemkalyani, A. D. , "Decentralized Network Connection Preemption Algorithms", Computer Networks and ISDN Systems, vol. 30 (11), pp. 1029-1043, June 1998.
- [PREEMPTION] de Oliveira, J. C. et al., "A New Preemption Policy for DiffServ-Aware Traffic Engineering to Minimize Rerouting", Proceedings of IEEE INFOCOM 2002.
- [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. McManus, "Requirements for Traffic Engineering Over MPLS", RFC 2702, September 1999.
- [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001.
- [RFC3272] Awduche, D., Chiu, A., Elwalid, A., Widjaja, I., and X. Xiao, "Overview and Principles of Internet Traffic Engineering", RFC 3272, May 2002.
- [RFC3564] Le Faucheur, F. and W. Lai, "Requirements for Support of Differentiated Services-aware MPLS Traffic Engineering", RFC 3564, July 2003.
- [RFC4124] Le Faucheur, F., "Protocol Extensions for Support of Diffserv-aware MPLS Traffic Engineering", RFC 4124, June 2005.
- [RFC4126] Ash, J., "Max Allocation with Reservation Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering & Performance Comparisons", RFC 4126, June 2005.
- [RFC4127] Le Faucheur, F., "Russian Dolls Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering", RFC 4127, June 2005.
- [RFC4128] Lai, W., "Bandwidth Constraints Models for Differentiated Services (Diffserv)-aware MPLS Traffic Engineering: Performance Evaluation", RFC 4128, June 2005.
Authors' Addresses 💌
Here's who wrote this, and how to reach them. Jaudelice and JP are the editors, and Leonardo and Caterina helped write it too 🫶
Jaudelice C. de Oliveira (editor)
Drexel University
3141 Chestnut Street (ECE Dept.)
Philadelphia, PA 19104
USA
EMail: jau@ece.drexel.edu
JP Vasseur (editor)
Cisco Systems, Inc.
1414 Massachusetts Avenue
Boxborough, MA 01719
USA
EMail: jpv@cisco.com
Leonardo Chen
Verizon Laboratories
40 Sylvan Rd. LA0MS55
Waltham, MA 02451
USA
EMail: leonardo.c.chen@verizon.com
Caterina Scoglio
Kansas State University
2061 Rathbone Hall
Manhattan, Kansas 66506-5204
USA
EMail: caterina@eece.ksu.eduFull Copyright Statement ⚖️
The IETF Trust owns the copyright here, copyright (C) The IETF Trust (2007) 💜 This document is subject to the rights, licenses and restrictions in BCP 78 and at www.rfc-editor.org/copyright.html. Outside of what those say, the authors keep all their rights.
The document and everything in it is provided on an "AS IS" basis, and the disclaimer goes hard. THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. 💀
Intellectual Property 🔐
Okay, so the IETF is not saying anything about whether any patents or other rights apply to the tech in this document, or whether you could get a license for them. It also isn't claiming it checked for any of that. If you want the rules on rights in RFCs, look at BCP 78 and BCP 79 🧐
Any IPR disclosures sent to the IETF Secretariat, plus any promises of licenses, or results from trying to get a general license for implementers or users, can be found in the IETF online IPR repository at http://www.ietf.org/ipr.
The IETF also invites anyone to flag copyrights, patents, patent applications, or other proprietary rights that might cover technology needed to implement this standard. Send that to ietf-ipr@ietf.org 📬
Acknowledgement 🌷
Funding for the RFC Editor function is currently provided by the Internet Society. Thank you, Internet Society 🫶✨
That's the whole RFC, bestie!! 🌈💖
📦 where this page comes from
- ietf: rfc4829 2007-04
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms