[e2e] Preemption in a Multi-Class scenario

[Fred Baker]

I assume you are working on traffic engineering.

You clearly are working on a case where the remaining unallocated  
capacity on a link is smaller than the need that you have for a given  
new LSP. Otherwise you wouldn't be preempting.

I would also tend to assume that LSPs are of different sizes. Not all  
LSPs get the same capacity.

So the capacity that you need to preempt is the capacity you need to  
allocate less the remaining unallocated capacity (eg, if you have a  
pipe that is 90% allocated and have a new LSP that needs 15% of the  
pipe, you need to preempt an LSP or set of LSPs that owns 5% of the  
pipe to aggregate the necessary bandwidth). If it is large enough,  
you can preempt a smaller LSP and meet the needs of the new one. But  
there probably isn't one that exactly meets your needs, so you will  
wind up preempting at least one LSP, combining the now-freed  
bandwidth with the remaining unallocated capacity, allocating the new  
LSP, and now having some amount left over. If what you preempted was  
smaller than what you allocated, what you have remaining is smaller  
than what you had before. If what you preempted was larger, you will  
have more left over.

You now presumably have what you preempted to re-install. If it is  
smaller than what you installed, it will presumably be easier to  
route through the remaining network. If it is larger...

Just thinking through things, the LSPs that I am most likely to be  
willing to re-route in favor of a new LSP are likely to be ones that  
are the same size or smaller than the new LSP (and BTW are most  
likely to be protection paths as opposed to LSPs currently bearing  
traffic). That leads me to believe that there is a significant  
probability that there is not magically an LSP that is "just right",  
and I will have a significant chance of having to combine two or more  
smaller LSPs to make capacity available.

On Nov 18, 2005, at 7:41 AM, Fahad Dogar wrote:

> Hi,
>
> Regarding preemption, I wonder if anyone can comment on how likely  
> is that we will need to preempt several LSPs to accommodate a new LSP?
>
> We are currently considering the problem of preemption in a  
> DiffServ aware MPLS environment. Various preemption schemes exist  
> (in literature) some of which try to minimize the number of  
> preempted LSPs. All such schemes assume that the average bandwidth  
> of lower priority requests is *much* smaller as compared to the  
> mean size of higher priority requests and, therefore, imply that  
> multiple lower priority requests need to be preempted to  
> accommodate a higher priority request. Is it reasonable to assume  
> that in a multi-class environment, large variation in traffic  
> patterns of different classes would exist? Any measurements or  
> studies out there? Any justifications for assuming different mean  
> sizes for traffic requests belonging to different classes?
>
> In contrast to the popular assumption, if the traffic distribution  
> of different classes is similar in terms of mean bandwidth, it is  
> very *likely* that accommodating one high-priority LSP would  
> require preempting just one low-priority LSP, especially when the  
> number of LSPs is large. This significantly reduces the complexity  
> of preemption algorithm.
>
> How likely is it that for a given traffic request, typically we  
> would need to preempt several LSPs (and not just one) in order to  
> accommodate the new request .
>
> Thanks in advance,
> Fahad