Link-Layer Switches and Bridging

A link-layer switch is a store-and-forward device that operates on Ethernet frames using only Ethernet and the Frame Format information — specifically source and destination MAC addresses — with no awareness of IP addresses or routing. Each switch port connects to either a single host, another switch, or (historically) a shared hub segment; today almost every link is a dedicated, full-duplex, point-to-point cable, so each switch port is its own collision domain. This is the crucial structural difference from a hub, which is a pure physical-layer repeater: a hub retransmits every incoming bit out every other port, so all attached hosts share one collision domain and see all traffic (a security and performance liability). A switch instead makes a per-frame forwarding decision. The core data structure is the switch (forwarding) table, a set of entries of the form `(MAC address, interface, timestamp)`. A well-formed table entry asserts: "the host with this MAC address can be reached by sending frames out this interface." Critically, the table is not configured by an administrator or computed by a routing algorithm — it is built by self-learning (also called transparent bridging), a passive observation process that requires no protocol messages between switches at all. This is what makes switches "plug and play": you can cable an arbitrary tree of switches together and correct forwarding emerges automatically. Two mechanisms complete the picture. Filtering is the decision to not forward a frame out a particular interface — most importantly, dropping a frame entirely when its destination is already known to reside on the same interface the frame arrived on (the sender and receiver share a segment, so nothing needs to be relayed elsewhere). Flooding is the fallback of forwarding a frame out every interface except the one it arrived on, used whenever the destination's location is unknown or the destination is the broadcast/multicast address. Learning, filtering, and flooding together define the complete forwarding behavior of a switch; nothing else is needed for a tree-shaped network.

The switch runs one procedure per arriving frame. Two things happen on every frame: a learning step (always executed, using the source address) and a forwarding step (using the destination address). These are independent and can be thought of as two separate passes over the same frame.

Learning step. When a frame arrives on interface `x` with source address `S`, the switch records (or refreshes) the association `S → x` in its table, tagged with the current time. This is valid because Ethernet source addresses are (assumed) globally unique and a real physical arrival on interface `x` is direct evidence that `S` is reachable via `x`. Entries are not permanent: each carries an aging timer (typically minutes), and stale entries are purged so that the table adapts if a host moves to a different port (e.g., a laptop unplugged from one switch and plugged into another).

Forwarding step. When a frame arrives on interface `x` with destination address `D`, the switch does a table lookup on `D`:

• If `D` is the broadcast address, or a multicast address the switch treats as "flood," forward out every interface except `x`.
• If `D` has a table entry mapping to some interface `y`:
• If `y = x` (destination lives on the same segment as the sender — this happens on shared hub segments, or in degenerate cases), filter: drop the frame, forward nowhere.
• Else forward the frame out interface `y` only.
• If `D` has no table entry (an "unknown unicast"), flood: forward out every interface except `x`.

``` // State: table is a map from MAC address -> (interface, timestamp) // AGE_LIMIT is the maximum entry lifetime (e.g., 300 seconds) function ON_FRAME_ARRIVAL(frame, arrival_interface): S <- frame.source_mac D <- frame.dest_mac now <- CURRENT_TIME() // ---- Learning step (always runs) ---- table[S] <- (arrival_interface, now) // ---- Forwarding step ---- if D == BROADCAST_ADDR or IS_FLOOD_MULTICAST(D): for each interface i in ALL_INTERFACES: if i != arrival_interface: SEND(frame, i) return if D in table and (now - table[D].timestamp) <= AGE_LIMIT: target <- table[D].interface if target == arrival_interface: // destination already reachable without relaying: filter drop(frame) else: SEND(frame, target) else: // unknown destination: flood, and let learning fix this // for future frames once the destination itself transmits for each interface i in ALL_INTERFACES: if i != arrival_interface: SEND(frame, i) // Runs periodically, independent of frame arrivals function AGE_TABLE(): for each (mac, entry) in table: if CURRENT_TIME() - entry.timestamp > AGE_LIMIT: remove mac from table ``` A subtlety worth naming explicitly: learning and forwarding use different fields of the same frame — learning reads the source, forwarding reads the destination — and they happen in the same pass, so a switch effectively learns about a host's location before it might need to forward a reply back to that host, but only if that host has transmitted at least once. The first frame ever sent to a fresh MAC address is always flooded, because nothing has taught the switch where that address lives yet; only the reply (or any subsequent traffic from that host) teaches the switch, after which later frames to it are unicast-forwarded.

Reading the diagram: once every host has transmitted at least one frame, Switch A's table has collapsed the entire left subtree to "port 1" and the entire right subtree to "port 2" — it does not need to know which individual host is which switch's problem, only which of its own ports leads toward that host. This is exactly what lets forwarding tables stay small even in large fanout: a switch's table size is bounded by the number of distinct MAC addresses ever seen, not by the depth or width of the whole network.

Per-frame time complexity. With the table implemented as a hash map keyed by MAC address, both the learning update and the forwarding lookup are `O(1)` expected time. Flooding costs `O(k)` where `k` is the number of interfaces on the switch, since the frame must be copied/queued to each of the up-to-`k−1` other ports. In the worst case (every frame is an unknown unicast or broadcast), forwarding a stream of `n` frames through a switch with `k` ports costs `O(n·k)` total work; in the common case (steady state, most destinations known), it is `O(n)`. Real switch ASICs implement the table lookup in a content-addressable memory (CAM), giving true `O(1)` hardware lookup at line rate, which is why switches can forward at multi-gigabit or terabit aggregate rates without becoming the bottleneck.

Space complexity. The table stores one entry per distinct MAC address the switch has observed since entries last aged out, so space is `O(D)` where `D` is the number of distinct source addresses seen within one aging window. Real switch chips provision a fixed CAM size (e.g., 16K–128K entries); if the number of distinct addresses exceeds capacity — a MAC table exhaustion condition, sometimes triggered maliciously (MAC flooding attacks) — the switch typically degrades toward flooding-everything behavior, temporarily behaving like a hub. This is a real, documented tradeoff, not a hypothetical one: it is exactly why switches in adversarial environments need port security or rate limiting on learned addresses.

Correctness of self-learning, informally. Claim: in a network whose physical topology is a tree (no cycles among switches), after every host has transmitted at least one frame, every switch's table correctly maps every other host's MAC address to the interface on the (unique) path toward that host, and the algorithm never mis-delivers a frame to a host that shouldn't receive it (beyond unavoidable floods before learning completes). Proof sketch. Because the topology is a tree, there is a unique path between any two hosts, and hence for switch `T` and destination host `H`, there is a unique interface of `T` that lies on that unique path (call it `next(T, H)`). We show by induction on frames observed that once `T` has recorded an entry for `H`, that entry equals `next(T, H)`. Base case: `H`'s own first transmitted frame travels from `H` toward the rest of the network. Every switch it passes through receives that frame on the interface that is, by construction, the one lying on the path back to `H` — because the frame physically arrived from that direction. So every switch on the frame's path correctly learns `next(T,H)` immediately (this is the "learning step" applied to the source address). Inductive step: Suppose later, after topology and table contents have stabilized, some other host `H'` sends a frame toward `H`. At each switch `T` along the path, `T` looks up `H` in its table. Because table entries are only ever overwritten by a frame that actually arrived from a given interface (correct evidence), and because the tree topology guarantees at most one interface can ever be "the direction toward `H`," the entry `T` holds for `H`, once learned, cannot become wrong except through aging (removal) or a host physically moving (which produces a new, also-correct arrival event). Hence the invariant "table entries, when present, are correct" is preserved by every operation the algorithm performs: learning only inserts observed-true facts, and aging only removes facts (never inserts wrong ones). A missing entry causes a safe, if wasteful, flood rather than an incorrect unicast — so the algorithm degrades to correctness-preserving over-delivery, never under-delivery or mis-delivery, whenever information is incomplete. ∎ This argument depends essentially on the tree assumption. If the physical topology contains a cycle (e.g., two redundant links between the same pair of switches, added for fault tolerance), a broadcast or unknown-unicast frame injected into the cycle gets flooded around it, is received again by a switch that already forwarded it, gets flooded again, and the frame count grows without bound — this is the infamous broadcast storm, and it also corrupts learning, because a switch may see the same source's frame arrive on two different interfaces in rapid succession and thrash its table entry back and forth. The self-learning switch, as described, is only correct on acyclic topologies; making cyclic (redundant) physical topologies behave correctly requires computing a spanning tree over the physical links and logically disabling the redundant ones (the Spanning Tree Protocol), which is the natural next mechanism built on top of plain bridging, and is itself a prerequisite for safely running the segmented, VLAN-aware switching planes used in production networks.

Tradeoffs, stated honestly.

• Self-learning is fully distributed and needs zero configuration, but it is reactive: the first frame to any address is always flooded, which is wasted bandwidth and a (mild) information leak.
• Filtering reduces unnecessary traffic and increases effective throughput versus a hub, but only once tables have "warmed up"; a cold switch (just powered on, empty table) behaves exactly like a hub until it learns.
• Aging keeps tables adaptive to host movement, but too-short an aging interval causes needless re-flooding, while too-long an interval risks stale entries after a host moves ports.
• A switch cannot forward faster than the sum of its outgoing link rates for flooded traffic; heavy flooding (broadcast-heavy protocols, or attacks) degrades the very filtering benefit switches exist to provide.

Consider the three-switch tree from the figure, with Switch A in the middle connecting to Switch B (which serves H1, H2, H3) via port 1, and Switch C (serving H4, H5, H6) via port 2. All tables start empty. Trace the following sequence of frames arriving at Switch A (we omit Switch B and C's internal tables for brevity and focus purely on A's behavior).

Two steps deserve a closer look. Step 1 is a cold-cache flood: A has never heard from H4, so it must guess "everywhere but where this came from," which happens to be correct only because port 2 is the sole other port. Step 5 shows filtering in a case that would be wrong to get backwards: H3 and H1 are both reachable via port 1 (they are both under Switch B), so when H3 sends to H1, that traffic never needs to reach Switch A's port 2 side at all; forwarding it out port 2 would be a wasted (and mildly leaky) transmission, and the algorithm correctly suppresses it. Notice this is not a trivial symmetric case — H1 and H3 are different hosts on the same interface as seen by A, even though they are not directly on the same physical wire; A only knows "reachable via port 1," and that is exactly the granularity it needs. By the end of step 6, Switch A's table fully and correctly summarizes reachability: everything behind port 1 collapses to one entry-group, everything behind port 2 to another, regardless of how many hosts eventually appear behind each port — illustrating the `O(D)` space bound independent of topology depth.

The switch grew directly out of the need to interconnect and segment Ethernet's original shared-medium design once it became clear that a single collision domain could not scale to large numbers of hosts. The transparent, self-learning bridge — the key intellectual contribution — was formalized and standardized in the 1980s, turning what could have been a manually configured device into one that "just works" when cabled into any tree topology.

Every enterprise, campus, and data-center Ethernet network today is built from link-layer switches running exactly this self-learning algorithm as their baseline forwarding behavior, augmented with spanning tree (or its modern replacements) for loop safety and, in production networks, Virtual LANs (VLANs) to segment one physical switch fabric into multiple isolated broadcast domains. Data-center fabrics built from Clos or fat-tree topologies use thousands of switch ASICs, each running hardware CAM lookups derived directly from this learning-and-filtering model, to achieve terabit-scale forwarding. Home and small-office routers contain an embedded Ethernet switch chip performing the same self-learning algorithm to connect wired LAN ports before any routing or NAT logic runs. Understanding self-learning switches is also the necessary foundation for understanding Software-Defined Networking (SDN) controllers, which often replace or augment the learning algorithm with centrally computed forwarding rules while still relying on the same underlying frame-forwarding semantics, and for understanding why network engineers care so much about physical topology design, redundancy, and loop prevention in real cabling plans.

Ask the tutor: How does the Spanning Tree Protocol decide which redundant links to block, and how does that interact with the self-learning tables discussed here?