101
0/228
Loading content...
Consider a seemingly simple question: How does the receiver know if a frame is new or a duplicate?
Without retransmission, this question doesn't arise—every frame is new by definition. But the moment we introduce reliability through retransmission, we create the possibility of duplicates. And duplicates are dangerous: they can cause data to be delivered twice, corrupting higher-layer protocols that assume exactly-once semantics.
The Core Problem:
At step 5, how does the receiver know this is a retransmission of the same frame and not a new frame containing identical data? Without additional information, it can't.
Sequence numbers solve this problem by giving each frame a unique identifier. The receiver tracks which sequence number it expects, and can detect when a retransmitted frame arrives.
By the end of this page, you will master sequence numbers in Stop-and-Wait: why only 1 bit is sufficient, the state machines they enable, what happens without them, and how they generalize to sliding window protocols.
Let's explore what goes wrong without sequence numbers.
Scenario: No Sequence Numbers, ACK Lost
Sender Receiver
| |
|-------- Frame [Data: "Hello"] ---------> |
| [Deliver "Hello"] |
| [Send ACK] |
| <<< ACK LOST >>> |
| |
| [Timer expires] |
|-------- Frame [Data: "Hello"] ---------> |
| |
| [Receive "Hello"] |
| Is this new data? |
| [Deliver "Hello"] | ← WRONG!
Without sequence numbers, the receiver cannot distinguish the retransmission from a new frame. It delivers "Hello" twice—a duplicate delivery error.
Application Layer Consequences:
Most applications expect exactly-once delivery. They don't expect to handle duplicate packets. While some applications implement their own duplicate detection, the data link layer should provide this guarantee to simplify higher layers.
Scenario: No Sequence Numbers, Frame Delayed
An even more subtle problem:
Sender Receiver
| |
|-------- Frame [Data: "Hello"] ---------> |
| <<< Frame delayed >>> |
| [Timer expires] |
|-------- Frame [Data: "Hello"] ---------> |
| [Receive "Hello"] |
| [Deliver, ACK] |
|<------------- ACK ------------------ |
| |
|-------- Frame [Data: "World"] ---------> |
| |
| [Delayed "Hello" arrives!] |
| [Receive "Hello"] |
| Is this new? |
| [Deliver "Hello"] | ← WRONG!
The delayed frame from the first transmission finally arrives, but it's mistaken for a new frame. The receiver delivers "Hello" instead of "World"—a data ordering error.
Sequence Numbers Prevent Both Problems:
By labeling each frame with a sequence number:
A remarkable property of Stop-and-Wait: only a 1-bit sequence number is required. The sequence number alternates between 0 and 1: 0, 1, 0, 1, 0, 1...
Why 1 Bit Suffices:
In Stop-and-Wait, the sender has at most one unacknowledged frame at any time. The receiver expects exactly one frame at a time. There are only two possible situations:
Two states require only 1 bit to distinguish.
The Alternating Bit Protocol:
Stop-and-Wait with 1-bit sequence numbers is also called the Alternating Bit Protocol (ABP):
Sender sequence: 0, 1, 0, 1, 0, 1, ...
Receiver expects: 0, 1, 0, 1, 0, 1, ...
The sequence numbers "alternate" between 0 and 1, never repeating until the previous transmission is acknowledged.
Proof: 1 Bit Is Sufficient
Claim: For Stop-and-Wait, a 1-bit sequence number guarantees duplicate detection and correct ordering.
Proof:
Invariant: The sender never transmits frame n+1 until frame n is acknowledged.
Consequence: At most one frame is "in flight" (unacknowledged) at any time.
Observation: The only frames the receiver might see are:
Distinction: Two values (0 and 1) are sufficient to distinguish these cases.
No third possibility: Since only one frame is outstanding, we never need to distinguish more than two consecutive frames.
Therefore, 1 bit (2 values) is sufficient. QED.
Why Not 0 Bits?
With 0 bits (no sequence number), we cannot distinguish case (a) from case (b) above—exactly the duplicate problem we showed earlier.
Stop-and-Wait uses the absolute minimum sequence number space that provides correctness. This minimalism reduces overhead and simplifies implementation. Every additional bit doubles the sequence space—useful for sliding window protocols, but unnecessary for Stop-and-Wait.
Let's examine exactly how sequence numbers are used in Stop-and-Wait.
At the Sender:
The sender maintains a variable next_seq (the sequence number for the next frame to send):
next_seq = 0 // Initial state
function send_data(data):
frame = create_frame(data, next_seq)
stored_frame = frame
transmit(frame)
start_timer()
// Don't change next_seq yet - wait for ACK
function on_ack_received(ack):
if ack.seq == next_seq:
stop_timer()
next_seq = 1 - next_seq // Toggle: 0→1 or 1→0
signal_ready_for_next()
function on_timeout():
transmit(stored_frame) // Retransmit with same seq
start_timer()
Key point: The sequence number only advances when an ACK is received, not when a frame is transmitted.
At the Receiver:
The receiver maintains expected_seq (the sequence number it expects next):
expected_seq = 0 // Initial state
function on_frame_received(frame):
if crc_error(frame):
return // Discard silently
if frame.seq == expected_seq:
// New frame, as expected
deliver_to_network_layer(frame.data)
expected_seq = 1 - expected_seq // Toggle
send_ack(frame.seq) // ACK the received frame
else:
// Duplicate (frame.seq == 1 - expected_seq)
// Don't deliver, but still ACK
send_ack(frame.seq)
Why ACK Duplicates?
If a duplicate arrives, the receiver:
This combination—discard data, send ACK—is essential for deadlock prevention.
In Stop-and-Wait, ACK(0) means "I received frame 0." The sender expects ACK(next_seq). Upon receiving the correct ACK, the sender toggles next_seq. Different protocols have different ACK semantics (e.g., TCP's "next expected"), so always verify the convention.
State Transitions:
Sender State Machine:
+---------------------------+
| |
v |
STATE: [Waiting for data ,seq=0] |
| |
(data arrives) |
| |
v |
[Send Frame 0] |
| |
v |
[Waiting for ACK0] |
| |
+----+----+ |
| | |
(timeout) (ACK0) |
| | |
v v |
[Retransmit] [Advance to seq=1]----+
| |
+--> [Waiting for ACK0] |
|
... (similar for seq=1) ... |
Sequence number handling must correctly address several edge cases that arise in real networks.
Edge Case 1: Late ACK Arrival
Sender Receiver
seq=0 exp=0
|-------- Frame 0 ---------> |
| [Receive, exp=1, ACK0]
| <<< ACK0 delayed >>> |
| [Timeout, retransmit Frame 0] |
|-------- Frame 0 ---------> |
| [Dup! exp=1, frame.seq=0]
| [Don't deliver, send ACK0]
|<--------- ACK0 -------- (from retransmit)
| [seq=0, got ACK0, advance to seq=1] |
|-------- Frame 1 ---------> |
| [Receive, exp=1, match!]
| [Deliver, exp=0, ACK1]
|<--------- ACK0 -------- (delayed original)
| [Expected ACK1, got ACK0, IGNORE] |
Analysis: The delayed ACK0 arrives after the sender has moved to seq=1 and is expecting ACK1. The sequence number mismatch causes the sender to correctly ignore the late ACK.
Edge Case 2: Packet Reordering (Extreme)
While Stop-and-Wait typically assumes in-order delivery (common at the data link layer), let's analyze what happens if frames arrive out of order:
Sender Receiver
seq=0 exp=0
|-------- Frame 0 -------(slow path)--> |
| [Timeout] |
|-------- Frame 0 -------(fast path)--> |
| [Receive, match, deliver, exp=1]
|<--------- ACK0 -------- |
| [Advance to seq=1] |
|-------- Frame 1 ---------> |
| [Receive, match, deliver, exp=0]
|<--------- ACK1 -------- |
| [Advance to seq=0] |
| |
| [Slow Frame 0 finally arrives!]
| [frame.seq=0, exp=0, MATCH?!]
Problem: The very old Frame 0 arrives when the receiver happens to be expecting seq=0 again. This could cause incorrect duplicate delivery!
Solution: This is why Stop-and-Wait is used on reliable-ordering links (like point-to-point serial connections). For links with potential reordering, larger sequence spaces or additional mechanisms (timestamps, connection IDs) are needed.
With only 2 sequence numbers (0 and 1), wraparound happens quickly. If packets can survive in the network long enough, old packets might be confused with new ones. At the data link layer, this is usually okay (links are short, packets don't persist). At higher layers like TCP, larger sequence spaces and Maximum Segment Lifetime (MSL) limits are used.
Edge Case 3: Sender Reset During Transmission
What if the sender crashes and restarts?
Sender Receiver
seq=0 exp=0
|-------- Frame 0 ---------> |
| [Deliver, exp=1, ACK0]
|<--------- ACK0 -------- |
| [Crash and restart!] |
| seq=0 (reset) |
|-------- Frame 0 (new data!) --------->|
| [seq=0, exp=1, DUPLICATE?]
| [Don't deliver] ← WRONG!
Problem: After restart, the sender's sequence number resets to 0, but the receiver still expects seq=1. The new Frame 0 is incorrectly treated as a duplicate.
Solution: Connection-oriented protocols typically require a handshake to resynchronize after restart. The handshake establishes fresh sequence number bases. Simple data link protocols often rely on the physical layer to signal "link reset" events.
Different protocols use different conventions for what the ACK number means. Understanding these conventions is essential for correct implementation.
Convention 1: "I Received N" (Used in Stop-and-Wait)
ACK(n) means: "I successfully received frame n."
Frame 0 received → Send ACK(0) → "I got frame 0"
Frame 1 received → Send ACK(1) → "I got frame 1"
Convention 2: "Send Me N Next" (Used in TCP)
ACK(n) means: "I have received all bytes up to n-1. Please send n next."
Frame 0 received → Send ACK(1) → "I got frame 0, send frame 1"
Frame 1 received → Send ACK(2) → "I got frame 1, send frame 2"
This is the "cumulative ACK" or "next expected sequence" convention.
| Aspect | "I Received N" | "Send Me N Next" |
|---|---|---|
| ACK meaning | Explicit receipt confirmation | Implicit cumulative receipt |
| After receiving frame 0 | ACK(0) | ACK(1) |
| After receiving frames 0,1,2 | ACK(2) (latest) | ACK(3) (next expected) |
| Natural fit for | Stop-and-Wait, Selective Repeat | Go-Back-N, TCP |
| Duplicate handling | Match against current frame | Compare against send window |
Why Stop-and-Wait Uses "I Received N":
With only one outstanding frame, there's no need for cumulative acknowledgment. ACK(0) unambiguously acknowledges Frame 0. The sender knows exactly what was received.
Potential Confusion:
When reading protocol specifications, always verify which convention is used:
// Convention 1 (Stop-and-Wait style)
if ack.seq == current_seq: // ACK matches frame we sent
advance()
// Convention 2 (TCP style)
if ack.seq == current_seq + 1: // ACK indicates "got current, send next"
advance()
Using the wrong convention causes protocol failure—either premature advancement or deadlock.
When implementing or analyzing a protocol, the first thing to verify is the ACK numbering convention. HDLC, PPP, TCP, and custom protocols may all use different conventions. A single off-by-one error here breaks everything.
Stop-and-Wait uses 1-bit sequence numbers because it has at most 1 outstanding frame. What about protocols with multiple outstanding frames?
Sliding Window Protocols:
Go-Back-N and Selective Repeat allow multiple frames to be "in flight" simultaneously. This requires larger sequence number spaces.
The General Rule:
For a sliding window protocol:
Why the Difference?
Examples:
| Protocol | Window Size | Min Sequence Bits | Sequence Range |
|---|---|---|---|
| Stop-and-Wait | 1 | 1 | {0, 1} |
| Go-Back-N (W=7) | 7 | 3 | {0, 1, ..., 7} |
| Selective Repeat (W=4) | 4 | 3 | {0, 1, ..., 7} |
| TCP | 2^16 - 1 | 32 | {0 to 2^32 - 1} |
Sequence Number Wraparound:
With finite bits, sequence numbers eventually wrap around:
Wraparound Safety:
The sequence space must be large enough that by the time sequence numbers wrap, old frames with the same number are no longer in the network.
Maximum Segment Lifetime (MSL):
TCP defines MSL (typically 60-120 seconds) as the maximum time a packet can exist in the network. Sequence numbers are sized so that:
MSL × Maximum_Data_Rate < Sequence_Space
With 32 bits and reasonable network speeds, TCP can handle gigabit speeds without wraparound problems. For faster networks, the TCP timestamp option provides additional protection.
Stop-and-Wait's 1-bit sequence space implicitly assumes frames don't persist long enough to cause wraparound confusion. This is reasonable at the data link layer (point-to-point links have minimal delay) but not necessarily at higher layers where packets traverse complex networks.
The Alternating Bit Protocol (Stop-and-Wait with 1-bit sequence numbers) is simple enough to formally verify. Let's sketch the key properties and their proofs.
Property 1: Safety - No Duplicate Deliveries
Claim: If frame F is delivered at time T, it will not be delivered again at any time T' > T.
Proof Sketch:
Property 2: Safety - In-Order Delivery
Claim: If frame n is delivered before frame n+1 at the sender, frame n is delivered before frame n+1 at the receiver.
Proof Sketch:
Property 3: Liveness - Every Frame Is Eventually Delivered
Claim: If the network eventually allows at least one successful round trip, every submitted frame is eventually delivered.
Proof Sketch:
Assumption Required:
The liveness proof requires:
If the channel is permanently broken, no protocol can deliver data—Stop-and-Wait correctly reports failure after retry limit.
The Alternating Bit Protocol is a classic example used in formal methods courses. It's been verified using model checkers like SPIN, TLA+, and various theorem provers. The proofs confirm that with correct implementation and reasonable assumptions, the protocol achieves its reliability goals.
Sequence numbers are the key to distinguishing new data from retransmissions. In Stop-and-Wait, the elegantly minimal choice of 1-bit sequence numbers provides all necessary functionality. Let's consolidate:
The Elegance of Minimalism:
Stop-and-Wait with 1-bit sequence numbers demonstrates a beautiful principle: use exactly as many resources as needed, no more. The protocol achieves perfect reliability with minimal state, minimal overhead, and minimal complexity.
Looking Ahead:
With basic operation, acknowledgments, timeouts, and sequence numbers understood, we're ready to analyze Stop-and-Wait's efficiency. How well does it utilize the available bandwidth? When is it appropriate, and when should we use more sophisticated protocols?
You now have deep understanding of sequence numbers in Stop-and-Wait ARQ: why they exist, why 1 bit suffices, how they're used at sender and receiver, and how they generalize to larger protocols. This concept is foundational to understanding all reliable protocols.