The Data Link Layer

What the data link layer does

The physical layer can push bits onto a wire or into the air, but bits alone are useless: the receiver does not know where a message starts, whether noise flipped some bits, or who the message is for. The data link layer (layer 2) turns a raw bit pipe into a usable link between two directly connected devices. Its unit of data is the frame.

Its jobs, in order of how often interviewers ask about them:

1. Framing: marking where each frame begins and ends.
2. Error detection (and sometimes correction): noticing corrupted frames with parity, checksums or CRC.
3. Addressing: using MAC addresses to say which device on the link should take the frame.
4. Media access control: deciding who may transmit when many devices share one medium (ALOHA, CSMA/CD, CSMA/CA).
5. Flow control: stopping a fast sender from overrunning a slow receiver (on some links).

It also covers the devices and protocols that live here: Ethernet, switches and their MAC tables, ARP, VLANs, spanning tree and Wi-Fi. This is a calculation-heavy topic in exams and interviews. Expect to divide by a CRC generator, build a Hamming codeword, compute ALOHA throughput or a minimum Ethernet frame size. Every number in this lesson has been checked with a script.

Remember the scope from the OSI lesson: layer 2 is hop to hop. A frame only ever crosses one link (or one LAN); a router strips it and builds a new one.

Framing

The receiver sees a continuous stream of bits. Framing is how the sender marks frame boundaries so the receiver can split the stream back into frames. Four methods exist.

1. Character (byte) count

The header starts with the number of bytes in the frame. Simple, but fragile: if noise corrupts the count, the receiver loses track of every later boundary and cannot resynchronise. It is rarely used alone.

2. Flag bytes with byte stuffing

Each frame starts and ends with a special flag byte. PPP (Point-to-Point Protocol) uses 0x7E. Problem: what if the data itself contains 0x7E? The sender inserts an escape byte (0x7D in PPP) before it, and the receiver removes escapes. In PPP the escaped byte is also XORed with 0x20, so 0x7E in data is sent as 0x7D 0x5E, and 0x7D in data is sent as 0x7D 0x5D.

data:   41 7E 42 7D 43
sent:   7E | 41 7D 5E 42 7D 5D 43 | 7E
        flag          payload         flag

The cost is that frames grow when data contains many flag or escape bytes.

3. Flag bits with bit stuffing

HDLC uses the bit pattern 01111110 as a flag. To keep that pattern out of the data, the sender applies bit stuffing: after any five consecutive 1s in the data, it inserts a 0. The receiver deletes any 0 that follows five 1s. Now six 1s in a row can only mean a flag.

Worked example. Stuff the data 0111111011111001.

1. Read 0, then five 1s (11111): output them and insert 0.
2. Next data bit is 1 (the sixth 1 of the original run): output it; the count restarts.
3. Next 0, then five 1s again: output and insert 0.
4. Output the rest: 001.

data:    0 11111   1 0 11111   001
sent:    0 11111 0 1 0 11111 0 001
result:  011111010111110001   (16 bits became 18)

4. Physical layer coding violations

Some line codes have signal patterns that never occur in data (for example invalid symbols in 4B/5B encoding). These can mark frame boundaries without stuffing. Fast Ethernet uses this.

Real Ethernet uses a preamble (7 bytes of 10101010) followed by a start frame delimiter 10101011 to mark the start, and a gap of silence (the inter-frame gap) after the end.

Error detection

Noise, interference and weak signals flip bits. Error detection adds redundant bits computed from the data; the receiver recomputes them and compares. A mismatch means an error. Error detection says "something is wrong" but not where, so the frame is discarded (and maybe retransmitted). Error correction adds enough redundancy to also find and fix the flipped bits.

Terms:

• Single-bit error: exactly one bit flipped.
• Burst error of length L: the first and last flipped bits are L positions apart (bits in between may or may not be flipped). Bursts are common because noise lasts longer than one bit time.
• Hamming distance between two codewords: the number of bit positions where they differ. 10110 and 11100 have distance 2. If the minimum distance between any two valid codewords is d, the code detects up to d - 1 errors and corrects up to (d - 1) / 2 (rounded down).

Simple parity

Add one parity bit so the total number of 1s is even (even parity) or odd (odd parity).

Example with even parity: data 1011001 has four 1s, so the parity bit is 0 and 10110010 is sent. If one bit flips, the count becomes odd and the error is detected.

Limit: any even number of flipped bits leaves the parity unchanged, so 2-bit errors go unnoticed. Minimum distance is 2, so it detects 1 error and corrects none.

Two-dimensional parity

Arrange data in a grid; add a parity bit to each row and each column (plus a corner bit). A single flipped bit causes exactly one row and one column to fail. Their intersection pinpoints the bit, so a single-bit error can be corrected.

Worked example (even parity). Data is four rows of four bits.

          c1 c2 c3 c4 | row parity
  row 1:   1  0  1  1 |  1
  row 2:   0  1  1  0 |  0
  row 3:   1  1  1  0 |  1
  row 4:   0  0  1  0 |  1
  ------------------------------
  col par: 0  0  0  1 |  1   <- corner

Check: row 1 has three 1s, so parity 1. Column 3 has four 1s, so parity 0. Column 4 has one 1, so parity 1. The corner is the parity of the row parities (1+0+1+1 = 3, odd, so 1), which equals the parity of the column parities (0+0+0+1 = 1).

Now the bit at row 2, column 3 flips from 1 to 0. The receiver sees row 2 = 0100 with parity bit 0: one 1, odd, row 2 fails. Column 3 = 1, 0, 1, 1 with parity 0: three 1s, odd, column 3 fails. The error is at (row 2, column 3); flip it back.

Two-dimensional parity detects all 1-, 2- and 3-bit errors, but some 4-bit errors placed at the corners of a rectangle cancel out and go undetected.

Checksum

A checksum treats the data as a sequence of numbers and adds them up. The Internet checksum, used in the IPv4 header, UDP and TCP, works on 16-bit words:

1. Add all 16-bit words using ones' complement arithmetic: any carry out of the top bit is wrapped around and added back to the bottom.
2. The checksum is the ones' complement (bit inversion) of the sum.
3. The receiver adds all words including the checksum. If the result is 0xFFFF (all 1s), no error was detected.

Worked example. Data words: 0x4A3C, 0x9B21, 0xE007, 0x1234.

  0x4A3C
+ 0x9B21  = 0xE55D
+ 0xE007  = 0x1C564   (17 bits: carry out)
+ 0x1234  = 0x1D798
fold carry: 0xD798 + 0x1 = 0xD799
checksum  = NOT 0xD799 = 0x2866

Receiver check: 0x4A3C + 0x9B21 + 0xE007 + 0x1234 + 0x2866, folded, gives 0xFFFF. Valid.

Checksums are cheap in software, which is why higher layers use them. They are weaker than CRC: for example, swapping two 16-bit words does not change the sum. That is acceptable because the link layer below has already run a CRC.

Cyclic redundancy check (CRC)

CRC is the workhorse of link-layer error detection. Ethernet and Wi-Fi both use CRC-32. The idea is polynomial division with modulo-2 arithmetic, where addition and subtraction are both XOR and there are no carries or borrows.

Treat bit strings as polynomials: 10011 means x^4 + x + 1. Sender and receiver agree on a generator polynomial G of degree r (so G has r + 1 bits).

Sender steps:

1. Append r zero bits to the data.
2. Divide this by G using modulo-2 division.
3. The remainder has r bits. Replace the appended zeros with the remainder. This is the transmitted frame, and it is exactly divisible by G.

Receiver: divide the received frame by G. Remainder zero means no error detected; non-zero means error.

Worked example: CRC division

Data D = 1101011011, generator G = 10011 (x^4 + x + 1, degree r = 4).

Step 1. Append four zeros: 11010110110000.

Step 2. Divide by 10011. At each step look at the current 5-bit window. If its leading bit is 1, XOR with 10011 (quotient bit 1). If it is 0, XOR with 00000 (quotient bit 0). Drop the leading bit and bring down the next bit of the dividend.

dividend: 1101011011 0000      divisor: 10011

  window   XOR with   result   quotient bit
  11010    10011      01001    1
  10011    10011      00000    1
  00001    00000      00001    0
  00010    00000      00010    0
  00101    00000      00101    0
  01011    00000      01011    0
  10110    10011      00101    1
  01010    00000      01010    0
  10100    10011      00111    1
  01110    00000      01110    0

quotient  = 1100001010
remainder = last 4 bits = 1110

How each window forms: take the result, drop its first bit, and append the next dividend bit. For example, the first result 01001 becomes 1001, and appending the 6th dividend bit 1 gives 10011.

Step 3. Transmit D followed by the remainder: 1101011011 1110.

Receiver, no error. Dividing 11010110111110 by 10011 gives remainder 0000. Accept.

Receiver, one bit flipped (the 4th bit, giving 11000110111110): the remainder is 0111, non-zero, so the error is detected.

You can verify this in Python:

def crc_remainder(bits: str, gen: str) -> str:
    r = len(gen) - 1
    buf = list(bits + "0" * r)
    for i in range(len(bits)):
        if buf[i] == "1":
            for j, g in enumerate(gen):
                buf[i + j] = "1" if buf[i + j] != g else "0"
    return "".join(buf[-r:])

def crc_check(frame: str, gen: str) -> str:
    r = len(gen) - 1
    buf = list(frame)
    for i in range(len(frame) - r):
        if buf[i] == "1":
            for j, g in enumerate(gen):
                buf[i + j] = "1" if buf[i + j] != g else "0"
    return "".join(buf[-r:])

rem = crc_remainder("1101011011", "10011")
print(rem)                                   # 1110
print(crc_check("1101011011" + rem, "10011"))  # 0000
print(crc_check("11000110111110", "10011"))    # 0111 -> error

What CRC can detect

With a well-chosen generator of degree r, CRC detects:

• All single-bit errors (if G has at least two terms).
• All double-bit errors, for frames up to a length that depends on G.
• Any odd number of errors, if G has x + 1 as a factor.
• All burst errors of length r or less. Longer bursts slip through with probability about 1 / 2^r.

CRC-32 (r = 32) therefore catches every burst up to 32 bits. CRC is also very fast in hardware: it is just a shift register with a few XOR gates.

Error correction: Hamming code

Retransmission is not always possible (deep-space links, memory chips, one-way broadcasts). Forward error correction (FEC) adds enough redundancy to fix errors at the receiver. The Hamming code is the classic single-error-correcting code and a common exam topic.

How many parity bits?

With m data bits and r parity bits, the r parity checks give 2^r possible results. They must name every one of the m + r positions where a single error could be, plus "no error":

2^r >= m + r + 1

Placing the bits

Number the codeword positions from 1. Parity bits go at the powers of two (1, 2, 4, 8, ...); data bits fill the rest. Parity bit at position p checks every position whose binary number has the p bit set:

• p1 checks positions 1, 3, 5, 7 (binary ends in 1).
• p2 checks positions 2, 3, 6, 7.
• p4 checks positions 4, 5, 6, 7.

Worked example: Hamming(7,4)

Encode data 1011 with even parity.

Step 1. Place data at positions 3, 5, 6, 7:

position:  1   2   3   4   5   6   7
bit:       p1  p2  1   p4  0   1   1

Step 2. Compute parity bits (even parity).

• p1 covers 3, 5, 7: bits 1, 0, 1. Two 1s, so p1 = 0.
• p2 covers 3, 6, 7: bits 1, 1, 1. Three 1s, so p2 = 1.
• p4 covers 5, 6, 7: bits 0, 1, 1. Two 1s, so p4 = 0.

Step 3. Codeword: 0110011.

Step 4: an error. Position 6 flips during transmission. Received: 0110001.

Step 5: receiver recomputes checks (including the parity bit itself):

• Check 1 (positions 1, 3, 5, 7): 0, 1, 0, 1. Even, result 0.
• Check 2 (positions 2, 3, 6, 7): 1, 1, 0, 1. Odd, result 1.
• Check 4 (positions 4, 5, 6, 7): 0, 0, 0, 1. Odd, result 1.

Step 6. Read the results as a binary number, check 4 as the high bit: 110 = 6. The error is at position 6. Flip it back to get 0110011, and extract data bits 3, 5, 6, 7: 1011.

A syndrome of 0 means no error. Hamming(7,4) has minimum distance 3: it corrects 1 error or detects 2 (but not both at once). Adding one overall parity bit gives SECDED (single error correct, double error detect), used in ECC memory.

Flow control at the data link layer

Flow control prevents a fast sender from overflowing a slow receiver's buffer. The receiver gives feedback that limits the sender. Two schemes appear at this layer (and again, in more detail, in the transport lesson).

Stop-and-wait

The sender sends one frame and waits for an acknowledgement (ACK) before sending the next. If an ACK does not arrive within a timeout, it resends. Frames carry a 1-bit sequence number (0, 1, 0, 1...) so the receiver can spot duplicates when an ACK is lost.

Its efficiency depends on a, the ratio of propagation delay to transmission delay:

a = Tp / Tt        efficiency = Tt / (Tt + 2Tp) = 1 / (1 + 2a)

Worked example. Frames of 1,000 bits on a 1 Mbps link, one-way propagation 20 ms.

• Tt = 1,000 / 10^6 = 1 ms. Tp = 20 ms. So a = 20.
• Efficiency = 1 / (1 + 40) = 1/41 ≈ 2.44%.

The sender is idle about 97.6% of the time, waiting for ACKs.

Sliding window

The sender may have up to W unacknowledged frames outstanding. While ACKs travel back, it keeps sending. If W frames take at least one round trip to send, the link stays busy:

efficiency = min(1, W / (1 + 2a))

Same link: to reach 100% you need W >= 1 + 2a = 41 frames. With W = 7: efficiency = 7/41 ≈ 17.1%.

The two error-recovery flavours are Go-Back-N (on loss, resend from the lost frame onward) and Selective Repeat (resend only the lost frame). They are worked in detail in the transport lesson. Ethernet itself does no retransmission: a corrupted frame is simply dropped, and TCP recovers. HDLC and Wi-Fi do use link-level ACKs.

MAC addresses

A MAC address (media access control address) is a 48-bit identifier for a network interface, written as six hex bytes: 3c:22:fb:1a:9e:07.

• The first 3 bytes are the OUI (organisationally unique identifier), assigned by IEEE to a manufacturer. The last 3 bytes are chosen by the manufacturer.
• Bit 0 of the first byte (the least significant bit) is the I/G bit: 0 for unicast, 1 for multicast/group.
• Bit 1 of the first byte is the U/L bit: 0 for a globally unique (burned-in) address, 1 for a locally administered one. Phones generate random, locally administered MACs for Wi-Fi privacy, so the "MAC is permanent" idea is no longer true in practice.
• ff:ff:ff:ff:ff:ff is the broadcast address.

Why have both? MAC addresses are flat, like a national ID number: unique but saying nothing about location. Routers could never keep a table of billions of flat addresses. IP addresses are hierarchical, like a postal address, so routers keep one entry per network instead of per device.

The Ethernet frame

Ethernet (IEEE 802.3) is the dominant wired LAN. The Ethernet II frame format:

+----------+-----+------+------+------+-------------+-----+
| Preamble | SFD | Dest | Src  | Type | Payload     | FCS |
|    7     |  1  |  6   |  6   |  2   | 46 to 1500  |  4  |
+----------+-----+------+------+------+-------------+-----+
  bytes     (physical layer)  |<---- frame: 64 to 1518 ---->|

• Preamble (7 bytes) of alternating 1s and 0s lets the receiver lock onto the clock. SFD (1 byte), 10101011, marks the start of the frame. Both are usually treated as physical layer and are not counted in frame size.
• Destination MAC (6) comes first so a switch can start its lookup as early as possible.
• Source MAC (6).
• Type (2): the EtherType, naming the payload protocol: 0x0800 IPv4, 0x86DD IPv6, 0x0806 ARP, 0x8100 VLAN tag. In the older IEEE 802.3 format this field held a length; values of 1,500 or less mean length, values of 1,536 (0x0600) or more mean type.
• Payload (46 to 1,500 bytes). If the data is shorter than 46 bytes, padding is added. The 1,500-byte maximum is the Ethernet MTU.
• FCS (4): CRC-32 over destination, source, type and payload.

So a frame is between 64 and 1,518 bytes (1,522 with an 802.1Q VLAN tag). Data centres often enable jumbo frames of about 9,000 bytes to reduce per-frame overhead.

Why a 64-byte minimum?

On shared half-duplex Ethernet, a sender must still be transmitting when news of a collision gets back to it, or it will not know its frame was damaged. The frame must last at least one round-trip propagation time across the largest network. At 10 Mbps, the 512-bit (64-byte) minimum covers a 51.2 µs slot time, the worst-case round trip in a maximum-size classic Ethernet. More on this under CSMA/CD.

ARP: finding a MAC address

To send an IP packet across the LAN, a host must put a destination MAC in the frame. ARP (Address Resolution Protocol) finds the MAC that belongs to an IP address on the same network. Each host keeps an ARP cache of recent answers, with entries expiring after a timeout (tens of seconds to minutes, depending on the operating system).

Worked example: ARP step by step

Host A (192.168.1.10, MAC aa:aa:aa:aa:aa:01) wants to send to host B (192.168.1.20, MAC bb:bb:bb:bb:bb:02) on the same /24 network. A's ARP cache is empty.

1. Is B local? A compares B's network (using its subnet mask 255.255.255.0) with its own. Both are 192.168.1.0, so B is on the same LAN. (If not, A would ARP for the default gateway's IP instead.)
2. Cache lookup. No entry for 192.168.1.20.
3. ARP request (broadcast). A sends a frame to ff:ff:ff:ff:ff:ff with EtherType 0x0806: "Who has 192.168.1.20? Tell 192.168.1.10 (aa:..:01)." The packet's target MAC field is all zeros because it is unknown.
4. Everyone receives it. The switch floods the broadcast out every port. Every host reads it. Those whose IP is not 192.168.1.20 ignore it.
5. B learns A. B stores A's IP-to-MAC mapping from the request (so it will not need to ARP when replying).
6. ARP reply (unicast). B sends directly to aa:..:01: "192.168.1.20 is at bb:..:02."
7. A caches and sends. A stores the mapping and sends its queued IP packet in a frame addressed to bb:..:02.

 A                          Switch                         B
 |-- ARP req (bcast) ---------->|---- flood to all ports -->|
 |   who has .20? tell .10      |                           |
 |<------------------------------------ ARP reply (unicast)-|
 |   .20 is at bb:..:02                                     |
 |-- IP packet in frame to bb:..:02 ----------------------->|

Off-subnet destinations

If A sends to 8.8.8.8, it does not ARP for 8.8.8.8. It ARPs for its default gateway, say 192.168.1.1, and sends the frame to the router's MAC with 8.8.8.8 still in the IP header.

Related variants and risks

• Gratuitous ARP: a host announces its own IP-to-MAC mapping unprompted, for example at boot or after a failover. It updates other caches and helps detect duplicate IPs.
• Proxy ARP: a router answers ARP requests on behalf of hosts on another network.
• RARP: the old reverse protocol (MAC to IP), replaced by BOOTP and then DHCP.
• ARP spoofing (poisoning): ARP has no authentication, so an attacker can send fake replies ("the gateway's IP is at my MAC") and intercept traffic. Defences include dynamic ARP inspection on switches and static entries for critical hosts.
• In IPv6, ARP is replaced by Neighbor Discovery (ICMPv6 over multicast).

Switches and MAC learning

A switch forwards frames only where they need to go. It builds a MAC address table (also called the CAM table, or forwarding table) automatically, a process called backward learning.

For every frame:

1. Learn: record (source MAC, incoming port, time). The sender must live on that port.
2. Look up the destination MAC:
   • Known, different port: forward out that port only (filtering everything else).
   • Known, same port as it arrived on: drop the frame (sender and receiver are on the same segment).
   • Unknown, or broadcast/multicast: flood out all ports except the incoming one.
3. Age: entries that are not refreshed expire (300 seconds by default on many switches), so moved devices are relearned.

Worked example: a switch learns

A 4-port switch has hosts A on port 1, B on port 2, C on port 3, D on port 4. The table starts empty.

After a few frames, the switch knows everyone and stops flooding unicast.

Switching methods

• Store-and-forward: receive the whole frame, check the FCS, then forward. Drops corrupted frames. The default on most switches.
• Cut-through: start forwarding as soon as the destination MAC (first 6 bytes after the preamble) is read. Lowest latency, but forwards corrupted frames.
• Fragment-free: wait for the first 64 bytes (collisions happen within them), then forward.

MAC flooding attack: an attacker sends frames with thousands of fake source MACs to fill the table. When it is full, some switches flood all unknown unicast, letting the attacker sniff traffic. Port security limits MACs per port.

VLANs

By default, all ports on a switch are one broadcast domain: an ARP or DHCP broadcast reaches every host. A VLAN (virtual LAN) splits one physical switch into several logical ones. Ports in VLAN 10 (say, Engineering) cannot exchange frames directly with ports in VLAN 20 (Finance); they need a router or layer 3 switch.

Why VLANs:

• Smaller broadcast domains, so less broadcast noise.
• Security and isolation: guests cannot reach internal servers at layer 2.
• Flexibility: group users by role, not by which floor their desk is on.

Access and trunk ports

• An access port belongs to one VLAN and connects an ordinary host. Frames are untagged.
• A trunk port carries many VLANs between switches (or to a router). Frames carry an IEEE 802.1Q tag: 4 bytes inserted after the source MAC, with TPID 0x8100 and a 12-bit VLAN ID (so 4,094 usable VLANs: IDs 1 to 4094), plus a 3-bit priority field.

untagged: | Dest | Src |             Type | Payload | FCS |
tagged:   | Dest | Src | 8100 | TCI | Type | Payload | FCS |
                         4-byte 802.1Q tag
                   TCI = 3-bit priority, 1-bit DEI, 12-bit VLAN ID

The trunk's native VLAN carries untagged frames. Inter-VLAN routing is done by a router with one sub-interface per VLAN ("router on a stick") or, more commonly today, by a layer 3 switch.

Spanning tree in brief

Redundant links between switches protect against a cable failure, but they create loops. Ethernet frames have no TTL, so a broadcast caught in a loop circulates forever and multiplies (a broadcast storm), and MAC tables flap as the same source appears on different ports. The network melts down within seconds.

The Spanning Tree Protocol (STP, IEEE 802.1D) fixes this by blocking just enough ports to leave a loop-free tree:

1. Switches exchange BPDUs (bridge protocol data units) and elect a root bridge: the one with the lowest bridge ID (priority, then MAC).
2. Every other switch picks its root port: the port with the lowest path cost to the root.
3. Each segment picks one designated port to forward towards the root.
4. All other ports are blocked. If a link fails, blocked ports can be unblocked.

        [S1 root]
        /       \
     [S2]-------[S3]
        X  <- one port on the S2-S3 link is blocked

Classic STP takes 30 to 50 seconds to converge. RSTP (802.1w) cuts this to about a second or less. Data-centre networks often avoid STP entirely with routed (layer 3) designs.

Media access control: sharing one channel

On a shared medium (old bus Ethernet, all Wi-Fi), two transmissions at once collide and both are garbled. Multiple access protocols decide who sends when. Three families exist:

• Channel partitioning: split the channel (TDMA, FDMA, CDMA). Fair and collision-free but wasteful when few stations are active.
• Random access: transmit when you have data; recover from collisions. ALOHA, CSMA, CSMA/CD, CSMA/CA.
• Taking turns: polling or token passing. No collisions, but the master or token is a single point of failure and adds delay.

Pure ALOHA

Developed at the University of Hawaii around 1970. A station sends whenever it has a frame. If no ACK arrives, it waits a random time and resends.

Let T be the frame time and G the average number of transmission attempts per frame time (offered load). A frame sent at time t collides with any other frame starting in (t - T, t + T), a vulnerable period of 2T. With Poisson arrivals, the throughput (successful frames per frame time) is:

S = G × e^(-2G)        maximum at G = 0.5:  S = 1/(2e) ≈ 0.184

So at best about 18.4% of the channel carries useful frames.

Slotted ALOHA

Time is divided into slots of length T; stations may only start at slot boundaries. Frames now collide only if they start in the same slot, so the vulnerable period is T:

S = G × e^(-G)         maximum at G = 1:    S = 1/e ≈ 0.368

Slotting doubles the best-case throughput to about 36.8%, at the cost of clock synchronisation.

Worked example: ALOHA throughput

A shared channel runs at 200 kbps and frames are 200 bits, so frame time T = 1 ms and the channel can carry at most 1,000 frames per second. All stations together generate the loads below. How many frames per second succeed?

Pure ALOHA peaks at G = 0.5 (184 frames/s); slotted peaks at G = 1 (368 frames/s). Beyond the peak, more traffic means less throughput, because collisions dominate.

CSMA: listen before talking

Carrier sense multiple access (CSMA): a station listens to the channel first and transmits only if it is idle. Variants differ in what happens when the channel is busy:

• 1-persistent: keep listening; transmit immediately when it goes idle. Classic Ethernet. If two stations are waiting, they collide for sure.
• Non-persistent: if busy, wait a random time and sense again. Fewer collisions, more delay.
• p-persistent (slotted channels): when idle, transmit with probability p, otherwise wait one slot and repeat.

Collisions still happen because of propagation delay: station B may not yet hear A's signal when B senses the channel.

CSMA/CD: collision detection (classic Ethernet)

On a wire, a station can listen while transmitting. CSMA/CD adds:

1. Sense the channel; if idle, transmit (1-persistent).
2. While transmitting, compare what is on the wire with what you sent. If they differ, a collision happened.
3. On collision, stop and send a 32-bit jam signal so everyone notices.
4. Binary exponential backoff: after the n-th collision, pick K at random from 0 to 2^m - 1 where m = min(n, 10), and wait K × 512 bit times. Give up after 16 attempts.

For collision detection to work, the sender must still be transmitting when the collision news returns. The worst case is when the far station starts just before A's first bit reaches it, so the news takes a full round trip:

Tt >= 2 × Tp      so      minimum frame size L_min = 2 × Tp × R

Worked example. A 10 Mbps bus is 2 km long, signal speed 2 × 10^8 m/s.

1. Tp = 2,000 / (2 × 10^8) = 10 µs.
2. L_min = 2 × 10 µs × 10^7 bit/s = 200 bits.

Worked example: why gigabit could not keep 64 bytes. With 512-bit frames at 1 Gbps, Tt = 0.512 µs, so 2Tp must be at most 0.512 µs, which gives a maximum length of 0.256 µs × 2 × 10^8 m/s = 51.2 m. Too short, so half-duplex gigabit used "carrier extension". In practice, modern Ethernet is full duplex on switched links, with a dedicated wire pair each way, so there are no collisions and CSMA/CD is effectively unused.

CSMA/CA: collision avoidance (Wi-Fi)

Wi-Fi cannot use collision detection:

• A radio's own transmission is millions of times stronger than a faraway signal at its antenna, so it cannot hear a collision while sending.
• The hidden terminal problem: A and C both reach the access point B but cannot hear each other (distance or a wall). Both sense "idle" and transmit; their frames collide at B.

   (A) ----range---- (B: AP) ----range---- (C)
    A and C cannot hear each other, both reach B

So 802.11 tries to avoid collisions and uses ACKs to learn about them:

1. Sense the channel. If idle for a DIFS (distributed inter-frame space), continue.
2. Choose a random backoff counter from the contention window. Count down only while the channel is idle; freeze while busy.
3. Transmit the whole frame when the counter hits zero.
4. The receiver waits a short SIFS and sends an ACK. No ACK means assume collision: double the contention window and retry.

Optional RTS/CTS (request to send / clear to send) handles hidden terminals: the sender sends a short RTS; the access point replies CTS, which every station in range of the AP hears (including hidden ones). They set their NAV (network allocation vector), a timer of how long to stay silent. Collisions now only waste tiny RTS frames.

Wi-Fi basics

• Architecture: stations associate with an access point (AP); a group of them forms a BSS (basic service set), named by an SSID. Ad hoc mode connects stations directly.
• Joining: the station scans (APs send periodic beacon frames, or the station sends probe requests), then authenticates and associates. WPA2 or WPA3 then derive encryption keys with a four-way handshake.
• Frames carry up to four MAC addresses because the wireless sender, wireless receiver, original source and final destination can all differ (for example when the AP bridges to a wired router).
• Bands: 2.4 GHz (longer range, crowded, few non-overlapping channels), 5 GHz and, with Wi-Fi 6E and 7, 6 GHz (more channels, shorter range).
• Generations: 802.11n (Wi-Fi 4), 802.11ac (Wi-Fi 5), 802.11ax (Wi-Fi 6/6E), 802.11be (Wi-Fi 7). Advertised speeds are shared air capacity, not per-device throughput.

Interview questions

Q1. What are the main responsibilities of the data link layer?

Framing, physical (MAC) addressing, error detection with CRC, media access control on shared channels, and on some links flow control and retransmission. It provides reliable or at least error-checked delivery across a single hop, not end to end.

Q2. What is bit stuffing and why is it needed?

When a flag pattern like 01111110 marks frame boundaries, the same pattern could appear in data. The sender inserts a 0 after every five consecutive 1s, and the receiver removes it, so six 1s in a row can only be a flag. Byte stuffing does the same with an escape byte for byte-oriented protocols like PPP.

Q3. Compute the CRC for data 1101011011 with generator 10011.

The generator has degree 4, so append four zeros and divide 11010110110000 by 10011 with modulo-2 (XOR) division. The remainder is 1110, so the sender transmits 11010110111110. The receiver divides by 10011 and gets zero if there was no error.

Q4. Why is CRC preferred over a simple checksum at the link layer?

CRC detects all burst errors up to the generator's degree and is very cheap in hardware with a shift register. Simple sums miss some patterns, like reordered words. Link noise tends to come in bursts, which CRC handles well.

Q5. How many parity bits are needed for a Hamming code with 7 data bits?

We need the smallest r with 2^r >= m + r + 1. For m = 7, r = 4 gives 16 >= 12, while r = 3 gives 8, which is less than 11. So 4 parity bits and an 11-bit codeword.

Q6. Explain ARP. What happens if the destination is on another network?

ARP maps an IP address to a MAC address on the local link: a broadcast request asks who owns the IP, and the owner replies with a unicast. For a destination on another network the host ARPs for its default gateway instead and sends the frame to the router's MAC, keeping the final destination in the IP header.

Q7. How does a switch learn MAC addresses?

It reads the source MAC of each incoming frame and records that MAC against the incoming port, refreshing a timer. To forward, it looks up the destination MAC: known means send out one port, unknown or broadcast means flood all other ports. Entries age out so moved devices are relearned.

Q8. What is the purpose of the minimum Ethernet frame size?

In half-duplex CSMA/CD, a sender must still be transmitting when a collision at the far end propagates back, so the frame's transmission time must be at least twice the propagation delay. For 10 Mbps Ethernet this gave 512 bits (64 bytes). Shorter data is padded.

Q9. Compare pure and slotted ALOHA.

Pure ALOHA lets stations send any time, so the vulnerable period is two frame times and peak throughput is 1/(2e), about 18.4%, at G = 0.5. Slotted ALOHA aligns transmissions to slots, halving the vulnerable period and doubling peak throughput to 1/e, about 36.8%, at G = 1. Slotted needs time synchronisation.

Q10. Why does Wi-Fi use CSMA/CA rather than CSMA/CD?

A wireless station cannot detect collisions while transmitting because its own signal drowns out others, and hidden terminals may collide at the receiver without hearing each other. So 802.11 avoids collisions with random backoff, confirms delivery with link-layer ACKs, and can use RTS/CTS.

Q11. What is a VLAN and how do frames carry VLAN information between switches?

A VLAN splits one switch into multiple broadcast domains. Between switches, trunk links carry frames with a 4-byte 802.1Q tag holding a 12-bit VLAN ID. Hosts on access ports send untagged frames, and traffic between VLANs needs a router or layer 3 switch.

Q12. Why do we need the Spanning Tree Protocol?

Redundant switch links create loops, and Ethernet frames have no TTL, so broadcasts loop forever and multiply into a broadcast storm. STP elects a root bridge and blocks redundant ports to form a loop-free tree, unblocking them if an active link fails.

Q13. What is ARP spoofing and how is it prevented?

An attacker sends forged ARP replies that map a victim IP (often the gateway) to the attacker's MAC, so traffic flows through the attacker. It works because ARP has no authentication. Defences are dynamic ARP inspection on switches, static ARP entries for critical hosts, and end-to-end encryption such as TLS.

Q14. What is the efficiency of stop-and-wait when propagation delay is 20 times the transmission time?

Efficiency is 1/(1 + 2a) with a = 20, so 1/41, about 2.4%. A sliding window of at least 41 frames would keep the link fully busy.

Q15. Store-and-forward vs cut-through switching?

Store-and-forward receives the whole frame and checks its CRC before forwarding, dropping corrupted frames at the cost of latency proportional to frame size. Cut-through starts forwarding once it reads the destination MAC, minimising latency but passing on corrupted frames. Fragment-free is a middle ground that waits for the first 64 bytes.

Key takeaways

• The data link layer delivers frames across one hop: framing, MAC addressing, error detection, media access, sometimes flow control.
• Framing uses byte counts, flag bytes with byte stuffing, flag bits with bit stuffing (insert 0 after five 1s), or coding violations.
• Parity detects odd numbers of errors; 2D parity corrects single errors; the Internet checksum is ones' complement sum; CRC is modulo-2 division and catches every burst up to its degree.
• Hamming codes need 2^r >= m + r + 1 parity bits; the syndrome gives the error position.
• Ethernet frames are 64 to 1,518 bytes, with a 1,500-byte MTU, EtherType field and CRC-32 FCS.
• ARP broadcasts a request and gets a unicast reply; off-subnet traffic goes to the gateway's MAC.
• Switches learn source MACs, forward known destinations, flood unknown ones; VLANs split broadcast domains; STP prevents loops.
• Pure ALOHA peaks at 18.4%, slotted at 36.8%; CSMA/CD needs frames at least 2 × Tp × R bits; Wi-Fi uses CSMA/CA with ACKs and RTS/CTS.

Next lesson

Continue with IP addressing and subnetting.