Feature #1: Total Time
Explore how to calculate the total time required for messages to reach all devices in an Ethernet spanning tree topology. Learn to use BFS traversal on adjacency lists, analyze delays, and optimize network communication timing.
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 transmission delay when it broadcasts the message. Considering the time required for a message to pass through a single device, we have to find the total time required by a message to reach all devices on a network.
Let’s try to understand this better with an illustration:
We’ll be provided with two lists: parents and delays. Each index of the ...