Description
1. Background
Queueing networks are widely used to model systems where customers must utilize some service,
and wait if the service is being utilized by other customer(s). For example, in a fast food restaurant,
the restaurant employee standing behind the counter is modeled by a server who must handle
customers waiting in a queue to place their order and receive food. Such models are widely used
to analyze health care systems, air and road transportation networks, businesses such as restaurants
or department stores, manufacturing systems, and computers and communication networks, to
mention a few. All of these systems involve customers (e.g., people, aircraft, vehicles, data
packets, computer jobs, parts) that travel from one station to another to receive service at each
station. Each station includes a server and a queue to hold waiting customers. Here, we assume
each station can only process one customer at a time. Customers wanting to use a server that is
busy handling another customer must wait in the queue until the server is available to process
another customer.
This assignment involves developing a simulation model for a system of queues, and using it to
analyze a hypothetical cafeteria. You will work in teams of two students each to complete this
assignment with each person in the team required to implement a significant portion of the
simulation. An important part of the assignment concerns dividing up the software development
into two parts and defining simple, clear interfaces between them so each person can develop their
own software without having to become overly familiar with implementation details of other parts
of the software.
2. The Queueing Network Simulator: CPS-Sim
The simulator dubbed CPS-Sim is a general-purpose queueing network simulator that can be used
by others with no ability to program. It will include four different types of components, enumerated
below. Each component has one or more parameters. Each component may have some number of
input and out ports (possibly zero) through which customers arrive and depart. The components
are (see Figure 1):
• Generator (G): creates new customers and injects them into the system. The generator
component (also called a source in the literature) has a single output port. The component
has a single parameter indicating the average time between the arrival (generation) of
successive customers, i.e., the interarrival time. Assume the interarrival time is drawn from
a random number generator following an exponential distribution.
• Exit (E): a sink to remove customers from the system. Each customer arriving at an exit
component is immediately removed from the system. This component has no parameters.
• Queueing Station (Q): a server and a queue holding waiting customers. The station’s
server processes customers, one at a time. If the server is idle when a customer arrives, that
customer immediately receives service. If the server is busy, the customer is placed into a
FIFO queue and waits for the server. Once the server completes processing a customer, it
provides service to the first customer in the FIFO queue, if there is one. The queueing
station has one input through which customers arrive, and one output port through which
customers depart after they have received service. This component has a single parameter
that indicates the average time required to serve a customer; a customer remains in a
queueing station for this service time plus the amount of time (if any) that it must wait in
the FIFO queue. Here, service times are drawn from a random variable following an
exponential distribution.
• Fork(F): a router that sends customers to another component. A fork component has one
input on which customers arrive, and K outputs. Each arriving customer is routed to exactly
one of the K outputs. A customer is routed to output port i with probability Pii (∑#$% ‘( ) �# =
1). Each fork component has K+1 parameters, namely the number of output ports K and
the K probability values.
Assume customers require a negligible (i.e., zero) amount of time to travel between components,
or to travel through a fork component.
A sample queueing network is shown in Figure 1. The generator creates a new customer with
average interarrival time of 15 units of time. From the generator the customers flow to service
station Q1 with average service time of 20. The customer then is routed to Q2 with probability 0.3,
or to Q3 with probability 0.2 before traveling back to Q1. Alternatively, the customer may be routed
directly back to Q1 with probability 0.1 or may leave the system with probability 0.4.
3. Configuration File
The particular queueing network that your software will simulate is specified to a configuration
file that specifiesthe components, their parameters, and outgoing connections to other components.
The simulation program will first read this configuration file, instantiate the queueing network and
then run a simulation of the network.
The format of the configuration file is as follows:
Figure 1. Sample queueing network.
G
X
F
0.1
0.4
0.2
0.3
P=15 P=20
P=7
P=5 Q1
Q2
Q3
1. The first line of the file should contain a single integer indicating the total number of
components in the queueing network. If there are N components, each is assigned an
integer ID with ID values 0, 1, … N-1.
2. The remainder of the file contains N additional lines, with each line describing a single
component and its connections to other components. Each line contains a number of fields,
separated by one or more blank spaces. The first two fields of each line indicate the
component ID (0, 1, … N-1) and a single character indicating the type of component (G for
generator, E for exit, Q for a queueing station, and F for fork). The remaining fields in the
line indicate component parameters and the ID(s) of the component(s) to which this
component may send customers. These depend on the type of component. Average
interarrival times, service times, and probabilities for fork components should be specified
as floating point values while component IDs are integers. The specific format of each line
is as follows (note that the brackets < > do not appear in the file:
a. Generator:
generator component. P indicates the average interarrival time. D is the ID of the
component to which generated customers are sent.
b. Exit:
c. Station:
station component. P indicates the average service time. D is the ID of the
component to which departing customers are sent.
d. Fork:
indicates this is a fork component, and K indicates the number of output ports on
the component which are labeled 0, 1, … K-1. The next K fields are probability
values, with Pi indicating the probability a customer is routed to output port i. These
K probability values should add up to 1.0. The K parameters that follow are integers
indicating the ID of the components connected to the output ports, i.e., Di gives the
ID of the component connect to output port i.
For example, the queueing network shown in Figure 1 is represented with the following
configuration file:
6
0 G 15.0 1
1 Q 20.0 2
2 F 4 0.3 0.2 0.4 0.1 3 4 5 1
3 Q 7.0 1
4 Q 5.0 1
5 X
4. Software
You will build a discrete event simulation (DES) program to simulate the queueing network. The
software you develop must include two separate parts (the source code for these must reside in
different files) that will be compiled together to create an executable simulation:
1. Queueing network simulation library. This software is a library of functions for creating
and executing simulations of queueing networks. The library should be structured as a
general-purpose queueing network simulation library not specific to a particular network
configuration or application.
2. Configuration program. The configuration program is responsible for reading the
configuration file, checking it for errors, and using primitives defined in the queueing
network library to create the queueing network specified in the file. It then uses a primitive
provided by the library to execute a simulation of that network. After the execution is
complete it produces various output statistics.
You must define an interface to the simulation library that hides as much as possible the internal
implementation of the library. You should minimize (ideally, complete avoid) any variables that
are shared between the library and the configuration program. The interface to the simulation
library must be clearly documented in a .h file. At a minimum, the simulation library interface
should include the following functions:
1. Functions to dynamically (i.e., during the execution of the program) create new
components. Define one function for each component type that includes function
parameters corresponding to the parameters of the component.
2. A function to run the simulation of the network that was created.
3. Functions to extract information (e.g., statistics such as station waiting time) as needed.
You may need to define other functions. The details of the above primitives, and any other
functions needed in the interface are up to you and your partner.
Further, the implementation of the simulator must adhere to the following rules:
1. You must implement an event-driven, discrete event simulation, not a time-stepped
simulation.
2. Use a double precision floating point number to represent simulation time.
3. Storage for components and events must be allocated dynamically by calling malloc(),
and the storage released when you are done using the memory by calling free().
Programs that have memory leaks or dangling pointers will be considered erroneous!
4. Similarly, malloc() must be used for each customer to create storage that holds
information concerning that customer, e.g., statistics such as time in the system. This
storage should be allocated when the customer is created and released when the customer
exits the system.
5. Each event and information concerning a customer must be implemented using a C
struct. Each event must include a timestamp value and any parameters you deem
necessary to characterize the event.
6. To generate random numbers from an exponential distribution with mean U, create a
function double urand(void) that returns a random number uniformly distributed
over the interval [0,1) (note it cannot return the value 1.0), then define double
randexp() that returns -U*(log(1.0–urand())) where log() is the C function
defined in
Your simulator should take as command line parameters (1) a value indicating the amount of
simulation time the simulator should run (2) the name of the configuration file, and (3) the name
of the file in which the output from the simulation is stored. For example:
% cpssim 1000.0 config outfile
will execute the program cpssim that create the simulator specified in the file config, runs the
simulator for 1000 units of simulation time, and writes the resulting statistics into outfile. The
format of the output file is up to you, but it should be designed for people to read, and readily
understand the results of the simulation run.
The configuration program that reads the configuration file and creates the queueing network must
be robust, able to detect errors and print useful information concerning the error. It is up to you to
determine what types of errors might occur, and write this program to detect them and provide
useful information to the user to fix the problem.
5. Sample Simulation Software
A sample discrete event simulation (DES) program is provided. You may reuse any portion of this
code in your own software, but be sure to acknowledge the source of code you use through
comments in the code as appropriate.
Rather than using a time-stepped approach where simulation time advances from one clock “tick”
to the next, discrete event simulations advance time from one event to the next, where each event
represents something “interesting” occurring in the actual system, i.e., the physical system. For
example, typical events might be the arrival of a new customer in a simulation of a department
store or a vehicle arriving at an intersection in a traffic simulation. Each event contains a
timestamp, a simulation time value indicating when that event occurs in the physical system. The
timestamp is analogous to the time step number in a time-stepped simulation, however, events
occur at irregular points in time, not at regular, periodic time steps. Simulation time advances at
irregular intervals as the computation proceeds from one event to the next.
The simulation includes a number of state variables that represent the current state of the system,
e.g., a queue of customers waiting to use a server or the state of a traffic signal. The computation
consists of a sequence of event computations. Each event computation can (1) modify one or more
state variables, and/or (2) schedule one or more new events into the simulated future. For example,
when modeling air traffic at an airport, the computation for an event denoting that an aircraft has
just touched down on the runway might schedule a new event five minutes into the simulated
future to represent the aircraft arriving at the arrival gate and beginning to unload passengers.
The simulation program (implemented by the simulation library) contains two main part:
• Simulation engine. This part of the program is independent of the simulation model, i.e.,
the same simulation engine software could be used to simulate a transportation system or
a manufacturing application. It includes a data structure called the future event list (FEL)
that is a priority queue that contains the set of events that have been scheduled, but have
not yet been processed. The simulation engine holds the main event processing loop which
repeatedly (1) removes the smallest timestamped event from the FEL, and (2) calls a
function (defined in the simulation application, discussed next) to simulate that event. The
loop continues processing events until some termination condition is met, e.g., simulation
time reaches a certain value. The simulation maintains a clock variable indicating how far
the simulation has advanced in simulation time. It also includes a function called by the
simulation application to schedule a new event, i.e., to allocate memory for the event, fill
in various parameters, and insert the new event into the FEL. The main event processing
loop updates the clock variable in each iteration of the loop to the timestamp of the event
it just removed from the FEL.
• Simulation model. This part of the program contains code to model the physical system. It
includes a set of state variables that represent the current state of the system being modeled.
It also includes one or more functions or event handler procedures, one for each type of
event modeled by the simulation. The event handler procedures collectively model the
operation of the system being simulated. To develop the simulation application, one must
define the state variables and the different types of events that are modeled, and implement
a function for each different event type.
This simulation model in the example code implements a specific discrete event simulation model,
specifically, the operation of a simple gasoline station. Although this application is a queueing
network, the code is provided for illustrative purposes to understand how a discrete event
simulation works. It does not conform to the requirements of this assignment. We recommend you
completely rewrite this code. Some of the event types used in this sample simulation will likely be
similar to the kinds of events your simulation code must use.
6. Simulation Study
Once your software is running, construct a simulation to analyze the operation of a food court. In
the following all time values are in minutes. The food court includes:
1. A queueing station where customers enter and receive a tray to carry their food; assume
the mean service time for this station is 0.2 minutes.
2. Five queueing stations (A, B, C, D, E) each serving a different type of food. Assume the
popularity of these stations (i.e., the probability a customer will select that station) are as
follows: A: 0.10; B: 0.15; C: 0.20; D: 0.25; E: 0.30. The average service time of these
stations are: A: 3.0; B: 2.5; C: 3.3; D: 2.8; E: 1.50.
3. Two beverage stations where beverages are obtained, after obtaining food. Assume all
customers purchase one beverage and each customer is equally likely to select either
station. The average service time of the beverage station is 1.0 minute.
4. One or more check out stations where customers must pay for their food. Assume a
customer is equally likely to select any check out station. After departing the check out
station, most customers (95%) will exit the system. However, the remaining customers
(5%) will find they do not have sufficient funds to pay for their food. In this case, their
food order will be left at the check out station, and the customer will go back to make
another food order. Specifically, the customer will bypass the station for picking up a tray,
randomly select one of the five queueing stations (using the same probabilities as reported
earlier) and proceed directly to that station to get a new order of food and then get a new
beverage.
The following statistics are of interest:
1. Number of customers entering and exiting the system during the simulation run. Note these
values will usually not be the same because there will be some customers still in the system
when the simulation ends.
2. The minimum, maximum, and average amount of time a customer remains in the system
among those customers who exited during the simulation run.
3. The minimum, maximum, and average amount of the total time each customer must wait
in queues in traveling through the system.
4. The average waiting time experienced by customers at each station/queue. This
information can be used to identify bottlenecks in the system.
You should complete several simulation runs varying the rate (the inverse of the interarrival time)
of customers entering the system. You should plot curves of (2) and (3) above for different
numbers of check out stations in order to determine how many stations should be utilized. Set the
length of the simulation run to 4 hours (240 minutes). In an actual simulation study, you would
perform each simulation experiment multiple times with different random number streams (initial
seeds), however, here, you need only complete one run for each experiment.
7. Teams and Timeline
You will work in teams of two students each to complete this assignment. We will assign students
to teams. For each team one student should implement the simulation library, and the other the
configuration program. Beyond that, it is up to your team to decide who does what.
You have three weeks to complete this assignment. We recommend that you spend the first week
becoming familiar with discrete event simulations (a document is provided) and the sample
simulation software, figure out how to divide up the work between team members and who will
do what, and jointly develop the simulation library API. We recommend you develop the
simulation software in the second week and get it to work on some test configuration files that you
should define. Use the third week for experimentation and writing the report.
Don’t wait until the last week to complete the entire assignment!
8. Project Report
The project report should be a single document developed by your team. It should be selfcontained, and understandable by someone not familiar with the assignment. It should include a
short introduction section describing the simulation in high level terms and the goals of the study.
The API to the simulation library should be described, as well as description of the implementation
of the library and configuration program. It should include a description of the testing procedure
and evidence the code works correctly. Describe the results of the experiments that were
performed, your analysis of the results (do they make sense?), and explanations of what you
observed. Be sure to discuss any anomalous results and explain what happened.
9. Student Taking CX 4010
If you are a CX 4010 student, you must implement the simulation software, collect the results of
the simulation runs, and produce a report documenting your results. Examine the results you obtain
and argue why you believe your simulator is functioning correctly. You must provide evidence
your code works correctly. Pay special attention to your results for high arrival rates.
10. Students Taking CSE 6010
If you are a CSE 6010 student you must complete the steps described above for students taking
CX 4010. In addition, validate that your software is producing reliable results. To do this consider
the operation of a single queue with a generator to create customers, and exit component to remove
customers once they exit queue. This type of queueing network is called an M/M/1 queue and has
a known mathematical solution. Compare the mathematical solution with the results produced by
your simulation by showing a graph of waiting time as the arrival rate is varied. Write up your
results, including references to the relevant literature, and include in your report.
11. Collaboration, Citing, and Honor Code
Finally, we remind you of class policies regarding collaboration, citations, and the honor code.
All students are expected to follow the Georgia Tech Honor Code. You are encouraged to work
together and help each other on assignments and preparing for exams, but all work you turn in
must be entirely your own work.
We encourage discussion with other students, but all code you turn in must be written entirely by
you. We recommend you destroy any notes taken while consulting with other students before
writing your own code. For team programming projects each student you must clearly document
what code was written by each student; for example, each student’s code may reside in separate
files. Dissemination of code to other students is not allowed, except in the case of students working
together on the same team in team programming projects.
The Internet is a useful resource to solve specific programming problems. You are encouraged to
use the Web for information or to answer specific questions, but copying or utilizing code from
the Web violates the Honor Code. If you use the Web or other sources for any information, you
must cite these sources in your assignment submission. If you are unsure what is permissible,
consult with the instructor or a TA.
