CSE 326 Data Structures
Project 1
Simulating a Network
Due: Wednesday, 11 April 2001, 10pm
This assignment is
currently in draft status and may be changed!
Objectives
·
Review stack and queue ADTs
·
Become comfortable programming with UNIX/LINUX
and g++
·
Learn how to use templates
·
Practice algorithm design
Overview
Stacks and Queues are two very basic abstract
data types for storing data that are useful in a wide variety of applications.
Stacks have a Last-In-First-Out (LIFO) behavior: an element is removed only
after all items added after it are themselves removed. So, if a number of items
are put on a stack, they will be removed from the stack in reverse order.
Queues have a First-In-First-Out (FIFO) behavior: an item leaves a queue only
after all items added before it leave. Items leave a queue in the order that
they were placed on the queue.
In any network (e.g. a small office LAN, Sieg
Hall, the Internet) there are terminals (e.g. your PC, a server, a
printer). The terminals are connected
via nodes (e.g. modems, internet routers) which are in turn connected via
cables or wireless links. When messages
(e.g. email, print jobs) are sent from one terminal to another, they are first
broken up into data packets of manageable size, and the packets are reassembled
once they reach their destination. The
nodes (as well as the lines connecting the nodes) have a limited capacity (or
bandwidth), which is why message transmission is sometimes very slow, as anyone
who has tried to download a large file over a 56k modem knows.
In this assignment we will simulate the routing
of packets between nodes in a network.
More
detail
The
basic idea
We are just simulating a small piece of a
network, and will be focusing on the problem of deciding where to send a packet
(supposing, of course, that there are multiple paths that lead to the
destination). The basic problem can be
formulated as follows: given a set of packets that need to be sent, and a set
of network nodes they may be routed through, choose the best node for each
packet so that the throughput of the network is maximized. It’s a bit more complicated than that, but
that’s the basic idea.
How
the simulation works
The input to the program has two parts: a list
of nodes in the network, and a list of packets to be sent (see the
“Input
files” section below). Each
node has a
capacity (number of packets it can hold at a time), and either uses a Queue or
a Stack to hold the packets it is sent while they’re waiting to be
processed. Each packet has a “start
time” (the time at which it is to be sent), a priority (how important it is),
and a character representing the data it contains.
When the simulation begins all the nodes are
empty (because no packets have been sent yet).
The NetworkSimulator class (which runs the simulation) keeps a list
of all the
packets waiting to be sent, sorted by their start time, and also a list of
packets that have safely arrived at their destination. At each time step two things happen: first,
every non-empty node processes (dequeues or pops) one packet, and that packet
is added to the list of arrived packets; second, any packets who are due to
start at the current time are sent to one of the nodes in the network. Which node a packet is sent to is determined
by the routing algorithm. The supplied
routing algorithm just sends each packet to whichever node has the most
room. If all the nodes are full then
the packet must wait until the next time step.
When you are implementing your own routing algorithm (see the
“What you
must do” section below) you may want to consider the priority of the
packet
when deciding where to send it, and keep in mind the difference between FIFO
and LIFO.
When all the packets have been sent, and all the
nodes are once again empty, the simulation will terminate and output the
results (see the “Viewing the results”
section below).
What you
must do
Your assignment, if you choose
to accept it, has the following three parts.
I suggest getting Part 1 working completely before starting on Part 2.
Part
1: Implement Stacks and Queues
Implement two versions of the
Queue ADT, QueueA and QueueLL; and two versions of the Stack ADT, StackA and
StackLL. Each should be derived from
(and adhere to the interface of) the supplied abstract base classes for Queue
and Stack. The –LL versions should be
implemented using linked-lists to hold the data. StackA should be implemented using an array, with the top of the
stack at position size-1. QueueA should
be implemented using a circular array, as outlined in the lecture slides. When your program is run with the –l flag the linked-list
versions of your data structures will be used.
Otherwise the array versions will be used.
Part
2: Build a better routing algorithm
Write your own version of the
routing algorithm for packets. The
supplied version is in the function NetworkSimulator::route(Packet). You may add data members or methods to the
NetworkSimulator class as you see fit to help you create your own routing
algorithm. Your version should be used
whenever your program is run with the –r flag (you need to implement this flag). It is important that you use these flags
exactly as specified, otherwise I will not be able to efficiently test your
program.
Part
3: The README file
A large proportion of your grade will be based
on the completeness and clarity of your README file. See the “The README” section below
for a description of what your
README file must include.
The
project skeleton
As a starting point, we've provided a few files
for you to build on:
Stack.h,
Queue.h (do not modify)
These
define the ADTs that you must extend.
You must implement all the undefined functionality (i.e. the pure
virtual functions) in each of your concrete derived classes.
Vector.h,
Vector.cpp, SortedVector.h, SortedVector.cpp (do not modify)
A
Vector is used by NetworkSimulator to keep track of the Nodes in the
network; a
SortedVector is used to store the packets waiting to be sent.
Node.h
(do not modify)
This
defines the Node ADT.
QueueNode.h,
QueueNode.cpp, StackNode.h, StackNode.cpp (do not modify)
These
files define the concrete data types derived from the Node class.
Packet.h,
Packet.cpp (do not modify)
These
files define the Packet type. Although
they are implemented with templates, in our simulation the data will always be
a single character (data packets in the real world are much bigger, of course).
NetworkSimulator.h,
NetworkSimulator.cpp
The
NetworkSimulator class is the heart of the whole program. It reads the input data, keeps track of the network configuration
and when packets are sent, and runs the simulation. You will need to add your own routing method to this class, and
may modify it in other ways as you see fit (as long as your program conforms to
the specifications).
netsim.cpp
This
is the main driver code for the program, which we have partially
implemented. Its main task is to
process the command-line arguments. The
NetworkSimulator class does the rest of the work.
You will need to modify this file to handle the –r option.
Makefile
make netsim will build your program.
You will need to modify the Makefile to include any new files you create. It is very important that you understand (at
least on a fundamental level) how Makefiles work. In the past I have wasted lots of time looking for an error in my
code when the problem was really in my Makefile.
All provided files can be found in the project
directory:
/cse/courses/cse326/01sp/project1
Input
files
Input files have a list of nodes followed by a
list of packets. A single node is
represented by one of the characters ‘q’ or ‘s’, followed by a positive
integer. A ‘q’ means that the node uses
a queue to hold packets, and an ‘s’ means that it uses a stack. The integer determines the capacity of the
node. A packet is represented by two
integers and a character. The first
integer is the packet’s start time, the second is its priority, and the
character is the data. The start time
must be at least 0 and the priority must be in the range 1 to 9 (1 being the
best). Here is an example input file:
q 10 q 18 s 20 s 3
0 5 o
0 1 l
0 9 H
3 5 !
0 7 e
1 4 l
In the network described by this file there are
four nodes. Nodes 0 and 1 are
QueueNodes with capacities 10 and 18, and nodes 2 and 3 are StackNodes with
capacities 20 and 3. There are six
packets, four of which are sent at time 0, one at time 1, and one at time
3. The simulation (with the supplied
routing algorithm, which ignores priorities) will proceed as follows:
Time 0:
send ‘o’ to node 2
send ‘l’ to node 2
send ‘H‘ to node 1
send ‘e’ to node 2
Time 1:
dequeue ‘H’ from node 1
pop ‘e’ from node 2
send ‘l’ to node 1
Time 2:
dequeue ‘l’ from node 1
pop ‘l’ from node 2
Time 3:
pop ‘o’ from node 2
send ‘!’ to node 2
Time 4:
pop ‘!’ from node 2
Then the simulation ends, and the results are
displayed. Note that nodes 0 and 3 were not used at all. That is because
my routing algorithm is very inefficient; make sure yours performs
better! There
are other sample input files in the directory project1/inputs
that you can use to test your program.
Viewing
the results
When the simulation is complete (i.e. all
packets have arrived at their destinations), the program will output two
things. First, a concatenation of the
data in all the packets, in the order they arrived; and second, some statistics
regarding the average amount of time it took each packet to reach its
destination. It will also display these
statistics broken down by priority.
When run on the above file, the output would look like this:
Message: Hello!
Average Transit Time: 1.5
ATT for priority 1: 2.0
ATT for priority 4: 1.0
ATT for priority 5: 2.0
ATT for priority 7: 1.0
ATT for priority 9: 1.0
Note that the output of your
program should look exactly like the output of the sample executable except
when run with the –r flag! When run with the –v
flag (verbose mode), it will output what is happening as the simulation
progresses (something like what is shown above in the “Input files” section).
Turnin
You are required to turn in your project1
directory, which must include at least the following files:
·
QueueA.[h,cpp], QueueLL.[h,cpp], StackA.[h,cpp],
StackLL.[h,cpp]
·
Your modified version of
NetworkSimulator.[h,cpp]
·
Your modified netsim.cpp
·
Your modified Makefile
·
Your README file
·
One or more original
sample input files you used to test your program
·
Any additional files you used
Note: of the files we provide to you, you should
need to change only NetworkSimulator.[h,cpp], netsim.cpp and Makefile (of
course, you
may create whatever files you wish). If you want to change any other files in
the project, contact Nic first!
Turn your files in electronically using turnin:
% cd ~/your326Directory/yourProject1Directory
% make clean
% cd ../
% turnin -c cse326 -p project1 yourProject1Directory
The README
Your README file should document your submission
(though it does not by any means replace comments in the code!). It should
contain the following:
·
Your name.
·
Approximately how long the project took you to
complete.
·
A brief statement of completeness: does your
project meet the requirements? if not, in what ways does it fall short?
·
Acknowledgement of any assistance you received
from anyone but the 326 staff or the Weiss book.
·
A list of the files used in your project with a
brief (anywhere from one sentence to one paragraph) description of each
file. You should describe the provided
files as well as the files you create.
·
A description of your routing algorithm, and in
what ways it improves upon the supplied algorithm.
·
A description of any extra credit you attempted
(see below).
Also answer the following questions (justify
your answers):
·
What do you consider to be an appropriate
measure of the performance of a routing algorithm? Put in another way, how much is it appropriate to delay
transmission of a low priority packet in order to speed the delivery of a
higher priority packet?
·
Can you think of any data structures that might
work better than Stacks and Queues for this purpose?
·
What did you enjoy about this assignment? What
did you hate? Do you have any suggestions or requests for the other projects?
Additional
utilities
We've provided a few utilities to help you
develop and test your program. These are located in the directory project1/bin.
Sample
executable
The executable sample1 is our sample solution
for this assignment. Use it to see what we expect from you.
% ./bin/sample1 < inputfile > outputfile
will run the simulation as specified in inputfile,
and write the results to outputfile.
If you
find this too easy…
For a small amount of extra credit, you may attempt one of the following. If you choose to do one of these, it is important that you first have your program working exactly according to the specifications, so that it will work with my test scripts.
·
Visualization:
Currently, the program merely outputs text descriptions of what’s going
on. Implement a graphical display
(could be ASCII-based or use X-Windows tools) to animate the simulation. Contact the staff if you want to do this but
don’t know where to start.
·
Interaction:
Provide a way for the user to interact with the simulation. Some possibilities are: halting the
simulation at will; controlling the speed of the simulation (delay between time
steps); sending packets on the fly, as opposed to being limited to what’s in
the input file.
·
Alternative Data Structures: Design and implement a different data
structure that you think would perform better than Stacks and Queues according
to the guidelines you specified in your README file. Modify the file format (i.e. change the constructor for
NetworkSimulator)
to allow the use of your new data structure.
This would also necessitate creating a new subclass of Node to use your
new data structure.
·
Other ideas...? (we’re open to suggestions)
Approximate
grading breakdown
·
20% - correct implementation of Stack and Queue
classes
·
10% - your routing algorithm
·
5% - if your routing algorithm performs better
than mine
·
40% - if it works on my secret test files (i.e.
all the command line arguments are implemented, it doesn’t crash, and it
outputs correct results)
·
25% - your README file
Acknowledgements
The format of this document and some of the text
is based on (or in some cases, directly quoted from) the Winter
2000 CSE 326 Project 1 Description. I am using it here with permission of the
author, Steve Wolfman.
Some of the supplied code is also based on the
Winter 2000 version of this assignment, and is used with permission of the
authors, Steve Wolfman, Zasha Weinberg and Nic Bone.
The idea behind this assignment was developed by
Alon Halevy, Maya Rodrig, and Nic Bone.
Except as mentioned above, this document and all the supplied code were
written by Nic Bone.