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/Bridge.java | 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.
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
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.
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: http://www.gac.edu/~max/courses/S2002/MCS-394/
Instructor: Max Hailperin <email@example.com>