MAC Address Tables

The previous lesson took the switch’s table as given: all eight of the eight addresses were mapped to the right port, and the table therefore sent all forty of the forty frames out a single port. Under that assumption, the table brought delivered down from 280 to 40.

A real table does not start that way and does not stay that way. When a switch powers on, its table is empty; entries fill in through observation; a silent station never gets an entry written; and a written entry does not stay correct forever, since the station can move to another port. This lesson’s question is not what the table does, but how long it lives.

Three Separate Shortfalls

A table falls short in three separate ways, and the three do not cost the same.

Unlearned entry. The address is not in the table. The switch does not know where the destination is and passes the frame to every port but the one it arrived on. The frame reaches its destination; the cost is only unnecessary copies. The learning mechanism itself — writing the source address together with its arrival port, and flooding a frame whose destination is unknown — was established in the Ethernet and MAC Addresses lesson of the Network Models and Protocols course and is not repeated here.

Aged entry. The address was in the table, but the time since the entry was placed exceeded the entry’s lifetime, and the entry was deleted. The result is the same as an unlearned entry: flooding, a frame that reaches its destination, unnecessary copies. The reason it is counted separately is that it comes from a different source — one arises from never having been learned, the other from having been forgotten.

Stale entry. The address is in the table, the entry is fresh, and it is wrong. The station has moved to another port, and the table still points at the old one. The switch does not flood here; it confidently sends the frame out the wrong port. The frame finds no one there and falls into a black hole. Of the three shortfalls, only this third one kills the frame.

The distinction comes down to this: flooding is expensive but correct, a stale entry is cheap and wrong. An entry’s lifetime is a choice between the two.

Which Domain Flooding Does Its Work In

A flooded frame goes out every port even though its destination is a single station. The two scopes from the previous lesson diverge here. Flooding does not grow the collision domain: the ports are still isolated from each other, and the copies going out do not clash with each other. Flooding uses up the broadcast domain: the copies go exactly where a broadcast frame would go.

The result is this: an unlearned destination temporarily turns a single frame into a broadcast frame. The larger the broadcast domain, the larger flooding’s cost, and this cost is multiplied by the number of frames flooded.

A station that never speaks makes this cost permanent. In the measurement, station h never sends a frame; because its source address never appears in any frame, it never gets written to the table. Every frame going to it is flooded to the end of the measurement. The table’s row count is therefore not eight but seven.

The Table Looks at the Address, Not the Port

The table’s orientation looks backward at first glance: the switch has eight ports, but the table counts not ports but addresses. A port need not hold exactly one station. If another switch is connected to it, the addresses of every station behind it map to that same port; a virtualized host can likewise show more than one address from a single port.

This has two consequences. First, the table’s row count grows not with the port count but with the number of addresses seen; the seven rows in the measurement come from eight stations, not nine ports. Second, the same address cannot appear on two ports at once: a new observation updates the entry rather than duplicating it. An address moving back and forth between two ports is not the table contradicting itself, it is the network producing contradictory observations — its source is the subject of a later lesson in this topic.

The table’s capacity is also finite. When the number of entries exceeds capacity, an entry is dropped to make room, and frames going to the dropped entry’s address are flooded. This gives the same result as shortening the lifetime; the difference is that the choice is made by occupancy, not by the administrator.

# taught transcript, not run

MAC address table (instant 12)
  address  port  instant written
  a        1     13
  b        2      9
  c        3     11      <- this entry goes stale at instant 12
  d        4      8
  e        5     10
  f        6     12
  g        7      5
  (no row for h: never transmitted)

at instant 12: station c moves from port 3 to port 9.
  instant 15, destination c -> table says port 3 -> no one there -> black hole
  if the entry ages out    -> flooding -> every port      -> reaches
  if c transmits again     -> entry becomes port 9         -> reaches

The Measurement’s Assumptions

• ND8 — Eight stations are connected to a switch with nine ports; the ninth port is empty and is the target of the move. The oracle is known because we built the layout ourselves, and it says which address is on which port at every instant.
• ND9 — Forty frames are drawn from a single generator with a single modulus. Draws where the source equals the destination, or where the source is the silent station, are discarded; the silent station therefore never sends anything.
• ND10 — The unit of time is the frame: an entry’s age is the number of frames elapsed since it was placed. In the regime where the lifetime is None, the entry is never deleted.
• ND11 — The table learns only from the source address, and every frame first learns, then forwards. This order matches the real mechanism and affects the measurement: a station’s own transmission refreshes its own entry.
• ND12 — In the move regime, a station switches to the empty port on frame 12 and announces this to no one. The table corrects itself only two ways: the entry ages out, or the station transmits again.
• ND13 — The fate names are the same as in the shared definition. A frame that leaves a copy on the destination’s real port is counted reached; one that does not is counted a black hole. In this single-switch setup, a loop cannot form.
• ND14 — The set’s resolution is forty frames; the smallest measurable difference is $1/40 = 0{,}025$.

The Measurement

"""MAC address table age: cost of unlearned and aged entries.

The learning mechanism was established in the Network Models course;
what is measured here is how long an entry lives.
"""
SEED = 20260810
STATIONS = ["a", "b", "c", "d", "e", "f", "g", "h"]
PORTS = 9
SILENT = "h"
MOVED, MOVE_TIME = "c", 12


def generator(seed):
    d = seed % 2147483646 + 1

    def r(n):
        nonlocal d
        d = (d * 48271) % 2147483647
        return d % n
    return r


def frames(count=40):
    r, result = generator(SEED), []
    while len(result) < count:
        x, y = STATIONS[r(8)], STATIONS[r(8)]
        if x != y and x != SILENT:
            result.append({"instant": len(result), "source": x, "destination": y})
    return result


def oracle(instant, move):
    """Reality: at the move instant, one station switches to the empty port."""
    location = {a: i + 1 for i, a in enumerate(STATIONS)}
    if move and instant >= MOVE_TIME:
        location[MOVED] = PORTS
    return location


def measure(C, age, move):
    table, fate = {}, {"reached": 0, "black hole": 0}
    flood = {"unlearned": 0, "aged": 0}
    delivered = unnecessary = 0
    for c in C:
        location = oracle(c["instant"], move)
        table[c["source"]] = (location[c["source"]], c["instant"])
        entry = table.get(c["destination"])
        fresh = entry is not None and (age is None or c["instant"] - entry[1] < age)
        if fresh:
            outputs = [entry[0]]
        else:
            flood["aged" if entry else "unlearned"] += 1
            outputs = [p for p in range(1, PORTS + 1) if p != location[c["source"]]]
        delivered += len(outputs)
        unnecessary += sum(1 for p in outputs if p != location[c["destination"]])
        fate["reached" if location[c["destination"]] in outputs else "black hole"] += 1
    return flood, fate, delivered, unnecessary, len(table)


C = frames()
print(f"frames {len(C)} | ports {PORTS} | silent station {SILENT}, frame as "
      f"destination {sum(1 for c in C if c['destination'] == SILENT)} | "
      f"flooding ceiling {len(C) * (PORTS - 1)}")
HEADER = (f"{'age':>5s} {'unlearned':>12s} {'aged':>9s} {'reached':>6s} "
          f"{'black hole':>10s} {'delivered':>6s} {'unnecessary':>8s} {'rows':>5s}")
for move in (False, True):
    print()
    print("with move" if move else "no move")
    print(HEADER)
    for age in (None, 20, 10, 5, 2):
        f, k, d, u, n = measure(C, age, move)
        print(f"{str(age):>5s} {f['unlearned']:12d} {f['aged']:9d} "
              f"{k['reached']:6d} {k['black hole']:10d} {d:6d} {u:8d} {n:5d}")

frames 40 | ports 9 | silent station h, frame as destination 4 | flooding ceiling 320

no move
  age    unlearned      aged reached black hole delivered unnecessary  rows
 None           10         0     40          0    110       70     7
   20           10         0     40          0    110       70     7
   10           10         6     40          0    152      112     7
    5           10        14     40          0    208      168     7
    2           10        24     40          0    278      238     7

with move
  age    unlearned      aged reached black hole delivered unnecessary  rows
 None           10         0     37          3    110       73     7
   20           10         0     37          3    110       73     7
   10           10         6     38          2    152      114     7
    5           10        14     39          1    208      169     7
    2           10        24     40          0    278      238     7

The Unlearned Entry’s Unchanging Share

In both tables, the unlearned column is 10, and no lifetime value changes it. This number has two parts: the initial encounters from the table starting empty, and the 4 frames going to the silent station. The first part is paid once, the second throughout the measurement.

The result matters: extending an entry’s lifetime does not reduce unlearned entries. Lifetime only decides how long an entry survives; it does not produce an entry that was never written. The only way to bring a silent station into the table is to make it speak. Because the table is fed only by observation, an endpoint that produces none at all sits entirely outside its field of view, and every frame going there pays the cost of this blindness.

The regime that leaves lifetime unlimited delivers 110; if everything could be flooded, the ceiling is 320. So even working correctly, the table produces less than a third of the ceiling’s deliveries — the rest is already saved. As lifetime shrinks, this saving erodes: at a 10-frame lifetime, delivered is 152; at 5, 208; at 2, 278. In the last row, the switch has climbed to 0.869 of the ceiling; the table is nearly void, and the device has stopped being one that makes decisions.

Two Sides of Lifetime

The lower table reads the same lifetime series together with a move, and the direction reverses.

In the regime that leaves lifetime unlimited, 3 frames fall into a black hole. All three are sent after the move, before the moved station speaks again; the table is confident and wrong over that stretch. A 20-frame lifetime gives the same result, because no entry reaches that age before the measurement ends: a lifetime longer than the measurement window is indistinguishable from an unlimited one.

At a 10-frame lifetime, black holes drop to 2; at 5, to 1; at 2, to 0. What performs the correction is not an announcement — no one reports the move. It is forgetting: the moment the entry is deleted, the switch again admits it does not know, floods, and the flooded frame reaches its destination because it visits the new port too.

The cost sits on the same rows. Bringing black holes down from 3 to 0 raises delivered from 110 to 278: saving one frame costs an average of fifty-six extra copies. Three frames in a set of forty is 0.075 and three times the resolution, so it is a measurable difference; but the copies paid to zero out the loss exceed half the flooding ceiling.

The pattern is this: an entry’s lifetime is a choice between how long it stays wrong and the cost of not knowing. A long lifetime makes the table cheap and prolongs the error; a short lifetime shortens the error and voids the table. No lifetime zeroes out both at once, because the only way for the switch to learn of a move is a new observation, and the time until that observation arrives cannot be measured.

Lifetime Is Not Chosen Alone

The measurement had a single lifetime because it had a single table. On a real path, two separate caches for the same destination stand side by side: the switch’s MAC address table, and the address-resolution cache on the sending host. The second was established in the ARP lesson of the Network Models and Protocols course and is not repeated here; what matters here is only that the two lifetimes are chosen relative to each other.

When the two are not equal, an asymmetry arises. If the sending host keeps holding the destination’s hardware address while the switch’s entry has been deleted, the host keeps sending without querying, and the switch floods every frame. If the destination station is only ever a responder — it never speaks on its own — its entry never gets rewritten, and flooding becomes permanent. The silent station’s persistent share of 10 in the measurement is a small instance of this.

The rule is this: if the switch entry’s lifetime is chosen shorter than the upper-layer address cache’s lifetime, flooding is not a malfunction but the ordinary result of the design. Chosen the other way around, the stale entry’s lifetime lengthens and the black-hole window widens. The measurement’s two tables show these two directions separately; the choice lies between them.

Tables Do Not Know Each Other

The measurement was run with a single switch, which makes the result more optimistic than it is. When two switches stand side by side, there are two tables, and there is no synchronization between them. Each switch sees only frames passing through its own ports; it writes what it sees and does not know what it does not see. An entry one switch has just refreshed can already be stale in the other.

This is not a flaw in the table but its definition: a table is a local copy of a shared reality. There is no announcement that keeps the copy current; the only thing that keeps it current is seeing the same traffic. Two switches that do not see the same traffic can point to different ports for the same address.

In the single-switch setup, this cost was not visible, because the only fate measured was the black hole: a frame going out the wrong port died there. With two tables, a third fate opens up. If one switch sends the frame forward and the other sends it back, the frame does not die; it goes back and forth between the two devices. A loop is not something a single table can produce — it is a disagreement between at least two tables, and it will be counted for the first time in a later lesson in this topic.

Summary

• A table falls short in three separate ways: unlearned and aged entries lead to flooding, a stale entry leads to a black hole; the first two are expensive but correct, the third is cheap and wrong.
• Flooding does not use up the collision domain, it uses up the broadcast domain: a flooded frame does the work of a broadcast frame even though it is bound for a single destination.
• The unlearned-entry count stays 10 across every lifetime value; 4 of it goes to the station that never speaks, and the table therefore stays at 7 rows, not eight.
• As lifetime shortens, delivered grows 110, 152, 208, 278; the last value is 0.869 of the flooding ceiling of 320 and leaves the table nearly void.
• In the move regime, black holes drop 3, 3, 2, 1, 0; what performs the correction is not an announcement, it is the entry being forgotten.

Next Step

In this measurement, flooding always went to the same place: all nine ports. The reason was that the eight stations were in a single broadcast domain — in the previous lesson’s measurement too, the broadcast-domain count was one in every regime. But flooding’s cost is multiplied directly by the size of this domain. The next lesson measures splitting the domain: when more than one broadcast domain is defined on the same physical switch, how many copies does flooding come down to, how many rows does the table grow to, and where does the black hole that segmentation itself produces come from.