Programming Project #2		COSC 311
Distributed 1/29/2013		Due: 2/19/2013

Queueing Theory:  Experimental Results for Little's Theorem

Little's Theorem states that 
N = lambda * T
where N is the number of customers in the queue
lambda is the customer arrival rate,
T is the customer service time.

A good visualization is to imagine customers coming in to a restaurant. The restaurant is
*very* large, and able to accomodate all the customers that come.  N, then, will be the
number of customers in the restaurant.  T is the length of time between when the customer
enters the restaurant and the customer leaves (after ordering, eating and paying).  
The customer arrival rate is lambda; it is the average number of customers that
arrive at the restaurant per tick.  Notice that N is directly proportional to 
lambda and to T.

Your job is to run experiments that vary lambda and T in order to demonstrate that Little's
Theorem is true. You will be *simulating* the queue in order to demonstrate
Little's Theorem.


Implementation

The queue must be implemented as a linked list. If you You may use the Java Collection for linked
list (if you really want to), but you *must* implement all operations on the
linked list yourself (insert() or enqueue(), delete() or dequeue(), isEmpty() ).
You may also want a peek(), which looks at the value of the first element in 
the queue without removing it. You may also want a variable count that keeps track of
the current length of the queue.

The simulation for this experiment is a time-based simulation.  You will have
a for loop, that steps through time, one tick at a time. In the body of the
for loop are the following steps:
   remove customers (nodes) whose remaining service time has gone to zero.
   update remaining customers in the queue (each customers must have one unit
        of service time removed)
   collect statistics on the queue (in this experiment, we need the number of
        customers in the queue)
   insert new customers to queue (service time for each is initialized to T)

The order of events in the body of the loop is not really strict, as long as the
simulation runs for a large number of ticks.

An example might help. Suppose we start with an empty queue. Service time T = 2,
customer average arrival rate is 1 every 2 ticks ( = 0.5). Suppose each customer has
three data fields: id (for debugging purposes only), remaining service time,
and next; (4, 2, null)  means customer # 4, has 2 ticks of service remaining, and
is the last item in the queue.

time = 0
   remove completed customers ==> there are none
     queue: null
   update remaining customers ==> there are none
     queue: null
   collect stats ==>   queue length = 0
   insert new customers ==> 2
     queue: 	(1, 2, =)=> (2, 2, null) 
      		
time = 1
	removed completed customers ==> 
		queue: (1, 2, =)=> (2, 2, null)
	update remaining customers ==>
		queue: (1, 1, =)=> (2, 1, null)
	collect stats ==>			2
	insert new customers ==> 0
		queue: (1, 1, =)=> (2, 1, null)
			
time = 2
	remove completed customers ==> 
		queue: (1, 1, =)=> (2, 1, null)
	update remaining customers ==> 
		queue: (1, 0, =)=> (2, 0, null)
	collect stats ==>			2
	insert new customers ==> 1
		queue: (1, 0, =)=> (2, 0, =)=> (3, 2, null)
		
time = 3
	remove completed customers ==>  2 are completed
		queue: (3, 2, null)
	update remaining customers ==>
		queue: (3, 1, null)
	collect stats ==> 			1
	insert new customers ==> 0
		queue: (3, 1, null)
		
time = 4
	remove completed customers ==> none are completed
		queue: (3, 1, null)
	update remaining customers ==>
		queue: (3, 0, null)
	collect states ==>			1
	insert new customers ==> 0
		queue: (3, 0, null)
		
time = 5
	remove completed customers ==>
		queue: null
	update remaining customers ==>
		queue: null
	collect stats ==>			0
	insert new customers ==> 0
		queue: null
		
etc.

The *average* customer arrival rate is lambda.  The number of customers that arrive
at every tick is a Poisson distributed random number with expected value lambda.
A Poisson random number is a non-negative integer, that over time, will
average to the expected value (aka lambda, aka arrival rate).

In order to convert a uniform distribution between 0 and RAND_MAX (largest
integer returned by rand()), modify the C function given at
http://emunix.emich.edu/~haynes/Papers/ProbabilityDistributions/probabilityDistributions.html
In C, rand() returns a uniform distributed number between 0 and RAND_MAX (not 
including RAND_MAX), so it is very similar to Java's random() function.


Experiments:

One set of experiments will fix lambda, vary T (use integer values for T), and
calculate the average queue length for each different T. 

The second set of experiments will fix T, vary lambda, and, again, calculate
the average queue length for each different lambda.


Results:

Collect the data, draw two graphs (by hand or with Excel or with other). You do not have
to export the data -- you can transfer the data to the graphs by hand.
One graph will show T versus length, the other graph will show lambda versus
length. (independent variable goes on the abscissa, dependent variable goes
on the ordinate).


Write-up:

Your data should confirm Little's Theorem (we hope and expect).

Give a short write-up relating your simulation results to the confirmation
(or not) of Little's theorem. One to two short paragraphs will be sufficient.


Grading based on:
  -- Satisfying spec
  -- Elegance and readability of code (see Style Standards)
  -- Graphs (easy to comprehend, good color, axis labels, points marked, ...)
  -- Write-up (good, clear English)
  
Development advice:
 (1) Debug int nextPoisson(double eV) separately
 (2) Debug queue code separately
 (3) Run simulation for 5 ticks with short T and large lambda, using verbose
 output -- make sure your queue ops are ok.