Problem 37 - Computer Networking: A Top-Down Approach

Question

Compare GBN, SR, and TCP (no delayed ACK). Assume that the timeout values for all three protocols are sufficiently long such that 5 consecutive data segments and their corresponding ACKs can be received (if not lost in the channel) by the receiving host (Host B) and the sending host (Host A) respectively. Suppose Host A sends 5 data segments to Host B, and the 2 nd segment (sent from \(\mathrm{A}\) ) is lost. In the end, all 5 data segments have been correctly received by Host B. a. How many segments has Host A sent in total and how many ACKs has Host B sent in total? What are their sequence numbers? Answer this question for all three protocols. b. If the timeout values for all three protocol are much longer than 5 RTT, then which protocol successfully delivers all five data segments in shortest time interval?

Step-by-Step Solution

Answer

GBN: 10 segments, 9 ACKs; SR: 6 segments, 5 ACKs; TCP: 6 segments, 5 ACKs. SR delivers segments fastest.

Step 1: Understanding GBN Protocol

In Go-Back-N (GBN), if a segment is lost, all subsequent segments must be resent after a timeout. Initially, Host A sends segments 1 to 5. Segment 2 is lost, so Host B only acknowledges segment 1 (ACK for 1). Upon timeout (since ACK for 2 is not received), Host A resends segments 2 to 5. All are successfully acknowledged by Host B. Total segments sent by Host A: 10 (initial 5 + resend 5). Total ACKs sent by Host B: 9, one for each received segment.

Step 2: Understanding SR Protocol

In Selective Repeat (SR), only the lost segment needs to be resent. Host A sends segments 1 to 5. Host B receives 1, acknowledges it (ACK for 1), notices the loss of 2, and then receives 3, 4, and 5, sending ACKs for 3, 4, and 5. Upon timeout for segment 2, Host A resends just segment 2, which is then acknowledged. Total segments sent by Host A: 6 (initial 5 + resend 2). Total ACKs sent by Host B: 5.

Step 3: Understanding TCP Protocol

TCP without delayed ACK means it acknowledges every segment received. Host A sends segments 1 to 5. Segment 2 is lost, so Host B responds with ACK 1, then ACK 1 after receiving segments 3, 4, 5 (cumulative ACK). Host A resends segment 2 upon timeout. After receiving segment 2, Host B sends ACK 5 to indicate all are received. Total segments sent by Host A: 6 (initial 5 + resend 2). Total ACKs sent by Host B: 5 (multiple ACK 1's then ACK 5).

Step 4: Analyzing Time Efficiency

For time efficiency, both SR and TCP can potentially deliver the data in the shortest time. However, TCP may wait for a duplicate ACK threshold before resending segment 2. Assuming immediate retransmission after timeout, SR is quickest as it minimizes resend operations compared to GBN.

Key Concepts

Go-Back-N (GBN)

Go-Back-N (GBN) is a reliable data transport protocol used in computer networks, specifically tailored to manage the transmission and acknowledgment of data segments. In GBN, only the last in-order acknowledgment received by the sender dictates the next data segment sequence to send. Here's how it works in practice:

• Host A sends several data segments sequentially to Host B.
• Host B acknowledges the last received in-order segment.
• If a segment is lost, Host B stops sending acknowledgments for subsequent packets.
• This prompts Host A to timeout and resend the sequence starting from the lost segment.

Using this method guarantees reliable data delivery but can lead to inefficiencies, especially if the network experiences frequent packet losses. The need to retransmit potentially long sequences of segments can become costly in terms of time and resources.

Selective Repeat (SR)

Selective Repeat (SR) is another protocol for reliable data transmission, designed to optimize the efficiency problems found in Go-Back-N. Unlike GBN, Selective Repeat allows individual acknowledgment of each packet.

• When a segment is lost, only that segment is sent again, sparing other correctly received segments from being resent.
• Both Host A and Host B maintain windows of accepted sequence numbers, allowing them to track out-of-order packets.
• This independent acknowledgment reduces unnecessary data transmission.
• The complexity increases due to the additional storing and ordering of packets at the receiver side.

SR tends to be more efficient in networks with higher latency or packet loss, as it minimizes redundant retransmissions.

Transmission Control Protocol (TCP)

Transmission Control Protocol (TCP) is the foundation for reliable communication on the internet, balancing between the need for reliability and efficiency. While TCP offers several features, we'll focus on its behavior without delayed acknowledgments in this context.

• TCP is inherently connection-oriented, meaning it ensures all data sent by the sender is received and acknowledged by the receiver.
• TCP uses a cumulative acknowledgment system, which acknowledges the last sequence of segments received in order.
• Lost segments trigger a retransmission either by timeout or detecting several duplicate acknowledgments.
• This approach prioritizes complete data receipt but may lead to additional delays if the network conditions cause frequent segment losses.

Despite its complexity, TCP remains the protocol of choice for applications requiring reliable data transfer.

Data Segments

Data segments are the fundamental units exchanged between networks in transport layer protocols like GBN, SR, and TCP. Each segment carries a portion of the data stream from the sender to the receiver.

• The sender breaks down the data into smaller packets or segments.
• Each segment carries a sequence number to track its position in the overall data stream.
• In protocols like GBN and SR, the handling of these sequence numbers affects how segments are retransmitted or acknowledged following errors.
• Efficient segment transmission and management are key to optimizing network performance and reducing latency.

Correctly sequencing and acknowledging these segments ensures accurate data delivery over networks, especially over unreliable channels.

Acknowledgments (ACKs)

Acknowledgments (often abbreviated as ACKs) are responses sent by the receiver to inform the sender that a data segment has been received successfully. They are crucial for maintaining communication reliability in protocols such as TCP, GBN, and SR.

• ACKs confirm the reception of segments and provide feedback to the sender about the state of data transmission.
• In GBN, ACKs may only confirm the last contiguous reception, prompting potential retransmissions of multiple segments if an error occurs.
• SR sends individual ACKs for each data segment, which precision guides retransmissions for only the segments that are lost.
• TCP employs a mix of cumulative ACKs and duplicate ACKs to handle segment retransmission efficiently.

ACKs form the backbone of error control, enabling reliable communication across potentially faulty network channels.