Feature #1: Total Time
Explore how to determine the total time required for a message to reach all devices in an Ethernet network running the Spanning Tree Protocol. Learn to transform device data into an adjacency list and apply BFS traversal to compute maximum message propagation time from the server to clients. Understand time and space complexity of the solution.
We'll cover the following...
Description
An Ethernet LAN topology is built with redundant connections between switches. However, an Ethernet can only work in a loop-free topology. Therefore, Ethernet switches run the Spanning Tree Protocol (STP), which computes a minimum spanning tree for the underlying topology. STP disables some of the network links to obtain a loop-free spanning tree. Messages on the LAN are forwarded only on network links that are part of the spanning tree.
The server is at the root of the spanning tree, and the clients are at the leaves of the spanning tree. All the other nodes in the spanning tree are Ethernet switches that forward messages from the server to the clients. The nodes are labeled with weights representing the time(in seconds) it takes a message to go from the device on one end of the link to reach the device on the other. The delays will always be positive. For simplicity, we will assume that the link weights are integers. In addition, the main server on the root node will also experience a ...