COMP90007 Chap.3 Framing, Errors and Reliable Delivery
Framing, Errors and Reliable Delivery
The data-link layer needs to decide where a frame begins and ends, whether its bits are plausible, and what to do when delivery is incomplete. Character count uses a length field but can lose synchronisation if that field is corrupted. Flag bytes and byte stuffing reserve a boundary value while escaping it inside data. Bit stuffing performs the same logical separation at the bit level. Error control then adds redundancy.
A parity bit catches any odd number of flips but cannot locate the error. An Internet checksum sums fixed-width words with end-around carry and complements the result. CRC uses a generator polynomial and modulo-two division so the transmitted polynomial is divisible by the generator.
Hamming distance provides the general guarantee: distance must exceed the error count for detection and exceed twice the error count for correction. Reliable delivery adds acknowledgements, timeouts and sequence numbers. Stop-and-Wait is simple but leaves a long-delay path idle. Go-Back-N and Selective Repeat pipeline frames, trading retransmission volume against receiver buffering.
What this chapter covers
- 01
Byte stuffing
- 02
Automatic Repeat reQuest
- 03
Selective Repeat
- 04
Character counts, flag bytes and byte stuffing
- 05
Bit flags and bit stuffing
- 06
Parity, checksum and CRC
- 07
Hamming distance and correction capacity
- 08
Acknowledgements, timeouts and sequence numbers
- 09
Stop-and-Wait, Go-Back-N and Selective Repeat
Read a Hamming-distance guarantee
- 1For guaranteed detection of d errors, the minimum distance must be at least d plus one.
- 1Distance five therefore guarantees detection of up to four bit errors.
- 1For guaranteed correction of d errors, the minimum distance must be at least two d plus one.
- 1Five is two times two plus one, so the code guarantees correction of up to two bit errors.
Key terms
- Byte stuffing
- Escaping a reserved flag value when it appears in payload bytes so the receiver does not treat it as a boundary.
- Automatic Repeat reQuest
- A reliability pattern using feedback and retransmission when acknowledgement or timing indicates unsuccessful delivery.
- Selective Repeat
- A window protocol that buffers acceptable out-of-order frames and retransmits missing frames selectively.
Framing, Errors and Reliable Delivery FAQ
Why is a checksum different from a CRC?
A checksum uses arithmetic over fixed-width words and complements the sum. A CRC interprets the message algebraically and divides by a generator polynomial using modulo-two operations. Both detect corruption, but their structures and error-pattern guarantees differ.
When is Selective Repeat preferable to Go-Back-N?
It is attractive when retransmitting many already-correct frames is costly and the receiver can afford out-of-order buffering. Go-Back-N keeps receiver state simpler. The choice depends on delay, error rate, frame size and memory rather than protocol name alone.
Exam move
Classify the problem before choosing a mechanism. Boundary ambiguity calls for framing; corrupted bits call for a detection or correction code; missing feedback calls for a timeout; duplicates call for sequence numbers; and an idle long-delay link calls for a window. Then draw one sender-receiver timeline to test the answer. Practise framing by encoding and decoding the same short payload under three boundary schemes.
With a character count, corrupt the length field and follow the loss of synchronisation. With flag bytes, insert the escape convention into payload data and reverse it at the receiver. With bit stuffing, mark every inserted zero and verify that removal restores the original bits without deleting genuine data. This side-by-side trace turns a definition into an observable boundary mechanism.
Build a second ledger for error control. For parity, checksum and CRC, name the redundancy added, the receiver operation and the error patterns the method can or cannot guarantee to detect. Perform modulo-two division explicitly for one CRC example, and use Hamming distance to separate detection claims from correction claims rather than transferring a bound between them.
Then model reliable delivery as sender and receiver state. Place frame number, acknowledgement, timer and buffered data on a timeline; remove an acknowledgement, delay a frame or duplicate a transmission and follow the mechanism that restores progress. Compare Stop-and-Wait, Go-Back-N and Selective Repeat using link delay, window size, retransmission volume, sequence-number space and receiver memory.
A protocol name is not a conclusion: state which cost dominates the scenario. After every trace, identify the earliest divergence between expected and observed state. Check whether corruption detection, frame recovery and flow of outstanding frames have been treated as separate responsibilities.
Finish by changing one assumption—error rate, round-trip time or buffer capacity—and revising the preferred protocol without rewriting unrelated parts of the analysis. Keep detected corruption, discarded frames and recovered delivery as separate events in the ledger. This prevents an error-detection result from being reported as proof that the original data reached the application.
Working through Framing, Errors and Reliable Delivery in COMP90007? Sia is AskSia’s AI Computer Science tutor — ask any COMP90007 Framing, Errors and Reliable Delivery question and get a clear, step-by-step explanation grounded in how COMP90007 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
COMP30023 Computer Systems · COMP90038 Algorithms and Complexity · COMP20008 Elements of Data Processing
