CS3873 UDP Connection

Introduction to Reliable Data Transfer

  • The study of reliable data transfer ($rdt$) centers on the techniques used to ensure that data packets are delivered in order, without errors, and without loss, even when the underlying physical or network layer is unreliable (such as the Internet Protocol / IP).

  • This involves creating a service abstraction that provides a bit-error-free, non-lossy channel to the application layer, despite the complexities of the lower-level transport.

Data Transmission Principles

  • Fundamental Objectives: Achieving reliability requires mechanisms for error detection, receiver feedback, retransmission, and sequence numbering.

  • UDP Structure Overview:

    • The User Datagram Protocol (UDP) utilizes an $8$-byte ($64$-bit) fixed-size header.

    • Fields (each $16$ bits / $2$ bytes):

      • Source Port: Identifies the sending process.

      • Destination Port: Identifies the receiving process.

      • Length: The total length of the segment (header plus data).

      • Checksum: Used for error detection during transmission.

    • Efficiency: The minimal overhead of UDP allows for low-latency transmission, common in real-time applications where speed is prioritized over strict reliability.

Checksums in Data Transfer

  • Purpose of Checksums: To detect "bit flips" or alterations in the segment that occur during transit over physical media or routers.

  • One's Complement vs. Two's Complement:

    • Two's Complement ($2$'s C):

      • Standard for signed integer arithmetic in modern CPUs (e.g., Java int).

      • To find the negative value of $x$: Invert all bits of $x$ and add $1$.

      • Example: If $3$ is 0011, $-3$ is 1100 + 1 = 1101.

    • One's Complement ($1$'s C):

      • Historically used in networking (like UDP and IP checksums) because it treats the carry-out differently, aiding in better error detection across $16$-bit boundaries.

      • To find the negative value: Simply flip every bit.

      • Example: If $3$ is 0011, then $-3$ in $1$'s C is 1100.

      • Limitations:

        • Two representations for zero: Positive zero (0000) and Negative zero (1111).

        • A $k$-bit range covers $[-(2^{k-1}-1), 2^{k-1}-1]$. For $4$ bits, this is $-7$ to $+7$.

Summation and its Algorithms

  • Two's Complement Addition:

    • Add the numbers normally using binary arithmetic. If there is a carry-out bit beyond the most significant bit (MSB), it is typically discarded in standard CPU arithmetic.

    • Example: Adding $-3$ (1101) and $-4$ (1100) results in 1 1001. Discarding the carry yields 1001 ($-7$).

  • One's Complement Addition (End-Around Carry):

    • When summing values, any carry-out from the MSB is not discarded. Instead, it is "wrapped around" and added to the least significant bit (LSB).

    • This "End-Around Carry" ensures that every bit has the potential to influence the final sum, improving the probability of detecting multiple bit errors.

Calculation of Checksum in UDP Segment

  • Step-by-Step Methodology:

    1. Segmentation: Split the entire UDP segment (header and data) into a sequence of $16$-bit integers.

    2. Padding: If the total byte count is odd, append a byte of zeros to the end to complete the final $16$-bit word for calculation purposes.

    3. Summation: Add all $16$-bit words together using One's Complement arithmetic (perform the end-around carry for every addition).

      • Note: The checksum field itself is treated as all zeros during this initial sum.

    4. Final Bit-Flip: After summing all words, take the One's Complement of the final sum (flip all bits). This result is stored in the UDP checksum field.

Data Reception and Verification

  • Verification Process:

    • The receiver sums all $16$-bit words of the segment, including the transmitted checksum field.

    • The All-Ones Test:

      • If no errors occurred, the sum should result in a string of $16$ ones (1111 1111 1111 1111).

      • If any bit in the sum is zero, an error hit the segment during transmission.

  • Receiver Feedback Mechanisms:

    • Positive Acknowledgment (ACK): Receiver explicitly tells the sender the packet was received correctly.

    • Negative Acknowledgment (NAK): Receiver tells the sender a packet had errors; this triggers an immediate retransmission.

    • Sequence Numbers: Essential to handle duplicate packets. If an ACK is lost and the sender retransmits, the receiver uses the sequence number to determine if the packet is new or a duplicate.

Reliable Data Transfer (rdt) Evolution

  • rdt 1.0: Assumes a perfectly reliable underlying channel.

  • rdt 2.0: Adds checksums for error detection and ACKs/NAKs for feedback (Stop-and-Wait protocol).

  • rdt 3.0 (The Alternating-Bit Protocol): Introduces timers to handle packet loss. If an ACK doesn't arrive within a specific timeout, the sender retransmits. This solves the "deadlock" of waiting forever for a lost packet.

  • Pipelining for Performance:

    • Stop-and-Wait is inefficient ($U_{sender} = \frac{L/R}{RTT + L/R}$).

    • To increase utilization, protocols like Go-Back-N (GBN) and Selective Repeat (SR) allow the sender to send multiple packets without waiting for immediate ACKs.

Conclusion and Design Philosophy

  • Using One's Complement is a deliberate trade-off. While Two's Complement is faster for hardware arithmetic, One's Complement is mathematically more robust for detecting errors that occur in the structure of internet packets.

  • These principles form the bedrock of the Transmission Control Protocol (TCP), which builds on these simple checksum and feedback loops to provide a robust, byte-stream oriented transmission service.