V22.0480-005 Lab 3: Ethernet bridge

Due date: Tuesday March 2, 3:30pm
Free extension to midnight if you attend lecture

Reading:

Sect 3.2.2 of textbook Computer Networks.

Introduction

Your task is to write the spanning-tree software for a transparent ethernet bridge. Your bridge must exchange spanning tree update messages with the other bridges in a network to find the tree, and it must forward data frames along the spanning tree. You need not implement learning or filtering.

If you have knowledge of the entire structure of a network, finding a spanning tree is fairly easy. The point of this assignment is to discover how to do the same job when no one entity has more than local knowledge.

We will supply you with a simple network simulator, called NS. NS reads a configuration file that describes a set of networks, bridges, and connections. NS will start up one instance of your program for each bridge in the configuration. Your bridge program can send frames by writing them to its standard output, and NS will send frames to your bridge on the bridge's standard input.

NS

NS keeps track of which bridges are connected to which networks, and copies frames sent by one bridge over a certain port to the other bridges on the same net as that port.

NS expects the name of a configuration file as its argument. You could, for instance, start it with this UNIX shell command:

% ./NS config

The configuration file must have lines with these formats:

bridge program net1 address1 net2 address2 ...
This creates a bridge with one port for each of the net/address pairs. The nets and addresses are arbitrary numbers. More than one bridge can be connected to a given net. The addresses must be unique; two router ports cannot have the same address. NS runs program, your bridge program, as a UNIX process, and talks to it over pipes.
go seconds
This causes NS to simulate the indicated number of seconds of network activity. A configuration file can have more than one go command.
send net src dst
Send a data frame onto the indicated network, with src and dst as the source and destination ethernet addresses. Net should be a network number mentioned in one or more of the bridge lines. This simulates an ordinary host sending a frame; the bridges should forward the frame along the spanning tree.
break bridge
Breaks a bridge, so that any frames it sends are thrown away, and no frames are sent to it. bridge is the index of one of the bridge configuration lines; they start with zero.
fix bridge
Causes a broken bridge to resume operation.

These lines can be intermixed in any order, except that a go line must precede the first send line.

Consider the following configuration file example:

bridge prog 0 91 1 92
bridge prog 0 93 1 94 2 95
go 30
send 0 501 502
go 10

It describes this network:

Each port is labeled with its port number and ethernet address. After setting up the simulated network, NS will let the bridges run for 30 seconds, during which time they will presumably exchange spanning tree update messages. Then, NS will inject a frame onto net 0, as if a host (not shown in the picture) had sent it. If the bridges are functioning correctly, they should copy the frame onto nets 1 and 2, and the frame should appear on those nets exactly once. The source and destination addresses (501 and 502) are for convenience in tracking packets through the system; the only interesting destination address is BRIDGE_MULTICAST_ADDR (999), which indicates a spanning tree update frame.

NS prints log messages every time a frame appears on a network. This is an example:

8: frame on net 0 from bridge 1 port 0 src 93 dst 999
  root 91 distance 1 me 93 my_port 0 age 0

The 8 is the simulated time in seconds. The bridges are numbered by their order in the configuration file, as are the ports on each bridge. The fields correspond to those in the ethernet frame described below.

NS will eventually give up and exit if your bridge causes a frame to loop. This means your bridge is not working very well.

The Bridge Program

NS will start your bridge program with one command-line argument for each port it has, indicating that port s ethernet address. Your program can use its standard input and output to communicate with NS. Given the sample configuration above, NS would run the bridge program prog twice, once as prog 91 92 and once as prog 93 94 95.

NS will send instances of struct from_NS to the bridge program's input. This structure indicates the current simulated time, whether or not the struct includes a valid ethernet frame, the port on which the frame arrived, and the frame itself. NS sends a frameless message to each bridge program every two seconds to help remind the bridges to take care of any periodic processing they might need to do.

The bridge program can send ethernet frames out one of its ports by writing a struct to_NS on its standard output. This structure contains the port number and the ethernet frame. A port does not hear frames it sends out.

An ethernet frame contains source and destination addresses and the fields required for the spanning tree update messages. Update messages must be sent to the special destination address BRIDGE_MULTICAST_ADDR (999); frames with any other destination are ordinary data frames.

Note that your bridge should use the frame format specified by the ether_frame structure in formats.h, not the real Ethernet frame format described in the textbook. In particular, for simplicity NS uses unsigned integers as Ethernet addresses, rather than 48-byte quantities. You also do not need to worry about byte-swapping--assume all data you receive is in host byte order. (I.e., you don't need to call htonl/htons for this assignment.) You should choose the lowest address of a bridge's ports as its unique bridge identifier. You should use hop count as the distance to the root. You should increment the age field in update messages once per second, and use MAX_AGE (20) as the maximum age. You should send out updates roughly once every two seconds.

Getting started

We have provided a skeleton bridge project directory. It is available in ~class/src/bridge.tar.gz. Start by unpacking and building the source code in your home directory. On the class machines, you can do so with the following commands (note, you don't need to use automake/autoconf for this assignment):

% tar xzf ~class/src/bridge.tar.gz
% cd bridge
% gmake
cc -g -ansi -Wall -O2 -c NS.c
cc -o NS NS.o
cc -g -ansi -Wall   -c -o bridge.o bridge.c
cc -o bridge bridge.o
%

Note that the build directory comes with a skeletal bridge program that copies all frames from any port to all other ports. There is a toy configuration file, toyconfig, that contains no loops and only sends one packet. You can run this configuration as follows:

% ./NS toyconfig
2: frame on net 0 src 101 dst 201
2: frame on net 1 from bridge 0 port 1 src 101 dst 201
2: frame on net 2 from bridge 1 port 1 src 101 dst 201
%

In order to form a spanning tree, you will want to edit the file bridge.c. Search for the string XXX, which denotes places where you may want to add code.

As distributed, bridge.c contains several variables that will be of use to you.

int nports;
This is the number of ports for this particular bridge.
int myid;
This is the lowest Ethernet address of any of the bridge's ports. You should use this as your bridge's ID.
struct port_info *ports;
This points to an array of port_info structures, port_info[0] ... port_info[nports-1]. struct port_info has two fields as distributed. addr is the Ethernet address of the port (just an integer). disabled is an integer which, when non-zero, prevents packets from being forwarded to or from the particular port. You will very likely want to add fields to the port_info structure, to keep track of more data on a per-port basis. You can then extend the function clear_port to initialize any new fields you have added to the structure.

For your bridge to function properly, you must set the disabled field of the port_info structure of any port that is not part of the spanning tree. Initially, disabled is clear for all ports. In order to set it, you will want to implement the following (currently empty) functions:

void spantree_update (int time, int src_port, struct ether_frame *fp);
This function is called when the bridge receives a packet to the bridge multicast address, BRIDGE_MULTICAST_ADDR (999). Such packets are not forwarded by default--nothing happens to them in the supplied bridge.c file. If you want to forward a spanning tree packet, you will need to do so explicitly from the spantree_update function (after adjusting any necessary fields).
void spantree_maintenance (int now);
This function is called every UPDATE_INTERVAL (2) seconds. You can use it, for example, to send spanning tree update messages, and to age spanning tree packets you have received. (In particular, make sure you forget about update packets that are older than MAX_AGE (20) seconds, so that you can recover from broken bridges.)

Note, another useful function you may want to call from within the above is:

void co_write (int port, const struct ether_frame *fp);
Writes ethernet frame fp to port port.

Testing your bridge

The skeletal bridge distribution comes with several example configuation files you can use to test your bridge. Look at the files config and config-*. You can use these as a starting point for developing your own config files.

It is also important to make sure that your bridge properly inter-operates with other bridges. For that reason, the distribution comes with a program ourbridge that properly implements the spanning tree protocol. You should run NS in a configuratio that contains a mixture of bridge directives, some for your bridge, some for our bridge.

Finally, there is a test-program, test-bridge (in ~class/bin) that will compare the output of your program to the output of a configuration in which all bridges are ourbridge. For example, to see if your bridge program works properly with the supplied configuration file config, you can run:

% test-bridge -config ./config
Testing file ./config... passed
%

This means that your bridge and our bridge did roughly the same thing on configuration file config. If your bridge seems to have misbehaved, the test will fail. In either case, test-bridge will produce an output file, test.log, with detailed information about the simulation results and, if the test failed, why your bridge's behavior differed from what was expected.

The test-bridge program also contains a built-in set of configuration files against which you can test your bridge. These are what will be used to grade the assignment. To use the built-in tests, just supply the name of your bridge program on the command line. For example:

% test-bridge ./bridge
Testing simple forwarding (1 point)... passed
Testing network with one loop (1 point)... passed
Testing bridge with two ports on same network (2 points)... passed
Testing recovery from a broken bridge (2 points)... passed
Testing interaction with our bridge (2 points)... passed
Testing interaction with our bridge as root (2 points)... passed
FINAL SCORE: 10/10
[internal use only: student:10:1076991992:efde1808e8a4e60c50e4:c1ceee6c91672a58e90b]
%

(Ignore the last line, it is just for use in grading.) Note that particularly in this case, if you fail any of the tests, you will probably want to examine the test.log file in the directory where you ran test-bridge.

Turning in the assignment

In order to turn in the assignment, you just need to run the command gmake handin. You should see output like the following:

% gmake handin
gmake clean
...
`echo ~class`/bin/test-bridge ./bridge > score
Testing simple forwarding (1 point)... passed
Testing network with one loop (1 point)... passed
Testing bridge with two ports on same network (2 points)... passed
Testing recovery from a broken bridge (2 points)... passed
Testing interaction with our bridge (2 points)... passed
Testing interaction with our bridge as root (2 points)... passed
cp bridge-0.tar.gz test.log score bridge `echo ~class`/handin/lab3/$USER/
================================================================
Your assignment has been turned in Tue Feb 17 00:15:06 2004.
Your final score is 10 point(s).
================================================================
%

Make sure the last four lines look similar to the above. In particular, the output must say "Your assignment as been turned in". If you have any problems with submitting the assignment, please contact the TA or instructor.