STP: Spanning Tree Protocol

Spanning Tree Protocol (STP) was developed before switches were created in order to deal with an issue that occurred with networks that were implementing network bridges. STP serves two purposes: First, it prevents problems caused by loops on a network. Second, when redundant loops are planned on a network, STP deals with remediation of network changes or failures.

The difference between a bridge and a switch is that a switch functions like a multiport bridge; whereas a bridge might have two to four ports, a switch looks like a hub and, on an enterprise network, will usually have 12 to 48 ports. As you go through this chapter, note that STP technology uses the term bridges, when you are actually placing switches (multiport bridges). At the time STP was created, switches did not exist. Clear as mud?

STP is a Layer 2 protocol that passes data back and forth to find out how the switches are organized on the network and then takes all the information it gathers and uses it to create a logical tree. Part of the information STP receives defines exactly how all the network switches are interconnected.
STP builds this information by sending out network packets called Bridge Protocol Data Units (BPDUs or sometimes BDUs). These BPDUs — or rather the data in them — control the way STP determines the network topology.
The following figure shows a basic network with simplified 4-digit MAC addresses for the switches. All the switches on the network will send BPDU frames to the entire network, even if a network that does not have any loops. These packets, by default, are sent out on the network every two seconds, are very small, and do not negatively affect the network traffic.
If you are performing a packet capture on a network, however, be aware that these packets fill your capture screen quickly and can be distracting when reviewing your captured data. The initial process of sending BPDU frames will determine which switch will be the Root Bridge and act as the controller or manager for STP on the network. By default, the Root Bridge is the switch with the numerically lowest MAC address.

Identifying Root Ports

The BPDU, which every switch sends, contains information about the switch and its Bridge ID that uniquely identifies the switch on the network. The Bridge ID is made of two components: a configurable Bridge Priority value (which is 32,769 by default) and the switch MAC address.
If none of the switches on your network has had its Bridge Priority values adjusted, then the switch with the lowest MAC address will be the Root Bridge; but if the Bridge Priority values on your network have been modified, the Root Bridge will be the switch with the lowest Bridge Priority value. The Root Bridge shown in the preceding figure is switch 11:11.
After the Root Bridge is identified, all other switches determine the quickest path from themselves to the Root Bridge. Some switches have more than one path to the Root Bridge due to a network loop. In the preceding figure, switch 11:22 has two paths, one that is two hops away from the Root Bridge and one that is one hop away.
If the speed of the networking technology is the same for all network segments, the path with the fewest number of hops is designated as the Root Port.
The switch will identify which of its interfaces is the Root Port. Each network technology has a rated speed, so based on the technology of each network segment between the switch and the Root Bridge, the switch is able to calculate the cost of each available path.
The following table lists the STP cost associated with each network technology speed. Notice in the table that the data rate is inversely proportional to the STP cost.

Network Speeds and STP Costs

Data Rate	STP Cost
4 Mbps	5,000,000
10 Mbps	2,000,000
16 Mbps	1,250,000
100 Mbps	200,000
1 Gbps	20,000
2 Gbps	10,000
10 Gbps	2,000

In the following figure, all the Root Ports are identified. In the event that a switch has two paths to the Root Bridge and each path has the same cost, then the switch will look at the BPDU frames from its closet neighbor on each of the paths. The switch will designate its Root Port based on the neighbor with the lowest Bridge ID.

Identifying Designated Ports

Each switch knows the least cost path to take to get to the Root Bridge, which may require passing data to another switch's interface. For the sake of this example, the main switch that is being used in the example the reference switch and its neighbor the neighbor switch. The port on the next closest switch (neighbor switch) to the Root Bridge that is facing the reference switch is called the Designated Port.
The reference switch will use the Designated Port as its path to get to the Root Bridge. The following figure identifies all the Designated Ports that the downstream switches will use to send data to the Root Bridge.

Blocking Loops

You still have one outstanding problem to resolve. There are still loops on this network that threaten to bring the current network down; however, by working through how all the Root Ports and Designated Ports are assigned, you have actually completed the work to resolve the loop issue on the network.
In the figure immediately preceding this section, only two ports are used to connect to neighboring switches that are neither Root Ports nor Designated Ports. Because these ports do not have either role assigned to them, they are part of a loop on the network. If you review the figure, you should be able to identify the loops on the network. To resolve the loop issue, STP puts these ports without a role into Blocking state, which means these are Blocking Ports.
Blocking Ports are ports that do not allow traffic to be sent or received through the port; it is blocking the traffic. Essentially, you could say that the Blocking Ports have been disabled, but they are not disabled. Since the ports are not disabled, the switch on the other end of the link still sees the link as active, but frames that are sent over that link (excluding BPDU frames) are dropped (blocked).
The following figure shows you the completed STP diagram, including the Blocking Ports.

STA: Spanning Tree Algorithm

STP: Spanning Tree Protocol

STP的目的是為了要用layter 2網路設備建構一個沒有迴圈的網路(loop free network)，而且是最低cost(速度最快)的網路(即minimal cost spanning tree)。由此可知為何path cost會定義成1000/頻寬(以Mb為單位)，因為速度愈快，cost就愈低。也就是說用STP所建夠出來的網段會是速度最快的，此點可在elect designated port 看的更清楚，在此先提醒一個重點：designated port會與消除loop有關；在某一個網段(segment)選擇designated port時，我們會選擇從那個到root bridge的cost最低的port，另外一個port(較慢的那個)會被設成block。

以下說明STP的過程：

STP會經過三個選擇階段，而且是依序的先選擇root bridge，接著在所有非root bridge 選出root port，最後再選出designated port，一旦選完designated port，剩下的port會被設成block port且設成block mode，並且將root port，designated port設成forwarding mode。

一、Root bridge的選擇規則如下：

Bridge ID最小的bridge會被選成root bridge。注意Bridge ID=priority(2 bytes) + MAC address(6 bytes)。
比Bridge ID時，先比bridge priority，較小的priority會被選成root bridge，若priority一樣則比MAC address，較小的MAC address會被選成root bridge。

二、Root port的選擇規則如下：
注意：直接連接至根橋接器的連接埠即成為根連接埠
每一個非root bridge要選出一個root port。
計算某bridge的所有port到root bridge的root cost，root cost最小(即到root bridge最快)的port就是root port。若root cost一樣，則比其所連的Bridge ID，比法同Root bridge的選擇規則。(見參考資料(一))
其中root cost =沿途每段網路的path cost之總和，path cost = 1000/頻寬(以Mb為單位)

三、designated port的選擇規則如下：見參考資料(二)
注意root bridge上的每個port都是designated port
designated port的選擇可分成兩種cases：
Case I：先檢查每個網段(segment)，若此網段上有一個port已經是root port則另一個port就是designated port

Case II：此時剩下的網段(segment)的兩個port旣沒有被mark成root port也沒被mark成designated port。注意此段網路就是loop的一部分，我們必須在此二port中選出一個designated port，且將剩下的另一個port設成block port。選擇designated port的方式是計算當封包經由此二port到root bridge時，哪一個的root cost較小，較小的那個port就是designated port，這意謂封包經由此port會比較快到root bridge。若此二port的root cost一樣，則比此二port所在的bridge 之Bridge ID。比法同Root bridge的選擇規則。

至此我們已經選出root port、designated port。

剩下的port就被設成block port。