Source string Source string

English Actions
The `MAC address learning` algorithm combined with the forwarding algorithm work well in a tree-shaped network such as the one shown above. However, to deal with link and switch failures, network administrators often add redundant links to ensure that their network remains connected even after a failure. Let us consider what happens in the Ethernet network shown in the figure below.
Ethernet switches in a loop
When all switches boot, their `MAC address table` is empty. Assume that host `A` sends a frame towards host `C`. Upon reception of this frame, switch1 updates its `MAC address table` to remember that address `A` is reachable via its West port. As there is no entry for address `C` in switch1's `MAC address table`, the frame is forwarded to both switch2 and switch3. When switch2 receives the frame, its updates its `MAC address table` for address `A` and forwards the frame to host `C` as well as to switch3. switch3 has thus received two copies of the same frame. As switch3 does not know how to reach the destination address, it forwards the frame received from switch1 to switch2 and the frame received from switch2 to switch1... The single frame sent by host `A` will be continuously duplicated by the switches until their `MAC address table` contains an entry for address `C`. Quickly, all the available link bandwidth will be used to forward all the copies of this frame. As Ethernet does not contain any `TTL` or `HopLimit`, this loop will never stop.
The `MAC address learning` algorithm allows switches to be plug-and-play. Unfortunately, the loops that arise when the network topology is not a tree are a severe problem. Forcing the switches to only be used in tree-shaped networks as hubs would be a severe limitation. To solve this problem, the inventors of Ethernet switches have developed the `Spanning Tree Protocol`. This protocol allows switches to automatically disable ports on Ethernet switches to ensure that the network does not contain any cycle that could cause frames to loop forever.
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
20000
2000
100 Gbps
200
The `Spanning Tree Protocol` uses its own terminology that we illustrate in the figure above. A switch port can be in three different states : `Root`, `Designated` and `Blocked`. All the ports of the `root` switch are in the `Designated` state. The state of the ports on the other switches is determined based on the `BPDU` received on each port.
The `Spanning Tree Protocol` uses the ordering relationship to build the spanning tree. Each switch listens to `BPDUs` on its ports. When `BPDU = <R,c,T,p>` is received on port `q`, the switch computes the port's `root priority vector`: `V[q] = <R,c+cost[q],T,p,q>` , where `cost[q]` is the cost associated to the port over which the `BPDU` was received. The switch stores in a table the last `root priority vector` received on each port. The switch then compares its own `identifier` with the smallest `root identifier` stored in this table. If its own `identifier` is smaller, then the switch is the root of the spanning tree and is, by definition, at a distance `0` of the root. The `BPDU` of the switch is then `<R,0,R,p>`, where `R` is the switch `identifier` and `p` will be set to the port number over which the `BPDU` is sent.
Otherwise, the switch chooses the best priority vector from its table, `bv = <R,c+cost[q'],T,p,q'>`. The port `q'`, over which this best root priority vector was learned, is the switch port that is closest to the `root` switch. This port becomes the `Root` port of the switch. There is only one `Root` port per switch (except for the `Root` switches whose ports are all `Designated`). The switch can then compute its own `BPDU` as `BPDU = <R,c',S,p>` , where `R` is the `root identifier`, `c'` the cost of the best root priority vector, `S` the identifier of the switch and `p` will be replaced by the number of the port over which the `BPDU` will be sent.
Component Translation Difference to current string
This translation Propagated Read only cnp3-ebook/protocols/ethernet
The following string has the same context and source.
Propagated Read only cnp3-ebook/protocols/lan

Loading…

User avatar None

String updated in the repository

cnp3-ebook / protocols/ethernetEnglish

a year ago
Browse all component changes

Glossary

English English
No related strings found in the glossary.

String information

Flags
read-only
Source string location
../../protocols/ethernet.rst:339
String age
a year ago
Source string age
a year ago
Translation file
locale/pot/protocols/ethernet.pot, string 78