Ethernet: minimum frame, switches, spanning tree and VLANs
Frame and MAC addresses, CSMA/CD and the minimum frame length proved, self-learning switches, broadcast storms, the spanning tree with proof of tree properties, VLANs.
Ethernet was born in 1973 as a coaxial cable shared by a few computers in a laboratory, and it has become the technology of almost every local network and of much of operators’ networks, from 10 Mb/s to 800 Gb/s. In this lesson we look at the Ethernet frame and addresses, multiple access with collision detection with the proof of the minimum frame length, switches that learn by themselves where stations are, the problem of loops with the spanning tree and the proof of its properties, and VLANs.
The frame and addresses
An Ethernet frame contains the destination and source addresses, a field indicating the protocol carried (for instance IPv4 or IPv6), the data, from 46 to 1500 bytes in the classic version, and a 32-bit check code (CRC) that lets the receiver discard damaged frames. MAC addresses are 48 bits, written in hexadecimal as 3C:22:FB:1A:07:9E: the first 24 identify the manufacturer, the rest the card. The address with all bits set to 1 is the broadcast, received by all stations.
The shared medium and collisions
In the original Ethernet all stations were connected to the same cable. The CSMA/CD protocol (carrier sense multiple access with collision detection): a station listens to the medium, transmits only if it is free, and keeps listening while transmitting; if it detects a collision with another transmission it stops, waits a random time and tries again, doubling the mean waiting interval each time (binary exponential backoff). It is an evolution of ALOHA (Electrical Communications lesson on multiple access).
Theorem. For a station always to notice a collision while it is still transmitting, the frame duration must be at least twice the maximum propagation time 
between two stations: 
.
Proof. The worst case: station A, at one end, starts transmitting; the signal takes almost to reach station B at the other end, which an instant earlier found the medium free and started transmitting. The collision happens near B, and B’s signal takes another to return to A. A receives evidence of the collision about 
after the start of its own transmission: if it had already finished by then, it would believe the frame had arrived. A transmission lasting at least , i.e. at least 
bits, is therefore needed. ∎
In 10 Mb/s Ethernet the value set was 512 bits (51.2 µs), covering 2500 m with repeaters: hence the 64-byte minimum frame length, still in the standard.
Switches
Today every station is connected with its own cable to a switch, in full duplex: it can transmit and receive at the same time, and collisions no longer exist. The switch receives a frame on one port and forwards it only on the port where the destination is. How does it know? It learns by itself:
- for every frame received, it records in a table that the source address lies behind the port it came from;
- if the destination address is in the table, it forwards the frame only on that port (or discards it, if it is the same port it came from);
- if it is not, or if it is a broadcast, it forwards it on all the other ports (flooding).
Entries age and are deleted after a few minutes, so the table follows stations as they move. No configuration is needed: plug in the cables and it works.
The problem of loops
For reliability, switches are connected with redundant paths. But a loop is fatal: a broadcast frame is forwarded by every switch on all ports, comes back round the loop and is forwarded again, forever, multiplying at every turn. In a few seconds the network is saturated (broadcast storm), and the tables go haywire because they see the same source on different ports.
The spanning tree protocol (STP, and its rapid version RSTP) solves the problem: the switches elect a root (the one with the lowest identifier), each computes its shortest path to the root, and ports not on these paths are blocked. The result is a tree.
Theorem. A tree connecting 
nodes has exactly 
links, and between any two nodes there is a single path.
Proof. *Uniqueness of the path.* If there were two different paths between two nodes, joining them would give a cycle, which a tree by definition does not have. *Number of links.* By induction: a tree with one node has zero links. A tree with 
nodes has at least one leaf (a node with a single link: following a longest possible path, its last node cannot have other neighbours without creating a cycle or lengthening the path). Removing the leaf and its link leaves a tree with nodes, which by hypothesis has 
links; putting them back gives . ∎
The unique path guarantees that every frame arrives only once. The blocked links remain as spares: if an active link fails, the tree is recomputed and a spare one is activated, in a few seconds with RSTP.
VLANs
A flat local network sends every broadcast to everyone, and does not separate a company’s departments. VLANs (virtual LANs, IEEE 802.1Q standard) divide a physical switch into several logical switches: each port belongs to a VLAN, and frames passing between switches carry a 12-bit tag with the VLAN number, up to 4094 networks. Stations in different VLANs cannot see each other at the link layer: to communicate they must go through a router, where security rules can be applied (lesson on IP addressing).
