image is the diagram of the LAN network used.

I have been working on this for a week now and haven't been able to figure it out. I hope someone can crack this.

Objective: In this programming assignment, you will write a C or C++ program to simulate the spanning tree algorithm for extended LANs. The objective of the assignment is to understand how the distributed version of the spanning tree algorithm works.

Input: The extended LAN will be given in a text file. We make several assumptions to simplify the implemen- tation. An extended LAN with n bridges has 1, 2, 3, , n as the IDs of the bridges. If there are m LANs, they are represented by first m capital letters. The file contains n lines, one for each bridge. Each line begins with the ID of one bridge, followed by the list of the LANs it is connected to. The names of LANs are separated by exactly one space. For example, the extended LAN in Figure 3.10 on page 194 of the book can be represented as

1 D E F G H

2 C E

3 A C

4 H I J

5 A B D

6 G I

7 B F K

Spanning Tree Algorithm:

Node best configuration: Every bridge (node) records its own best configuration (which bridge is the root and the distance to the root) and how it got this best configuration (from which port and from which node). There are two cases: 1) it claimed itself to be the root; 2) it received a message from some node over one of its ports.

Best configuration for each port: In addition, every node records the best configuration for every port it is connected to. It is the best message among the messages received over this port and the message the node itself may send over the port.

Initializations: At the beginning, each node considers itself to be the root. should be the best configu- ration for the bridge and for each port, where ID is the ID of that bridge. Every port of the bridge should be open.

Sending and processing messages:

We can randomly select a node to send its message. It only sends out to those ports, over which it has not received a better message. All nodes connected to that link will receive the message.

Upon receiving a message over a link, the node will determine whether the message is better than its configurations. There are three scenarios:

1. it can ignore the message because the message is worse than its best configuration for that port 1;

2. it needs to change the best configuration at that port (and nothing else), because the message received is better for that port; and

3. in addition to changing the best configuration at a port as in the previous scenario, it needs to change its own node best configuration (and the port it got the node best configuration). Assume that the current best configuration of the node is . This includes two cases: 1) R = ID; or 2) previously, one of its ports has the best configuration because it has received a message from node S. Now, it receives a message that is better than its current best configuration at a port. If is better than 2, then the best configuration for the current node needs to be changed and information about from which port and node the current node gets the best configuration also needs to be changed. This can lead to changing the best configurations of its other ports. So the program needs to check each port.

For every node, it can determine that a port should be open, if

1) the sender ID in the best configuration of the port is its own; and

2) the port is the one from which it got its node best configuration.

All other ports should be closed.

With enough number of messages sent, we will be able to generate the spanning tree for the extended LAN.

Implementation and test:

You can implement a bridge as a class in C++.

In C, you can have an array of a bridge structure, each recording the status of one bridge. Then write a procedure for sending a message by the i-th bridge.

For the testing purpose, your program should accept a list of numbers indicating the order of nodes sending messages. For example, myprogram LANfilename 1 3 4 6 2 3 1 5 means that nodes 1, 3, 4, 6, 2, 3, 1, and 5 will send messages in that order. The program should print out the best configuration for each bridge, and which ports are open and which ports are closed for each bridge after execution.

EXAMPLE:

Example 1: If we run the program as myprogram LANfilename 1 3 4 6 2 3 1 5

the output will be:

Bridge 1: best configuration , from 1

port D: open port E: open port F: open

port G: open

port H: open

Bridge 2: best configuration , from 1 via E

port C: open port E: open

Bridge 3: best configuration , from 2 via C

port A: closed port C: open or closed

Bridge 4: best configuration , from 1 via H

port H: open port I: open port J: open

Bridge 5: best configuration , from 1 via D

port D: open port A: open port B: open

Bridge 6: best configuration , from 1 via G

port G: open or closed port I: closed

Bridge 7: best configuration , from 1 via F

port F: open port B: closed port K: open

B3 B5 B7 B2 B1 B6 B4 3.12 Spanning tree with some ports not selected. allest ID wins. Of course, each bridge is connected to more tha B3 B5 B7 B2 B1 B6 B4 3.12 Spanning tree with some ports not selected. allest ID wins. Of course, each bridge is connected to more tha