The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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}$
asked in Computer Networks by Active (3.3k points)
edited by | 6.5k views
@Arjun sir, Is this topic in syllabus for GATE 2017 ?
same doubt. Is this in syllabus since bridges are removed.
no...bridges are not there in the syllabus now
But spanning tree is there in syllabus. Can't they ask such questions on this basis?
honestly i cant comment on this...they may ask anything relating to any topic...on paper, bridges are not in the syllabus...
Yeah true. So unpredictable.

yes , this is in the syllabus.

 this is Ethernet Bridge problem and ethernet  is in syllabus comes under lan technologies, so it is also in syllabus,

An Ethernet network bridge is a device which connects two different local area networks together. Both networks must connect using the same Ethernet protocol.

4 Answers

+154 votes
Best answer
  • 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 ]

answered by Veteran (56.4k points)
edited by
Hats off for the dedication to present the answer /\  :)
Great answer bro!!

Awesome @ Debashish Deka . Its always pleasure reading your answers:)

/\/\/\....It's a privilege to read your answers!! Thanks
This kind of effort make GO so useful :) /\
/\ !
Why we are not selecting port no 1 when we are select S3 LAN from B5 because port no 2 is bigger port id.
s4 must be connected to B5 and not B3
@Mehul s4 is selected from B3 because seq Id  od B3 is 3 and B5 is 5 is we get same length then we give lower seq id to higher priority. Hats off for the dedication @Debashish.
@ Debashish Deka

Not sure about question difficulty level , but this is the best answer presented I have ever seen.

Great efforts.

Thank you !

Why S4 have taken port-2 of B3 and not port-1 of B5 ?
Because when there is a conflict then you have to select a bridge with lesser Id. so we select B3. Hope it's clear.
Excellent explanation and representation of data
Best answer I have seen on GO. Lots of thanks
+20 votes

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

answered by Boss (30.6k points)

There ia one more possibility as :-

Here B3 can forward through port 1 to h11 and h12

And B3 can forward through port 2 to h9 and h10.

Because B3 can send to B4 (via port 2 of b3) and B2 via port 1 of b3 too

Just want to clear my concept.

Am I wrong??

In switch B4 i think 1 should be the root port not 2, but even then answer will not change right?
+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 .


          /     \

       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.)
answered by Loyal (7.4k points)

If you refer to diagram in first answer how H9,H10 are also reachable from B3 via B2 from port 1 of B3 ?

Same doubt .. How 9,10 reachable via B2

This condition is there in question - " Port conflicts are always resolved in favour of the port with the lower index value. " and taking consider this we should consider port 1 as a root port instead port 2 via B4.

 H9 and H10 are connected to b3 via port 1, that means B4:1 comes via B3:1 and B2:1 comes via B3:2 .


if we take port 2 as root then H9 and h10 have to connect via switch B4 with port 2 but this not possible if you check given options in Q no 82 .

but now if we take port 1 as a root via b4 , then Only H9 and H10 can connect with B3 via port 1 .

my conclusion , Answer is both A and A in 82 and 83 , 

This is correct picture .

@Bikram sir

Could you please help why port 2 of B3 is used instead of port 1 of B4, for H7 and H8 ?
@Vishwesh Vinchurkar

Bridges are selected with least serial number (B3< B5 )

If same then resolved by port number.
+7 votes

           /   \
          /      \
         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

answered by Boss (13.2k points)
Could you please upload some image for this solution or the method that you have approached.Although I know the method to create MST for bridges,everything here looks so messy that I am stuck.

please upload your version of solution to get the solution.
how to solve second part?
Got this useful link

wonderful explanation
thanks david

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,094 answers
71,001 users