`

Homework 4

(due in stages; see below)

Problem I, due Tuesday, November 20:

This problem will serve as your introduction to JSim, preparing you for the ALOHA network simulation in Problem III.

Modify the M/M/1 queue example in the JSim package to model server breakdown. (Note: Do NOT modify JSim itself, i.e. the JSim classes JSSim, JSElt and JSFacil, though you are welcome to subclass.) Specifically, assume that the server stays up for an exponentially-distributed time with mean MeanUpTime, with repair taking an exponentially-distributed time with mean MeanDownTime. The server continually goes through this up/down cycle, regardless of whether a job is in service at the time (i.e. the server ages even when not serving a job).

If a job arrives when the server is down, the job is put in the queue. If the server goes down while a job is in service, that job is placed at the head of the queue; assume that when it is later restarted, it must start from scratch, not "getting any credit" for work done before the breakdown.

Your simulation will calculate the mean wait, as before, and also the mean number of service interruptions per job.

Suggestions: Add methods DoBreak() and DoRepair() to the existing DoArrival() and DoDone(). In DoBreak(), if there is a currently-executing job, be very careful in your code that stuffs the interrupted job back into the queue; you won't be able to call JSAppendToFclQ() here, since you must put the job at the front of the queue, but look at the source code JSAppendToFclQ() as a guide as to what must be done.

Before you start writing any code at all, make absolutely sure that you understand the existing M/M/1 example. Compile and run that code first, setting the debug flag during execution, so you can "walk" through the execution of the program and see what it does. Then read the M/M/1 source files Main.java and MachineJob.java very carefully to see how the program achieves the desired effect.

In debugging your program, be sure to use a debugging tool (!), as well as using JSim's debug flag.

Validation check: For input values of MeanArrive = 1.0, MeanServe = 0.5, MeanUpTime = 5.0 and MeanDownTime = 0.2, you should get mean wait and mean number of interuptions of about 1.62 and 0.11, respectively. Use a long simulation run time; I used 1000000 here.

JSim is available on the CSIF PCs, in ~matloff/Pub/JSim, and on my JSim Web page. Note: I've made two slight changes to JSim since the time I presented it in class: I've added a random-number seed to the command line, after the debug flag (put any integer in for the seed), and in the JSim code I've changed JSDebug to type boolean.

Problem II, due Tuesday, November 20:

This problem involves CRC error detection. (Note: Remember, you must use LyX or LaTeX for your writeup here, since it is mathematical.) Suppose our CRC divisor is C = 111.

A. For each of the following classes of errors, answer either WDA (will detect all such Es), WDS (will detect some such Es) or WDN (will detect no such Es). In each case, prove your answer if it is WDA or WDN, and give a counterexample if your answer is WDS.

B. Suppose each bit has probability p of being in error, independently across bits, so that for example the probability of the error vector E having the all-1s pattern is pm+c-1. Find P(A|B), where:

Remember, E consists of m+c-1 bits, including both the message and CRC portions. Note that the exact form of C here, C = 111, does not matter; all that is relevant is that c = 3. Examples of Es that satisfy conditions in A are 100100..., 010010... and so on.

Your answer must be an expression in p and m. Here are some numerical examples with which to check your answers:

p = 0.1, m = 4:  0.069
p = 0.1, m = 6:  0.056
p = 0.4, m = 4:  0.065
p = 0.4, m = 6:  0.023

Problem III, due Tuesday, November 27:

Here you will use JSim to simulate an ALOHA network in which many terminals communicate with a central computer. (Note: The model here is somewhat different from the one in the printed lecture notes.)

The application-specific command-line arguments are (in this order):

Each terminal does the following:

   while true  
      think
      do
         start timeout timer
         send frame
         wait for ACK from computer or timeout expiration
         if timeout
            wait for backoff time
      until frame is successfully sent

(Note that this is merely a description of what each terminal does, NOT pseudocode for your program.)

Frame transmit time is 1.0. It also takes 1.0 time for the computer to send an ACK (on a separate frequency, so no collisions with the terminals). Latency is 0.0. There is a random delay between the time the computer receives a frame and the computer starts sending an ACK; this delay, plus the ACK transmit time, has a U(1.0,2.0) distribution. You may write your program on the assumption that the user will set the timeout value to at least 3.0 (1.0 time to send frame, plus at most 2.0 time to get ACK).

The backoff has duration of a geometrically-distributed number of frame times. In other words, the backoff time will have length k with probability (1-P)kP for k = 0, 1, ... where P = 1.0 / NNodes.

The program will compute and output the mean time it takes to send a frame successfully (measured from when the first bit is first sent out to the time the last bit is sent out successfully). Also, if the Verbose flag is set to 1, the program will, at the end of each call to Main.EvntHandler(), output the current value of JSSim.JSSimTime and the state of each terminal. For the latter, give the node number, the current activity -- thinking, transmitting, waiting for ACK/timeout, waiting for timeout (i.e. collision has occurred), backing off -- the time that activity will end, and whether the frame has been in a collision in its most recent transmission attempt.

(The Reader will base a lot of your grade on the accuracy of the verbose output.)

Here are some suggestions:

Here is some sample output to help you check your program:

% jsm 1000000 0 9999 2 0.6 3.5 0
total frames sent = 217961
mean wait = 8.57481
mean number of xmits per frame = 2.3499663
% jsm 1000000 0 9999 3 0.6 3.5 0
total frames sent = 201647
mean wait = 14.279022
mean number of xmits per frame = 3.1427047

(The command, "jsm", is an alias I made for running JSim.)