COM 1204 Object-Oriented Design - Summer 2001 - First Network Assignment (A4)

Professor Futrelle -- College of Computer Science, Northeastern U., Boston, MA

Updated Saturday 7/21/2001

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:

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.

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.

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, the simulation class that runs it.


      java Sim

Single file with all three class files appended.

Go to COM1204 home page

Return to Prof. Futrelle's home page