This week's laboratory project involves writing rules for the behavior of individual objects in a network. The network is made up of nodes -- depicted as large circles -- and channels -- depicted as lines connecting the nodes. Each node may have multiple input channels and multiple output channels. Channels may contain packets. Your job is to write a node behavior that has a single method, transmitPacket, which moves a single packet from one of its input channels to one of its output channels. That's the whole assignment. Well, plus a little bit of experimentation....
This assignment emphasizes the following topics:
You should read through this entire assignment and complete the Lab preparation sections before you come to lab. Some portions of the Post Lab write-up also require your thinking about them before and during the laboratory portion of the assignment.
As per policy, you are encouraged to discuss in detail this assignment with you classmates, but you should do the write-up on your won. You may also get comments from other students onall poritons of your write-up before turning it in, if you wish. Please include the names of anyone with whome you collaborate, in any way, on this assignment, and indicate the nature of the collaboration. [Failure to include this information is a violation of the collaboration policy.]
This assignment is due at the beginning of class on Friday, 8 October.
This week's laboratory project involves a network routing simulation. In the simulation, routers (nodes) send and receive packets (pieces of information) to each other along various routes (channels). The nodes could be computers, for instance, sending and receiving information from each other across the internet. This problem set could be a scaled down (very scaled down) version of a commercially available product.
This section walks you through using the application. A demonstration of the simulation will be available should you wish to play with it before lab. Watch your email for details.If you do not have the opportunity to test the application before lab, you may do this experimentation at the beginning of the lab. If you can make the opportunity to try it out prior to coming to lab, we think that you will find the rest of the lab preparation more straightforward.
The idea of the simulation is to experiment with various network configurations and empirically determine their behaviors. In other words, play with the application and see what happens.
When the GUI pops up, you will see two panels, side by side. The panel on the right, which is currently empty, is where all of the simulations will take place. The panel on the left contains the available GUI elements -- all nodes, in this case. Above both panels are three menus: File, Simulation, and Selection. To use the simulator in the most basic way, you first construct a network and then set it in motion. The necessary steps are described below.
One of the main things you need in this simulator are nodes. In order to add a node to your simulator, select one of the nodes from the panel on the left, then click on the drawing panel to place it somewhere. There are three types of nodes which appear when you first run the program:
To remove an element, click on it and then select Remove from the Selection menu.
The other crucial element in a simulator are channels. Channels run from one node to another, and are represented by a black line with an arrow, connecting the two nodes. In order to add a channel to your simulator, double click on the first node, then click on the second node. Channels have directions: they go from the node you start with to the node you end with. It is possible to have more than one channel between two nodes (e.g., one in each direction), but this isn't drawn particularly well. To remove a channel, outline the channel's arrow by clicking on it, then select Remove from the Selection menu.
To start objects moving through the demo, select Start from the Simulation menu. You can pause the simulation using Pause. You can dynamically add elements while the simulation is running. You can also temporally disable a node or channel by selecting it and then choosing the Disable command from the Selection menu. To re-enable an element, use Enable. Using the Remove option to physically remove an element from the network while the simulation is running is discouraged; deletion is provided only for creating a new network, not for dynamically changing network behavior.
Experiment with the network for a few minutes. Can you get the channels to fill up? Can you create any other interesting behaviors? Remember that you can disable channels (using the Selection menu) while the simulation is running.
[TURN-IN] Keep a record of your experiments to compare your later results with. (Such a record should include both network topology (how things are connected) and dynamic behavior (what you did, what it did).) You can even save any particularly interesting network configurations using the Save As option under the File menu.
We have provided two types of connecting nodes. The first, and the one you have been using (Default Connecting Node), uses a DefaultNodeBehavior. The other type of connecting node you can load is IntermediateNodeBehavior. To run a node with the IntermediateNodeBehavior, try
In the GUI elements panel, you will see this fourth type of node. Can you discern any differences between the IntermediateNodeBehavior and the DefaultNodeBehavior?
[TURN-IN] You should also think about what the simplest networks you could build and test would be. What kinds of networks might cause problems? When might code break? What is the simplest network that you can design? What ought to happen if you run it?
In this lab, you're going to create your own behavior for a Node.
You will do this by creating a class that implements NodeBehavior:
public interface NodeBehavior
{
public void transmitPacket( InputChannelVector inputChannels,
OutputChannelVector outputChannels );
}
Any class implementing NodeBehavior must have a transmitPackage method whose signature matches that of the NodeBehavior interface. The transmitPackage method takes two arguments. The first is a Vector (or collection) of InputChannels; the second is a Vector of OutputChannels. The job of your NodeBehavior's transmitPacket method is to take a single packet from a single InputChannel and move it to an OutputChannel. transmitPacket will be called over and over again.
An InputChannel is a thing from which you can read an object:
public interface InputChannel
{
public Object readObject() throws ChannelEmptyException,
ChannelDisabledException;
}
You only need to read one packet from one input channel on each time around the interactive control loop. Note that a given input channel may be empty or disabled, in which case it will throw an appropriate exception.
An OutputChannel is something to which you can write an object:
public interface OutputChannel
{
public void writeObject(Object o) throws ChannelFullException,
ChannelDisabledException;
}
An active non-full output channel would be a good place to put any packet you may have picked up. But be careful: when an output channel is full, it will throw an exception if you try to write to it. Make sure that you don't drop any packets if this happens, or write packets that don't exist.
Note, however, that your NodeBehavior 's transmitPacket method will not be passed an InputChannel and an OutputChannel. Instead, it will receive a (possibly empty) collection of inputs representing the set of InputChannels leading into that node. This is represented using a class called InputChannelVector, which simply holds a bunch of InputChannels. Your job is to select one particular InputChannel (if there are any available) from which to read. Similarly, your NodeBehavior's transmitPacket method will be passed a (possibly empty) collection of outputs.
An InputChannelVector is a collection of InputChannels. It has the following methods (among others):
public final boolean isEmpty( );
/* Returns true if the InputChannelVector is empty. */
public int size( );
/* Returns the size of the InputChannelVector. */
public final InputChannel elementAt( int index );
/* Returns the InputChannel at a certain index. */
/* Note that numbering begins at 0 */
public final InputChannel firstElement( );
/* Returns the first InputChannel in the InputChannelVector. */
public InputChannel lastElement( );
/* Returns the last InputChannel in the InputChannelVector. */
An OutputChannelVector is similar, except that its methods return OutputChannels.
Your NodeBehavior class will not be an Animate, i.e., it will not have an act() method, although it will behave almost as though it does. Instead, your NodeBehavior will have a transmitPacket method that will be called much like an act() method, but with additional information provided (specifically, the currently connected input and output channels).Since transmitPacket( ) will be called repeatedly, you only have to handle one object at a time.
The main piece of your job is to implement the transmitPacket( )method of NodeBehavior. This method should select a particular InputChannel from inputChannels and take an object out of that channel (using readObject()) . It should also select a particular OutputChannel from outputChannels and feed the recently read object to it (using writeObject()).
You should begin by implementing the simplest NodeBehavior class that you can. For example, assume that the input channel vector will contain exactly one input channel and that the output channel vector will contain exactly one output. How would you get a packet (object) from the input channel? How would you write it to the output channel? Design a class that implements this.
Remember that Channels occasionally throw exceptions. You need to be concerned about four of these:
At first, you should simply catch these exceptions; you need not do anything smart when they happen. By the end of lab, you should make sure that your code is robust to these exceptions, and does not lose objects.
[CHECK-IN, TURN-IN] Design your simple code. In lab, build it and test it. What is a network on which you could test your code? What is a network on which you would expect your code to break? How will it break when it does? You will need to turn in your predictions on these questions.
Next, design a (possibly different) NodeBehavior that can handle a more complex situation. What single aspect of the problem will you scale up first? Remember that, in a fully general solution, you may have multiple InputChannels and OutputChannels, and that some of them may be disabled. Also remember that you need to make sure you neither lose nor create packets. There are also many strategies that you can use to choose the input and output channels from their respective Vectors.
Scale up slowly. You should bring to lab a development plan that describes each addition you'll make to your class. You should test each addition as you make it, so you will need test networks on which you expect your code to succeed, and others on which you expect it to fail, at each stage. You should also come up with multiple strategies for choosing input and output channels. You should describe these strategies in English, think about how to implement them, and have examples of neworks on which each of these strategies would work or not work particularly well. The more creative you can be, the more interesting your lab will be.
[CHECK-IN, TURN-IN] You should design code for at least one of these strategies, and ideally for more than one.
[TURN-IN] One of the main points of this lab is to observe the effects of different strategies on the behavior of your network as a whole. Is a particular strategy fair? Does it drop packets? Create them? Do packets cluster in certain parts of your network? Can you come up with a strategy that behaves differently?
Some utilities that you might want to use:
public static void cs101.util.Console.println( String what );
prints its argument to the Java console. This is extremely useful for debugging. You can refer to this method as Console.println if you include the line import cs101.io.*; at the top of your file.
public static int cs101.util.MoreMath.randomInt( int range );
returns an int between 0 and range, inclusive. You can refer to it as Math.randomInt if you include the line import cs101.util.*; at the top of your file.
public static void Thread.sleep( int millis )
throws InterruptedException;
causes the current Thread to sleep for millis milliseconds. This allows you to put delays in your nodes. Warning: You will have to catch the exception, though you don't necessarily have to do anything with it.
If you have other ideas, design them and then ask us about them.
1. Write a statement that could appear inside a nodeBehavior's transmitPacket method and that would read a single packet from a single input channel and assign it to some name. Under what assumptions would this expression work? Under what assumptions would it fail? Can you make it more robust?
2. Write a statement that could appear inside a nodeBehavior's transmitPacket method and that determines whether there are any output channels available for writing. A channel is available if it exists, is not disabled, and is not full.
3. Chapter 9, exercise 2. (Hint: Console also has a readln() method.)
[CHECK-IN, TURN-IN] You should bring
Your job in lab is to implement one or more node behaviors, to test these behaviors on your own examples, and to exchange example networks with other students in the class. During lab, you may share your test networks. Test data development should be pooled, and sharing of test data is encouraged. Discussion of why networks behave as they do is strongly encouraged. Talk to the people next to you to get good ideas for test networks. See if you can find a network that stumps your neighbor.
Begin the lab by implementing a very simple node behavior. You will need to define a new class, say MyClass. What should you call the file it's defined in? What does it need to extend or implement? What methods does it have? (Remember that the interactive control loop is already defined for you, but it expects to be able to call your transmitPacket() method with two arrays.
The first lines of your file, before your class definition, will need to say:
package nodeNet; import nodeNet.Exceptions.*;
Also, you should be sure that your class is public, and you may want to import the cs101 packages as described above (e.g. if you want to use Console or MoreMath).
[TURN-IN] Once your code compiles, you should try running it. To run your code, you will need to supply the name of your node behavior class to nodeNet. You can do this by running the Java target
nodeNet.Main
on the argument
nodeNet.MyClass
or whatever your class is actually called. You can now test your code. It is probably best to use a very simple network first. See the instructions above for how the simulation works. Don't forget to start the simulation....
Once you have this network running, try some others. See if you can find one that stumps your code. If you built a simple enough node behavior, this shouldn't be too hard.
[TURN-IN] Now is the time to try to fix it. Make one improvement at a time, then test it to see both where it works and where it doesn't. Keep copies of each version of code as it works. (You can make as many node behavior classes as you want. Print them out and also keep them online.)
[TURN-IN] Also keep a log of which networks it runs on, which it fails on, and how it fails. You will need to turn each of these things in with your final assignment.
This lab does not have a target assignment. Instead, your target should be to write a program that runs as successfully as you can and to test it thoroughly. Testing will involve designing networks that might trip up your code. If you can't figure out how to break your code, let your neighbor try. If s/he can't stump it, ask a course assistant. If none of you can cause your code to break, congratulations!
Before you leave lab, you will need to have your work checked off by a course staff member. You should allow time for an adequate demonstration and discussion of what you have done, and you should expect to show your notes regarding experiments you have done. Please do not wait until the last minute to be checked off.
Print out a copy of your various node behavior files and turn them in along with your writeup. (A TA can help you print out your code.) In addition, be sure you turn in your finger exercises, your development plan, your predictions of how things will and won't work in lab, and an explanation of how your code actually worked and didn't. Your complete assignment should include:
In addition, briefly discuss the following questions:
Don't forget to include information about any collaboration you may have engaged in!
This course is a part of Lynn Andrea Stein's Rethinking CS101 project at the MIT AI Lab and the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.
Questions or comments:
<cs101-webmaster@ai.mit.edu>