2

In computer networking, if we want to prevent loop-topology we use STP(spanning tree protocol) or RSTP(Rapid Spanning Protocol). I have read in Discrete Mathematics that for finding spanning tree two algorithms have been described, breadth-first search algorithm and depth-first search algorithm.

I am just curious which algorithm has been used in IEEE 802.1D (STP) or IEEE 802.1w (RSTP)?

3
3

It is a good question. I don't claim to have the perfect answer, but there seem to be two possible ways of answering. One is that the algorithm is by Radia Perlman, published in about 1984 and adopted/adapted by IEEE. Two is that, if you strip out the discretionary components described in the "extensions" in that paper, and if you treat the problem as a weighted undirected graph, then you have something similar to the Bellman-Ford algorithm. This algorithm calculates a root path cost and a predecessor for every vertex, requiring knowledge only of neighbours. So it works to provide a distributed calculation, unlike Dijkstra, which requires a controlling hand.

2
  • u are late. but nice effort. I think i have to read this paper. – muneeb_ahmed Aug 23 '18 at 8:47
  • 1
    Better late than never! – Anthony Aug 23 '18 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.