The MPLS-OPS Archive

[nbwaite@attglobal.net]

Andrew Frazer:

Saw your question:

>    Probably every carrier oversubscribes their core network,
>    when they sell bandwidth on their network.
>
>    Does anyone have any links to any formulas for
>    calculating the probability of blocking when doing this?

Depending on amount of detail involved, this calculation can
range from fairly simple to quite complicated.

Here is a relatively simple approach:  A network consists of
various 'resources'.  With an appropriate representation in
terms of resources, we can say that the network has 'blocking'
if and only if some resource does.

For some networks, finding a representation terms of such
resources may require some effort.  For example, two links
between the same two end points and fed with load balancing
would be treated as one resource.  Thus, we would want to know
where our 'nodes' did such load balancing.  In a sufficiently
complicated network, such a representation need not exist.
But, here we assume that such resources do exist, either for
all of our network or for enough of it for some useful
results.

So, we should calculate the probability of blocking for each
of the resources.  What you are likely to find is just a few
'bottlenecks', that is, resources with much higher
probabilities of blocking than all the other resources.  In
this case, typically we pay attention to just the bottlenecks.

To calculate probabilities, first we can draw from some
classic work on stochastic processes:  So, consider time t >=
0. At some resource, let N(t) be the number of packets that
arrive at this resource in time [0, t].  Assume, for s, t >=
0, (1) with probability 1, packets arrive just one at a time;
(2) N(0) = 0; (3) the 'increment' N(t + s) - N(s) is
independent of (N(u), u <= s), and (4) the distribution of the
increment N(t + s) - N(s) is independent of s.

Then (N(t), t >= 0) is a 'Poisson process' and, just from
these relatively 'qualitative' assumptions, it follows that
(1) for some constant c >= 0, for any k = 0, 1, 2, ..., P(N(t)
= k) = exp(-ct)(ct)**k/k!  (2) E[N(t)] = Var(N(t)) = ct.

Due to E[N(t)] = ct, constant c is called the 'arrival rate'.

Further, for k = 0, 1, 2, ..., we can let T(k) be the first t
where N(t) = k (the time of the kth arrival).  Then (1) (T(k),
k = 0, 1, ...) is independent and (2) for t >= 0, P(T(k + 1) -
T(k) <= t) = 1 - exp(-ct), which is the 'exponential
distribution' with 'density' (c)exp(-ct).  Further, (1) and
(2) are sufficient for (N(t), t >= 0) to be a Poisson process
(useful in 'simulation').

If (N(t), t >= 0) (M(t), t >= 0) are independent Poisson
processes with rates c and d, respectively, then (N(t) + M(t),
t >= 0) is a Poisson process with rate c + d.

Note:  Some of these statements have to be taken mostly
intuitively or be supported with some relatively advanced
topics including 'monotone class' arguments from 'measure
theory'.

Moving on, suppose we are given a 'network cloud' with some n
'edge nodes' and the flows from each of the n edge nodes to
each of the other (n - 1) edge nodes.  So, we have n(n - 1)
flows.  Suppose each of these flows is a Poisson process.
Then the flow on each resource is a sum of Poisson processes
and, assuming that the flows are independent, thus, Poisson.
Suppose, in our first-cut approximation, we say that
'blocking' on a given resource in our network cloud is a
function only of the Poisson process of the flow on that
resource.  Continuing, divide time into increments s > 0.
Suppose on some resource its flow is Poisson process (N(t), t
>= 0) with arrival rate c. Suppose for some integer b > 0
there is blocking on this resource in an interval s if and
only if N(t + s) - N(t) >= b.  Then the probability of
blocking is P(N(t + s) - N(t) >= b) = P(N(s) >= b) = P(T(b) <=
s) which has Erlang-n distribution -- basically get just a sum
of terms of the form P(N(t) = k).  The equation is simple to
derive from what we have said here but something of a mess for
this simple flat ASCII typing.  This is one way to arrive at
the classic role of Erlang distributions in telecommunications
capacity planning.

We should return to E[N(t)] = Var(N(t)) = ct.  'Blocking' in
some interval of time is the same as too many arrivals in that
interval which, for time interval of length t, is having N(t)
too large.  A first-cut way to estimate N(t) being too large
is to consider just the mean and standard deviation of N(t).
We know the mean, ct, and the standard deviation is just its
square root.  Hmm ....  Analogy:  Hold up a sheet of paper.
Notice that the air molecules striking one side essentially
determine a Poisson process.  At sea level, the resulting
pressure is about 14 pounds per square inch; for a sheet of
paper 8 1/2 x 11 inches that is 1309 pounds -- on one side of
this flimsy piece of paper.  And the paper stands still.  The
reason for the stability is that there is an independent and
opposing Poisson process on the other side.  Lesson:  When
N(t) is large, the standard deviation is a small fraction of
the mean -- that is, in percentage terms, N(t) is quite
stable, does not vary very much.  A somewhat more precise way
to see this is to notice that N(t), being a sum of independent
arrivals, can be described by the central limit theorem and,
thus, when ct is large, must be nearly Gaussian distributed
with mean ct and standard deviation the square root of ct;
then a random variable with Gaussian distribution with large
mean ct and standard deviation the square root of ct is nearly
constant -- witness the stable paper.

For capacity planning, this means that, in terms of the
Poisson approach here, flows on high capacity resources are
nearly deterministic.  To confirm this, look at the graphs of
flow rates over time for some of the Internet nodes -- other
than the time of day variation, they are quite stable.  As a
result, for how much 'spare' capacity we want at such a
resource, typically considerations other than blocking
probabilities (as we have outlined here) dominate.  For one,
we are concerned with hypothetical 'peak' loads from Mother's
day, natural disasters, etc. and are not sure that our Poisson
process argument appropriately captures such rare events with
such large changes from the usual.  For another, we want to
allow room for growth in our network over coming weeks and
months.  So, 'engineering judgement' can tell us that we do
not want flows through high capacity resources to be over,
say, 70% of capacity.  Here, then, blocking probabilities are
not very important.  Just why in such complicated situations
such simple arguments can be the more appropriate ones is one
of the inscrutable parts of our universe!

So, blocking probabilities can become more important on
resources where flow rates are smaller, so that standard
deviation is a large fraction of the mean values.  So, these
resources will typically be the smaller ones, closer to the
edge nodes and before consolidation into larger resources.

For really complicated situations, we may have to resort to
Monte Carlo simulation.  We should be reluctant to take this
step because (1) the purpose of computing is insight, not
numbers, and some good, if only approximate, analytical
attacks commonly can give more insight than long Monte Carlo
experiments and (2) in a well designed network, blocking will
be rare so that we are simulating for rare events which is the
most challenging work for simulation -- quickly we get into
'swindles', 'importance sampling', etc.

Norman B. Waite, Ph.D.
Founder
Network Architectonics
9 Fox Run
Wappingers Falls, NY 12590
nbwaite@attglobal.net
845-227-7821

-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml