Data link layer: framing and addressing
Framing puts packets into link-layer frames and addressing gives each network interface a MAC so nodes on a shared link find each other.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Frame boundaries and link addresses are what let two directly connected machines exchange packets reliably and efficiently. An engineer working on switches, NIC drivers, LAN protocols (Ethernet, IEEE 802.3, HDLC/PPP) or implementing ARQ and CSMA/CD must understand framing methods, MAC addressing, and minimum/maximum frame sizes to ensure correctness and performance.
Key ideas
Byte count: a fixed field in the header gives the payload length. Assumes the length field itself is received correctly; one must handle corruption of the count (e.g., duplicate bytes or resync policies).
Byte (character) stuffing / character framing: a special flag byte (e.g., ASCII 0x7E) delimits frames. If the flag byte appears in payload, insert an escape byte (e.g., 0x7D) and transform the byte. This is used in protocols like PPP in byte mode.
Bit stuffing: used when the link is a raw bit stream and a unique flag sequence (e.g., 01111110) marks frame boundaries. To prevent the flag from appearing in the payload, the sender inserts a 0 after any sequence of five consecutive 1 bits in the payload. The receiver removes stuffed 0s. This is used by HDLC.
Physical-layer coding violation: the physical layer uses illegal symbol patterns to indicate frame boundaries (less common in general LANs but used in some serial links).
Frame fields (typical): preamble (synchronization), start-of-frame delimiter (SFD), destination address, source address, type/length, payload, padding (to enforce minimum length), and FCS (frame check sequence, often CRC). Draw a rectangle labeled left-to-right with these fields; label lengths in bytes (see Ethernet below).
Frame Check Sequence (FCS): an error-detection code (commonly CRC-32 for Ethernet) computed over the frame header and payload. Receiver recomputes CRC and rejects frames with mismatch.
Link-layer address (MAC address): a 48-bit identifier assigned to each network interface (typically globally unique when factory-assigned), usually written as six hex byte pairs (e.g., 00:11:22:33:44:55). Define unicast (single destination MAC), broadcast (all-ones MAC, ff:ff:ff:ff:ff:ff), and multicast (addresses with least-significant bit of first octet = 1 for Ethernet; mapping from IP multicast to MAC is defined by standards). Note: in the first octet, the least-significant bit is the I/G (individual/group) bit; the next least-significant bit is the U/L (universally/local administered) bit. When U/L=1, the address is locally administered (not globally unique).
Ethernet (IEEE 802.3) frame structure (common version -- drawing required in answers): draw a horizontal bar showing, left to right: 7-byte Preamble (0x55 repeated) | 1-byte SFD (0xD5) | 6-byte Destination MAC | 6-byte Source MAC | 2-byte Type/Length | 46–1500 byte Payload | 4-byte FCS. Mention minimum frame size 64 bytes (from Destination MAC through FCS) and maximum payload 1500 bytes (unless jumbo frames supported). Note: if the 2-byte field is ≤ 1500 (0x05DC) it denotes length (IEEE 802.3 LLC); if ≥ 1536 (0x0600) it denotes EtherType. On the medium, Ethernet also enforces a 12-byte Interframe Gap (IFG) between frames. With IEEE 802.1Q VLAN tagging, a 4-byte tag (Ethertype 0x8100 + TCI + inner EtherType) is inserted after the Source MAC, increasing the maximum frame size on the wire to 1522 bytes (excluding preamble/SFD).
Minimum frame size and CSMA/CD: to guarantee collision detection, a transmitting station must still be transmitting when a collision that occurs at the far end can propagate back. The requirement is t_transmit >= 2·t_propagation. This yields a minimum frame size depending on link bandwidth and maximum network diameter. In classic Ethernet, the slot time is 512 bit times (51.2 µs at 10 Mb/s), which implies a 64-byte minimum frame (excluding preamble/SFD). On modern full-duplex switched Ethernet, CSMA/CD and the minimum-frame collision constraint do not apply.
Maximum Transmission Unit (MTU): largest payload a layer accepts (commonly 1500 bytes for Ethernet). If a network-layer packet is larger than MTU, it must be fragmented (IP) or dropped, depending on protocol.
Address resolution: on a LAN, the mapping between network-layer addresses (e.g., IPv4) and link-layer addresses is done by ARP (Address Resolution Protocol). ARP is a separate protocol but belongs to link-layer operations in practice. For IPv6, Neighbor Discovery (ND) replaces ARP.
HDLC / PPP framing: HDLC uses bit stuffing and flag 01111110; PPP uses 0x7E flags and is byte-stuffed with 0x7D on asynchronous links and bit-stuffed on synchronous links (RFC 1662). Both include address and control fields (often set to standard values) and an FCS (16-bit by default in PPP, 32-bit optional).
Assumptions and failure modes: framing assumes a reasonably reliable channel for control bytes/flags and powers of synchronization. A corrupted length field in byte-count framing can desynchronize the receiver until a resync strategy; bit/byte stuffing rely on exact removal of inserted bits/bytes and correct detection of flags.
Where an exam often asks for a diagram: draw an Ethernet frame as specified above and label sizes in bytes. For bit-stuffing, draw bit stream with flag (01111110) markers and show insertion of a 0 after five consecutive 1s in the payload.
Formulas
Efficiency = Payload_bytes / (Payload_bytes + Overhead_bytes)
- Payload_bytes: number of data bytes in frame (B)
- Overhead_bytes: headers, addresses, FCS, padding, preamble/SFD if counted (O)
- Unit: dimensionless fraction between 0 and 1
- Applies for computing fraction of bandwidth used for user data per frame.
t_transmit = Frame_bits / Bandwidth_bits_per_second
- Frame_bits: total bits transmitted (including header, payload, FCS)
- Bandwidth_bits_per_second: link rate in bits/s (e.g., 100e6 for 100 Mbps)
- t_transmit in seconds; used when comparing with propagation delay for collision detection.
Minimum_frame_bits >= 2 · t_propagation · Bandwidth_bits_per_second
- Gives minimum frame length required for CSMA/CD collision detection.
Frame_overhead_bytes (Ethernet canonical) = 14 (MAC header) + 4 (FCS) [+ 8 preamble/SFD if counted by designer] [+ 12 IFG on the medium if counted for on-the-wire efficiency]
- Use to compute efficiency and bytes on wire.
Note: Other specific CRC polynomials (e.g., Ethernet's CRC-32 polynomial 0x04C11DB7) are implementation details — verify polynomial if needed.
Worked examples
- Byte (character) stuffing example (PPP-like)
Problem: Frame payload bytes: [0x01, 0x7E, 0x20, 0x7D, 0x30]. Flag = 0x7E, Escape = 0x7D. When a flag or escape appears in payload, send 0x7D followed by byte XOR 0x20.
Solution steps:
- Start frame: send Flag (0x7E).
- Payload bytes processed left to right:
- 0x01 -> not special -> send 0x01
- 0x7E -> special (flag). Send 0x7D, then 0x7E XOR 0x20 = 0x5E
- 0x20 -> not special -> send 0x20
- 0x7D -> special (escape). Send 0x7D, then 0x7D XOR 0x20 = 0x5D
- 0x30 -> not special -> send 0x30
- End frame: send Flag (0x7E).
Resulting transmitted bytes: [0x7E, 0x01, 0x7D, 0x5E, 0x20, 0x7D, 0x5D, 0x30, 0x7E].
- Bit stuffing example (HDLC)
Problem: Bit-level payload to send between flags 01111110 and 01111110: payload = 011111101111110 (includes runs that would look like a flag without stuffing).
Solution steps:
- Put starting flag: 01111110
- Process payload bits, insert a 0 after any run of five consecutive 1 bits seen in the transmitted bit stream.
- Suppose payload has sequence: ...01111110... We encounter five 1s: we transmit 11111 then insert 0, then continue.
Illustration (transforming a short sample):
- Original payload bits: 1111101111110 (grouping runs)
- Transmit with stuffing: 1111100 11111010 (zeros inserted after each five 1s; after the first five 1s insert 0, then transmit the sixth 1 and the following 0)
- Wrap with flags: 01111110 [stuffed bits] 01111110
Receiver removes each 0 that follows five consecutive 1s.
- Minimum frame-size calculation for collision detection (numerical)
Problem: On a 10 Mbps Ethernet with a worst-case one-way propagation delay 25 μs, find minimum frame size in bytes (assume full-duplex not used; CSMA/CD applies).
Solution steps:
- Use condition t_transmit >= 2 · t_propagation.
- 2 · t_propagation = 2 · 25 μs = 50 μs.
- Bandwidth = 10 Mbps = 10·10^6 bits/s.
- Required bits = Bandwidth · 50 μs = 10e6 · 50e-6 = 500 bits.
- Bytes = 500 / 8 = 62.5 -> round up to 63 bytes; Ethernet standard minimum is 64 bytes (includes header+FCS). Final answer: 64 bytes.
(Exact numeric parameters like the 25 μs propagation should be checked against the network's maximum diameter used by your professor; I used 25 μs as an example.)
Common mistakes
- Forgetting preamble/SFD or counting them inconsistently when computing frame sizes.
- Using byte count framing without mentioning how corruption of the count desynchronizes the receiver.
- In bit-stuffing examples, inserting a 0 after five 0s instead of after five 1s (the rule is after five consecutive 1 bits for HDLC).
- Mixing up Ethernet Type field versus 802.3 Length field semantics.
- Ignoring padding: Ethernet payload must be at least 46 bytes — students sometimes forget to pad short payloads to reach minimum frame size.
- For CSMA/CD derivations, plugging in an incorrect propagation delay or forgetting the factor 2 for round-trip.
For your exam
Typical question types:
- Definitions: What is a frame? What is a MAC address? Explain unicast/broadcast/multicast.
- Short notes: Byte stuffing vs bit stuffing; Ethernet frame format; why minimum frame size exists for CSMA/CD.
- Derivations: Show t_transmit >= 2·t_propagation and derive minimum frame size for given bandwidth and propagation delay.
- Numericals: Perform byte/bit stuffing on small data, compute efficiency given header/payload sizes, compute frames per second given frame length and link speed.
- Diagrams: Draw an Ethernet frame and label fields with sizes; draw bit-stuffing process showing flags and stuffed 0s.
What full-marks answers include:
- Clear definitions with bold term usage (frame, MAC address, FCS, MTU).
- Correct diagrams labelled with field names and sizes (bytes) and a short note about preamble/SFD if asked.
- For derivations, state assumptions (e.g., maximum propagation delay used, whether preamble is counted), show step-by-step algebra, and give final numeric value with units and brief interpretation.
- For stuffing problems, show the original and resulting bit/byte streams with steps of where stuffing was applied and how it's removed.
Quick check
- What is the Ethernet minimum frame size (bytes) including header and FCS?
- In bit stuffing (HDLC), what bit pattern triggers insertion of a 0?
- Write the formula relating transmit time, propagation time and minimum frame size for CSMA/CD.
Answers: 1. 64 bytes (from Destination MAC through FCS; preamble/SFD often counted separately). 2. Five consecutive 1 bits (insert a 0 after any run of five 1s). 3. Minimum_frame_bits >= 2 · t_propagation · Bandwidth_bits_per_second.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?