17,312 views

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}$

Is this in gate 2020 ?
Yes
ethernet bridging is there in GATE 2021
Ethernet bridging is syllabus of GATE 2021.

Source: https://gatecse.in/gate-2021-syllabus-including-changes/

• 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 ]

by

Best answer I have seen on GO. Lots of thanks
🔥🔥
Thanks for breaking the tie and video link. Thanks go.

This makes it clear that:

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?
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.

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 .

edited
@Bikram sir

@Vishwesh Vinchurkar

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

If same then resolved by port number.

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

how to solve second part?
edited by
https://en.wikipedia.org/wiki/Spanning_Tree_Protocol

wonderful explanation
thanks david