edited by
22,723 views
53 votes
53 votes

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge. 

Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred.

For the given connection of LANs by bridges, which one of the following choices represents the depth first traversal of the spanning tree of bridges?

  1. $\text{B1, B5, B3, B4, B2}$
  2. $\text{B1, B3, B5, B2, B4}$
  3. $\text{B1, B5, B2, B3, B4}$
  4. $\text{B1, B3, B4, B5, B2}$
edited by

5 Answers

Best answer
343 votes
343 votes
  • First select $B1$ as the root bridge. This selection is based on lower serial ID as given in the question.
  • All ports of root bridge are designated ports and they are in forwarding state.


  • Every non-root bridge must have a root port. All root ports are placed in forwarding state.
  • Root port is the port that is closest to the root bridge
  • For example, we observe bridge $B3$.
  • It has two ports leading to the root bridge. If we assume bridge-to-bridge cost as $1$ unit, both these paths have the same cost. Then we will select the lower port index as given in the question as the root port for the bridge $B3$.
  • port 3 of $B3$ becomes the root port.

  • Using the same logic we will find out the root ports for $B5$ also.

  • Coming to $B4$ for root port selection.

  • We have again two different paths with the same cost. We will select port 1 as the root port for $B4$ 
  • Using the same logic port $1$ is selected as root port for $B2$ as well.


  • Now we have to consider the designated ports
  • The designated ports are the ports responsible for forwarding traffic onto a network segment
  • We have total $6$ network segments or LAN's.  Each segment will have one designated ports.

  • $S1$ and $S2$ are connected to the root bridge itself via two designated ports. So no issue with segments $S1$ and $S2$ traffic.
  • Let's consider other segments.
  • For example $S3$.

  • $B2$,$B3$,$B4$,$B5$ all can forward traffic to this segment $S3$
  • According to the question in this situation, we will consider only those bridges which are nearer to the root bridge $B1$.
  • $B5$ and $B3$ are both nearer to the root bridge.
  • Then we will break this tie by selecting the lower bridge serial ID i.e. $B3$ is selected and designated port is port 1 of $B3$ for the segment $S3$

  • Similarly, we can choose designated ports for $S4$ , $S5$ and $S6$


  • Remaining all ports are blocked ports.

  • This the final spanning Tree

  • DFS traversal will give answer as A

PLEASE check the following two videos.[ IITB lectures ]

edited by
22 votes
22 votes

This makes it clear that:
Q.82 answer = option A
Q.83 answer = option A

8 votes
8 votes
82 : Though we have paths from every bridge to every other bridge so technically all the  dfs path will result from all  options given in the question . But on carefully reading the question it says that you need shortest path from source Root to any other bridge .Therefor option A looks most suitable .

            B1

          /     \

       B3      B5

      /    \

    B2   B4

83 .  Option A

  Following the above connectivity  we notice that :

H1,H2 are reachable to from B3 via the port 3 because B3 is connected to B1 and which in turn is connected to the H1,H2.

H9,H10 are also reachable from B3 via B2 from port 1 of B3 .

H5,H6 are reachable from B3 directly via port 1.

H7,H8 via port 2.

H11,H12 via port 2 only because of B3 connection to B2.

H3 and H4 are also reachable directly via port 3 of B3.

Hence  answer ( option A.)
7 votes
7 votes

            B1
           /   \
          /      \
         B5    B3
                  / \
                 /   \
               B4   B2

this is the spanning tree for the above question,

DFS traversal will be B1-B5-B3-B4-B2

So Option A is the Answer

Answer:

Related questions

21 votes
21 votes
1 answer
1