14 · UDP + Internet checksum ★

Slides 3-13 → 3-19 · HW3 P2 · Sample midterm 1c

UDP: User Datagram Protocol (RFC 768)

"No frills, bare bones" transport. Best-effort: segments may be lost or delivered out of order.
Connectionless: no handshake between sender and receiver, and every segment is handled independently.

Why is there a UDP? (sample 1c)

No connection setup, which would add an RTT of delay.
Simple: no connection state at the sender or receiver.
Small header (8 bytes).
No congestion control: UDP can blast away as fast as it wants, and still works when the network is congested.

Used by: streaming multimedia (loss-tolerant, rate-sensitive), DNS, SNMP, HTTP/3. If an app needs reliability over UDP (like HTTP/3), it adds reliability and congestion control at the application layer.

UDP header: 4 fields × 16 bits = 8 bytes

|<------------ 32 bits ------------>|
|  source port #  |   dest port #    |
|     length      |    checksum      |
|      application data (payload)    |

Length = length of the whole UDP segment in bytes, including the header.

The Internet checksum

Goal: detect errors (flipped bits) in a segment.

Sender	Receiver
Treat the segment's contents (data, UDP header fields, and IP addresses) as a sequence of 16-bit integers	Compute the checksum of what it received
Checksum = 1s complement of the 1s complement sum of those integers	Compare with the checksum field. Not equal → error detected. Equal → no error detected (but there could still be one)
Put it in the UDP checksum field

The recipe (3 steps)

1. Add the words in binary, normally.
2. Wrap around: if there's a carry out of the leftmost bit, drop it and add 1 to the result. Do this after every addition.
3. Flip every bit (0↔1). That's the checksum.

Steps 1–2 give the 1s complement sum. Step 3 takes its 1s complement.

Worked example: HW3 P2

Q: Three 8-bit bytes: 01010011, 01100110, 01110100. What's the 1s complement of their sum? Show all work.

Step 1: add the first two

    01010011    (83)
  + 01100110   (102)
  ----------
    10111001   (185)   ← no carry out, nothing to wrap

Step 2: add the third

    10111001   (185)
  + 01110100   (116)
  ----------
  1 00101101   (301)   ← carry out of the leftmost bit!

Step 3: wrap the carry around

    00101101
  +        1
  ----------
    00101110   ← 1s complement sum

Step 4: flip every bit

    00101110
 →  11010001   ← checksum

Answer: 11010001

Check yourself with decimal (not as your shown work): for \(n\)-bit words, the 1s complement sum = (decimal sum) mod \((2^n - 1)\). Here: \(83 + 102 + 116 = 301\), and \(301 \bmod 255 = 46 = 00101110\) ✓. Checksum \(= 255 - 46 = 209 = 11010001\) ✓.

Why take the 1s complement instead of just sending the sum?

So the receiver's check is dead simple. The receiver adds all the words plus the checksum. With no errors, the result is all 1s:

    00101110   (sum of the data)
  + 11010001   (checksum)
  ----------
    11111111   ✓ no error detected

(A number plus its own bit-flip is always all 1s.)

How does the receiver detect errors?

It adds all the received words and the checksum (with wraparound). If any bit of the result is 0, there's an error.

Can a 1-bit error go undetected? A 2-bit error?

1-bit error: always detected. Flipping one bit changes the sum.
2-bit error: can go undetected. If the same bit position flips 0→1 in one word and 1→0 in another, the changes cancel and the sum stays the same.

Example: flip the last bit of the first two bytes.

  01010011 → 01010010   (−1)
  01100110 → 01100111   (+1)
  01110100   unchanged

The sum is still 00101110, so the checksum still matches. Error missed.

Slide example (16-bit, 3-18)

                1110011001100110
              + 1101010101010101
              ------------------
              1 1011101110111011   ← carry out
wraparound:       1011101110111011
                +                1
              ------------------
sum:              1011101110111100
checksum:         0100010001000011   ← flip every bit

Weak protection (3-19): if bits change in a way that keeps the sum the same (like the 2-bit example above), the checksum doesn't change and the error is missed.

Traps
• Don't forget the wraparound. A carry out of the leftmost bit gets added back at the right end, not thrown away.
• Don't forget to flip at the end. "Sum" and "checksum" are different answers.
• Keep the word length fixed (8 bits here, 16 in real UDP). Pad with leading zeros.
• Binary addition: 1+1 = 0 carry 1. 1+1+1 = 1 carry 1.

Quick check

1. What are the 4 fields of the UDP header? How big is it?

Source port, dest port, length, checksum. 16 bits each → 8 bytes.

2. Checksum of the 8-bit words 11001010 and 10110110?

    11001010
  + 10110110
  ----------
  1 10000000   ← carry out
wrap: 10000000 + 1 = 10000001
flip: 01111110

01111110. (Check: 202 + 182 = 384, 384 mod 255 = 129 = 10000001 ✓)

3. Checksum of the 4-bit words 1011, 0110, 1100?

  1011 + 0110 = 10001 → carry out → 0001 + 1 = 0010
  0010 + 1100 = 1110   (no carry)
  flip: 0001

0001. (Check: 11 + 6 + 12 = 29, 29 mod 15 = 14 = 1110 ✓)

4. The receiver gets the HW3 P2 bytes but the first one arrived as 01010111. What does the check give?

Add all four (with wraparound): 01010111 + 01100110 + 01110100 + 11010001 → 00000100. Not all 1s, so the error is detected. (Decimal: 87 + 102 + 116 + 209 = 514, 514 mod 255 = 4.)

5. Why does UDP send the complement of the sum instead of the sum?

So the receiver can add everything including the checksum and just check for all 1s. Any 0 bit = error.

6. Can a 2-bit error go undetected? Give the condition.

Yes: when the same bit position flips 0→1 in one word and 1→0 in another. The sum doesn't change.

7. Give two reasons to use UDP instead of TCP. (sample 1c)

Any two: no connection setup delay, no connection state, small 8-byte header, no congestion control (app sends as fast as it wants).

← 13 · Mux/demux · all topics · 15 · GBN & SR →