Spanning tree protocol (STP)

What is a spanning tree? (For any graph)

Spanning tree is a tree made of different network nodes wherein there is always a least cost path to reach from one node to another.

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges.

1. Spanning tree does not have cycles
2. Spanning tree nodes cannot be disconnected.

How many spanning trees can a connected and undirected graph have?

• Minimum # of spanning trees: At least one spanning tree.
• Maximum # of spanning trees: n^(n-2) spanning trees.

Properties of spanning tree:

• All possible spanning trees from a Graph G, have same number of edges and vertices.
• Spanning tree does not have a cycle.
• Removing one edge from a spanning tree, will make the Graph G a disconnected graph.
• Adding one edge to a spanning tree, will create a loop (maximally acyclic).

Mathematical properties of a spanning tree:

• n-1 edges
• n vertices
• G - (e-n+1) edges => spanning tree
• maximum n^(n-1) spanning trees

What is a minimum spanning tree? (For weighted graph)

In a weighted graph, a minimum spanning tree is a spanning tree having least cost path from one node to another.

Examples of GREEDY algorithms for minimum spanning tree:

• Kruskal's
• Prim's

Why do we need spanning tree?

Avoid loops within a broadcast domain. Spanning tree builds a loop free topology for Ethernet networks.

STP creates a spanning tree within a network of connected layer2 bridges and disables the links that are not part of the spanning tree, leaving a single active path between any two network nodes.

Standardization was done with 802.1D, 802.1w(RSTP) and 802.1s(MSTP).

How does STP work?

Steps:

• Select root bridge with (lowest bridge id + lowest priority)
• Determine least cost path to root bridge
• Least cost path from each bridge
  • Root sends BPDUs with "root path cost" as 0.
  • Each non-root bridge increments "root path cost" and forwards frame.
  • For each bridge, each port that gets BPDU with smallest "root path cost" is ROOT PORT of the bridge.
• Least cost path from each network segment
  • Bridges on a network segment collectively determine which bridge has the least-cost path from the network segment to the root. The port connecting this bridge to the network segment is called DESIGNATED PORT for the segment.
• Disable all the other non-DP or non-ROOT ports

Tie breaker:

• Ties for ROOT port: Use neighbor with lower bridge id.
• Ties for DP port: Use lowest port id.

BDPU (Bridge Protocol Data Units):

• Destination is STP multicast address 01:80:C2:00:00:00
• Keepalive every 2 secs
• Config BPDU
• Topology Change Notification BPDU

STP port states:

Why to avoid STP?

Because STP disables links between switches thereby reducing the effective bandwidth usage between those switches. Even though its trying to create a loop free topology.