Error Detection & Correction

Question 1

Checksum (used mainly at layer 4)

Answer 1

• Sender:
  
  • treat packet contents as sequence of 16-bit integers
  • calculate checksum as sum (1’s complement) of packet contents
  • put checksum value into UDP checksum field
• Receiver:
  
  • compute checksum of received packet
  • check if checksum field value = computed checksum
    ¤ NO - error detected
    ¤ YES - no error detected
• But there may be errors nonetheless?
• No way to correct any errors

Question 2

Error Detection and Correction using
Redundancy (used mainly at layer 2)

Answer 2

• D = Data protected by error checking
• EDC = Error Detection and Correction bits (redundancy)
• Error detection still not 100% reliable!
  ¤ Some errors may be missed, but rarely
  ¤ Larger EDC field yields better detection - and correction

Question 3

A simple approach: Parity Bits

Answer 3

• Idea: add extra bits to keep the number of 1s even
  ¤ Example: 7-bit ASCII characters + 1 parity bit
• Detects 1-bit errors and some 2-bit errors
• Not reliable against bursty errors
• No possibility of error correction

Question 4

Two-dimensional parity bits

Answer 4

• Can detect all 1, 2, and 3 bit errors, some 4 bit errors
• 14% overhead
• Ability to correct errors!

Question 5

Example of Error Correction

Answer 5

Question 6

A more sophisticated approach:
Cyclic Redundancy Checks (CRC)

Answer 6

• Compute an almost-unique “CRC” value for a given message
• Much better performance than parity approaches
  ¤ Fixed size overhead per frame (usually 32-bits)
  ¤ Quick to implement in hardware
  ¤ With 32-bit CRC, only 1 in 232 chance of missing an error
• Widely used in practice (Ethernet, 802.11 WiFi)

Question 7

CRC Overview (very quick!)

Answer 7

• View to-be-sent data as a binary number D
• Sender and Receiver agree in advance on a “generator” bit pattern G
• Sender: choose a CRC value R such that <D:R> MODULO G = 0</D:R>
• Receiver: divide <D:R> by G; remainder => error detected!</D:R>

Question 8

A Day in the Life of a Web Request

Answer 8

• our journey down the protocol stack is pretty-much complete!
  – application, transport, network, data-link (not phy!)
• let’s now look at putting it all together
  – goal: review the operation of the protocols involved in realising a very simple scenario
  – scenario: student attaches their laptop to campus network, opens a web browser, and requests/receives Google home page

Question 9

The scenario

Answer 9

Question 10

1. Connecting to the Internet

Answer 10

• connecting laptop needs to get its own IP address, addr
  of 1st-hop router, addr of DNS server: use DHCP
• DHCP request encapsulated in UDP, encapsulated in IP, encapsulated in Ethernet frame
• Ethernet frame is broadcast (dest: FFFFFFFFFFFF) on the LAN, and received at router running DHCP server
• Ethernet frame is demuxed to IP -> UDP -> DHCP

Question 11

Connecting to the Internet (cont)…

Answer 11

• DHCP server formulates DHCP ACK containing client’s IP address, IP address of 1st-hop router, name & IP address of DNS server
• encapsulation at DHCP server, frame forwarded through LAN, demultiplexed at client
• DHCP client receives DHCP ACK reply

Client now has its own IP address, the name and IP address of a DNS server, and the IP address of its 1st-hop router

Question 12

2. ARP (before DNS, before HTTP)

Answer 12

• before sending HTTP request, need IP address of www.google.com: DNS
• DNS query created, encapsulated in UDP, encapsulated in IP, encapsulated in Eth. To send frame to router, we need the router’s MAC address: ARP
• ARP query broadcast, received by router, which replies with MAC address of router interface
• client now knows MAC address of 1st-hop router, so can now send frame containing DNS query

Question 13

3. DNS

Answer 13

Question 14

4. TCP connection carrying HTTP

Answer 14

• to send HTTP request, client first opens TCP socket to web server
• TCP SYN segment (step 1 in 3- way handshake) routed to web server
• web server responds with TCP SYNACK (step 2 in 3-way handshake)
• TCP connection established! (N.B. step 3 ACK packet may contain data)

Question 15

5. HTTP request/reply

Answer 15

• HTTP request sent into TCP socket
• IP datagram containing HTTP request routed to
  www.google.com
• web server responds with HTTP reply (containing web page)
• IP datagram containing HTTP reply routed back to client