This assignment is due by the end of Friday, July 27th (midnight)

This is the full description of the first networking assignment, which is Assignment #4.

Networking is a complex topic, so I've had to pick through a veritable minefield of issues to try to focus in on a model that's a reasonable assignment. There are two issues that naturally arise, message structure and message traffic. To begin we'll need to ignore one and concentrate on the other. Luckily, we can design the system in a modular way so that we can start with either and add in the other aspect later, with little or no change to the structure we designed initially.

Here is how I decided on an initial direction. Messages are passive, but the modules that create and dismantle them are not. Contention, on the other hand, would be very much an abstraction in which a module would be given a message that might not be delivered immediately, but the user of that module would be unaware of that, unless the system became saturated. In the end, message construction is simply not as interesting as the contention abstraction. So we'll begin with trivial messaging and solving the contention problem. Hopefully we'll be able to jazz up the message structure in the next assignment.

The contention problem in networking

Nodes on a many networks send messages independently, without knowing what the other nodes are doing. Though there are many protocols they all have problems similar to this, at the lowest level. Why? Because if they tried to ask another node what it was up to in order to decide whether or not to send a message, the mere asking would be another message! So this problem is pretty hard to avoid and most networking systems have some strategy for avoiding it.

The system we'll model is the classic Ethernet, invented in 1973 by Bob Metcalfe (currently dividing his time between Beacon Street and Lincolnville, Maine).

Here's Metcalfe's picture of it, from a 1976 presentation.

The problem. Collisions occur: When a node places a message on the net, while it's still propagating on the net another node may place a message on the net. The resultant message represents a "collision" and is just the sum of the two (the electrical sum of the two signals) so it is garbled and neither message can be sorted out. Imagine that I printed two messages on transparencies and then laid them on top of each other and looked at the result. It would be a mess. That's the kind of contention problem that the ethernet has to deal with.

The solution: Collision sensing and backoff. Each node that sends a message monitors the link to see if there is a garbled message there. Each node that senses this "backs off" -- it waits a random time and resends the message. In the real ethernet, each successive time it fails it picks its random wait duration from a longer set of possible wait times -- a key innovation. We'll ignore this nicety. But the important point to note is this. If an application on a node gives its network driver a message to send, the message may encounter a collision, so the driver must store the message for later transmission. We'll model this with a queue, the only sensible model. The important point here is the abstraction involved. The application gives the message to the driver and forgets about it, assuming it will be sent. The driver may not actually send it until some later time. We can still limit the queue and eventually return an error code to the application if the net is becoming saturated. But one thing at a time.

The science and technology of networking: The two most popular texts on networking are Tannenbaum's Computer Networks or the more recent one, Computer Networking by Kurose and Ross. You can find info about them on-line and may even be able to access the second book on-line if you register.

What you are to do for this Assignment #4

You will be producing:

• A design document in HTML
• A testing document in HTML
• Source code compiled, but executing it is not required
• Javadoc documentation

The instructions below for what the system design is to be are deliberately brief because it is your job to produce the design! On the other hand the instructions are intended to be quite clear about the form and structure of what you are to produce.

The design document, brief notes

The design document should be well-organized English text. It should not focus too much on the REQUIRES, MODIFIES, EFFECTS style of specification, since a fair amount of it will talk about temporal issues and the flow of messages through the system. The overall form of the document is laid out below but the details of your design and how you present and explain it are up to you. If you wish to add graphics, you're welcome to draw them by hand and hand them in as clearly labeled hardcopy to Ms. Shan or me. But this could be a bit problematical since the assignment is due by midnight on a Friday. You work it out. And of course any graphics that you can put in your web pages will obviate these difficulties.

HTML for the design and testing documents: You are required to write your two documents in HTML. Not everyone in the class may know how to write HTML, but simple HTML is not hard in the slightest. And it's time to learn it if you don't know it! To see just how easy it is, bring up this simple model page in your browser and choose view source to look at the HTML source code. You can also save the HTML source code to a file or select and copy the source into an editor. Then edit away to change it into your design document.

The system design -- for a C (OK job) or a B grade (particularly good job).

Here is an overall description of the design and functioning of the simulation.

• The basic modules will be nodes, links, messages and the simulation.



• Within each node will be more four modules, a sending application, either "email" or a "file" sender (virtually identical), and a sending driver that takes application data and tries to put it on the link. There will be two other modules that parallel these, a receiving application and a receiving driver. There should be two or four classes corresponding to these modules, depending on your design.



• For testing purposes, a "sniffer" is useful for monitoring web traffic, but it only tells you what's there, not whether or not an application's attempt succeeded. For this you'll have to describe some more specialized testing functionality that keeps track of queue sizes, etc. You should make up some sample output to show what they might produce, output they'd typically write to a file.



• You should use Interfaces and Abstract classes in your design wherever appropriate.



• The functional design of the simulation will differ somewhat because of collision checking. The order in your simulation should now be:
  1. Use a senders() call to the nodes to run the senders in the appropriate order, i.e., app then driver.
  2. Run collisionChecker() on all nodes so drivers can now check to see if a collision occurred. (This can be facilitated by having the link contain a Vector of all messages inserted by senders. If there's more than one entry, a collision has occurred.)
  3. Run receivers() on each node which in turn run the receiver drivers and then the apps.
  4. Clear the link.



• You should do something to distinguish the message format passing between the driver and app from the message format on the link. The message on the link should contain the message from the higher level, that is, the message on the link should have a member variable whose value is the higher level message. Subclassing should not be used, since these messages can be of radically different character. That is, an email message in an application responds to all sorts of application methods, e.g., spellCheck() whereas the message on the link has much less functionality -- it's just a "wrapper".

Here is a brief description of the source code you are to produce. For this part of the project (C or B grade), your source code should compile but it is not necessary that it run. That is, many of your procedures will just be stubs, most with no bodies at all.

• Write source files for each class and interface you specify. These should include method stubs and member variables. You may have static finals in your interfaces. Remember, these should all compile.



• The source code should include the standard REQUIRES, MODIFIES and EFFECTS specifications, within javadoc comments (separated by the standard <br> tags).



• You must produce javadoc pages for all your classes. Run javadoc on the source files all at once to produce an integrated output. Direct them to some subdirectory your create such as jdocs/ to avoid their cluttering up your code directory. Javadoc information is available on the course site.



• You should use Interfaces and Abstract classes in your design wherever appropriate.

For an A grade:

The major difference here is that in addition to the requirements above, you should produce a simple working system, including some simple testing. At a minimum, monitor the queue sizes in the drivers and produce output whenever a queue adds a message that raises the queue size to above one and whenever it's reduced from any value more than one. The normal behavior is for the queue to fluctuate. Use parameters that lead to very rare messages so the queues will rarely have any waiting messages, as well as parameters that produce much more frequent send requests, causing the queues to build up in size. At worst, with a very high send rate the queues will just continue to grow until you end the simulation. You'll have to keep track of the number of simulation loops (the time steps) in the drivers so they can set backoff times and reduce them to zero and try again. The built-in LinkedList class supports queue operations.

The earlier code examples

Sim.java, the simulation class that runs it.

Execute:

      java Sim

Node.java

Link.java

Single file with all three class files appended.

Go to COM1204 home page

Return to Prof. Futrelle's home page