|
The first Ethernet relays that operated in the datalink layers were called `bridges`. In practice, the main difference between switches and bridges is that bridges were usually implemented in software while switches are hardware-based devices. Throughout this text, we always use `switch` when referring to a relay in the datalink layer, but you might still see the word `bridge`.
|
|
The Spanning Tree Protocol (802.1d)
|
|
The `Spanning Tree Protocol` (STP), proposed in [Perlman1985]_, is a distributed protocol that is used by switches to reduce the network topology to a spanning tree, so that there are no cycles in the topology. For example, consider the network shown in the figure below. In this figure, each bold line corresponds to an Ethernet to which two Ethernet switches are attached. This network contains several cycles that must be broken to allow Ethernet switches, using the MAC address learning algorithm, to exchange frames.
|
|
Spanning tree computed in a switched Ethernet network
|
|
In this network, the STP will compute the following spanning tree. `Switch1` will be the root of the tree. All the interfaces of `Switch1`, `Switch2` and `Switch7` are part of the spanning tree. Only the interface connected to `LAN B` will be active on `Switch9`. `LAN H` will only be served by `Switch7` and the port of `Switch44` on `LAN G` will be disabled. A frame originating on `LAN B` and destined for `LAN A` will be forwarded by `Switch7` on `LAN C`, then by `Switch1` on `LAN E`, then by `Switch44` on `LAN F` and eventually by `Switch2` on `LAN A`.
|
|
Switches running the `Spanning Tree Protocol` exchange `BPDUs`. These `BPDUs` are always sent as frames with destination MAC address as the `ALL_BRIDGES` reserved multicast MAC address. Each switch has a unique 64 bit `identifier`. To ensure uniqueness, the lower 48 bits of the identifier are set to the unique MAC address allocated to the switch by its manufacturer. The high order 16 bits of the switch identifier can be configured by the network administrator to influence the topology of the spanning tree. The default value for these high order bits is 32768.
|
|
The switches exchange `BPDUs` to build the spanning tree. Intuitively, the spanning tree is built by first selecting the switch with the smallest `identifier` as the root of the tree. The branches of the spanning tree are then composed of the shortest paths that allow all of the switches that compose the network to be reached. The `BPDUs` exchanged by the switches contain the following information :
|
|
the `identifier` of the root switch (`R`)
|
|
the `cost` of the shortest path between the switch that sent the `BPDU` and the root switch (`c`)
|
|
the `identifier` of the switch that sent the `BPDU` (`T`)
|
|
the number of the switch port over which the `BPDU` was sent (`p`)
|
|
We will use the notation `<R,c,T,p>` to represent a `BPDU` whose `root identifier` is `R`, `cost` is `c` and that was sent from the port `p` of switch `T`. The construction of the spanning tree depends on an ordering relationship among the `BPDUs`. This ordering relationship could be implemented by the Python function below.
|
|
In addition to the `identifier` discussed above, the network administrator can also configure a `cost` to be associated to each switch port. Usually, the `cost` of a port depends on its bandwidth and the [IEEE802.1d]_ standard recommends the values below. Of course, the network administrator may choose other values. We will use the notation `cost[p]` to indicate the cost associated to port `p` in this section.
|
|
Bandwidth
|
|
Cost
|
|
10 Mbps
|
|
2000000
|
|
100 Mbps
|
|
200000
|
|
1 Gbps
|
