Charles M. Kozierok The TCP-IP Guide

Подождите немного. Документ загружается.

The Main Weakness of the TCP Sliding Window System: Handling Non-Contiguous

Acknowledgments

Even the most elegant technique has certain weaknesses, however. In the case of the TCP

acknowledgment system, it is the inability to effectively deal with the receipt of non-

contiguous TCP segments. The Acknowledgment Number specifies that all sequence

numbers lower than its value have been received by the device sending that number. If we

receive bytes with sequence numbers in two non-contiguous ranges, there is no way to

specify this with a single number.

This can lead to potentially serious performance problems, especially on internetworks that

operate at high speed or over inherently unreliable physical networks. To see what the

problem is, let's go back to the example in the previous topic. There, the server sent four

segments, and received back an acknowledgment with an Acknowledgment Number value

of 201. Segment #1 and Segment #2 were thus considered acknowledged. They would be

removed from the retransmission queue, and this would also allow the server's send

window to slide 80+120 bytes to the right, allowing 200 more bytes of data to be sent.

However, let's again imagine that Segment #3, starting with sequence number 201, “disap-

pears”. Since the client never receives this segment, it can never send back a

acknowledgment with an Acknowledgment Number higher than 201. This causes the

sliding window system to get “stuck”. The server can continue to send additional segments

until it fills up the client's receive window, but until the client sends another acknowl-

edgment, the server's send window will not slide.

The other problem we saw is that if Segment #3 gets lost, the client has no way to tell the

server that it has in fact received any subsequent segments. It's entirely possible that the

client does receive the server's Segment #4, and in addition, later segments sent until the

window filled up. But the client can't send an acknowledgment with a value of 501 to

indicate receipt of Segment #4, because this implies receipt of Segment #3 as well.

Note: In some cases the client may still send an acknowledgment upon receipt of

Segment #4, but only containing a repeated acknowledgment of the bytes up to

the end of Segment #2. See the topic on congestion avoidance for an explanation.

And here we see the drawback of the single-number, cumulative acknowledgment system

of TCP. We could imagine a “worst-case scenario” in which the server is told it has a

window of 10,000 bytes, and sends 20 segments of 500 bytes each. The first segment is

lost and the other 19 received. But since it is the first segment that never showed up, none

of the other 19 segments can be acknowledged!

Key Concept: TCP’s acknowledgment system is cumulative. This means that if a

segment is lost in transit, no subsequent segments can be acknowledged until the

missing one is retransmitted and successfully received.

Policies For Dealing with Retransmission When Unacknowledged Segments Exist

This then leads to an important question: how do we handle retransmissions when there

are subsequent segments outstanding beyond the lost segment? In our example above,

when the server experiences a retransmission timeout on Segment #3, it must decide what

to do about Segment #4, when it simply doesn't know whether or not the client received it.

In our “worst-case scenario”, we have 19 segments that may or may not have shown up at

the client after the first one that was lost.

We have two different possible ways to handle this situation.

Retransmit Only Timed-Out Segments

This is the more “conservative”, or if you prefer, “optimistic” approach. We retransmit only

the segment that timed out, hoping that the other segments beyond it were successfully

received.

This method is best if the segments after the timed-out segment actually showed up. It

doesn't work so well if they did not. In the latter case, each segment would have to time out

individually and be retransmitted. Imagine that in our “worst-case scenario” that all 20 500-

byte segments were lost. We would have to wait for Segment #1 to time out and be retrans-

mitted. This retransmission would be acknowledged (hopefully) but then we would get stuck

waiting for Segment #2 to time out and be resent. We would have to do this many times.

Retransmit All Outstanding Segments

This is the more “aggressive” or “pessimistic” method. Whenever a segment times out we

re-send not only it but all other segments that are still unacknowledged.

This method ensures that any time there is a hold up with acknowledgments, we “refresh”

all outstanding segments to give the other device an extra chance at receiving them in case

they too were lost. In the case where all 20 segments were lost, this saves substantial

amounts of time over the “optimistic” approach. The problem here is that these retransmis-

sions may not be necessary. If the first of 20 segments was lost and the other 19 were

actually received, we'd be re-sending 9,500 bytes of data (plus headers) for no reason.

There Is No Ideal Answer

Since TCP doesn't know whether these other segments showed up, it cannot know which

method is better. It must simply make an “executive decision” to use one approach or the

other, and hope for the best. In the example of the previous topic, as shown in Figure 223, I

demonstrated the “conservative” approach—only the lost segment of the file was retrans-

mitted. In contrast, Figure 224 shows the “aggressive” approach to retransmission.

Key Concept: There are two approaches to handling retransmission in TCP. In the

more “conservative” approach, only the segments whose timers expire are retrans-

mitted; this saves bandwidth but may cause performance degradation if many

segments in a row are lost. The alternative is that when a segment’s retransmission timer

expires, both it and all subsequent unacknowledged segments are retransmitted. This

provides better performance if many segments are lost but may waste bandwidth on unnec-

essary retransmissions.

A Better Solution: Selective Acknowledgment (SACK)

It is in fact this lack of knowledge about non-contiguous segments that is the core of the

problem with non-contiguous segments. The solution is to extend the basic TCP sliding

window algorithm with an optional feature that allows a device to acknowledge non-

contiguous segments individually. This feature, introduced in RFC 1072 and refined in RFC

2018, is called TCP selective acknowledgment, abbreviated SACK.

To use SACK, the two devices on the connection must both support the feature, and must

enable it by negotiating the Selective Acknowledge Permitted (SACK-Permitted) option in

the SYN segment they use to establish the connection. Assuming this is done, either device

is then permitted to include in a regular TCP segment a Selective Acknowledgment (SACK)

option. This option contains a list of sequence number ranges of segments of data that

have been received but have not been acknowledged since they are non-contiguous.

Each device modifies its retransmission queue so that each segment includes a flag that is

set to 1 if the segment has been selectively acknowledged—the SACK bit. The device then

uses a modified version of the “aggressive” method above, where upon retransmission of a

segment all later segments are also retransmitted unless their SACK bits are set to 1.

For example, in our four-segment case, if the client receives Segment #4 but not Segment

#3, when it sends back a segment with an Acknowledgment Number field value of 201 (for

#1 and #2), it can include a SACK option that specifies “I have received bytes 361 through

500, but they are not yet acknowledged”. This can also be done in a second acknowl-

edgment segment if Segment #4 arrives well after #1 and #2. The server recognizes this as

the range of bytes for Segment #4, and turns on the SACK bit for Segment #4. When

Segment #3 is retransmitted, the server sees the SACK bit for Segment #4 on and does not

retransmit it. This is illustrated in Figure 225.

Figure 224: TCP “Aggressive” Retransmission Example

This example is the same as that of Figure 223 except that here the server is taking an “aggressive” approach

to retransmitting lost segments. When segment #3 times out, both #3 and #4 are retransmitted and their

retransmission timers restarted. (In this case #4 already arrived so this extra transmission was not useful.)

Ack

Ack Num = 201

Client Server

1. Se nd Part 1

80 Bytes (1 to 80)

4. Receive First 2 Segments,

Send Acknowledgment

File Part 1

Seq Num = 1

6. Receive Ack For Reply

6. Receive Part 4 of File; Cannot

Send Acknowledgment

7. Receive Ack For Parts 1 & 2

8. Timeout For Part 3;

Retransmit Part 3 & 4,

Restart Timer for Each

9. Receive Parts 3 and 4 of File;

Discard duplicate Part 4, Send

Acknowledgment for Parts 3 & 4

2. Se nd Part 2

120 Bytes (81 to 200)

3. Se nd Part 3

160 Bytes (201 to 360)

5. Se nd Part 4

140 Bytes (361 to 500)

RCV .WND = 560

RCV .NXT = 201

80 120

File Part 2

Seq Num = 81

File Part 3

Seq Num = 201

File Part 4

Seq Num = 361

RCV .NXT = 1

RCV .WND = 560

Usable = 560

SND.WND = 560

SND.UNA= 1

File Part 3

Seq Num = 201

RCV .WND = 560

RCV .NXT = 501

80 120 140160

...

Ack

Ack Num = 501

10. Receive Ack for Parts 3 & 4

Usable = 260

SND.NXT = 501

SND.WND = 560

140160

SND.UNA= 201

80 120

Usable = 60

SND.NXT = 501

SND.WND = 560

80 120 140160

SND.UNA= 1

RCV .WND = 560

RCV .NXT = 201

80 120 140???

Usable = 500

SND.NXT = 501

SND.WND = 560

SND.UNA= 501

80 120 140160

...

File Part 4

Seq Num = 361

After Segment #3 is retransmitted, the SACK bit for Segment #4 is cleared. This is done for

robustness, to handle cases where for whatever reason the client “changes its mind” about

having received Segment #4. The client should send an acknowledgment with an Acknowl-

edgment Number of 501 or higher, indicating “official” receipt of Segments #3 and #4. If this

does not happen, the server must receive another selective acknowledge for Segment #4 to

turn its SACK bit back on. Otherwise it will be automatically re-sent when its timer expires,

or when Segment #3 is retransmitted.

Key Concept: The optional TCP selective acknowledgment feature provides a more

elegant way of handling subsequent segments when a retransmission timer expires.

When a device receives a non-contiguous segment it includes a special Selective

Acknowledgment (SACK) option in its regular acknowledgment that identifies non-

contiguous segments that have already been received, even if they are not yet acknowl-

edged. This saves the original sender from having to retransmit them.

TCP Adaptive Retransmission and Retransmission Timer Calculations

Whenever a TCP segment is transmitted, a copy of it is also placed on the retransmission

queue. When the segment is placed on the queue, a retransmission timer is started for the

segment, which starts from a particular value and counts down to zero. It is this timer that

controls how long a segment can remain unacknowledged before the sender gives up,

concludes that it is lost and sends it again.

The length of time we use for retransmission timer is thus very important. If it is set too low,

we might start retransmitting a segment that was actually received, because we didn't wait

long enough for the acknowledgment of that segment to arrive. Conversely, if we set the

timer too long, we waste time waiting for an acknowledgment that will never arrive, reducing

overall performance.

Difficulties in Choosing the Duration of the Retransmission Timer

Ideally, we would like to set the retransmission timer to a value just slightly larger than the

round-trip time (RTT) between the two TCP devices, that is, the typical time it takes to send

a segment from a client to a server and the server to send an acknowledgment back to the

client (or the other way around, of course). The problem is that there is no such “typical”

round-trip time. There are two main reasons for this:

☯ Differences In Connection Distance: Suppose you are at work in the United States,

and during your lunch hour you are transferring a large file between your workstation

and a local server connection using 100 Mbps Fast Ethernet, at the same time you are

downloading a picture of your nephew from your sister's personal Web site—which is

connected to the Internet using an analog modem to an ISP in a small town near Lima,

Peru. Would you want both of these TCP connections to use the same retransmission

timer value? I certainly hope not!

Figure 225: TCP Retransmission With Selective Acknowledgment (SACK)

This is the example from Figure 223 and Figure 224, changed to use the optional selective acknowledge

feature. After receiving Parts 1, 2 and 4 of the file, the client sends an Acknowledgment for 1 and 2 that

includes a SACK for Part 4. This tells the server not to re-send Part 4 when Part 3’s timer expires.

Ack

Ack Num = 201

Client Server

1. Se nd Part 1

80 Bytes (1 to 80)

4. Receive First 2 Segments,

Send Acknowledgment

File Part 1

Seq Num = 1

6. Receive Ack For Reply

6. Receive Part 4 of File;

Send Ack with SACK for Part 4

7. Receive Ack For Parts 1 & 2

8. Timeout For Part 3 -

Retransmit 3 (but not 4)

9. Receive Part 3 of File,

Send Acknowledgment for 3 & 4

2. Se nd Part 2

120 Bytes (81 to 200)

3. Se nd Part 3

160 Bytes (201 to 360)

5. Se nd Part 4

140 Bytes (361 to 500)

RCV .WND = 560

RCV .NXT = 201

80 120

File Part 2

Seq Num = 81

File Part 3

Seq Num = 201

File Part 4

Seq Num = 361

RCV .NXT = 1

RCV .WND = 560

Usable = 560

SND.WND = 560

SND.UNA= 1

File Part 3

Seq Num = 201

RCV .WND = 560

RCV .NXT = 501

80 120 140160

...

Ack

Ack Num = 501

10. Receive Ack for Parts 3 & 4

Usable = 60

SND.NXT = 501

SND.WND = 560

80 120 140160

SND.UNA= 1

RCV .WND = 560

RCV .NXT = 201

80 120 140???

Usable = 500

SND.NXT = 501

SND.WND = 560

SND.UNA= 501

80 120 140160

...

Ack

Ack Num = 201

SACK = 361-500

7A. Receive SACK For Part 4

Usable = 260

SND.NXT = 501

SND.WND = 560

140160

SND.UNA= 201

80 120

SACK

☯ Transient Delays and Variability: The amount of time it takes to send data between

any two devices will vary over time due to various happenings on the internetwork:

fluctuations in traffic, router loads and so on. To see an example of this for yourself, try

typing “ping www.tcpipguide.com” from the command line of an Internet-connected PC

and you'll see how the reported times can vary.

Adaptive Retransmission Based on Round-Trip Time Calculations

It is for these reasons that TCP does not attempt to use a static, single number for its

retransmission timers. Instead, TCP uses a dynamic, or adaptive retransmission scheme.

TCP attempts to determine the approximate round-trip time between the devices, and

adjusts it over time to compensate for increases or decreases in the average delay. The

practical issues of how this is done are important, but are not covered in much detail in the

main TCP standard. RFC 2988, Computing TCP's Retransmission Timer

, discusses the

issue extensively.

Round-trip times can “bounce” up and down, as we have seen, so we want to aim for an

average RTT value for the connection. This average should respond to consistent

movement up or down in the RTT without overreacting to a few very slow or fast acknowl-

edgments. To allow this to happen, the RTT calculation uses a smoothing formula:

New RTT = (α * Old RTT) + ( (1-α) * Newest RTT Measurement)

Where “α” (alpha) is a smoothing factor between 0 and 1. Higher values of “α∀ (closer to 1)

provide better smoothing and avoiding sudden changes as a result of one very fast or very

slow RTT measurement. Conversely, this also slows down how quickly TCP reacts to more

sustained changes in round-trip time. Lower values of alpha (closer to 0) make the RTT

change more quickly in reaction to changes in measured RTT, but can cause “over-

reaction” when RTTs fluctuate wildly.

Acknowledgment Ambiguity

Measuring the round-trip time between two devices is simple in concept: note the time that

a segment is sent, note the time that an acknowledgment is received, and subtract the two.

The measurement is more tricky in actual implementation, however. One of the main

potential “gotchas” occurs when a segment is assumed lost and is retransmitted. The

retransmitted segment carries nothing that distinguishes it from the original. When an

acknowledgment is received for this segment, it's unclear as to whether this corresponds to

the retransmission or the original segment. (Even though we decided the segment was lost

and retransmitted it, it's possible the segment eventually got there, after taking a long time;

or that the segment got their quickly but the acknowledgment took a long time!)

This is called acknowledgment ambiguity, and is not trivial to solve. We can't just decide to

assume that an acknowledgment always goes with the oldest copy of the segment sent,

because this makes the round-trip time appear too high. We also don't want to just assume

an acknowledgment always goes with the latest sending of the segment, as that may artifi-

cially lower the average round-trip time.

Refinements to RTT Calculation and Karn's Algorithm

TCP's solution to round-trip time calculation is based on the use of a technique called

Karn's algorithm, after its inventor, Phil Karn. The main change this algorithm makes is the

separation of the calculation of average round-trip time from the calculation of the value to

use for timers on retransmitted segments.

The first change made under Karn's algorithm is to not use measured round-trip times for

any segments that are retransmitted in the calculation of the overall average round-trip time

for the connection. This completely eliminates the problem of acknowledgment ambiguity.

However, this by itself would not allow increased delays due to retransmissions to affect the

average round-trip time. For this, we need the second change: incorporation of a timer

backoff scheme for retransmitted segments. We start by setting the retransmission timer for

each newly-transmitted segment based on the current average round-trip time. When a

segment is retransmitted, the timer is not reset to the same value it was set for the initial

transmission. It is “backed off” (increased) using a multiplier (typically 2) to give the retrans-

mission more time to be received. The timer continues to be increased until a

retransmission is successful, up to a certain maximum value. This prevents retransmissions

from being sent too quickly and further adding to network congestion.

Once the retransmission succeeds, the round-trip timer is kept at the longer (backed-off)

value until a valid round-trip time can be measured on a segment that is sent and acknowl-

edged without retransmission. This permits a device to respond with longer timers to

occasional circumstances that cause delays to persist for a period of time on a connection,

while eventually having the round-trip time settle back to a long-term average when normal

conditions resume.

Key Concept: TCP uses an adaptive retransmission scheme that automatically

adjusts the amount of time to which retransmission timers are set, based on the

average amount of time it takes to send segments between devices. This helps avoid

retransmitting potentially lost segments too quickly or too slowly.

TCP Window Size Adjustment and Flow Control

We have seen the importance of the concept of window size to TCP's sliding window

mechanism. In a connection between a client and a server, the client tells the server the

number of bytes it is willing to receive at one time from the server; this is the client's receive

window, which becomes the server's send window. Likewise, the server tells the client how

many bytes of data it is willing to take from the client at one time; this is the server's receive

window and the client's send window.

The use of these windows is demonstrated in the topic discussing TCP's basic data transfer

and acknowledgment mechanism. However, just as the example in that topic was simplified

because I didn't show what happens with lost segments, there's another way that it doesn't

reflect the real world conditions of an actual Internet: the send and receive window sizes

never changed during the course of communication.

Impact of Buffer Management on TCP Window Size

To understand why the window size may fluctuate, we need to understand what it repre-

sents. The simplest way of considering the window size is that it indicates the size of the

device's receive buffer for the particular connection. That is, window size represents how

much data a device can handle from its peer at one time before it is passed to the appli-

cation process. Let's consider the aforementioned example. I said that the server's window

size was 360. This means the server is willing to take no more than 360 bytes at a time from

the client.

When the server receives data from the client, it places it into this buffer. The server must

then do two distinct things with this data:

☯ Acknowledgment: The server must send an acknowledgment back to the client to

indicate that the data was received.

☯ Transfer: The server must process the data, transferring it to the destination appli-

cation process.

It is critically important that we differentiate between these two activities. Unfortunately, the

TCP standards don't do a great job in this regard, which makes them very difficult to under-

stand. The key point is that in the basic sliding windows system, data is acknowledged

when received, but not necessarily immediately transferred out of the buffer. This means

that is possible for the buffer to fill up with received data faster than the receiving TCP can

empty it. When this occurs, the receiving device may need to adjust window size to prevent

the buffer from being overloaded.

Since the window size can be used in this manner to manage the rate at which data flows

between the devices at the ends of the connection, it is the method by which TCP imple-

ments flow control, one of the “classical” jobs of the transport layer. Flow control is vitally

important to TCP, as it is the method by which devices communicate their status to each

other. By reducing or increasing window size, the server and client each ensure that the

other device sends data just as fast as the recipient can deal with it.

Reducing Send Window Size To Reduce The Rate Data Is Sent

Let's go back to our earlier example so I can hopefully explain better what I mean, but let’s

make a few changes. First, to keep things simple, let’s just look at the transmissions made

from the client to the server, not the server’s replies (other than acknowledgments)—this is

illustrated in Figure 222. As before, the client sends 140 bytes to the server. After sending

the 140 bytes, the client has 220 bytes remaining in its usable window—360 in the send

window less the 140 bytes it just sent.

Sometime later, the server receives the 140 bytes and puts them in the buffer. Now, in an

“ideal world”, the 140 bytes go into the buffer, are acknowledged and immediately removed

from the buffer. Another way of thinking of this is that the buffer is of “infinite size” and can

hold as much as the client can send. The buffer's free space remains 360 bytes in size, so

the same window size can be advertised back to the client. This was the “simplification” in

the previous example.

As long as the server can process the data as fast as it comes in, it will keep the window

size at 360 bytes. The client, upon receipt of the acknowledgment of 140 bytes and the

same window size it had before, “slides” the full 360-byte window 140 bytes to the right.

Since there are now 0 unacknowledged bytes, the client can now once again send 360

bytes of data. These correspond to the 220 bytes that were formerly in the usable window,

plus 140 new bytes for the ones that were just acknowledged.

In the “real world”, however, that server might be dealing with dozens, hundreds or even

thousands of TCP connections. The TCP might not be able to process the data immedi-

ately. Alternately, it is possible the application itself might not be ready for the 140 bytes for

whatever reason. In either case, the server's TCP may not be able to immediately remove

all 140 bytes from the buffer. If so, upon sending an acknowledgment back to the client, will

want to change the window size that it advertises to the client, to reflect the fact that the

buffer is partially filled.

Suppose that we receive 140 bytes as above, but are able to send only 40 bytes to the

application, leaving 100 bytes in the buffer. When we send back the acknowledgment for

the 140 bytes, the server can reduce its send window by 100, to 260. When the client

receives this segment from the server it will see the acknowledgment of the 140 bytes sent

and slide its window 140 bytes to the right. However, as it slides this window, it reduces its

size to only 260 bytes. We can consider this like sliding the left edge of the window 140

bytes, but the right edge only 40 bytes. The new, smaller window ensures that the server

receives a maximum of 260 bytes from the client, which will fit in the 260 bytes remaining in

its receive buffer. This is illustrated in the first exchange of messages (Steps #1 through #3)

at the top of Figure 226.

Reducing Send Window Size To Stop The Sending of New Data

What if the server is so bogged down that it can't process any of the bytes received? Let’s

suppose that the next transmission from the client is 180 bytes in size, but the server is so

busy it can’t remove any of them. It could buffer the 180 bytes and in the acknowledgment it

sends for those bytes, reduce the window size by the same amount: from 260 to 80. When

the client received the acknowledgment for 180 bytes it would see the window size had

reduced by 180 bytes as well. It would “slide” its window by the same amount as the

window size was reduced! This is effectively like the server saying “I acknowledge receipt of

180 bytes, but I am not allowing you to send any new bytes to replace them”.

Another way of looking at this is that the left edge of the window slides 180 bytes while the

right edge remained fixed. And as long as the right edge of the window doesn't move, the

client can't send any more data than it could before receipt of the acknowledgment. This is

the middle exchange (Steps #4 to #6) in Figure 226.