Skip to content
Tutorials Center
My learning

Topics

Lesson 77 of 79 ยท Practice and Review

Practice: Link Layer and Transport Exercises

Work through seven exercises on CRC, Hamming codes, sliding windows, RTO and congestion windows, then check every answer with live Python code.

The data link and transport chapters are full of small calculations: divide a bit string by a polynomial, find the flipped bit, work out how many frames fit in a pipe, update a timeout, trace a congestion window. Exams and interviews love these because each one has exactly one right answer, and because you cannot get them right by memorizing sentences. You have to run the procedure.

This lesson gives you seven exercises. For each one, solve it on paper first, then open the live code to check your answer. The code prints the steps, so if your result differs you can see where. The ideas come from Framing and Error Detection, Error Correction and Hamming Codes, Flow Control and ARQ, TCP Reliability, TCP Flow Control and TCP Congestion Control.

Exercise 1: CRC

A sender uses the generator polynomial x4 + x + 1, written as the bit string 10011. The message is 1101011011.

  1. Compute the CRC remainder.
  2. Write the transmitted frame.
  3. What does the receiver get when it divides the clean frame? What if bit 4 is flipped?
  4. Is there an error pattern that this CRC cannot detect?

Method. Append four zeros (the generator has degree 4) and divide using XOR, not subtraction with borrows. Line the generator up under the leftmost 1, XOR, then slide to the next 1. What remains in the last four bits is the remainder. The transmitted frame is the message followed by that remainder, so the whole frame is divisible by the generator.

Python Exercise 1: CRC step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The remainder is 1110, so the frame is 11010110111110. A clean frame leaves remainder 0000; the damaged one does not. The one thing a CRC cannot catch is an error that is itself a multiple of the generator: adding 10011 to the frame changes it into another valid codeword. That is why the error pattern has to look exactly like the polynomial, which a random fault rarely does. A CRC with r check bits always catches bursts of up to r bits, and the loop confirms it by brute force.

Exercise 2: Hamming(7,4)

  1. Encode the data bits 0110 with the layout p1 p2 d1 p4 d2 d3 d4.
  2. A receiver gets 1011011. Find the syndrome, correct the word and extract the data.

Method. Each parity bit makes its group even: p1 covers positions 1, 3, 5, 7; p2 covers 2, 3, 6, 7; p4 covers 4, 5, 6, 7. At the receiver, the three checks read as a binary number (p4 p2 p1) give the position of the single bad bit.

Python Exercise 2: encode and correct

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Encoding 0110 gives 1100110. For the received word 1011011 all three checks fail, so the syndrome is 111 = 7: the last bit is wrong. Flipping it gives 1011010, and the data bits at positions 3, 5, 6 and 7 are 1010. Note that the answer depends on trusting the "only one error" assumption. Two flips would produce a different syndrome and a confident but wrong repair.

Exercise 3: Stop-and-wait and window sizes

A link runs at 1 Mbps. Frames are 1,000 bits, and the one-way propagation delay is 20 ms. Ignore ACK size and processing time.

  1. What is the transmission time Tt and the ratio a = Tp / Tt?
  2. What is the utilization of stop-and-wait?
  3. How many frames must be in flight to keep the link busy?
  4. How many sequence-number bits does Go-Back-N need for that window? And Selective Repeat?

Method. Stop-and-wait sends one frame and then waits a full round trip, so utilization is 1 / (1 + 2a). A sliding window of W frames gives min(1, W / (1 + 2a)). Go-Back-N needs W โ‰ค 2k โˆ’ 1; Selective Repeat needs W โ‰ค 2kโˆ’1, because the two windows must not overlap after an ambiguous retransmission.

Python Exercise 3: utilization and sequence bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

a = 20, so stop-and-wait uses only 1/41 = 2.44% of the link. You need 41 frames in flight. Go-Back-N then needs 6 bits (a window of up to 63), while Selective Repeat needs 7 bits (a window of up to 64), because half of its sequence space is reserved for the "old" window.

Exercise 4: Go-Back-N versus Selective Repeat

Ten frames (numbered 0 to 9) are sent with a window of 4. Frames 1 and 6 are lost on their first transmission only. Count the total transmissions and rounds for each protocol. Assume one round is one trip of a full window plus its acknowledgments, that Go-Back-N resends the lost frame and everything after it in the window, and that Selective Repeat resends only the missing frames.

Python Exercise 4: count transmissions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Go-Back-N sends 16 frames in 4 rounds; Selective Repeat sends 12 frames, also in 4 rounds. The 10 frames needed 10 transmissions, so Go-Back-N wasted 6 and Selective Repeat only 2. With a long pipe and a lossy link, that difference is why Selective Repeat (and TCP's SACK) is worth the extra receiver buffering.

flowchart LR
    A["Frame 1 lost"] --> B["Go-Back-N:<br/>resend 1, 2, 3, 4"]
    A --> C["Selective Repeat:<br/>resend 1 only"]
    B --> D["Receiver drops<br/>out-of-order frames"]
    C --> E["Receiver buffers<br/>frames 2, 3"]

The two protocols differ in what the receiver keeps and what the sender repeats.

Exercise 5: Retransmission timeout

TCP measures round-trip samples of 100, 140, 90, 300 and 110 ms. Using the Jacobson/Karels method with ฮฑ = 1/8, ฮฒ = 1/4 and RTO = SRTT + 4 ร— RTTVAR, compute SRTT, RTTVAR and RTO after each sample. The first sample sets SRTT = R and RTTVAR = R/2.

Python Exercise 5: RTO after each sample

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the first sample the RTO is 100 + 4 ร— 50 = 300 ms. The 300 ms outlier pushes RTTVAR from 39.38 up to 78.75 and the RTO to about 443 ms, even though the average barely moves. The most common slip is updating SRTT before RTTVAR; the deviation must use the old SRTT.

Exercise 6: Congestion window trace

A Reno-style sender starts with cwnd = 1 MSS and ssthresh = 16 MSS. In round-trip 8 it sees three duplicate ACKs; in round-trip 11 a timeout occurs. Trace cwnd and ssthresh for RTTs 1 to 14. Rules: below ssthresh, cwnd doubles each RTT (capped at ssthresh); at or above it, cwnd grows by 1 per RTT. Three duplicate ACKs set ssthresh = cwnd / 2 and cwnd = ssthresh. A timeout sets ssthresh = cwnd / 2 and cwnd = 1.

Python Exercise 6: trace cwnd

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The window goes 1, 2, 4, 8, 16, then climbs linearly to 19 at RTT 8. Three duplicate ACKs halve it to 9 (ssthresh 9), and it grows to 11 by RTT 11. The timeout is harsher: ssthresh becomes 5 and cwnd falls to 1, so the sender restarts in slow start. This asymmetry (mild reaction to duplicate ACKs, drastic reaction to timeouts) is the heart of Reno.

Exercise 7: How big a receive window?

A server and client are connected by a 100 Mbps path with an 80 ms round-trip time. What is the bandwidth-delay product in bytes? What is the throughput ceiling if the receive window is limited to 65,535 bytes (no window scaling)?

Python Exercise 7: bandwidth-delay product

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pipe holds 1,000,000 bytes, but an unscaled window is capped at 65,535, so the connection reaches only 6.55 Mbps, about 6.6% of the link. Window scaling (a shift of at least 4 here, since 65,535 ร— 16 is about 1 MB) fixes this; see TCP Flow Control.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A CRC generator has degree 8. What is the longest burst error it is guaranteed to detect?

    A CRC with r check bits detects every burst of length r or less. Longer bursts are detected with high probability but not with certainty.
  2. 2. The Hamming(7,4) syndrome of a received word is 101 in binary. Which position is flipped?

    The syndrome is read as a binary number that equals the position of the bad bit: 101 is 5.
  3. 3. Two frames out of a window of 8 are lost. Which statement about retransmission is correct?

    Selective Repeat buffers out-of-order frames at the receiver and repeats only what is missing. Go-Back-N resends from the first lost frame onwards.
  4. 4. After a timeout, a Reno sender with cwnd = 20 sets ssthresh and cwnd to:

    A timeout halves ssthresh and restarts slow start from one segment. Setting cwnd = ssthresh is the reaction to duplicate ACKs, not a timeout.
  5. 5. Why does the RTO calculation update RTTVAR before SRTT?

    RTTVAR measures how far the new sample is from the previous SRTT. If SRTT were updated first, the deviation would be understated.

Summary

  • A CRC remainder comes from XOR division by the generator; a degree-r generator catches every burst up to r bits, and only error patterns that are multiples of the generator slip through.
  • The Hamming syndrome is the position of the single flipped bit; two errors fool it.
  • Stop-and-wait utilization is 1 / (1 + 2a); a full pipe needs 1 + 2a frames in flight, which sets the sequence-number bits (Go-Back-N: window โ‰ค 2k โˆ’ 1, Selective Repeat: โ‰ค 2kโˆ’1).
  • Selective Repeat wastes far fewer transmissions than Go-Back-N when frames are lost.
  • RTO = SRTT + 4 ร— RTTVAR, updated with ฮฑ = 1/8 and ฮฒ = 1/4; one outlier raises the RTO quickly and it decays slowly.
  • Reno halves on duplicate ACKs and restarts at one segment on a timeout; the window must be at least the bandwidth-delay product to fill a path.

Next: Computer Networks Interview Questions