Comp 346               Spring 2003            Dordal
Trunk Line Usage Simulation		Due: Wed, April 23

Suppose that, during the "busiest hour" (the normal benchmark used),
a switching office has at any one time an average of 80 calls in 
progress to the outside world. There are 100 trunk lines. Is that enough?

To ask the question a little more precisely, what is the probability
that a caller during this busiest hour will *not* find a line available,
and thus get the "fast busy" (or "reorder") signal? If the calls are
spaced at uniform intervals, then at any given time exactly 80 (+/- 1)
calls are in progress and there will always be enough capacity. 
But real calls aren't spaced uniformly, and we run the risk of a certain
amount of "random bunching". The goal is to write a program to estimate
the percentage of blocked calls, given a certain call rate r and number
of lines n. 

We will make a major simplifying assumption: all calls are of fixed 
length. With that assumption in place, we might as well measure time 
in units of this fixed length. Thus, if r is the number of new calls 
in any given time unit, r is also the average number of calls. If r=80, 
this might mean 10 new calls a minute each with a length of 8 minutes,
or 16 new calls a minute each with a length of 5 minutes. 

This rate r is traditionally said to be measured in Erlangs, for the 
Danish telephone scientist Agner Krarup Erlang (1878 - 1929); that is,
a traffic rate of 80 calls at a time would be said to be 80 Erlangs.


You are to write a program that takes a rate r and a number of lines n,
and averages over a period of time to find the percentage of blocked 
calls. I recommend, but do not require, the use of Java. Note that even 
with r=n, we don't expect the blocking fraction to be 100%. 

You are then to analyse the situation for different n and r. 

Analysis 1
For n = 25, 50, 100, 200, 400 and r = 80% of n, find the percentage
of blocked calls. How much does it change as n grows? Does it get
smaller or larger? 

Analysis 2
For n=100, find the r (to the nearest whole number) that yields each
of the following percentages of blockage: 1%, 2%, 5%, 10%.

How to do it

You will run a simulation for time T; recall time is being measured
in units of the length of one call. Thus in this interval you expect
a total of callcount=r*T calls. The first step is to choose an array
of callcount random numbers, each random number between 0 and T.
Something like
        calltimes[i] = T*Math.random();
should work.

Next, sort the array; I've given you a file with a selectionSort
function that sorts arrays of double[]. It's slow, and is the main
bottleneck; feel free to grab a faster sort.

Finally, run through the calls from 0 to callcount-1, and see how
many are blocked; the blocked fraction is then blockedcount/callcount.
A call at time t is blocked if the number of calls placed earlier
between t-1 and t is greater than or equal to n; recall that each call
lasts 1 unit so calls beginning in the interval from t-1 to t are still
running at time t. Some kind of loop like the following may work, for
deciding the blockage of the call at time calltimes[i]; this algorithm
depends on the fact that the calltimes array has been sorted into
increasing order:
   int j = i-1;
   int callcount = 0;
   while (j>=0 && calltimes[j] >= calltimes[i]-1) {callcount++; j--;}

We will assume that blocked calls do *not* wait in a queue for service,
so that if a call is blocked, you should "remove" it from the array.
The easiest way to do this is to set that component of the array to 0,
or -1, and make sure you take into account such entries in the loop
above (that is, you don't want to increment callcount for such entries,
but you *do* want to keep decrementing j and continuing the loop).

Email me the following things (ideally both in one zip file):
  * Your java program (probably a single *.java file)
  * Some discussion for Analyses 1 and 2 above, including some program
    output in support of your analyses.