图解
首先我们来看看链路层+网络层的结构
Repeater
一般用于连接多个以太网络（如下图），还有一个功能就是放大信号的作用，包括错误信号和冲突的信号。
Bridge/Switch
Bridge 就是我们所说的网桥，是 Switch 的前身，这里就把他们看成是同一个东西啦。这个东西的主要作用是
- 用于连接多个不同类型的网络，如下图所示
- 用于传输链路层的数据，这里的数据传输主要依赖于 MAC 地址
Router
路由器一般在网络层操作。它的作用是连接不同的子网，并使用路由表和 IP 地址来传输数据。
从上面三个东西来看，就是连接网络一个比一个高级，这里不讨论以太网和路由器，主要说说 Switch，或者说 Bridge 的传数据机制。
Switch 特性
- 是主要处理链路层的设备，有像前面说到的数据传输的功能
- 它会检测发送方的 MAC 地址
- 然后选择性地将数据送到不同端口
- 对主机不可见
- 开箱即用，有自主学习能力。你可以不需要配置路由表，Switch 自己会维护一张转发表（看起来很像路由器里的路由表）
设备之间的数据传输
当一个 Switch 连接了多台设备后，Switch 自己会维护一个 Buffer 用于缓冲 Packet。主机和 Switch 一般都是直连的，而且设备之间还可以实现双工，不会出现冲突。当然在 Incoming Link 时也会出现冲突，这里说不冲突是指双向传的时候不会。
Switch 的转发表
Switch 的转发表和路由表差不多，只是路由表的目的地是某个主机或者网络，转发表的目的地是 MAC 地址。具体包含有：
- 设备的 MAC 地址
- 每个设备的网关
- 时间戳
之前我上计网实验的时候就手动配置过静态路由表，一旦设备多了真的配到爆炸，Switch 转发表就很聪明了，它可以自主学习，然后更新这个转发表。
自主学习
其实什么自主学习也不是什么高大上的东西，作为连接多台设备的 Switch，每次收到数据时都会去看发送发是谁，然后记录在这个转发表里就完了。
相当于你来我邮局里送信，邮局对每个送信的人都查一次水表，记录在案。下次别人发给你的时候我就知道要要送去的地址了。
举个例子，下面是 Port 3 发Src=x, Dest=y 到 Switch，这时候 Switch 就知道 x 在 Port 3，完了。
到这，你可能会问那第一次的数据呢？或者说第一次我送信邮局也不知道往哪发呀，难道随便发么？哎，对还真是随便发。对于不知道地址的数据包，Switch 会全部人都发，也就是广播一次。如果目的地和发送方地址一样，那就不发这个数据。伪代码可以写成这样：
// 记录发送方的 MAC 地址
if (data received):
forwardingTable.push(data.destination, data.source.MACAddr)
// 找接收方的 MAC 地址
found = forwardingTable.indexOf(data.destination)
// 如果找到了
if (found):
// 如果目的地和发送方地址一样，就扔掉
if (data.destination == data.source):
drop(data)
// 不一样则 Forward
else:
forward(data, interface)
// 找不到就广播，这里叫 flood
else:
flood(data)
题目
再举个例子，假如现在要 C -> I，然后I -> C`，每个 Switch 的转发表会变成什么样呢？
结果如下：
注意，第一次的时候因为每个 Switch 都不知道 I 在哪，所以会一直广播这个信息，这时间 S2 会记录到 C 为 Port 1。但是第二次 I -> C 的时候，大家都知道 C 在哪，所以不会经过 S2。
循环问题
还记得刚刚说的广播机制么？在找不到目的地 MAC 地址会广播数据，好像真的解决了第一次发数据的问题了。但是如果 Switch 之间是环结构就麻烦了。
如果 K 发到 I，这就出现了上图的循环：
S5 -> S6 -> S1 -> S2 -> S5
虽然最终 S4 会将信息发到 I 手上，但是因为信息都是复制一遍再广播的，别人根本不知道是否接收方已经收到的，所以还会继续循环广播。
解决循环问题
下面的 Bridge 和 Switch 看作一样
我们可能会想到 Counter 计数大法，可以设定一个 Counter 值，每过一个Switch 就减一，减到 0 就扔掉这个数据包。但是 Counter 的最大值也很难找呀，所以网络程序员想了个更好的方法——生成树。
刚刚那个小例子就是一棵树，我们可以去掉 S5 - S6 这条边就可以破除这个环了，难道拔掉网线？No no no，Switch 之间是使用端口来连接的，我们只需要将这个端口设置成 Block 就相当于切断 S5 和 S6 的连接了。
相关术语
在开始说怎么造好这棵生成树之前先说说一些相关术语。
Switch:
- Root Switch: 根 Switch，相当于树里的 Root 节点
- Designated Switch: 不是 Root 就是别的了呗，这个 Switch 会通过最短路径到达 Root。如果 LAN 里有多个 Switch，那么选择 ID 最小那个。
端口类型:
- Root Port，这个端口通过最短路径可以到达 Root
- Designated Port，Switch 通过这些指定的端口来传输 packet
- Blocked Port，数据不能通过，相当于切断连接
BPDU: Configuration Bridge Protocol Data Unit，这是一种数据包用于构造这棵树的。生成树不是说构造好了再投入运作的，而是靠每个 Switch 互相交换信息不断去更新这个棵树，最终构造出一棵最优的生成树。而这些用于交换的信息就是 BPDU。
BPDU 详细信息字段是这样的:
不过我们主要就看里面的 RootID，Cost，BridgeID，Port ID。
怎么造树
造树步骤
- 确定 Root Switch，一般为 ID 最小的
- 确定每个 Switch 上的 Root Port，这些 Root Port 可以通过最短路径到达 Root Switch
- 最后确定每个 Switch 上的 Designated Port，用于数据传输
是不是感觉很简单？要是人来做的话，给你一堆的 Switch 和主机，相信你很快做完，毕竟你是看到了全局，所以你能很快排好。
但是 Switch 是没有全局这个东西的，每个 Switch/Bridge 都是独立，要知道别人的信息只能通过发 BPDU。所以现在深入去看这三个步骤是怎么完成的。
如何确定 Root Switch
一开始每个 Switch 都会发信息到自己的 LAN，信息如下
每次接收和发送 BPDU 信息时，这个 Switch 就会去看自己的 ID 和 接收到的 BPDU 的 Switch ID/Bridge ID 哪个小，如果别人的 Switch ID/Bridge 小，那么别人就是 Root Switch，反之亦然。不断更新，直到算法确定 Root Switch。
如何计算 Cost
这棵树有个特点就是每个 Switch 到 Root Switch 的路径都要最短，所以 Cost 也是要计算的。
在确定了哪个 Root Switch 后，假如 Root Switch 叫 R，当前 Switch 叫 S。在接收到别人的 BPDU 后，会去计算最短路径。
如果 S == R，说明自己就是 Root，最短路径为 0。否则，去看接收到信息中最小的 cost，然后 + 1，代码如下：
if (S == R):
cost = 0
else if (B ≠ S):
cost = min(cost of BPDU) + 1
如何更新和共享BPDU
每个 Switch 都会发如下格式的信息：Root ID, Cost, Bridge ID, Port ID
- 只有相邻节点发送一个不太优的 BPDU 时，当前才会发自己的这条 BPDU 给这个相邻的节点，告诉它我 BPDU 的可能会更好
- 如果相邻节点发送了更优的 BPDU 时，当前节点会用这条信息更新自己的 BPDU，然后将更新后的 BPDU 广播给自己 non-root port，让别人也去更新
以上就是全部的造树过程。
不断更新生成树
虽然我们通过造树方式来解决循环问题，但是如果某个主机掉线了，那就要重新造一次树呀。网络工程师也想到这个问题了，所以 Root Switch 会每隔一段时间发送一个 Hello 信息，让 Switch 去更新一下这棵树。
举个例子，假如下面的树 S5 -> S2 走不通了，那么 Root 会发一个 Hello 信息到全部的节点，重新计算这个生成树。
如果某个节点在 3 次 Hello 信息都接收不到，那么就会重启自己的端口，然后假设自己是 Root 并发送 BPDU 来更新整个树，相当于再把自己加回去。
