CS 1723/1721 Data Structures Exercise 6

CS 1721 Recitation Exercise 6:
A Queue Application - Studying Network Node Behavior Using Event-Driven Simulation
Time Required: 2 Weeks

The final hand-ins are to be turned in to your lecture instructor at the beginning of class. No late assignments will be accepted! You may NOT turn in assignments in mailboxes or under doors.

Objectives:

Understand how event-driven simulation works.
Use a priority queue in a realistic application.
Use a queue in a realistic application.
Use an abstract class.
Use an abstract method.
Use a final method.
Understand a program in which multiple classes collaborate to solve a problem.
Learn about empirical approaches to performance assessment.

Prior to the Recitation:

Print out the recitation handout and read it carefully before you come to class.
Print out the Simulation Case Study and read Parts I - IV. Answer study questions #1 and #2.

Hand-in Requirements:

Hard-copy of the source for:

Week 1:

IncomingLineMain.java (1 pt)
EventMain.java (1 pt)
IncomingOnlyModel.java (with your additions highlighted) (2 pts)
IncomingOnlyMain.java (1 pt)
OutgoingLineMain.java (1 pt)

Week 2:

UnbufferedNodeModel (with your additions highlighted) (3 pts)
UnbufferedNodeModelMain.java (2 pts)
BufferedNodeModel (with your additions highlighted) (3 pts)
BufferedNodeModelMain.java (2 pts)

Required plots - Week 2:

Average time between messages versus average interarrival time for IncomingOnlyModel (1 pt)
Comparison of the results from the UnbufferedNodeModel and the BufferedNodeModel (2 pt)

NOTE:

processEvent

SimulationModel

Study Questions:

Week 1: Part I: (6 pts)
Week 2: Part II: (5 pts)

Files necessary for this recitation:

Details:

Part I: (One Week) Testing the components

A. Testing the Event Class

Create a new project called eventpkg.
Create a main test class called EventMain to test the Event class.
Save the following file in the eventpkg project source directory:

Event.java

<1> Generate client code to create three events representing the following:

who (`ID`)	what (`type`)	when (`time`)
`0`	`1`	`10`
`1`	`1`	`13`
`2`	`1`	`11`

toString

<2> Create an Event object with a type of event that is not identified such as what is 3. Use the toString method to print the event.
<3> Generate client code (in EventMain) to create a PriorityQueue named p. (You will need to import the package containing the priority queue classes, weiss.nonstandard.) Insert the three events you created in step &;lt 1> in the PriorityQueue p using the insert method.
<4> Write a loop that deletes events from the PriorityQueue p (use deleteMin) and prints each event until p is empty.
<5> Create 15 new MSG_ARRIVAL events from a sender with an ID of 1 and put them on PriorityQueue p. The time of the first event should be 10, the time of the next event should be 20, the next event should be 30, and so on.
<6> Write a loop that deletes events from the PriorityQueue p (use deleteMin) and prints each event and its interarrival time until the p is empty. (The interarrival of the first event is its time, the difference between its time and a last arrival time of 0.)
Answer study questions 3, 4, 5 and 6.

B. Testing the IncomingLine Class

Create a new project called incominglinepkg.
Create a main test class called IncomingLineMain to test the IncomingLine class.
Copy the following classes to the project source directory:
- IncomingLine.java
- Event.java
Add these files to the project and the package. Build and run.
<1> Write client code to create an IncomingLine object with an arrivalParm of 30, a start time of 0 and an ID of 1. Use the getNextArrival method of the object to generate 100 message arrival events and calculate the average interarrival time (i.e., the average time between messages).
<2> Write client code to create 2 IncomingLine objects with IDs 0 and 1, respectively. Each IncomingLine should have a start time of 0 and arrival parameters of 30 and 10, respectively. Generate 5 message arrival events on line 0 and 4 message arrival events on line 1. (Hint: Use getNextArrival to generate MSG_ARRIVAL events.) Print each event as it is generated and the interarrival time for each message and the average interarrival time for each line.
<3> Add a getAverageInterarrival method to IncomingLine. This method returns the average interarrival time of the messages generated so far by the IncomingLine. Modify the toString method of IncomingLine to show the average interarrival time of the messages generated so far. Add the client code after the part <1> code to call getAverageInterval and compare the results.
<4> Write client code to create an array of 10 IncomingLine objects with ID's of 0 through 9 respectively. Each IncomingLine should have a start time of 0 and an arrivalPara of 5. Generate 7 messages (message arrival events) from each IncomingLine and place them on a PriorityQueue p. Remove all of the events from p and calculate the average interarrival time of the interleaved event stream.
Answer study questions 7, 8, 9 and 10.

C. Writing a simulation model with multiple incoming lines

Create a new project called incomingonlypkg.
Create a main test class called IncomingOnlyMain to test the IncomingOnlyModel class.
Save the following files in the incomingonlypkg project source directory:

<1> Add client code to IncomingOnlyMain to create an IncomingOnlyModel with an interarrival time parameter of 20. Run the simulation for 100 time units and output the results.
<2> Add client code to run the IncomingOnlyModel object of <1> for an additional 200 time units and output the results. (What should the stoppingTime be?)
<3> Add getTotalArrivals and getAverageInterarrival methods to the IncomingOnlyModel class. Also include the total number of arrivals and average interarrival time information in the toString of IncomingOnlyModel. (Hint: SimulationModel already has a toString. Add a toString to IncomingOnlyModel that appends additional information to super.toString().) Write client code to test these additions. Be sure your answers are reasonable before going on.
<4>Modify IncomingOnlyModel so that it has a second constructor that has an additional parameter, lines, indicating the number of incoming lines. Change inLine to be an array with lines elements, each of which is an IncomingLine object. (You should change the original constructor to call the new constructor with a lines value of 1.) Be sure that getAverageInterarrival returns the average interarrival time of the interleaved stream. The IDs of the IncomingLine objects should be consecutive integers starting from 1.






<5> Now add client code to create the following IncomingOnlyModel
simulations:



3 lines with average interarrival time of 2.


8 lines with average interarrival time of 5.


2 lines with average interarrival time of 10.


6 lines with average interarrival time of 20.

Add client to run each simulation for 200 time units. Print the
results using the toString method.  Build and run. Get a
hardcopy of your results to use in Part II. C <1>.
 Answer study questions 12 and 13.



D.  Testing the OutgoingLine class


Create a new project called outgoinglinepkg.
 Create a main class called OutgoingMain and add it to the project.

Save the following files in the outgoinglinepkg project source
directory:



Event.java
 OutgoingLine.java

Add the files to the project and the package.
 Build and run.



<1> Write client code to create an OutgoingLine object named
g
with a service time of 30 and an ID of 1.
Print g using the toString method. 

<2> Write client code that sends a message at time 10.
If the message is not lost, output the time the message will be completed.
Use the toString method to print g.

<3> Send additional messages to g at times 45,
64, and 79.  If the message is lost, print out
an error message, otherwise print out the time the message was sent.
In both cases print g.

 




Study Questions Part I:

 1. Find another
real-world problem that is in the same form as the network router problem
and the
airport runway simulation. Fill in the equivalents for the following.

 Node:     
 Message:     
 Incoming Line:      
 Outgoing Line:      
 Waiting:      



 2. For the example that you gave in study question 1, list possible events.

 3. What types of events are identified by the 
Event class (Case Study Figure 2)?

 4. What
happened when an event that is not identified is created (Lab Part A <2>)?


 5. What
data field in the Event class determines the order the events are removed
from the PriorityQueue (Case Study Figure 9)?

 6. Why
does the Event class need to implement the Comparable
interface? (Case Study Figure 2)?



 7. How is
the average interarrival time of an IncomingLine
related to the arrivalParm (Lab Part B <1>)? 

8. Using the
interarrival times generated in your project in Lab Part I. B <2>,
 make a list of arrival times and interarrival times
for each line:

    Line        
    Arrival Times      
    Interarrival Times     
0         
1         



 9. Using
the arrival times for the two lines, what is the average time between
messages?
Show your work (Case Study Figure 4).


 10. What
is the expected time between the interleaved messages from the two lines if the simulation
is run for a long time (Case Study Figure 6)?


 11. Explain
why the two lines don't generate exactly the same number of messages.
(Case Study Figure 5 ).



 12. When the simulation
ends, why doesn't the number of events (numberEvents) equal
the number
of messages generated (totalMessages) (Case Study Figure 13)?


 13. How do you think
the average time between message arrival at the router should be related
to the 
number of incoming lines and their individual arrival rates?





 


 Part II: The UnbufferedNodeModel versus the BufferedNodeModel


A.  Testing the UnbufferedNodeModel class


Create a new project called unbufferednodemodelpkg


Create a main class called UnbufferedNodeModelMain.

Save the following files in the unbufferednodemodelpkg 
project source directory:



Event.java


IncomingLine.java


SimulationModel.java


OutgoingLine.java


UnbufferedNodeModel.java

Add these files to the project and the package. Build and run.

<1> Add client code to UnBufferedNodeModelMain that creates an
UnbufferedNodeModel
with an average interarrival time of 10 and a service time of
5.
Print using the toString method.


<2> Add client code to run the simulation until time 100 and
output the results. Build and run.  


<3>Now add client code to create the following UnbufferedNodeModel
simulations:



Average interarrival time of 2 and send time of 5.


Average interarrival time of 5 and send time of 5.


Average interarrival time of 10 and send time of 5.


Average interarrival time of 20 and send time of 5.

Add code to run each simulation for 200 time units. Print each
result using the toString. Build and run. Get a hardcopy
of your results to use in Part II. B <2>.

<4> Add a second constructor to UnbufferedNodeModel to allow
multiple input and output lines.  The second constructor has 4 parameters:
the interarrival parameter, the service time, the number of input lines and the number of
output lines. 
The IDs of the input and output lines should each start at 1 and
be consecutive (1 + index in the array). 
Assume that when a message comes in, it will be forwarded on the lowest
numbered available output line.  If all of the output lines
are busy, the message will be lost.
 Write client code to test this.  Modify your original constructor
to call the new constructor with one input line and one output line. 

Answer study questions 14 and 15.






B. Implement the Buffered Node Model


Create a new project called bufferednodemodelpkg
 Create a new main class called BufferedNodeModelMain.


Save the the following files  into the bufferednodemodelpkg
project source directory:



Event.java


IncomingLine.java


SimulationModel.java


OutgoingLine.java


UnBufferedNodeModel.java (from Part II A)



Add these files to the project and the package. Build and run.


BufferedNodeModel is similar to the UnbufferedNodeModel
except that it has a queue to temporarily hold messages that have arrived
but that cannot be sent until an outgoing line is free. Bring UnbufferedNodeModel
into the source editor. Use the Save As option on the File
menu to save the file as BufferedNodeModel.java. Add this new
file to the bufferednodemodelpkg project.

 <1> Make the following changes to BufferedNodeModel.java:


 Change the name of the class to BufferedNodeModel.
 Change the name of the constructor to BufferedNodeModel.
 Change the title in the call to super in the constructor.
 Add a private field of type Queue called messageBuffer.
 Change the lostMessages variable to
queuedMessages.  It should keep track of the number of
messages currently in messageBuffer. 
 Initialize messageBuffer in the constructor by instantiating
a ArrayQueue object.

Build and run the program.

<2> Add client code to create a BufferedNodeModel that has
an average interarrival time of 10 and a service time of 5.
Add client code to run the simulation until time 100 and output
the results. Build and run. The answers should be the same as with the
UnbufferedNodeModel
for the same parameters.

<3> Modify the processEvent as follows:

 To handle the MSG_ARRIVAL event:



If all of the OutgoingLine objects are busy, enqueue the event without further
processing.


Otherwise send the message as before.


In any case still create a new event corresponding to the incoming line
creating a new message.



To handle the MSG_SENT event:


 Update the count of the messages sent as before. 
 If messageBuffer is not empty, dequeue an event (don't forget
to type cast) and send the message on the outgoing line as if it had just
come in.


Build and run the program.
 <4> Now add client code to create the following BufferedNodeModel
simulations (1 IncomingLine and 1 OutgoingLine):


 Average interarrival time of 2 and service time of 5.
 Average interarrival time of 5 and service time of 5.
 Average interarrival time of 10 and service time of 5.
 Average interarrival time of 20 and service time of 5.

Add client code to run each simulation for 200 time units. Print
the results using toString.  Build and run. Get a hardcopy
of your results to use in Part II. C <2>.
 Answer study question 16.



C. Compare the UnbufferedNodeModel and the BufferedNodeModel.

(You will  use Microsoft Excel
and Microsoft Chart to create spreadsheets and graphs in this
part of the recitation.)
<1>  Analyze the IncomingOnlyModel results.
Use the output generated in Part I C <5>
 of the IncomingOnlyModel to do the
following:

 Graph the average interarrival time observed at the router and
the specified average interarrival time for an incoming line using the
y-axis  (Instructions). 
 Label the chart:


title:
 Incoming Only Model
 x-axis:  Sample Runs
 y-axis:  Interarrival Times






<2> Use the output generated in Part II. A <3>
to generate a chart with the average interarrival time plotted versus
the number of lost messages.  The chart should be labeled:
 
title: 
Lost Messages in the Unbuffered Model
x-axis:
Specified Arrival Parmeter
y-axis: 
 Lost Messages
 



<3> Use the output generated in Part II. A <3>
 and Part II. B <4>  to generate a chart with
specified average interarrival time plotted versus outgoing line utilization. 

 The
graphs for the two datasets should be on the same graph using different
line types to distinguish them. 
 The chart should be labeled:

title:
Comparison of the Unbuffered and Buffered Models
x-axis:
Specified Arrival Parameter
y-axis: 
 Outgoing Line Utilization



  Answer study questions 17, 18, 19 and 20.




Study Question Part II:


14. Suppose the UnbufferedNodeModel is run
with one incoming line and one outgoing line. The incoming line produces
 incoming messages  at
times 10, 45, 64, and 79.
The outgoing line (initially free) takes 30 time units to send a message.
Trace the
following values as the messsages
are being processed. Which message(s) will be lost? (Case Study Figure
16)? 

     Start Time     
     Done Time      
    Messages Sent      
    Messages Lost      
    

  


15. If the Event e
 received in processEvent is a MSG_ARRIVAL,
 the sendMessage
method in OutgoingLine is
 invoked. What will be returned if the line is free?
What will be returned if the line is busy?


 16. Explain why it is necessary to use the queue rather than a priority
queue for the message buffer.


 17. For each of 4 runs  in Part I. C <5>,
give an estimate of the expected average interarrival time.
Write the expected result for each of the 4 trials on the graph 
of Part II. C <1> and compare this
with your simulation results.


 18. As the average interarrival times increase, fewer
messages will be arriving.  Use your chart in Part II. C <1>
to explain how lost messages will be affected in the unbufferd case.


  19. Compare the outgoing line utilization of the buffered
and unbuffered models as the average interarrival times decrease. 


20.  Which of the models (unbuffered or buffered) performs
better when the lines are very busy (interarrival time is small).
Explain this observation.





Last revision: October 7, 2001 at 5:20 pm. by K. A. Robbins and C.
Key

Node:
Message:
Incoming Line:
Outgoing Line:
Waiting:

Line	Arrival Times	Interarrival Times
`0`
`1`

Start Time	Done Time	Messages Sent	Messages Lost

title:	Incoming Only Model
x-axis:	Sample Runs
y-axis:	Interarrival Times

title:	Lost Messages in the Unbuffered Model
x-axis:	Specified Arrival Parmeter
y-axis:	Lost Messages

title:	Comparison of the Unbuffered and Buffered Models
x-axis:	Specified Arrival Parameter
y-axis:	Outgoing Line Utilization