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 expects the name of a configuration file as its argument. You could, for instance, start it with this UNIX shell command:
% ./NS configThe configuration file must have lines with these formats:
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.
This causes NS to simulate the indicated number of seconds of network activity. A configuration file can have more than one go command.
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.
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.
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 10It describes this network:
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 0The 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.
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.
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.
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.
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.