TCP Flow Control

TCP Flow Control. Computer Networks (23CSE153). 1.

Transport Layer: Introduction to Transport Layer Services, UDP Protocol, Principles of Reliable Data Transfer - Stop – N – Wait protocol, Sliding Window Concepts – Go Back N Protocol, TCP Features, Header, Connection Management, Flow Control, Error Control and Congestion Control..

2. Introduction. TCP uses a sliding window protocol without selective or negative acknowledgments. Selective acknowledgments would let the protocol say it’s missing a range of bytes. TCP can only say that it has received “up to byte N”. The protocol has no way to specify a negative acknowledgment. It can only say what has been received Concepts same as discussed earlier, with some differences.

As discussed before, flow control balances the rate a producer creates data with the rate a consumer can use the data. TCP separates flow control from error control. TCP to the receiving TCP, and from the receiving TCP up to the receiving process (paths 1, 2, and 3). Flow control feedbacks, however, are traveling from the receiving TCP to the sending TCP and from the sending TCP up to the sending process (paths 4 and 5)..

The send window in TCP is similar to the one used with the Selective-Repeat protocol, but with some differences: One difference is the nature of entities related to the window. The window size in SR is the number of packets, but the window size in TCP is the number of bytes. Although actual transmission in TCP occurs segment by segment, the variables that control the window are expressed in bytes. The second difference is that, in some implementations, TCP can store data received from the process and send them later, but we assume that the sending TCP is capable of sending segments of data as soon as it receives them from its process. Another difference is the number of timers. The theoretical Selective-Repeat protocol may use several timers for each packet sent, but as mentioned before, the TCP protocol uses only one timer..

5. The first difference is that TCP allows the receiving process to pull data at its own pace. This means that part of the allocated buffer at the receiver may be occupied by bytes that have been received and acknowledged, but are waiting to be pulled by the receiving process. The receive window size is then always smaller than or equal to the buffer size. The receive window size determines the number of bytes that the receive window can accept from the sender before being overwhelmed (flow control). In other words, the receive window size, normally called rwnd, can be determined as: rwnd = buffer size - number of waiting bytes to be pulled The second difference is the way acknowledgments are used in the TCP protocol. The acknowledgement in SR is selective, defining the uncorrupted packets that have been received. The major acknowledgment mechanism in TCP is a cumulative acknowledgment announcing the next expected byte to receive (in this way TCP looks like GBN. The new version of TCP, however, uses both cumulative and selective acknowledgments..

Receiver Window. [image] Next byte to be pulled by the process 200 201 Next byte expected to be received 260 261 Bytes that have already been pulled by the process Bytes received and acknowledged, waitin to be consumed Ky process Bytes that can be received from sender Receive window size (rwnd) 300 301 Bytes that cannot be received from sender Allocated buffer a. Receive window and allocated buffer.

Opening and Closing Window. [image] Left wall b. Opening and closing Ot receive Window Right wall.

Example. [image] Therefore, only one window at each = 800 Size = 101 Client 901 side is shown. seqNo: 100 SYN + ACK seq No: I OOO ackNo: 101 : 800 ACK ackNo: 1001 rwnd : 2000 Data seqNo: 101 Data: 200 bytee ackNo; 301 : 600 Server 101 Send -w'indow is Set. Size = 800 201_ _ Sender sends 200 bytes. Size = 600 Bytes acknowledged, window Closes. Size = 600 901 Sender sends 300 bytes. Size = 400 Receive window is set. — 600 rwnd — 301 200 bytes received, window Closes. seqNo: Yata: 300 byték ACK ackNo: 601 rwnd: 400 ac o: 60 rwnd : 600 60 1 _ 400 1001 60 1 1001 Window closes and opens. Sire 601 W indow ope 300 bytes received, I oo bytes consumed. nvnd = 600 200 bytes consumed, window opens. 1201 :.

Shrinking of Windows. The receive window cannot shrink. The send window can shrink if the receiver defines a value for rwnd that results in shrinking the window. Some implementations do not allow shrinking of the send window. The limitation does not allow the right wall of the send window to move to the left. In other words, the receiver needs to keep the following relationship between the last and new acknowledgment and the last and new rwnd values to prevent shrinking of the send window. The left side of the inequality represents the new position of the right wall with respect to the sequence number space; the right side shows the old position of the right wall. The relationship shows that the right wall should not move to the left. The inequality is a mandate for the receiver to check its advertisement. The inequality is valid only if Sf < Sn; we need to remember that all calculations are in modulo 232..

Application may read the data at different speeds and at different times So, depending on when and how fast the application reads the data, the receiver’s window size may change So even if the receiver current window size is W bytes and the receiver receives and acknowledges p bytes, the window size may not be reset to W, it may still be only W – p until the application picks up the data.

This can be data sent from receiver to sender in the other direction, or ack’s for the data received from the sender Sender uses this advertised window size instead of a fixed value Window size (also called advertised window) is continuously changing, = current free buffer space at receiver Can go to zero; sender not allowed to send anything! Naïve implementations can cause silly window syndrome.

Silly Window Syndrome. The problem is called so because-.

Syndrome Created by the Sender. The sending TCP may create a silly window syndrome if it is serving an application program that creates data slowly, for example, 1 byte at a time. The application program writes 1 byte at a time into the buffer of the sending TCP. If the sending TCP does not have any specific instructions, it may create segments containing 1 byte of data. The result is a lot of 41-byte segments that are traveling through an internet. Solution: Nagle alg.

Nagle’s Algorithm. Nagle’s algorithm is an algorithm used in implementations of TCP/IP that controls traffic congestion on a network. Nagle’s algorithm limits transmission of small datagrams and controls the size of the TCP sending window. The algorithm increases the efficiency of routers by reducing the latency of the routing process. Nagle’s algorithm suggests- Sender should send only the first byte on receiving one byte data from the application. Sender should buffer all the rest bytes until the outstanding byte gets acknowledged. In other words, sender should wait for 1 RTT. After receiving the acknowledgement, sender should send the buffered data in one TCP segment. Then, sender should buffer the data again until the previously sent data gets acknowledged..

Syndrome Created by the Receiver. The receiving TCP may create a silly window syndrome if it is serving an application program that consumes data slowly, for example, 1 byte at a time. Suppose that the sending application program creates data in blocks of 1 kilobyte, but the receiving application program consumes data 1 byte at a time. Also suppose that the input buffer of the receiving TCP is 4 kilobytes. The sender sends the first 4 kilobytes of data. The receiver stores it in its buffer. Now its buffer is full. It advertises a window size of zero, which means the sender should stop sending data.

The receiving application reads the first byte of data from the input buffer of the receiving TCP. Now there is 1 byte of space in the incoming buffer. The receiving TCP announces a window size of 1 byte, which means that the sending TCP, which is eagerly waiting to send data, takes this advertisement as good news and sends a segment carrying only 1 byte of data. The procedure will continue. One byte of data is consumed and a segment carrying 1 byte of data is sent. Again we have an efficiency problem and the silly window syndrome.

Two solutions have been proposed to prevent the silly window syndrome created by an application program that consumes data more slowly than they arrive Clark’s solution is to send an acknowledgment as soon as the data arrive, but to announce a window size of zero until either there is enough space to accommodate a segment of maximum size or until at least half of the receive buffer is empty. The second solution is to delay sending the acknowledgment. This means that when a segment arrives, it is not acknowledged immediately. The receiver waits until there is a decent amount of space in its incoming buffer before acknowledging the arrived segments. The delayed acknowledgment prevents the sending TCP from sliding its window. After the sending TCP has sent the data in the window, it stops. This kills the syndrome..

Delayed acknowledgment also has another advantage: it reduces traffic. The receiver does not have to acknowledge each segment. However, there also is a disadvantage in that the delayed acknowledgment may result in the sender unnecessarily retransmitting the unacknowledged segments. The protocol balances the advantages and disadvantages. It now defines that the acknowledgment should not be delayed by more than 500 ms..

Error control. Checksum Each segment includes a checksum field, which is used to check for a corrupted segment. If a segment is corrupted, as detected by an invalid checksum, the segment is discarded by the destination TCP and is considered as lost. TCP uses a 16-bit checksum that is mandatory in every segment. Acknowledgment TCP uses acknowledgments to confirm the receipt of data segments. Control segments that carry no data, but consume a sequence number, are also acknowledged. ACK segments are never acknowledged..

Cumulative Acknowledgment. TCP was originally designed to acknowledge receipt of segments cumulatively. The receiver advertises the next byte it expects to receive, ignoring all segments received and stored out of order. This is sometimes referred to as positive cumulative acknowledgment, or ACK. The word positive indicates that no feedback is provided for discarded, lost, or duplicate segments. The 32-bit ACK field in the TCP header is used for cumulative acknowledgments, and its value is valid only when the ACK flag bit is set to 1..

Selective Acknowledgment. More and more implementations are adding another type of acknowledgment called selective acknowledgment, or SACK. A SACK does not replace an ACK, but reports additional information to the sender. A SACK reports a block of bytes that is out of order, and also a block of bytes that is duplicated, i.e., received more than once. However, since there is no provision in the TCP header for adding this type of information, SACK is implemented as an option at the end of the TCP header..

When Acks are Sent?. 14. Suppose A is sending data to B TCP acks are cumulative, acknowledges the longest contiguous sequence from the start that is received If ISN of A = 1000, A has sent 4 segments with sequence numbers 1001 (why not 1000?), 1600, 2800, and 3100, and B has received the 1st , 2nd and 4th segments only, then Longest contiguous sequence from start received is byte numbers1001 to 2799 TCP will ack with ack no. = 2800 (next byte expected) Segment 1 and 2 are received in-order, Segment 3 is a missing segment, Segment 4 is a segment received out-of order Note that receiver does not know there is one missing segment, it just knows there is at least one.

When Acks are Sent?. B sends an acknowledgement if/when If B has data to send to A, always piggyback the ack for the data received from A (ACK flag set, byte no. of next byte to expect put in Acknowledgement Number field If B has no data to send, receives a segment from A in-order (sequence number = next sequence number expected) If all previous in-order segments are acknowledged, delay sending the acknowledgement until one more segment arrives or a time elapses (typically 500 milliseconds), then send If B gets an out-of-order segment having a higher than expected sequence number, send an ack with next sequence number expected If the receiver gets a missing segment which extends the longest contiguous byte stream from the start that it has received, send an ack with the next sequence number to expect If a duplicate segment arrives, discard the segment but send an ack with the next sequence number expected.

Retransmission. The heart of the error control mechanism is the retransmission of segments. When a segment is sent, it is stored in a queue until it is acknowledged. When the retransmission timer expires or when the sender receives three duplicate ACKs for the first segment in the queue, that segment is retransmitted..

Retransmission after RTO The sending TCP maintains one retransmission time-out (RTO) for each connection. When the timer matures, i.e. times out, TCP resends the segment in the front of the queue (the segment with the smallest sequence number) and restarts the timer. Note that again we assume Sf < Sn. We will see later that the value of RTO is dynamic in TCP and is updated based on the round-trip time (RTT) of segments. RTT is the time needed for a segment to reach a destination and for an acknowledgment to be received.

Retransmission after Three Duplicate ACK Segments The previous rule about retransmission of a segment is sufficient if the value of RTO is not large. To expedite service throughout the Internet by allowing senders to retransmit without waiting for a time out, most implementations today follow the three duplicate ACKs rule and retransmit the missing segment immediately. This feature is called fast retransmission. In this version, if three duplicate acknowledgments (i.e., an original ACK plus three exactly identical copies) arrive for a segment, the next segment is retransmitted without waiting for the time-out..

Out-of-Order Segments. TCP implementations today do not discard out-of-order segments. They store them temporarily and flag them as out-of-order segments until the missing segments arrive. Note, however, that out-of-order segments are never delivered to the process. TCP guarantees that data are delivered to the process in order..

[image] Time-out occurred. Resend the first segment in the queue. Reset the timer. A corrupted ACK arnved. Discard it. A chunk of bytes is accepted from the process. Make a segment (seqNo Sn)- Store a copy of the segrnent in the queue and send it. If it is the first segment in the queue, start the timer. Note: All calculations are in modulo 232 Window full? Sets — n — Sn + data length. Start [falsel Ready [truel Blocking Time-out occurred. Resend the segment in front of the queue. Reset the timer. A corrupted ACK Discard it. A duplicate ACK arrived. Set dupNo dupNo + 1 - If (dupNo = 3) resend the segment in front Of the queue, restart the tirner, and set dupNo = O. An error-free ACK arrived that acknowledges the segment in front of the queue. Slide the window (Sf = ackNo) and adjust window size. Remove the segment from the queue. If any segment is left in the queue, restart the timer. A duplicate ACK arrived. Set dupNo = dupNo + l. If (dupNo = 3) resend the segment in front of the queue, restart the timer, and set dupNo O..

[image] Note: All calculations are in modulo 232. A request for delivery of k bytes of data from process carne. Deliver the data. Slide the window and adjust window size- An error-free duplicate seament or an error-free segment with sequence number outside window arrived. Discard the segment. Send an ACK with ackNo equal to the sequence number of expected segrnent (duplicate ACK). An expected error-free segment arrived. Buffer the message. Rn = Rn + data length. If the ACK-delaying timer is running, stop the timer and send a cumulative ACK. Otherwise, start the ACK-delaying timer. Start ACK-delaying timer expired. Send the delayed ACK. Ready An error-free, but out-of- order segment arrived. _l Store the segment if not duplicate. Send an ACK with ackNo equal to the sequence number Of expected segment (duplicate ACK). A corrupted segment arrived. Discard the segrnent..

Normal Operation of TCP. When the client receives the first segment from the server, it does not have any more data to send; it needs to send only an ACK segment. The acknowledgment needs to be delayed for 500 ms to see if any more segments arrive. When the ACK-delaying timer matures, it triggers an acknowledgment. This is because the client has no knowledge of whether other segments are coming; it cannot delay the acknowledgment forever. When the next segment arrives, another ACK delaying timer is set. However, before it matures, the third segment arrives. The arrival of the third segment triggers another acknowledgment..

Some scenarios Normal operation. [image] Start ms Time-out Start < 500 ms Rule 1 Rule 2 Client seq: 1201-1400 Ack: Ack: 5001 Ack: 7001 seq: Rule I Ack: 1401 seq: 5001-6000 Rule I Ack: 1401 Seq: 6001—7000 Ack: 1401 Rule 3 Stop Time Rule I Time.

Lost Segment. [image] Server RTO Start Stop Start Ack: 701 Time-out/restart Ack: 901 Stop Client seq: 501-600 Ack: x seq: 601-700 seq: 701-800 Ack: x seq: 801-900 Resent seq: 701-800 Ack: x • 701 Ack. Lost Receiver buffer Rule 3 Rule 4 Out of order Rule 5 Time Time.

the sender sends segments 1 and 2, which are acknowledged immediately by an ACK (rule 3). The receiver immediately sends an acknowledgment to the sender displaying the next byte it expects (rule 4) When the third segment times out, the sending TCP resends segment 3, which arrives this time and is acknowledged properly (rule 5)..

Fast Retransmission. [image] RTO timer Start Stop Start Restart Original First duplicate Second duplicate duplicate Client seq: 101-200 Ack: x seq: 201-300 Ack: x Seq: 301—400 Ack: x seq: 401-500 Ack: x seq: 501-600 ACk: x seq: 601-700 Ack: x seq: 301-400 Ack: x Resent Lost retransmission Stop Server Ack: 301 Ack•. 301 Ack•. 301 Ack: 301 Ack: 701 Receiver buffer All in order Time Time.

32. Delayed Segment. TCP uses the services of IP, which is a connectionless protocol. Each IP datagram encapsulating a TCP segment may reach the final destination through a different route with a different delay. Hence TCP segments may be delayed. Delayed segments sometimes may time out and be resent. If the delayed segment arrives after it has been resent, it is considered a duplicate segment and discarded..

Duplicate segment. A duplicate segment can be created, for example, by a sending TCP when a segment is delayed and treated as lost by the receiver. Handling the duplicated segment is a simple process for the destination TCP. The destination TCP expects a continuous stream of bytes. When a segment arrives that contains a sequence number equal to an already received and stored segment, it is discarded. An ACK is sent with ackNo defining the expected segmen.

Automatically Corrected Lost Segment. In the TCP acknowledgment mechanism, a lost acknowledgment may not even be noticed by the source TCP. TCP uses cumulative acknowledgment. We can say that the next acknowledgment automatically corrects the loss of the previous acknowledgment..

Lost Acknowledgment Corrected by Resending a Segment.

Deadlock Created by Lost Acknowledgment. There is one situation in which loss of an acknowledgment may result in system deadlock. T his is the case in which a receiver sends an acknowledgment with rwnd set to 0 and requests that the sender shut down its window temporarily. After a while, the receiver wants to remove the restriction; however, if it has no data to send, it sends an ACK segment and removes the restriction with a nonzero value for rwnd. A problem arises if this acknowledgment is lost. The sender is waiting for an acknowledgment that announces the nonzero rwnd. The receiver thinks that the sender has received this and is waiting for data. This situation is called a deadlock; each end is waiting for a response from the other end and nothing is happening. A retransmission timer is not set. To prevent deadlock, a persistence timer was designed.

Thank You!!!. 35.