Computer Networks Lecture 3 Notes

Codewords and Hamming Distance

Codewords are constructed from data and check bits.
Hamming distance measures the difference between two codewords, calculated using the exclusive-OR operation.
Exclusive-OR examples:
- $1 \oplus 1 = 0 \oplus 0 = 0$
- $1 \oplus 0 = 0 \oplus 1 = 1$
Example Hamming Distance Calculation:
- $10011101 \oplus 10111110 = 00100011$
- The Hamming distance is 3, as there are three 1s in the result.

Error Detection and Correction

To detect $\delta$ errors, a minimum Hamming distance of $\delta + 1$ is required between codewords.
- Example: Detecting 1 error requires a minimum distance of 2.
To correct $\delta$ errors, a minimum distance of $2\delta + 1$ is needed.
- This ensures the damaged codeword remains closest to the correct valid codeword after errors.
Example Code:
- Valid codewords: 0000000000, 1111100000, 0000011111, 1111111111
- Minimum distance: 5
- Error detection: $\delta + 1 = 5$ , so $\delta = 4$ (can detect 4 errors)
- Error correction: $2\delta + 1 = 5$ , so $\delta = 2$ (can correct 2 errors)

Error Correction with Redundancy

A transmission consists of:
- $m$ bits for the message
- $r$ bits of redundant information
Total transmitted bits: $n = m + r$
Critical question: How many redundant bits ( $r$ ) are needed for error correction?

Hamming Code

Developed in 1950 by Richard Hamming.
Achieves the lower bound: $m + r + 1 \le 2^r$
Procedure:
- Number codeword bits from 1.
- Bits at positions that are powers of 2 ({1, 2, 4, 8,…}) are check bits.
- Check bits enforce parity (even or odd) on bit collections.

Data Bit Contribution to Parity

A data bit contributes to the parity of bits whose positions sum to the data bit's position.
Examples:
- 3 = 2 + 1 (contributes to parity of bits 1 & 2)
- 7 = 4 + 2 + 1 (contributes to parity of bits 1, 2, & 4)
- 11 = 8 + 2 + 1 (contributes to parity of bits 1, 2, & 8)
List of contributions:
- Bit 1 is contributed to by bits 3, 5, 7, 9, 11
- Bit 2 is contributed to by bits 3, 6, 7, 10, 11
- Bit 4 is contributed to by bits 5, 6, 7
- Bit 8 is contributed to by bits 9, 10, 11

Hamming Code Example

ASCII character 'c' = 1100011 (using even parity).
Codeword construction:
- Positions: 1 2 3 4 5 6 7 8 9 10 11
- Data/Check: _ _ 1 _ 1 0 0 _ 0 1 1
- Check bit assignments (X denotes a position where a parity check is performed):
  - check 1: X X 1 X 1 0 1 X 1 0 1
  - check 2: X 1 X X 1 1 1 X 0 0 1
  - check 4: X 1 1 X 1 1 1 X 0 0 1
  - check 8: X 1 1 1 X 1 1 X 1 1 1
Resulting codeword: 11111000011

Hamming Code Error Correction

Process to check and correct received codeword:
1. Initialize counter $c = 0$ .
2. Check each bit in position $k = {1, 2, 4, 8}$ .
3. If parity is incorrect, add $k$ to $c$ ( $c += k$ ).
4. After checking all bits:
  - If $c = 0$ , codeword is correct.
  - Otherwise, bit at position $c$ is incorrect.

Hamming Code Correction Example

Transmitted: 11111000011. Received: 11111000010.
Checking process:
- k = 1: Parity for 3, 5, 7, 9, 11 is wrong! $c += 1$ ( $c = 1$ ).
- k = 2: Parity for 3, 6, 7, 10, 11 is wrong! $c += 2$ ( $c = 3$ ).
- k = 4: Parity for 5, 6, 7 is correct.
- k = 8: Parity for 9, 10, 11 is wrong! $c += 8$ ( $c = 11$ ).
Bit 11 is in error!

Cyclic Redundancy Codes (CRC)

CRCs are commonly used for error detection.
Refer to additional materials for more details.

Data Link Layer Services

Provides key services between the Physical and Network Layers:
- Bundling bits into frames.
- Error detection.
- Flow control.

MAC (Media Access Control)

Protocol for transmitting and receiving frames at the link layer.
Includes error detection and correction.
Uses MAC addresses (Link-layer addresses).

Frame Structure

Frame: A container for network packets.
Encapsulates bits for receiver to identify content.
Examples: Ethernet, PPP, Fibre Channel.
Framing: Wrapping data with control information before sending.

Frame Components

Typical frame components:
- Flag: Indicates start and end of frame.
- Header: Source/destination addresses, control information.
- Data: Payload from upper layer.
- Trailer: Error detection/correction codes.

Ethernet Evolution

Mid-1970s: Created at Xerox by Bob Metcalfe (2.74 Mbps over coax).
1980s: Standardized as IEEE 802.3.
- 10BASE-5 (thick coax).
- 10BASE-2 (thin coax).
1990:
- 10BASE-T over twisted pair (10 Mbps).
- Category 3 UTP wiring with RJ45 connectors.
1995: Fast Ethernet (100BASE-TX over Cat 5 UTP).
1999: Gigabit Ethernet (1000BASE-T over Cat 5e).
2006: 10 Gb Ethernet (10GBASE-T over Cat 6a).
2010: 100GbE / 40GbE (40GBASE-T over Cat 8).

Ethernet Frame Details

8 bytes: Preamble & start-of-frame delimiter.
Variable size data: 42-1500 bytes.
- No length field: transceiver grabs entire frame.
Interframe gap: At least 96 bit wait time.
Components:
- MAC destination, MAC source.
- Type (higher level protocol ID: 0x0800 = IPv4, 0x86DD = IPv6).
- Payload (42-1500 bytes).
- CRC.

Data Link Layer Complexity Levels

Three levels:
- Simplex Connectionless
  - One-way communication.
  - Sender sends frames without waiting for acknowledgment.
  - No re-transmission of lost frames.
  - Most modern LANs (e.g., Ethernet) use this, leaving error resolution to higher layers.
  - Also termed unacknowledged connectionless service.
- Half-Duplex Connectionless
  - Data transmission occurs in one direction at a time.
  - Each frame is individually acknowledged.
  - Lost or garbled frames are retransmitted upon request or timeout.
  - Also termed acknowledged connectionless service.
- Full-Duplex Connection-Oriented
  - Data transmitted in both directions simultaneously.
  - Logical connection established before data transfer.
  - Frames numbered and guaranteed to be received once, in order.
  - Presents a reliable frame stream to the network layer.
  - Also termed acknowledged connected service.

Data Link Layer Protocols

Simplest.
Stop-and-Wait (Noiseless channel).
Stop-and-Wait ARQ (Automatic Repeat Request).
Go-Back-N ARQ.
Selective Repeat ARQ.

Basic Protocol Datatypes

For simplicity and consistency, early protocols use common datatypes.
Frame consists of a header and data.
Header structure evolves as protocols develop.
Frames represented as structures with byte aliasing for access/copying.
In Python, frame contents are packed/unpacked from byte sequences.

Frame Class in Python

Frame class definition:

class Frame:
    MAX_DATA_SIZE = 1000

    def __init__(self, data: bytes = bytes()):
        self.len = len(data)
        if self.len > Frame.MAX_DATA_SIZE:
            raise RuntimeError('Too much data for one Frame!')
        self.data = data

Frame Packing

!: Network byte order, standard size, no alignment.
H: Unsigned two-byte integer (self.len).
1000s: One thousand bytes (self.data).

import struct

class Frame:
    ...
    def pack(self):
        return struct.pack('! H 1000s', self.len, self.data)

Frame Size Optimization

Avoid sending the whole frame when possible.
For example, an Ethernet frame can carry up to 1500 bytes, but may only need to carry 80 bytes.
Protocols often exchange header-only frames (e.g., acknowledgment frames).

Dynamic Frame Packing

{}: Formatted to exactly self.len bytes.

import struct

class Frame:
    ...
    def pack(self):
        return struct.pack('! H {}s'.format(self.len), self.len, self.data)

Frame Unpacking

import struct

class Frame:
    ...
    def unpack(self, packed: bytes):
        header_length = struct.calcsize('! H')
        self.len, = struct.unpack_from('!H', packed)
        self.data, = struct.unpack_from('!{}s'.format(self.len), packed, header_length)

Unrestricted Simplex Protocol Assumptions

Unidirectional, error-free channel.
Sender's network layer always has data.
Receiver's network layer has infinite buffer.
READ_xxx_LAYER() and WRITE_xxx_LAYER() block until complete.
Sender sends frames without waiting for acknowledgment.

Unrestricted Simplex Protocol Implementation - Sender

frame = Frame()
link = 1
while True:
    frame.data = READ_NETWORK_LAYER()
    frame.len = len(frame.data)
    packed = frame.pack()
    WRITE_PHYSICAL_LAYER(link, packed)

Unrestricted Simplex Protocol Implementation - Receiver

frame = Frame()
link = None
while True:
    link, packed = READ_PHYSICAL_LAYER()
    frame.unpack(packed)
    WRITE_NETWORK_LAYER(frame.data)

Unrestricted Simplex Protocol Diagram

Illustrates the continuous sending of frames from sender to receiver without acknowledgment.

Half-Duplex Stop-and-Wait Protocol

Addresses the limited buffer capacity of the receiver.
The receiver controls the rate of data reception by sending acknowledgements (ACKs) back to the sender.
Still assumes an error-free unidirectional channel.

Half-Duplex Stop-and-Wait Protocol Implementation - Sender

Sender waits for ACK after sending a frame.

frame = Frame()
link = 1
while True:
    frame.data = READ_NETWORK_LAYER()
    frame.len = len(frame.data)
    packed = frame.pack()
    WRITE_PHYSICAL_LAYER(link, packed)
    link, packed = READ_PHYSICAL_LAYER()  # Wait for ACK

Half-Duplex Stop-and-Wait Protocol Implementation - Receiver

Receiver sends ACK after receiving data.

frame = Frame()
link = None
while True:
    link, packed = READ_PHYSICAL_LAYER()
    frame.unpack(packed)
    WRITE_NETWORK_LAYER(frame.data)
    frame.len = 0
    WRITE_PHYSICAL_LAYER(link, frame.pack())  # Send ACK

Half-Duplex Stop-and-Wait Protocol Diagram

Illustrates the exchange of frames and ACKs between sender and receiver.

Half-Duplex Stop-and-Wait Protocol Issues

Adding acknowledgements ensures packet delivery.
Potential problems introduced: Packet loss, corruption.

Detecting Frame Corruption

Remove the error-free assumption.
Introduce checksums and FRAMETYPE to check frame integrity.
Receiver validates checksum.

Updated Frame Class with FrameType and Checksum

from enum import IntEnum
import struct

class FrameType(IntEnum):
    DLL_DATA = 0
    DLL_ACK = 1
    DLL_NACK = 2

class Frame:
    MAX_DATA_SIZE = 1000

    def __init__(self, frametype: FrameType, data: bytes = bytes()):
        self.type = frametype
        self.checksum = 0  # Initial checksum of the whole frame
        self.len = len(data)  # length of the payload, only
        if self.len > Frame.MAX_DATA_SIZE:
            raise RuntimeError('Too much data for one Frame!')
        self.data = data

    def pack(self):
        return struct.pack('!HHH{}s'.format(self.len), self.type, self.checksum, self.len, self.data)

    def unpack(self, packed: bytes):
        header_length = struct.calcsize('!HHH')
        self.type, self.checksum, self.len = struct.unpack_from('!HHH', packed)
        self.data, = struct.unpack_from('!{}s'.format(self.len), packed, header_length)

Detecting Frame Corruption; Stop & Wait ARQ - Sender

Sender calculates checksum and sends data frames.
If DLL_ACK, break. Note the checksum is calculated before packing.

frame = Frame(FrameType.DLL_DATA)
ackframe = Frame(FrameType.DLL_ACK)
link = 1
while True:
    frame.data = READ_NETWORK_LAYER()
    frame.type = FrameType.DLL_DATA            #Sets the frame type to data.
    frame.len = len(frame.data)
    frame.checksum = 0                          #The checksum must be reset before each pack.
    frame.checksum = crc16(frame.pack())
    while True:
        WRITE_PHYSICAL_LAYER(link, frame.pack())
        acklink, ackpacked = READ_PHYSICAL_LAYER()
        ackframe.unpack(ackpacked)
        if ackframe.type == FrameType.DLL_ACK:
            break

Detecting Frame Corruption - Receiver

Receiver validates checksum
Returns ACK if the data is correct; otherwise NACK

frame = Frame(FrameType.DLL_DATA)              #create frame as DLL_DATA
while True:
    link, packed = READ_PHYSICAL_LAYER()
    frame.unpack(packed)
    checksum = frame.checksum                   #temporary store the frame checksum
    frame.checksum = 0                          #must reset checksum as part of CRC calculation as part of the header.
    if checksum == crc16(frame.pack()):        #if it matches.
        WRITE_NETWORK_LAYER(frame.data)         #data is writen
        frame.type = FrameType.DLL_ACK       #DLL_ACK frame constructed if checksum is correct.
    else:
        frame.type = FrameType.DLL_NACK         #DLL_NACK frame constructed if checksum is incorrect

    frame.len = 0
    WRITE_PHYSICAL_LAYER(link, frame.pack())

Normal Operation

The normal operation of frame and ACK exchange.

Operation With Error

Frame1 will be sent and NACK will be returned due to CRC failure, the frame will then be resent.

Detecting Frame Loss

Frames (DLLACK, DLLNACK) lost in transmission.
Sender may wait forever.
Question: How long should the sender wait for an acknowledgment?

Handling Frame Loss

Change to event-driven programming.
Handle time and specific event-driven actions.

Frame Loss - Sender Code

Frame is initiated
If network layer is read, STOP the layer to prepare for the next step
Frame assigned checksum and datatypes
Timer begins after frame is sent.

ESTIMATED_ROUND_TRIP_TIME = 20000  # microseconds
frame = Frame(FrameType.DLL_DATA)

def network_layer_ready():  # called iff ready
    frame.data = READ_NETWORK_LAYER()
    STOP_NETWORK_LAYER()
    frame.type = FrameType.DLL_DATA
    frame.len = len(frame.data)
    frame.checksum = 0
    frame.checksum = crc16(frame.pack())
    link = 1
    WRITE_PHYSICAL_LAYER(link, frame.pack())
    start_timer(ESTIMATED_ROUND_TRIP_TIME)

Cont. Sender Code

If the physical layer is ready, timer is stopped
Frame unpacked of acknowledgement
If the ACK is correct, the network layer may start.
If incorrect, write physical layer and restart timer.

def physical_layer_ready():  # frame arrived
    stop_timer()
    ackframe = Frame(FrameType.DLL_DATA)
    link, packed = READ_PHYSICAL_LAYER()
    frame.unpack(packed)
    if ackframe.type == FrameType.DLL_ACK:
        START_NETWORK_LAYER()
    else:
        WRITE_PHYSICAL_LAYER(link, frame.pack())
        start_timer(ESTIMATED_ROUND_TRIP_TIME)

Cont. Sender Code

If timer expires, the physical layer continues.

def timer_has_expired():  # a timeout
    link = 1
    WRITE_PHYSICAL_LAYER(link, frame.pack())
    start_timer(ESTIMATED_ROUND_TRIP_TIME)

Operation with Frame Loss

Timeout for ACK will commence if frame is lost.