Comp 346               Spring 2005            Dordal
Trunk Line Usage Simulation		Due: Fri, April 22

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 parameters such as the following:

  r:	rate of new calls as a number per unit time
  	All calls are assumed to require a trunk line.
  	In a time interval of length t, there should be r*t calls
  L:	average length of calls
  
  r and L can be measured in hours, minutes, or seconds.
  Note that r*t*L is the total length of all the calls,
  and r*L is the AVERAGE number of calls at any one time.
  
It is convenient to measure time in units of L; that is, one time unit
is the average length of a call. This kind of rescaling is called
normalization; if we do this, then r represents both the rate of new calls 
and the average number of calls in place at any one time.
  
  r*L (or just r, with the time normalization L=1 above) is said to be 
  the traffic load, measured in Erlangs.  For example, if there are 30 
  new calls per hour, and each call lasts 6 minutes, that's 30*6 = 180 
  minutes of calls per hour,   or 3.0 Erlangs. If we do the normalization,
  then we need to measure calls in units of 6 minutes, and 30/hour
  = 30 calls in 60 minutes = 3 calls in 6 minutes, or r=3 Erlangs.
  The unit is named for for the Danish telephone scientist Agner 
  Krarup Erlang (1878 - 1929); a traffic rate of 80 calls at a time 
  would be said to be 80 Erlangs.
  
  k:	number of trunk lines available.
  Clearly you need k >= r; the question is how *much* greater
  n has to be, in order to handle bursts of traffic.
  
Additional relevant parameters:

  T: 	total time over which the simulation runs
  	T needs to be large relative to L.
  	In the entire simulation, we place N = r*T calls. 
  
To model calls, all we need are the start times and lengths. To model
the start times of N = r*T calls in a time interval 0 to T, we will 
typically choose N random numbers uniformly in the interval [0,T], 
and then sort them. The sorting is necessary to simulate calls made 
in time sequence. The i-th call succeeds, for i<N, if there is a line 
for it; it fails if among the previous i-1 calls there are still n calls 
in progress. In order to make that determination, we need to know the
lengths (and thus the end times) of those calls.

You are to produce three models, and answer some questions about
each model:

	1. Assume all calls are of fixed length; users who get a 
	   trunk-busy signal hang up and do not try again.
	   With our normalization assumption this fixed length is 1.0.
	   
	2. Like 1, except call lengths are "exponentially distributed".
	   Here, the length L[i] of the ith call is chosen to be -log(u),
	   where u is chosen uniformly at random in the interval [0,1].
	
	3. Assume all calls are of fixed length, but users wait in 
	   a queue until their call can be completed.
	   
You are to write a program that takes a rate r and a number of lines k,
and averages over a period of time to find the percentage of blocked 
calls. I recommend, but do not require, the use of Java.  

You are then to analyse the situation for different k and r, for each
of the three models (the analysis for Model 3 is slightly different,
as you also want to find the average waiting time).

Analysis 1 (Models 1 & 2)
For k = 10, 20, 30, 40, 60, 80, and 100 lines and r = 80% of k, find 
the percentage of blocked calls. How much does it change as k grows? 
Does it get smaller or larger? 

Analysis 2 (Models 1 & 2)
For k=30 lines, find the r (to the nearest whole number) that yields each
of the following percentages of blockage: 0.5%, 1%, 2%, 5%, 10%.

(Note that you might not see much difference between Models 1 and 2, 
for the two analyses.)

Analysis for Model 3: You can adapt Analysis 1 straightforwardly: 
using the k and r values given, find the percentage of delayed calls,
and the average waiting time. For Analysis 2, find r so that the percentage
of *delayed* calls is 0.5%, 1%, 2%, 5%, 10%, and also do 20%.


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 N=r*T calls. The first step is to choose an array
of N random numbers, each random number between 0 and T.
Something like
        calltimes[i] = T*Math.random();
should work.

Next, sort the array. To do this,
	import java.util.Arrays;
	...
	Arrays.sort(calltimes)

Next, if applicable, compute random lengths of each call. For models
1 and 3, you can assume each call has length 1.0. For the exponential
length in Model 2, set 
	length = - Math.log(Math.random());
(note that this is a positive number, as Math.random() returns u<1
and log(u) for u<1 is itself negative.) Then set
	endtimes[i] = starttimes[i] + length;
Choose a new random length for each i!

Finally, run through the calls from 0 to N-1, and see how
many are blocked; the blocked fraction is then blockedcount/N.
The ith call is blocked, at time ctime = starttime[i], if the number 
of calls in progress at ctime is (at least) k; that is, if the count of 
j<i for which endtimes[j] > ctime is >= k.

For model 1, we can simplify this by starting with j=i-1 and counting
down until we find the first j with endtimes[j] <= ctime; the number
of calls in progress (that is, with endtimes[j] > ctime) is thus i-j-1.
(You also have to stop when j=0). This is because the endtimes are
increasing. Here is a loop to do the counting:
   int j = i-1;
   int callcount = 0;
   while (j>=0 && calltimes[j] >= calltimes[i]-1)  {callcount++; j--;}

Model 1 assumes 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).

For Model 2, you can't in principle stop the loop before j=0, as you can't
be sure that the first call wasn't a very long one. However, this is 
unlikely, and you can greatly improve the efficiency of the inner loop
with the following. Compute *once* an array "maxes", of the same length
as endtimes, so that 
	maxes[i] = max{endtimes[0]...endtimes[i]}
(The easy way to do this is to set maxes[i]=max(endtimes[i], maxes[i-1]).)
Now, your while loop can stop when ctime >= maxes[j]; you now know that
all earlier calls have already completed at ctime. For T large, this
will almost certainly result in a significantly smaller runtime.


For Model 3, you should compute the percentage of calls that have to wait,
and also the average waiting time. For this model, calltimes[] represents
the array of times calls are *placed*, and lengths are all 1.0, but
you will also need an array connecttimes[] listing times the calls 
actually complete. Now consider the ith call, placed at time ctime =
calltimes[i]. Here is a sample calltimes[] vector:
	[0.8, 1.1, 1.3, 2.2, 2.5, 2.7, 3.0, 3.8]
One way to approach this is to first fill in the connecttimes[] and
endtimes[] vectors. We proceed from i=0 to 7. The first two calls 
connect immediately, as there are two lines. Thus, the connect and end
times are:
  calltimes:	[0.8, 1.1, 1.3, 2.2, 2.5, 2.7, 3.0, 3.7]
  connecttimes:	[0.8, 1.1, ...	
  endtimes:	[1.8, 2.1, ...
Now consider the call i=2 at t=1.3. There is no line available. 
So we find the first call to end (because call lengths are fixed here,
this will be the first endtime entry larger than 1.3; in this case, 1.8).
The i=2 call connects when the i=0 call frees the line, at t=1.8,
and then ends at t=2.8:
  calltimes:	[0.8, 1.1, 1.3, 2.2, 2.5, 2.7, 3.0, 3.7]
  connecttimes:	[0.8, 1.1, 1.8, ...	
  endtimes:	[1.8, 2.1, 2.8, ...
Now the call i=3, at t=2.2, is placed. It connects immediately, as by
then only the i=2 call is still in progress. The i=4 call at t=2.5 and
the i=5 call at t=2.7 must both wait, though, as no additional line is
free until the i=2 call completes at t=2.8. Adding these calls gives us:
  i:      	[ 0    1    2    3    4    5    6    7
  calltimes:	[0.8, 1.1, 1.3, 2.2, 2.5, 2.7, 3.0, 3.7]
  connecttimes:	[0.8, 1.1, 1.8, 2.2, 2.8, 3.2, 	
  endtimes:	[1.8, 2.1, 2.8, 3.2, 3.8, 4.2, 
Similarly, the i=6 call at t=3.0 has to wait (as the i=3 and i=4 calls
are still in progress at t=3.0); it has to wait until the i=4 call frees 
its line at t=3.8. It is not enough to wait for the i=3 call to finish
(at t=3.2) as that line goes to the i=5 call. Algorithmically, we know
at i=6 that there are two calls in progress, so, as lines are allocated
on a FIFO basis, we have to go back k=2 lines, to i=6-2 = 4, for that
call to complete. The final array is:
  i:      	[ 0    1    2    3    4    5    6    7
  calltimes:	[0.8, 1.1, 1.3, 2.2, 2.5, 2.7, 3.0, 3.7]
  connecttimes:	[0.8, 1.1, 1.8, 2.2, 2.8, 3.2, 3.8, 4.2]
  endtimes:	[1.8, 2.1, 2.8, 3.2, 3.8, 4.2, 4.8, 5.2]
  
Hints: endtimes are increasing (as connecttimes are increasing). 
So, at point, some calls are finished, and then some calls are in progress,
and the remaining calls [if any] are waiting. During all-lines-busy 
periods, call i connects at the time that call i-k frees its line.
   
We can get the desired statistics at the end by examining the arrays:
a call had to wait if its calltime is not equal to its connecttime;
the waiting time is simply that difference.

Email me the following things (ideally both in one zip file):
  * Your java programs (maybe all in one?)
  * Some discussion for Analyses 1-3 above, including some program
    output in support of your analyses.