MCS-394 Lab 4: Link Layer (Spring 2002)

Due: May 8, 2002 (note postponement from initial syllabus)

Optional extra credit portion due: May 20, 2002


In this lab, you will program the "learning" feature for a simple simulated network bridge. That is, you will make the simulated bridge pay attention to what source addresses are seen arriving through each port, so that it when those addresses are used as destinations, the bridge can direct traffic to only the relevant port. For the main part of the lab, you will have to manually ensure that the bridges are never connected in a cycle. For extra credit, you may optionally also program a simplified version of the spanning-tree protocol, which allows bridges to be connected in cycles by automatically turning off some of the ports. If you choose to do the extra-credit portion, it will carry as much additional credit as the main lab, 6% of the course total (as calculated without extra credit). You may do the lab either singly or with one partner. This applies to the main lab and, independently, to the extra credit option.

The simulated network

The simulated network consists of three kinds of devices: each of which has one or more Ports. A Host has only one Port, whereas a Hub or Bridge can be constructed with any specified number of Ports. Each Port on a Hub or Bridge is referenced by number starting from 0; for example, a four-port Hub refers to its Ports as numbers 0, 1, 2, and 3. These device-specific port numbers are distinct from the addresses of the Ports, which are unique across the whole network. (Even the Ports on Hubs have addresses, unrealistically. You can just ignore these addresses; they should never be used as source or destination addresses.) Each Port can be connected to another Port, in which case they are known as peers of each other. Any Message transmitted by one of the Ports is received by the other, and treated appropriately for the kind of device it is part of. Hosts simply print out a textual report of the Message either being received (if the destination address is a match) or ignored (otherwise). Hubs and Bridges may forward the Message out through other Ports.

The simulated network is built using Java. For simplicity, you will work with it in the BlueJ environment, as I will demonstrate in class. This will allow you to not only work with the code, but also interactively create objects that are instances of the classes, invoke methods on those objects, and inspect them. That way you will have full, direct access, without needing a user interface for the simulation.

One unrealistic aspect of the simulation is that it makes no attempt to accurately model the passage of time. When a Message is transmitted, all the consequent actions elsewhere in the network will take place one by one, at a pace and in an order that is determined just by the way in which the Java methods call each other. There is no concurrency; the whole simulation takes place within a single Java thread. Bridges will need to do some housekeeping at intervals, for example, to "age" and eventually discard learned addresses that have not been seen in a while. To simulate this, you can manually invoke the Bridge class's allTick method, which notifies each Bridge that some time has passed.

Note that Bridges as provided to you are actually essentially the same as Hubs. Both forward any Message received on one Port out all the others. Only once you have modified the Bridge class to at least do learning will it really deserve the name.

To experiment with the simulation, you will first need to download a copy of the file BridgeLab.tar.gz. Then you can unpack that file, creating a directory BridgeLab that contains all the Java files, documentation, and the rest of the stuff BlueJ needs. To do the unpacking, you can in a shell give the command

tar xzf BridgeLab.tar.gz
You can now run BlueJ by giving the command
~max/bluej/bluej BridgeLab &
Note that printing from BlueJ doesn't seem to be working at the moment. To work around this, you can print Java files using shell commands. For example, you could do
mpage -2f BridgeLab/ | lpr -Pmcs-lab

For your initial experiments, try connecting some Hosts and Hubs in an acyclic fashion. Verify that any message sent by any Host reaches all the others, even if it winds up getting ignored based on the destination address. Verify that this remains true even when the network has already had a chance to see the addresses in question. You can also repeat this with Bridges if you want, since they are essentially the same as Hubs at this point. You can also try out a cyclic network, though then you'll need to kill BlueJ.

Learning bridges

Modify the Bridge class so that each Bridge keeps track of addresses it has learned and which one of the Bridge's Ports those addresses correspond to. Messages destined for learned addresses should only be forwarded out the single Port. (However, no message should ever be forwarded to the port it arrived on.) Initially don't worry about aging and discarding table entries. You may want to use a HashMap to represent the table.

Verify experimentally that once a Host has transmitted a Message, subsequent Messages destined for that Host aren't seen (and ignored) by all the other Hosts. Also, verify experimentally that if you disconnect a Host and reconnect it elsewhere in the network, Messages destined for it may be lost (even if the Bridge class's allTick method has been invoked repeatedly), until the relocated Host broadcasts a Message of its own so as to give the Bridges a chance to learn its new location.

Now add in aging. Each entry in the table should gain age each time the tick method is invoked, and when an entry reaches some maximum age, it should be removed.

Verify experimentally that so long as a Host keeps communicating reasonably frequently (relative to the ticking), its entry remains, but if it falls silent, the entry is removed. Repeat the experiment of relocating a Host after the Bridges have learned about it. Do the allTick method a few times and then try sending a Message to the relocated Host. Hopefully the Message won't be lost now.

Lab report

Explain the experiments you have conducted and what you observed, as well as showing your modifications to the Bridge class. You may assume that the reader is familiar with networking concepts (including bridging) and has access to this lab assignment.

Extra credit option

You may turn in a second lab report (by the later due date shown above) in which you implement a spanning tree protocol. You can find the spanning tree protocol in all its gory detail in Clause 8 (pp. 58-109) of the ANSI/IEEE Standard 802.1D, 1998 Edition. In practice, all you may actually need to pay attention to are sections 8.1-8.3.3, pp. 58-63. Even section 8.3.3 (regarding the aging of the spanning tree information to allow for reconfiguration of the network) would be something you could initially leave out and add in once you have the basics working. You should also disregard anything pertaining to "management." If you choose to work on the spanning tree protocol, I would urge you to talk with me about it. I can also provide the relevant portion of the 802.1D standard in hardcopy form if that would help.

Course web site:
Instructor: Max Hailperin <>