This assignment is designed to make use of the queue ADT. You may use the queue implementation from the text (on Blackboard queues.zip), or you are welcome to use the queue implementation built into Java (java.util.queue). There are differences in the Java method names from those of the text implementation. Consult the Java API for more information: http://docs.oracle.com/javase/7/docs/api/ .

Note: Specifications may change, and design details will be looked at in class to help clarify requirements and language issues.

Why is the Internet so slow?

Queues are used to simulate real-world objects, in particular computer network performance. This assignment will abstract from the operation of the Ethernet in order to simplify the problem. The model still captures certain aspects of network performance and is a good illustration of the use of the queue.

Each device on the Ethernet is connected to the net via special hardware called a controller. You will model performance of the Ethernet when two or more controllers try to send a message at the same time. The network can only transmit one message at a time, so when two controllers start sending simultaneously, the message is garbled. The controllers listening to the network are able to detect the problem, so they ignore the garbled message. Also, the two controllers trying to send will each notice that the message didnt go through, resulting in a collision. In this case, the controller will back off and try again later. Randomness is used to prevent the two controllers from trying to send again at the same time.

Your PC (or other device) knows nothing about how Ethernet works, only that it can send and receive data on the network. When a device sends data to the controller, the controller may or may not be able to send it right out to the network. Likewise, when information is being captured by the controller, the device may not be able to keep up with the speed of the Ethernet. So the controller will have a queue at its interface with the device.

For this simulation, the focus is on sending data. By simulating the performance of the network under various assumptions about the number of devices, the frequency of messages, and the size of messages, you can estimate the frequency of network collisions. One performance characteristic is effective bandwidth ratio. This is a measure of the ratio between the amount of data actually transmitted and the maximum possible data. For example, if the network is transmitting data half the time and is idle half the time, its effective bandwidth ratio is 0.5. As the number of messages goes up on an Ethernet, the effective bandwidth ratio will go up; but if too many devices are trying to communicate at once, collisions will occur, and effective bandwidth ratio will decline.

Implementing Controllers and Devices

You will implement controllers and devices as Java classes. The Controller class will be a client of queue. While controllers can send and receive simultaneously, this simulation will divide the process into two phases. First, check with each controller to see whether it has data to send. If no controllers are sending, the network is quiet; if exactly one controller sends, the network contains the data sent by that controller. When two or more controllers try to send, a network collision occurs. In the second phase, each controller receives the contents of the network.

In the controller interface (below), values netQuiet and netCollide are special constants. The controllers either receive the data sent by one of the controllers, or else one of these special values.

The main program runs a sequence of simulations, with the number of controllers going up by ten each time. The code declares an array ctrl of controller objects. Each controller will have its own values for its variables. Thus different controllers will be in various states, but all this gets taken care of by Java. Each controller has the same logic, but each operates independently. [Way to go OOP!]

The Controller

The interface is shown below. In phase 1, the controller starts by calling the update function for its associated device if a device is trying to send data to the network, a value will be returned and stored in inchar; otherwise, 0 will be returned. This isnt too realistic, because it forces the controller and the device to operate synchronously, buts its good enough for the simulation. If a character arrives from the device, it is enqueued in outQ, which corresponds to the queue in the figure above.

/**

* Controller interface

*

* @jam

* @1.0

*/

public interface Controller

{

final int netQuiet = 0;

final int netCollide = -100;

final long maxWait = 20;

public enum state {Idle, Listen, Wait, Send}

public int phase1();

public void phase2(int netchar);

}

Controller State Machine

The operation of the controller is described by a set of states: Idle, Listen, Wait, Send. Designate each pair of calls to phase 1 and phase 2 a step. Each step begins in one of the four states and, depending on the results of calling the device and upon the contents of the queue, may stay in the same state or transition to another state. The operation of the controller is shown in state diagram below. Circles represent the four states, and arrows represent the possible transitions. The text along the arrows summarizes the conditions under which a transmission occurs.

The only transmission that can occur in phase 1 is from the Idle state to the Listen state if the controller is idle, and the device sends a character, the controller should now listen to the state of the network. Phase 1 communicates with the device, and also sends characters out to the network. A character is sent to the network only from the Send state; the character always comes from the outQ. In phase 2, the network sends to the controller its current contents a character, or one of the special values netQuiet or netColllide. Note that in phase 2, the controller does not have any output. Another subtle point is that phase 1 looks at the front of the queue using the front operation and doesnt dequeue the character, since phase 2 needs to examine the same character to determine whether it has reached the end of a message.

Devices

Each controller declares a device, so there will be multiple device objects operating simultaneously, each using the same logic but potentially in different states. The device is either Idle or Sending. An Idle device picks a random number between 0 and the constant avDelay-1. Each time a 0 comes up, the device moves to the Send state and returns nonzero values to the controller, finally ending with the special value endMessage, and then returning to the Idle state. The Device interface is shown below.

/**

* Device interface

*

* @jam

* @1.0

*/

public interface Device

{

final int avDelay = 5000;

final int avMsg = 10;

final int endMessage = -1;

public int update();

public enum state {Idle, Sending}

}

Your task is to implement the Controller and Device classes, and develop a test driver to run the simulation. The driver (main) will do some initialization to input the number of periods and number of controllers, and run the simulation. A loop is used, as determined by the input, to instantiate controllers and devices, send messages, and detect collisions.

The graph (on the next page) shows sample data from running the simulation. The average delay between messages is 5000 and the average message length is 10. For each controller, a trial of 100,000 steps was run, and the number of transmissions and collisions are shown. As the number of controllers increases, the amount of data goes up, until the growing number of collisions eats into the available bandwidth. Experiment with other values.

There are a number of modifications and improvements that can be made to this simulation in order to model more closely the real operation of an Ethernet. The simulation is by definition an abstraction from reality, and that whenever possible the results of simulation must be confirmed by comparing with real-world data. The choice of features to include in a simulation is quite difficult and requires judgment based upon experience.

Run the simulation with various values of the average delay and average message length. How do the result compare with the graph below?

Modify the code for the controllers to keep track of the average delay between the time a message arrives at the controller and the time it is successfully sent across the net. Create a graph of the average (across all controllers) of the averages. Compare this graph with the one below.