Link layer: Data link


We've reached the bottom of the stack that still involves protocols. The link layer moves frames across a single hop — one physical link, or one LAN — and it has to solve two problems the layers above never face: detecting that the bits themselves got corrupted, and deciding who gets to talk when several hosts share one wire or one slice of radio spectrum. Along the way we'll look closely at Ethernet and at switches, which turn out to learn their forwarding tables by a mechanism far simpler than anything in the routing unit. Then we'll assemble the whole course into one story: a laptop, a printer, a Wi-Fi access point, and a web request.

Slides from class

Files:

Additional information:

Agenda

These notes cover Ethernet and switching, then use a home network to put the whole course together, and finally take up the link layer's two distinctive problems: error detection and channel sharing. Wireless links get their own day next class.

Notes

The IP hourglass

Before going down another layer, a picture worth carrying with you. Draw the protocol stack as an hourglass. At the top, many application protocols: HTTP, DNS, SMTP, FTP. Below them, a few transport protocols: TCP, UDP, QUIC. At the bottom, many link and physical technologies: Ethernet, Wi-Fi, PPP, Bluetooth, PDCP, over copper, radio, and fiber.

And in the middle, at the thin waist, exactly one protocol: IP. Every one of the billions of Internet-connected devices must implement it, and each gets a locally unique IP address.

That shape explains a great deal. Innovation is easy at the top and the bottom, because anyone can add a new application protocol or a new physical medium without asking permission — they only need to speak IP at the boundary. And innovation is nearly impossible in the middle, which is why the IPv6 transition has taken 25 years. Today we're working entirely below the waist, where there are many technologies and no requirement that they resemble each other.

Ethernet

Network infrastructure — routers and switches — is typically connected by copper or fiber, and Ethernet is the dominant wired LAN technology at Layer 2. It was the first widely used LAN technology, it's simple and cheap, and it has kept up with the speed race from 10 Mbps to 400 Gbps, often with a single chip supporting multiple speeds.

Ethernet is full duplex, which it achieves physically: a copper cable uses two wires for transmit and two for receive, and fiber uses one strand each way. Separate paths, so both directions can be active at once.

From bus to switched

Ethernet's physical topology has changed fundamentally. Through the mid-1990s it was a bus — a coaxial cable that every node tapped into, putting all nodes in the same collision domain, so any two could collide with each other.

Today switched Ethernet prevails: an active link-layer switch sits logically at the center, with a point-to-point connection from each host to the switch. Each spoke runs its own separate instance of the Ethernet protocol, so hosts do not collide with each other at all. Keep that in mind during the channel-sharing section later — much of the collision machinery in Ethernet is a legacy of the bus era, which is why modern switched links rarely exercise it.

Frame structure

A sending interface encapsulates an IP datagram (or another network-layer packet) in an Ethernet frame with these fields:

Two details worth connecting to things you've already seen. First, that 1500-byte maximum is where the TCP MSS of 1460 comes from: 1500 − 20 (IP header) − 20 (TCP header) = 1460. A decision at Layer 2 propagates all the way up to how TCP segments your data. Second, the NIC removes the preamble and CRC before passing the frame up, so you will not see those bits in Wireshark — a reasonable thing to be confused about when the frame you capture doesn't match the diagram.

Unreliable and connectionless

Ethernet is connectionless: no handshaking between the sending and receiving NICs. And unreliable: the receiving NIC sends neither ACKs nor NAKs. Data in a dropped frame is recovered only if the original sender used a higher-layer reliable transport such as TCP; otherwise it's just gone.

Note what this means. The CRC lets Ethernet detect a corrupted frame, and its response is to discard it silently. Nobody at Layer 2 tells anyone. Recovery is entirely TCP's problem, which is exactly the layering philosophy we've seen throughout: the link layer does the one thing only it can do (check the bits on this hop) and declines to do anything else.

Ethernet's MAC protocol is unslotted CSMA/CD with binary backoff, which we'll unpack at the end.

Ethernet switches and self-learning

A switch is a link-layer device that takes an active role: it stores and forwards Ethernet frames, examines each incoming frame's MAC address, and selectively forwards it to one or more outgoing links.

Does a switch have a MAC address? Strictly it doesn't need one, since hosts never address traffic to the switch — but switches often have one anyway to provide a management interface (for VLAN setup, for instance).

Two properties make switches pleasant to work with. They are transparent: hosts are unaware of their presence, so you can think of a switch as a smart cable. And they are plug-and-play and self-learning, so they don't need to be configured at all.

Simultaneous transmissions

Because each host has a dedicated direct connection and the switch buffers packets, the Ethernet protocol runs independently on each link: no collisions, full duplex, each link its own collision domain.

Take a switch with six interfaces and hosts A, B, C and A', B', C'. A-to-A' and B-to-B' can transmit simultaneously without colliding — that's the whole benefit over a hub. But A-to-A' and C-to-A' cannot happen at the same time, because they need the same output link, so the switch must buffer. Contention hasn't vanished; it has moved from the shared medium to the switch's output queues, which is the same story as the router output ports from Day 7.

The switch table

How does the switch know A' is reachable via interface 4 and B' via interface 5? Each switch keeps a switch table whose entries are (MAC address of host, interface to reach that host, timestamp). It looks a lot like a routing table — so how does it get populated? Not with anything as elaborate as OSPF:

Self-learning. When a frame arrives, the switch learns the location of the sender: whatever interface the frame came in on is the way back to that source MAC address. It records the sender/interface pair in the table with a TTL. That's it. Every frame that crosses the switch teaches it something, for free, as a side effect of being forwarded.

The full filtering and forwarding algorithm: 

When a frame is received at the switch:
1. Record the incoming link and the MAC address of the sending host
2. Index the switch table using the MAC destination address
3. If an entry is found for the destination
     then {
       if the destination is on the segment the frame arrived from
         then drop the frame
         else forward the frame on the interface indicated by the entry
     }
     else flood    // forward on all interfaces except the arriving one

Flooding is the fallback for an unknown destination, and it's what makes the scheme work from a cold start: the first frame to an unknown host goes everywhere, the reply teaches the switch where that host is, and subsequent frames are forwarded precisely. Note also the drop case — if the destination is on the same segment the frame came from, the frame has already reached it, so forwarding would be pointless.

Interconnecting switches

Switches can be connected to each other, and the mechanism doesn't change at all. If host A on switch S1 sends to host G reachable via S4 and S3, how does S1 know to forward that way? Self-learning, exactly as in the single-switch case. Nothing about the algorithm above assumed that a neighbor was a host rather than another switch.

For a sense of scale, the UMass campus network runs 4 firewalls, 10 routers, 2,000+ switches, 6,000 wireless access points, 30,000 active wired jacks, and 55,000 active wireless devices — all built, operated, and maintained by roughly 15 people. Plug-and-play self-learning is a large part of why that ratio is possible.

Switches vs. routers

These are easy to conflate, so state the comparison precisely. Both are store-and-forward devices, and both have forwarding tables. The differences:

The deeper contrast: routers compute, switches observe. A router runs Dijkstra over a topology it assembled by flooding link-state advertisements. A switch just remembers where traffic came from. That's cheaper and requires no configuration, but it also means a switch has no notion of a path, no shortest-path guarantee, and no way to route around anything.

Virtual LANs

What happens as LANs grow and users change where they attach? Two problems arise with a single broadcast domain.

Scaling. All Layer 2 broadcast traffic — ARP, DHCP, frames to unknown MAC addresses — must cross the entire LAN. That's an efficiency problem and also a security and privacy problem, since broadcast traffic reaches everyone.

Administration. A CS user moves to an office in Thayer. They're now physically attached to a Thayer switch but want to remain logically attached to the CS network.

Port-based VLANs solve both. Switch ports are grouped by management software so that a single physical switch operates as multiple virtual switches: ports 1–8 are the CS VLAN, ports 9–15 are the Thayer VLAN. Frames to and from ports 1–8 can only reach ports 1–8 — that's traffic isolation.

Three refinements. VLANs can also be defined by the MAC addresses of endpoints rather than by switch port. Forwarding between VLANs is done by routing, just as with physically separate switches — in practice vendors sell combined switch-plus-router boxes. And membership can be dynamic, with ports reassigned among VLANs as needed, which is what solves the user-moved-offices problem.

MAC addresses and ARP

Two addresses, two purposes. An IP address is a 32-bit network-layer address for an interface, used for Layer 3 forwarding (e.g. 128.119.40.136). A MAC address — Media Access Control, also called a LAN, physical, or Ethernet address — is used locally to get a frame from one interface to another physically connected interface on the same subnet. It's 48 bits, written in hexadecimal (e.g. 1A:2F:BB:76:09:AD), burned into the NIC's ROM, though sometimes settable in software. We'll assume they're fixed today, but remember they can be changed — that matters for both privacy and attacks.

Who has MAC addresses? Hosts do. Routers do too — or rather their interfaces do, so a router with multiple interfaces has multiple MACs. Switches generally don't, except for management.

Allocation is administered by the IEEE: a manufacturer buys a portion of the address space, so the first three octets identify the manufacturer (the OUI) and the last three identify the device.

The analogy worth keeping: a MAC address is like a Social Security number (identity); an IP address is like a postal address (location). That's why MAC addresses are a flat address space and portable — move an interface to a different LAN and it keeps its MAC — while IP addresses are hierarchical and not portable, since the first part identifies the network you're attached to.

ARP

So: how do you determine an interface's MAC address knowing only its IP address? Every IP node — host or router — on a LAN keeps an ARP table of <IP address, MAC address, TTL> entries for some LAN nodes. The TTL is the time after which the mapping is forgotten, typically 20 minutes.

Note this is a different table from the switch table. The ARP table maps IP addresses to MAC addresses and lives on hosts and routers; the switch table maps MAC addresses to interfaces and lives on switches. Two tables, two purposes, easy to confuse.

ARP in action, with A wanting to send a datagram to B, and B's MAC address not in A's table:

  1. A broadcasts an ARP query containing B's IP address, in an Ethernet frame addressed to FF-FF-FF-FF-FF-FF. All nodes on the LAN receive it.
  2. B recognizes its own IP address and replies with an ARP response giving its MAC address. This reply is sent unicast, directly to A's MAC.
  3. A receives the reply and adds the entry to its ARP table — and so does everyone else who heard it.

The whole table is built automatically; system administrators never configure it. Which is convenient, and is also why ARP spoofing works: nothing in step 2 is authenticated, and step 3 means a single forged reply can poison several hosts at once.

Sending to another subnet

Now the case that ties Layer 2 and Layer 3 together: A sends a datagram to B on a different subnet, via router R. Assume A knows B's IP address (perhaps from DNS), knows R's IP address (from DHCP), and knows R's MAC address (from ARP).

Using the standard example, where A is 111.111.111.111 with MAC 74-29-9C-E8-FF-55, R has interfaces 111.111.111.110 (E6-E9-00-17-BB-4B) and 222.222.222.220 (1A-23-F9-CD-06-9B), and B is 222.222.222.222 with MAC 49-BD-D2-C7-56-2A:

  1. A creates a datagram with IP source A, IP destination B, and puts it in a frame whose MAC destination is R's interface on A's subnet. The frame carries an A-to-B datagram to R.
  2. R receives the frame, sees its own MAC, and passes the datagram up to IP. IP examines the destination address and determines the outgoing interface.
  3. R creates a new link-layer frame with MAC source 1A-23-F9-CD-06-9B (R's other interface) and MAC destination 49-BD-D2-C7-56-2A (B), still carrying the same IP source A and destination B, and transmits it.
  4. B receives the frame, checks the MAC, passes up to IP, which checks the IP address, passes up to transport, which extracts the port and delivers to the process.

The IP addresses never changed; the MAC addresses changed at every hop. We noted this back on Day 3, but now you can see exactly which device rewrites what and why: MAC addresses are meaningful only within a subnet, so crossing a subnet boundary necessarily means a new frame.

Putting it all together: one house, 26 concepts

Here is the entire course in one scenario. Your house has a Wi-Fi access point, a printer connected to it by Ethernet, and a laptop connected over Wi-Fi.

The AP bridges two link-layer technologies. The laptop sends a Wi-Fi signal to the AP; the AP extracts the Layer 2 frame, converts it to Ethernet, and forwards it to the printer. In the other direction it converts Ethernet to Wi-Fi. Same Layer 3 packet inside, different Layer 2 wrapper — exactly the substitutability the hourglass promised.

Getting the routes sorted out

Your AP connects to your ISP, which is an autonomous system controlling routing within its own network and maintaining multiple Layer 3 routers doing forwarding and routing. Working outward:

Getting an address and setting up NAT

Your Wi-Fi AP acts as a Layer 3 router and gets one IP address from the ISP's block, via DHCP. It broadcasts a Discover (it doesn't know the DHCP server), gets an Offer, sends a Request, receives an Ack, and ends up with, say, IP 123.45.67.89, netmask 255.255.255.255, and the ISP's router as its next-hop gateway.

Look at that netmask: 255.255.255.255 is equivalent to /32 — all 32 bits identify the network and none identify hosts. One address, which is exactly what the ISP is willing to give you.

So the AP creates an internal network using NAT. It picks a non-routable range — say 10.0.0.0/8 — and gives its internal interface an address on it, 10.0.0.1. Then the hosts inside get their own addresses from the AP by DHCP: the printer gets 10.0.0.2 and the laptop 10.0.0.3, both with netmask 255.255.255.0 and gateway 10.0.0.1. The AP is simultaneously a DHCP client (facing the ISP) and a DHCP server (facing your house).

Printing: a purely local exchange

The laptop wants to send a print job to the printer at 10.0.0.2. It compares that address to its own subnet, 10.0.0.0/24, and sees the destination is local — so no router is involved. But it doesn't know the printer's MAC address, so it broadcasts an ARP request: "who has 10.0.0.2? Tell 10.0.0.3."

The AP, acting as a switch for the internal network, learns the laptop's MAC on its Wi-Fi interface from that very frame, floods the broadcast, and the printer replies with its MAC. The laptop caches the mapping in its ARP table and sends the job. Every mechanism from the switch section is visible in one exchange.

Fetching a web page: crossing the boundary

Now the laptop makes an HTTP request to a web server at 11.11.53.27 (on network 11.11.0.0/16). If it had a hostname instead of an address, it would start with a DNS lookup.

  1. The laptop compares 11.11.53.27 to its netmask and realizes the destination is not on 10.0.0.0/24. So the frame must go to the gateway.
  2. It ARPs for 10.0.0.1, the AP replies with its MAC, and the laptop updates its ARP table — which now holds entries for both the printer and the router.
  3. The frame goes to the AP with the AP's MAC as the Layer 2 destination but 11.11.53.27 as the Layer 3 destination. The AP applies NAT, rewriting the source address to 123.45.67.89 and recording the mapping so the reply can find its way back.
  4. The packet travels to the ISP, across ASes chosen by BGP, and within the destination's AS along OSPF-computed shortest paths, to the router connected to the web server.
  5. The frame arrives at the server, travels up its stack — Ethernet strips the frame, IP strips the packet, TCP delivers to port 80 — and the HTTP GET reaches the web server process. The response reverses the whole path.

Ethernet, Wi-Fi, ISP, IP addresses, AS, routers, forwarding, routing, OSPF, forwarding tables, BGP, DHCP, broadcast, NAT, ARP, LAN, switch, MAC addresses, MAC tables, ARP tables, netmasks, HTTP, TCP, DNS. Nothing in that list is optional; a single page load uses all of it.

Error detection and correction

Now the link layer's own problems. First: the bits may arrive wrong.

The general framework. The sender takes data D — which includes link-layer header fields — and computes EDC (error detection and correction) bits, sending both over a bit-error-prone link. The receiver gets D' and EDC', which may differ from what was sent, and checks whether they're consistent.

Two caveats to state up front. Error detection is not 100% reliable: a protocol may miss some errors, though rarely. And a larger EDC field yields better detection and correction — you're buying reliability with bandwidth. If an error does slip through Layer 2, it will likely be caught at a higher layer, so the probability of a corrupted byte reaching the application is low, though not zero.

1) Parity checking

Single-bit parity appends one bit chosen so that the total number of 1s is even (even parity) or odd (odd parity). The receiver computes the parity of the received bits and compares. If they differ, an error is detected — more precisely, an odd number of bit errors is detected. An even number of errors goes unnoticed.

Two-dimensional parity does better. Arrange the d data bits in i rows and j columns, and compute a parity bit for every row and every column. Now a single-bit error shows up as a parity failure in exactly one row and one column — which identifies the position of the bad bit, so the receiver can correct it without retransmission. Two-bit errors can be detected but not corrected.

That's worth pausing on: with enough redundancy you can fix errors locally rather than asking for the data again. On a link with a long RTT, that trade is often worth it.

2) Internet checksum

The same mechanism from the transport unit, applied here. Treat the contents as a sequence of 16-bit integers, take the one's complement sum, and put the result in the checksum field. The receiver recomputes and compares: not equal means an error was detected; equal means no error was detected, which as we saw is not quite the same as no error. It's used in IP, UDP, and TCP.

3) Cyclic Redundancy Check

CRC is a more powerful error-detection code, and it's what Ethernet and 802.11 actually use. The setup: D is the d data bits, thought of as a binary number, and G is a generator bit pattern of r+1 bits, specified by a CRC standard and known to everyone in advance.

The sender computes r CRC bits R such that the concatenation <D,R> is exactly divisible by G in modulo-2 arithmetic. Since multiplying by 2r shifts left by r bits, the bits to send are <D,R> = D · 2r XOR R, and the value of R that makes this work is

R = remainder of ( D · 2r / G )

The receiver, knowing G, divides the received <D,R> by G. A non-zero remainder means an error was detected. The guarantee is strong and precise: CRC detects all burst errors of fewer than r+1 bits — which matters because real link errors tend to come in bursts rather than as isolated flips. International standards define G for 8-, 12-, 16-, and 32-bit generators; the 32-bit one is 100000100110000010001110110110111.

Channel sharing: multiple access protocols

The link layer's second distinctive problem. There are two kinds of link:

On a shared channel, two or more simultaneous transmissions interfere: a collision occurs when a node receives two or more signals at once. A multiple access protocol is a distributed algorithm determining how nodes share the channel — when each node may transmit.

And here is the constraint that makes the problem interesting: communication about channel sharing must use the channel itself. There's no out-of-band channel for coordination. You cannot ask permission to speak except by speaking.

What we'd want

Given a shared channel of rate R bps, an ideal protocol would have four properties:

  1. when one node wants to transmit, it can send at the full rate R;
  2. when M nodes want to transmit, each can send at average rate R/M;
  3. fully decentralized — no coordinating node, no clock or slot synchronization;
  4. simple.

No real protocol achieves all four, and the three families below each sacrifice something different.

Channel partitioning

Divide the channel into pieces and give each node a piece for exclusive use.

TDMA (Time Division Multiple Access): access in rounds, each station getting a fixed-length slot in each round. FDMA (Frequency Division Multiple Access): the spectrum is divided into bands, each station assigned one.

Both share the same flaw. In a 6-station LAN where only stations 1, 3, and 4 have data, slots (or bands) 2, 5, and 6 sit idle — and nobody else may use them. So partitioning satisfies property 2 but violates property 1: even a lone active node gets only 1/N of the channel.

Random access

Don't divide the channel. Let a node with a packet transmit at the full rate R with no a priori coordination, accept that collisions will happen, and specify how to detect and recover from them.

Slotted ALOHA. Assume all frames are the same size, time is divided into slots equal to one frame transmission time, nodes transmit only at slot boundaries, nodes are time synchronized, and all nodes detect a collision when it happens. Operation: when a node gets a fresh frame, it transmits in the next slot. No collision, and it can send a new frame next slot. Collision, and it retransmits in each subsequent slot with probability p until success.

Why randomize? Because if two nodes collided and both retried immediately, they would collide again, forever. Randomness breaks the symmetry.

Slotted ALOHA's virtues: a single active node can transmit continuously at the full channel rate, it's highly decentralized (only slot timing needs syncing), and it's simple. Its costs: collisions waste slots, idle slots waste capacity, and clock synchronization is required.

Efficiency. With N nodes each transmitting in a slot with probability p, the probability a given node succeeds in a slot is p(1−p)N−1, so the probability that any node succeeds is Np(1−p)N−1. Maximizing over p and taking N to infinity gives

max efficiency = 1/e ≈ 0.37

At best the channel does useful work 37% of the time. (Of the rest, roughly 37% of slots go empty and 26% hold collisions.) On a 10 Mbps channel that's an effective 3.7 Mbps.

Pure (unslotted) ALOHA drops the synchronization requirement: transmit as soon as a frame arrives. Simpler, but the vulnerable window doubles — a frame sent at t0 collides with anything sent in [t0−1, t0+1] — and efficiency falls to 18%. That's the price of not synchronizing clocks.

CSMA (Carrier Sense Multiple Access) adds an obvious improvement: listen before transmitting. If the channel is sensed idle, transmit the whole frame; if busy, defer. The human analogy is not interrupting others.

But collisions still occur, and the reason is instructive: propagation delay. Two nodes may each sense an idle channel because neither has yet heard the other's just-started transmission. The farther apart the nodes, the larger the window in which this can happen — so distance and propagation delay determine collision probability. And when a collision does occur, the entire packet transmission time is wasted.

CSMA/CD adds collision detection: collisions are detected within a short time and the colliding transmissions are aborted, so only part of a frame time is wasted instead of all of it. The human analogy is the polite conversationalist who stops talking on realizing someone else started. Collision detection is easy on wired media and difficult wirelessly — which is why Wi-Fi uses CSMA/CA (collision avoidance) instead, next class.

Ethernet's CSMA/CD algorithm:

  1. Ethernet receives a datagram from the network layer and creates a frame.
  2. Sense the channel: if idle, start transmitting; if busy, wait until idle, then transmit.
  3. If the entire frame is transmitted without collision, done.
  4. If another transmission is detected while sending: abort and send a jam signal.
  5. After aborting, enter binary exponential backoff: after the mth collision, choose K at random from {0, 1, 2, ..., 2m−1}, wait K × 512 bit times, and return to step 2.

The backoff is adaptive inference: more collisions imply a busier channel, so the node waits longer, and the range it draws from doubles each time. Compare TCP's congestion response — same idea (back off multiplicatively when the network says no), one layer down.

Efficiency, with tprop the maximum propagation delay between two nodes and ttrans the time to transmit a maximum-size frame, approaches 1 as tprop goes to 0 or ttrans goes to infinity. In other words: short networks and long frames. Much better performance than ALOHA, and still simple, cheap, and decentralized.

Taking turns

The two families above have complementary failures. Channel partitioning shares fairly and efficiently at high load but is inefficient at low load, since a single active node gets only 1/N of the bandwidth. Random access is efficient at low load, where one node can use the whole channel, but suffers collision overhead at high load. "Taking turns" protocols try for the best of both.

Polling. A centralized controller invites the other nodes to transmit in turn, typically used with "dumb" devices. Concerns: polling overhead, latency, and a single point of failure in the master. Bluetooth uses polling.

Token passing. A control token is passed explicitly from node to node, and a node may transmit while holding it. No master node needed. Concerns: token overhead, latency, and a different single point of failure — if a node fails to release the token, some recovery procedure has to put it back in circulation.

Cable access: all three at once

Cable networks are a nice demonstration that these families combine. Under DOCSIS, Internet frames, TV channels, and control information travel downstream on different frequencies — FDM, with up to 1.6 Gbps per channel, all transmitted by a single CMTS (cable modem termination system). Upstream there are multiple channels of up to 1 Gbps, divided into time slots — TDM. Some of those slots are assigned, and others are contended for by all users using random access with binary backoff. A downstream MAP frame tells the modems which upstream slots they've been assigned. FDM, TDM, and random access in one system.

Summary

Three families: channel partitioning by time, frequency, or code; random access (ALOHA, slotted ALOHA, CSMA, CSMA/CD), where carrier sensing is easy on wire and hard wirelessly; and taking turns via polling or token passing. In practice: CSMA/CD in Ethernet, CSMA/CA in 802.11, polling in Bluetooth, token passing in FDDI and token ring.

Exercises

To do before/around the next class:

Terms

Not a comprehensive reference — the textbook has much more — but these are the terms from Day 10 that will keep coming back.

IP hourglass / thin waist
The shape of the protocol stack: many application protocols above, many link and physical technologies below, and exactly one network-layer protocol (IP) in the middle that every device must implement.
Ethernet
The dominant wired LAN technology, from 10 Mbps to 400 Gbps. Full duplex via separate transmit and receive wires or fibers. Unreliable and connectionless; its MAC protocol is unslotted CSMA/CD with binary backoff.
collision domain
A set of nodes whose transmissions can collide with each other. On bus Ethernet the whole LAN was one domain; on switched Ethernet each link is its own.
Ethernet frame fields
Preamble (7 bytes of 10101010 plus the SFD 10101011, for clock synchronization), 6-byte destination and source MAC addresses, type (IPv4 = 0x0800, IPv6 = 0x86DD), payload (46 to 1500 bytes), and CRC. The NIC strips the preamble and CRC, so Wireshark doesn't show them.
MTU and MSS
Ethernet's 1500-byte maximum payload, minus a 20-byte IP header and a 20-byte TCP header, is where TCP's typical 1460-byte MSS comes from.
switch
A link-layer store-and-forward device that examines frames' MAC addresses and selectively forwards them. Transparent to hosts, plug-and-play, and self-learning.
switch table
Entries of (host MAC address, interface, timestamp) telling the switch where to send frames. Distinct from an ARP table.
self-learning
A switch records the source MAC address and arrival interface of every frame it receives, building its table as a side effect of forwarding, with no protocol required.
flooding
Forwarding a frame out every interface except the one it arrived on, used when the destination MAC address isn't in the switch table.
VLAN (Virtual LAN)
Grouping switch ports (or endpoint MAC addresses) so one physical switch operates as several virtual switches, giving traffic isolation and dynamic membership. Forwarding between VLANs requires routing.
MAC address
A 48-bit interface identifier in hex, burned into NIC ROM (though software-settable), administered by the IEEE with the first three octets identifying the manufacturer (OUI). Flat and portable — like a Social Security number, where an IP address is like a postal address.
ARP (Address Resolution Protocol)
Maps an IP address to a MAC address on a LAN. A broadcast query to FF-FF-FF-FF-FF-FF gets a unicast reply; requester and any listeners cache the mapping.
ARP table
Per-host <IP, MAC, TTL> entries, with a TTL typically around 20 minutes. Built automatically, never configured.
EDC (error detection and correction bits)
Redundant bits sent alongside data so the receiver can check consistency. Detection is never 100% reliable, and a larger EDC field buys better detection at the cost of bandwidth.
parity
Single-bit parity detects an odd number of bit errors. Two-dimensional parity (row and column bits) locates and therefore corrects a single-bit error, and detects but cannot correct two-bit errors.
CRC (Cyclic Redundancy Check)
The sender picks r check bits R so that <D,R> is divisible by a known generator G modulo 2; the receiver divides and looks for a non-zero remainder. Detects all burst errors shorter than r+1 bits. Used by Ethernet and 802.11.
multiple access protocol
A distributed algorithm determining when each node may transmit on a shared broadcast channel. All coordination must occur over the shared channel itself.
TDMA / FDMA
Channel partitioning by time slots or frequency bands, each assigned exclusively. Fair at high load, but unused slots and bands go idle even when other nodes have data.
slotted ALOHA
Random access with synchronized slots: transmit in the next slot, and on collision retry each subsequent slot with probability p. Maximum efficiency 1/e ≈ 37%.
pure ALOHA
Unsynchronized ALOHA — transmit on arrival. Simpler, but the vulnerable window doubles and efficiency drops to about 18%.
CSMA (Carrier Sense Multiple Access)
Listen before transmitting. Collisions still occur because propagation delay means a node may not yet hear a transmission that has already begun.
CSMA/CD
CSMA with collision detection: abort on detecting a collision, wasting only part of a frame time. Easy on wire, hard wirelessly (where 802.11 uses CSMA/CA instead).
jam signal
The signal an Ethernet node sends after aborting a transmission, ensuring all other nodes recognize that a collision occurred.
binary exponential backoff
After the mth collision, wait K × 512 bit times where K is drawn at random from {0, ..., 2m−1}. More collisions imply a busier channel, so the wait grows.
polling / token passing
"Taking turns" protocols. A controller invites nodes to transmit in turn (Bluetooth), or a token circulates and its holder may transmit (FDDI, token ring). Both add overhead and latency and have a single point of failure.
DOCSIS
The cable access standard, combining FDM across downstream and upstream frequency channels, TDM upstream with some slots assigned and some contended, and random access with binary backoff for requesting slots.

Credit: Most information on this page is from Computer Networking: A Top Down Approach", 9th edition by Kurose and Ross.
This page was generated by Claude from in-class slides.