in Computer Networks edited by
17,312 views
49 votes
49 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}$
in Computer Networks edited by
17.3k views

4 Comments

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

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

4 Answers

322 votes
322 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 ]

edited by
by

4 Comments

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

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

2 Comments

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

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

4 Comments

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 .

2
2
edited by
@Bikram sir

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

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

If same then resolved by port number.
0
0
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

4 Comments

how to solve second part?
0
0
edited by
Got this useful link
https://en.wikipedia.org/wiki/Spanning_Tree_Protocol

wonderful explanation
1
1
thanks david
0
0
Answer:

Related questions