EE 644 Project 1 (5 pts): Simulate M/D/1/20 Queueing System

Due Date: February 27, 1998 (Fri.)

System Description: Consider a communication link with the following parameters

• The link has a capacity of 1 Mbps (megabits per sec.)
• Packets arrive to be transmitted on the link as a Poisson arrival process at rate 2000 packets per second. When a packet arrives it is stored in the link buffer, which can hold up to 20 packets.
• Each packet is 53 bytes.
• Packets are transmitted from the link buffer using a first come first served service policy. The head of the line (HOL) packet occupies the buffer until it is completely transmitted.
• If a packet arrives and the link buffer is full then the packet is lost and considered blocked.

Assignment:

• Write a program that simulates the communication link and determines the following data:
  • The probability b of a packet being blocked.
  • For i = 0, 1, ..., 20, the steady-state probability p(i) that there are i packets in the link buffer.
  • The average number of packets in the link buffer.
• In addition, compute the probability of a packet being blocked, but when the length of each packet is independent, exponentially distributed with mean 53 bytes. (Note that this means that the packets have a continuous length, e.g., it is possible for the packet to have a length of 512.134 bits.) To compute the probability use the M/M/1/20 formulas. Compare this probability with the one from your simulations -- is it larger or smaller?

Turn in the data (probabilities and averages described above) from your simulations, and the computed probability for the M/M/20/20 system.

Hints, if you're writing the code in C:

Random Number Generator. To write your simulator, it would be useful to have a "random number generator." However, a true random number generator is difficult to build, so use a "pseudo random number generator" Basically, a pseudo random number generator is a function f(). To generate a sequence of numbers, you supply a "seed" number X0. Then a sequence of numbers X0, X1,... can be generated by the recursion X1 = f(X0), X2 = f(X1),.....

The pseudo random generator to use is drand48(), which returns a double precision floating point pseudo random number in the interval [0,1) (note that drand48() does not require an argument). To plant a seed, use the function srand48(int seed) (note that the input parameter is an integer). In your program, you should plant the seed once at initialization. Also note that drand48() and srand48() require the inclusion of the stdlib.h library. (For more information on drand48 and srand48, see their man pages.)

The following is an example of a program that prints 5 random numbers produced by calling drand48().

#include<stdlib.h> 
#include<stdio.h>

main()
{  srand48(1);
   printf("Random number 1:  %f\n",drand48());
   printf("Random number 2:  %f\n",drand48());
   printf("Random number 3:  %f\n",drand48());
   printf("Random number 4:  %f\n",drand48());
   printf("Random number 5:  %f\n",drand48());
}

The function drand48() produces a pseudo random number that is uniformly distributed over the interval [0,1), and independent of other function calls. One can transform these uniformly distributed random numbers to exponential random numbers by using what we learned from an earlier homework.

Discrete Event Simulation.

To simulate the queueing system, you should model the system as a discrete event system. This means that the system is constant except at certain time epochs when the system state can change.

For this system, the system state is the number of packets in the buffer. Note that this system state is a function of time. The time epochs occur when event occurs, e.g., an arrival or departure. Then the system state may change by increasing or decreasing by one. Note that between time epochs, the system state is constant. (Also note that changes in state occur due to "discrete" events, which make abrupt changes to the state.)

A discrete even simulation models the system over time. A variable t is used to represent the current time. Initially, t is set to 0. The system state N (the current number of customers in the system) is kept track of as time t progresses. Initially, N is set to some value, for example, 0.

The simulator will continually update the time t to the next time epoch, which is due either to an arrival or departure. Each update of t requires updating the system state N, as well as the performance statistics (e.g., total time the system is in state i, total number of packets blocked, total number of arrived packets, etc.)

The simulator stops according to some stopping rule. The stopping rule could be to stop after a fixed number of events, or after a certain amount of simulated time.

The following is an outline of a discrete event simulator algorithm:

Step 1.   Initialize
               Current time t to 0
               State N 
               Variables holding performance statistics
               S, the set of "next events"
Step 2.   Determine from S, the next event to occur.  Let this event
               occur at time t + y.
Step 3.   Update 
               Current time:  t = t + y
               State N
               Variables holding performance statistics
               S, the set of "next events"
Step 4.   If it's time to stop then go to Step 5.  Otherwise, go to Step 2.
Step 5.   Process the performance statistics and output results.