[e2e] Preemption in a Multi-Class scenario
fred at cisco.com
Fri Nov 18 11:15:01 PST 2005
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:
> 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,
More information about the end2end-interest