Debian Codegraph @

rfc1016.html

raw
1 <pre>Network Working Group W. Prue
2 Request for Comments: 1016 J. Postel
3 ISI
4 July 1987
5
6 <span class="h1">Something a Host Could Do with Source Quench:</span>
7
8 The Source Quench Introduced Delay (SQuID)
9
10 Status of this Memo
11
12 This memo is intended to explore the issue of what a host could do
13 with a source quench. The proposal is for each source host IP module
14 to introduce some delay between datagrams sent to the same
15 destination host. This is an "crazy idea paper" and discussion is
16 essential. Distribution of this memo is unlimited.
17
18 Introduction
19
20 A gateway may discard Internet datagrams if it does not have the
21 buffer space needed to queue the datagrams for output to the next
22 network on the route to the destination network. If a gateway
23 discards a datagram, it may send a source quench message to the
24 Internet source host of the datagram. A destination host may also
25 send a source quench message if datagrams arrive too fast to be
26 processed. The source quench message is a request to the host to cut
27 back the rate at which it is sending traffic to the Internet
28 destination. The gateway may send a source quench message for every
29 message that it discards. On receipt of a source quench message, the
30 source host should cut back the rate at which it is sending traffic
31 to the specified destination until it no longer receives source
32 quench messages from the gateway. The source host can then gradually
33 increase the rate at which it sends traffic to the destination until
34 it again receives source quench messages [<a href="#ref-1" title="&quot;Internet Protocol - DARPA Internet Program Protocol Specification&quot;">1</a>,<a href="#ref-2" title="&quot;Internet Control Message Protocol - DARPA Internet Program Protocol Specification&quot;">2</a>].
35
36 The gateway or host may send the source quench message when it
37 approaches its capacity limit rather than waiting until the capacity
38 is exceeded. This means that the data datagram which triggered the
39 source quench message may be delivered.
40
41 The SQuID Concept
42
43 Suppose the IP module at the datagram source has a queue of datagrams
44 to send, and the IP module has a parameter "D". D is the introduced
45 delay between sending datagrams from the queue to the network. That
46 is, when the IP module discovers a datagram waiting to be sent to the
47 network, it sends it to the network then waits time D before even
48 looking at the datagram queue again. Normally, the value of D is
49
50
51
52 <span class="grey">Prue &amp; Postel [Page 1]</span></pre>
53 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
54 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
55
56
57 zero.
58
59 Imagine that when a source quench is received (or any other signal is
60 received that the host should slow down its transmissions to the
61 network), the value of D is increased. As time goes by, the value of
62 D is decreased.
63
64 The SQuID Algorithm
65
66 on increase event:
67
68 D &lt;-- maximum (D + K, I)
69 (where K = .020 second,
70 I = .075 second)
71
72 on decrease event:
73
74 D &lt;-- maximum (D - J, 0)
75 (where J = .001 second)
76
77 An increase event is receipt of one or more source quenches in a
78 event period E, (where E is 2.000 seconds).
79
80 A decrease event is when S time has passed since D was decreased and
81 there is a datagram to send (where S is 1.000 seconds).
82
83 A cache of D's is kept for the last M hosts communicated with.
84
85 Note that when no datagrams are sent to a destination for some time
86 the D for that destination is not decreased, but, if a destination is
87 not used for a long time that D for that destination may fall out of
88 the cache.
89
90 Possible Refinements
91
92 Keep a separate outgoing queue of datagrams for each destination
93 host, local subnet, or network.
94
95 Keep the cache of D's per network or local subnet, instead of per
96 host.
97
98 "I" could be based upon the basic speed of the slowest intervening
99 network (see <a href="#appendix-A">Appendix A</a>).
100
101 "D" could be limited to never go below "I" if the above refinement
102 were implemented.
103
104 "S" could be based upon the round trip time.
105
106
107
108 <span class="grey">Prue &amp; Postel [Page 2]</span></pre>
109 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
110 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
111
112
113 "D" could be adjusted datagram by datagram based upon the length of
114 the datagrams. Wait longer after a long datagram.
115
116 The delay algorithm could be implemented such that if a source
117 doesn't send a datagram when it is next allowed (the introduced delay
118 interval) or for N such intervals that the source gets a credit for
119 one and only one free (no delay) datagram.
120
121 Implementation Ideas
122
123 Since IP does not normally keep much state information about things,
124 we want the default or idle IP to have no state about these D values.
125 Since the default D value is zero, let us propose that the IP will
126 keep a list of only those destinations with non zero D's.
127
128 When the IP wants to send a datagram, it searches the D-list to see
129 if the destination is noted. If it is not, the D value is zero, so
130 the IP sends the datagram at once. If the destination is listed, the
131 IP must wait D time indicated before sending that particular
132 datagram. It could look at a datagram addressed to a different
133 destination, and possibly send it in the mean time.
134
135 When the IP receives a source quench, it checks to see if the
136 destination in the datagram that caused the source quench is on the
137 list. If so, it adds K to the D value. If not, it appends the
138 destination to the list with the D value set to "I".
139
140 A Closer Look At the Problem
141
142 Some implementations of IP send one SQ for every N datagrams they
143 discard (for example, N=20) so the SQ messages will not make the
144 congestion problem much worse [<a href="#ref-3" title="&quot;Re: Source Quench&quot;">3</a>]. In such situations any of the
145 sources of the 20 datagrams may get the SQ not necessarily the one
146 causing the most traffic. However if a host continues to send
147 datagrams at a high rate it has a high probability of receiving a SQ
148 message sooner or later. It is much like a speeder on a highway.
149 Not all speeders get speeding tickets but the ones who speed most
150 often or most excessively are most likely to be ticketed. In this
151 case they will get a ticket and their car may be destroyed.
152
153 With memory becoming so inexpensive many IP nodes put an artificially
154 low limit on the size of their queues so that through node delay will
155 not be excessive [<a href="#ref-4" title="&quot;On Packet Switches With Infinite Storage&quot;">4</a>]. For example, if one megabyte of data is
156 buffered to be sent over a 56 kb/s line the last datagram will wait
157 over 2 minutes before being sent.
158
159 One problem with SQ is that the IP or ICMP specification does not
160 have a well defined event to indicate receipt of SQ to higher level
161
162
163
164 <span class="grey">Prue &amp; Postel [Page 3]</span></pre>
165 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
166 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
167
168
169 protocols. Therefore many TCP implementations do not get notified
170 about SQ events and thus do not react to SQ. TCP is not the only
171 source of IP datagrams either. Other protocols should also respond
172 to SQ events in some appropriate way. TCP and other protocols at
173 that level should do something about a source quench, however,
174 discussion of their behavior is beyond the scope of this memo. Note
175 that implementation of SQ processing at one level of protocol should
176 not interfere with the behavior of higher level protocols. This
177 however, is difficult to do.
178
179 For protocols using IP which are trying to transfer large amounts of
180 data the data flow is most typically very bursty. TCP for example,
181 might send 5-10 segments into a window of 5-10 K bytes then wait for
182 the acknowledgment of the data which opens the window again. NETBLT
183 as defined by <a href="./rfc998">RFC-998</a> is a rate based protocol which has parameters
184 for burst size and burst rate.
185
186 One purpose of the bursts is to allow the source computer to generate
187 several datagrams at once to provide more efficient scheduling. An
188 other reason is to keep the network busy accepting data to maximize
189 effective throughput in spite of a potentially large network round
190 trip delay. To send a datagram then wait for an acknowledgment is a
191 simple but not efficient protocol on a large wide area network.
192
193 The reasons for efficiencies obtained at the source node by
194 generating many datagrams at once are not as applicable in an
195 intermediate IP node. Since each datagram is potentially from a
196 different node they must all be treated individually. Datagrams
197 received in a burst may also overload the queue of an intermediate
198 node losing datagrams and causing SQs to be generated. If the queue
199 is near a threshold and a burst comes, possibly all of the datagrams
200 will be lost. When datagrams arrive evenly spaced, less datagrams
201 are likely to be lost because the inter-arrival time allows the queue
202 a little time to empty out. Therefore datagrams spaced with some
203 delay between them may be better for intermediate IP nodes.
204
205 Congestion is most likely to occur at IP nodes which are gateways
206 between a slower network and a faster one. The congestion will be in
207 the send queue from the slow network to the fast network. An SQ
208 being returned to the sender will return on the faster network. (See
209 diagram below.)
210
211 A Gateway Source Quench Concept
212
213 In order for the SQuID algorithm to work we rely upon the gateways to
214 send SQs to us to tell us how we are doing. Because the loss of a
215 single datagram affects data flow so much (see lost datagram
216 discussion in Observed Results below) it would be much better for the
217
218
219
220 <span class="grey">Prue &amp; Postel [Page 4]</span></pre>
221 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
222 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
223
224
225 source IP node if it got a warning before datagrams were discarded.
226
227 We propose gateway IP nodes start SQing before the node is flooded at
228 a level we call SQ Keep (SQK) but forward the datagram. If the queue
229 level reaches a critical level, SQ Toss level (SQT), the gateway
230 should toss datagrams to resolve the problem unless the datagram is
231 an ICMP message. Even ICMP messages will be tossed if the MaxQ level
232 is reached. Once the gateway starts sending SQs it should continue
233 to do so until the queue level goes below a low water mark level
234 (SQLW) as shown below. This is analogous to methods some operating
235 systems use to handle memory space management.
236
237 The gateway should try to send SQ to as many of the contributors of
238 the congestion as possible but only once per contributor per second
239 or two.
240
241 Source Quench Queue Levels
242
243 +--------------+ MaxQ level
244 | |&gt; datagrams tossed &amp; SQed (but not ICMP msgs.)
245 +--------------+ SQT level (95%)
246 | |\
247 | | &gt; datagrams SQed but forwarded
248 | |/
249 +--------------+ SQK level (70%)
250 | |\
251 | | \ datagrams SQed but forwarded if SQK level
252 | | / exceeded &amp; SQLW or lower not yet reached
253 | |/
254 +--------------+ SQLW level (50%)
255 | |\
256 | | \
257 | | \
258 | | \ datagrams forwarded
259 | | /
260 | | /
261 | | /
262 | |/
263 +--------------+
264
265 Description of the Test Model
266
267 We needed some way of testing our algorithm and its various
268 parameters. It was important to check the interaction between IP
269 with the SQuID algorithm and TCP. We also wanted to try various
270 combinations of retransmission strategy and source quench strategy
271 which required control of the entire test network. We therefore
272 decided to build an Internet model.
273
274
275
276 <span class="grey">Prue &amp; Postel [Page 5]</span></pre>
277 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
278 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
279
280
281 Using this example configuration for illustration:
282
283 _______ LAN _______ WAN _______ LAN _______
284 | 1 | | 2 | | 3 | | 4 |
285 |TCP/IP |---10 Mb/s--| IP |---56 kb/s--| IP |---10 Mb/s--|TCP/IP |
286 |_______| |_______| |_______| |_______|
287
288 A program was written in C which created queues and structures to put
289 on the queues representing datagrams carrying data, acknowledgments
290 and SQs. The program moved datagrams from one queue to the next
291 based upon rules defined below
292
293 A client fed the TCP in node 1 data at the rate it would accept. The
294 TCP function in node 1 would chop the data up into fixed 512 byte
295 datagrams for transmission to the IP in node 1. When the datagrams
296 were given to IP for transmission, a timestamp was put on it and a
297 copy of it was put on a TCP ack-wait queue (data sent but not yet
298 acknowledged). In particular TCP assumed that once it handed data to
299 IP, the data was sent immediately for purposes of retransmission
300 timeouts even though our algorithm has IP add delay before
301 transmission.
302
303 Each IP node had one queue in each direction (left and right). For
304 each IP in the model IP would forward datagrams at the rate of the
305 communications line going to the next node. Thus the fifth datagram
306 on IP 2's queue going right would take 5 X 73 msec or 365 msec before
307 it would appear at the end of IP 3's queue. The time to process each
308 datagram was considered to be less than the time it took for the data
309 to be sent over the 56 kb/s lines and therefore done during those
310 transmission times and not included in the model. For the LAN
311 communications this is not the case but since they were not at the
312 bottleneck of the path this processing time was ignored. However
313 because LAN communications are typically shared band width, the LAN
314 band width available to each IP instance was considered to be 1 Mb/s,
315 a crude approximation.
316
317 When the data arrived at node 4 the data was immediately given to the
318 TCP receive function which validated the sequence number. If the
319 datagram was in sequence the datagram was turned into an ack datagram
320 and sent back to the source. An ack datagram carries no data and
321 will move the right edge of the window, the window size past the just
322 acked data sequence number. The ack datagram is assumed to be 1/8 of
323 the length of a data datagram and thus can be transmitted from one
324 node to the next 8 times faster. If the sequence number is less than
325 expected (a retransmission due to a missed ack) then it too is turned
326 into an ack. A larger sequence number datagram is queued
327 indefinitely until the missing datagrams are received.
328
329
330
331
332 <span class="grey">Prue &amp; Postel [Page 6]</span></pre>
333 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
334 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
335
336
337 We also modeled the gateway source quench algorithm. When a datagram
338 was put on an IP queue the number on the queue was compared to an SQ
339 keep level (SQK). If it was greater, an SQ was generated and
340 returned to the sender. If it was larger than the SQ toss (SQT) level
341 it was also discarded. Once SQs were generated they would continue
342 to be sent until the queue level went below SQ Low Water (SQLW) level
343 which was below the original SQK level. These percentages were
344 modifiable as were many parameters. An SQ could be lost if it
345 exceeded the maximum queue size (MaxQ), but a source quench was never
346 sent about tossing a source quench.
347
348 Upon each transition from one node to the next, the datagram was
349 vulnerable to datagram loss due to errors. The loss rate could be
350 set as M losses out of N datagrams sent, thus the model allowed for
351 multi-datagram loss bursts or single datagram losses. We used a
352 single datagram loss rate of 1 lost datagram per 300 datagrams sent
353 for much of our testing. While this may seem low for Internet
354 simulation, remember it does not include losses due to congestion.
355
356 Some network parameters we used were a maximum queue length of 15
357 datagrams per IP direction left and right. We started sending SQ if
358 the queue was 70% full, SQK level, tossed data datagrams, but not SQ
359 datagrams, if 95% of the queue was reached, SQT level, and stopped
360 SQing when a 50% SQLW level was reached (see above).
361
362 We ignored additional SQs for 2 seconds after receipt of one SQ.
363 This was done because some Internet nodes only send one SQ for every
364 20 datagrams they discard even though our model sent SQs for every
365 datagram discarded. Other IP node may send one SQ per discarded
366 packet. The SQuID algorithm needed a way to handle both types of SQ
367 generation. We therefore treated one or a burst of SQs as a single
368 event and incremented our D by a larger amount than would be
369 appropriate for responding individually to the multiple SQs of the
370 verbose nodes.
371
372 The simulation did not do any fragmenting of datagrams. Silly window
373 syndrome was avoided. The model did not implement nor simulate the
374 TTL (time-to-live) function.
375
376 The model allowed for a flexible topology definition with many TCP
377 source/destination pairs on host IP nodes or gateway IP nodes with
378 various windows allowed. An IP node could have any number of TCPs
379 assigned to it. Each line could have an individually set speed. Any
380 TCP could send to any other TCP. The routing from one location to
381 another was fixed. Therefore datagrams did not arrive out of
382 sequence. However, datagrams arrived in ascending order, but not
383 consecutively, on a regular basis because of datagram losses.
384 Datagrams going "left" through a node did not affect the queue size,
385
386
387
388 <span class="grey">Prue &amp; Postel [Page 7]</span></pre>
389 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
390 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
391
392
393 or SQ chances, of data going "right" through the node.
394
395 The TCP retransmission timer algorithm used an Alpha of .15 and a
396 Beta of 1.5. The test was run without the benefit of the more
397 sophisticated retransmission timer algorithm proposed by Van Jacobson
398 [<a href="#ref-5" title="&quot;Re: interpacket arrival variance and mean&quot;">5</a>].
399
400 The program would display either the queue sizes of the various IP
401 nodes and the TCP under test as time passed or do a crude plot of
402 various parameters of interest including SRTT, perceived round trip
403 time, throughput, and the critical queue size.
404
405 As we observed the effects of various algorithms for responding to SQ
406 we adapted our model to better react to SQ. Initial tests showed if
407 we incremented slowly and decremented quickly we observed
408 oscillations around the correct value but more of the time was spent
409 over driving the network, thus losing datagrams, than at a value
410 which helped the congestion situation.
411
412 A significant problem is the delay between when some intermediate
413 node starts dropping datagrams and sending source quenches to the
414 time when the source quenches arrive at the source host and can begin
415 to effect the behavior at the data source. Because of this and the
416 possibility that a IP might send only one SQ for each 20 datagrams
417 lost, we decided that the increase in D per source quench should be
418 substantial (for example, D should increase by 20 msec for every
419 source quench), and the decrease with time should be very slow (for
420 example, D should decrease 1 msec every second). Note that this is
421 the opposite behavior than suggested in an early draft by one of the
422 authors.
423
424 However, when many source quenches are received (for example, when a
425 source quench is received for every datagram dropped) in a short time
426 period the D value is increased excessively. To prevent D from
427 growing too large, we decided to ignore subsequent source quenches
428 for a time (for example, 2 seconds) once we had increased D.
429
430 Tests were run with only one TCP sending data to learn as much as
431 possible how an unperturbed session might run. Other test runs would
432 introduce and eliminate competing traffic dynamically between other
433 TCP instances on the various nodes to see how the algorithms reacted
434 to changes in network load. A potential flaw in the model is that
435 the defined TCPs with open windows always tried to forward data.
436 Their clients feeding them data never paused to think what they were
437 going to type nor got swapped out in favor of other applications nor
438 turned the session around logically to listen to the other end for
439 more user commands. In other words all of the simulated TCP sessions
440 were doing file transfers.
441
442
443
444 <span class="grey">Prue &amp; Postel [Page 8]</span></pre>
445 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
446 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
447
448
449 The model was defined to allow many mixes of competing algorithms for
450 responding to SQ. It allowed comparing effective throughput between
451 TCPs with small windows and large windows and those whose IP would
452 introduce inter-datagram delays and those who totally ignored SQ. It
453 also allowed comparisons with various inter-datagram increment
454 amounts and decrement amounts. Because of the number of possible
455 configurations and parameter combinations only a few combinations of
456 parameters were tested. It is hoped they were the most appropriate
457 ones upon which to concentrate.
458
459 Observed Results
460
461 All of our algorithms oscillate, some worse than others.
462
463 If we put in just the right amount of introduced delay we seem to get
464 the best throughput. But finding the right amount is not easy.
465
466 Throughput is adversely affected, heavily, by a single lost datagram
467 at least for the short time. Examine what happens when a window is
468 35 datagrams wide with an average round trip delay of 2500 msec using
469 512 byte datagrams when a single datagram is lost at the beginning.
470 Thirty five datagrams are given by TCP to IP and a timer is started
471 on the first datagram. Since the first datagram is missing, the
472 receiving TCP will not sent an acknowledgment but will buffer all 34
473 of the out-of-sequence datagrams. After 1.5 X 2500 msec, or 3750
474 msec, have elapsed the datagram times out and is resent. It arrives
475 and is acked, along with the other 34, 2500 msec later. Before the
476 lost datagram we might have been sending at the average rate a 56
477 kb/s line could accept, about one every 75 msec. After loss of the
478 datagram we send at the rate of one in 6250 msec over 83 times
479 slower.
480
481 If the lost datagram in the above example is other than the first
482 datagram the situation becomes the same when all of the datagrams
483 before the lost datagram are acknowledged. The example holds true
484 then for any single lost datagram in the window.
485
486 When SQ doesn't always cause datagram loss the sender continues to
487 send too fast (queue size oscillates a lot). It is important for the
488 SQ to cause feed-back into the sending system as soon as possible,
489 therefore when the source host IP receives an SQ it must make
490 adjustments to the send rate for the datagrams still on the send
491 queue not just datagrams IP is requested to send after the SQ.
492
493 Through network delay goes up as the network queue lengths go up.
494
495 Window size affect the chance of getting SQed. Look at our model
496 above using a queue level of 15 for node 2 before SQs are generated
497
498
499
500 <span class="grey">Prue &amp; Postel [Page 9]</span></pre>
501 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
502 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
503
504
505 and a window size of 20 datagrams. We assumed that we could send
506 data over the LAN at a sustained average rate of 1 Mb/s or about 18
507 times as fast as over the WAN. When TCP sends a burst of 20
508 datagrams to node 1 they make it to node 2 in 81 msec. The
509 transition time from node 2 to node 3 is 73 msec, therefore, in 81
510 msec, only one datagram is forwarded to node 3. Thus the 17th, 18th,
511 19th, and 20th datagram are lost every time we send a whole window.
512 More are lost when the queue is not empty. If a sequence of acks
513 come back in response to the sent data, the acks tend to return at
514 the rate at which data can traverse the net thus pacing new send data
515 by opening the window at the rate which the network can accept it.
516 However as soon as one datagram is lost all of the subsequent acks
517 are deferred and batched until receipt of the missing data block
518 which acks all of the datagrams and opens the window to 20 again.
519 This causes the max queue size to be exceeded again.
520
521 If we assume a window smaller than the max queue size in the
522 bottleneck node, any time we send a window's worth of data, it is
523 done independently of the current size of the queue. The larger the
524 send window, the larger a percentage of the stressed queue we send.
525 If we send 50% of the stressed queue size any time that queue is more
526 than 50% we threaten to overflow the queue. Evenly spaced single
527 datagram bursts have the least chance of overflowing the queue since
528 they represent the minimum percentage of the max queue one may send.
529
530 When a big window opens up (that is, a missing datagram at the head
531 of a 40 datagram send queue gets retransmitted and acked), the
532 perceived round trip time for datagrams subsequently sent hits a
533 minimum value then goes up linearly. The SRTT goes down then back up
534 in a nice smooth curve. This is caused by the fact IP will not add
535 delay if the queue is empty and IP has not sent any datagrams to the
536 destination for our introduced delay time. But as many datagrams are
537 added to the IP pre-staged send queue in bursts all have the same
538 send time as far as TCP is concerned. IP will delay each datagram on
539 the head of the queue by the introduced delay amount. The first may
540 be undelayed as just described but all of the others are delayed by
541 their ordinal number on the queue times the introduced delay amount.
542
543 It seems as though in a race between a TCP session which delays
544 sending to IP and one who does not, the delayer will get better
545 throughput because less datagrams are lost. The send window may also
546 be increased to keep the pipeline full. If however the non delayer
547 uses windowing to reduce the chance of SQ datagram loss his
548 throughput may possibly be better because no fair queuing algorithm
549 is in place.
550
551 If gateways send SQs early and don't toss data until its critical and
552 keep sending SQs until a low water mark is hit, effective throughput
553
554
555
556 <span class="grey">Prue &amp; Postel [Page 10]</span></pre>
557 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
558 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
559
560
561 seems to go up.
562
563 At the startup of our tests throughput was very high, then dropped
564 off quickly as the last of the window got clobbered. Our model
565 should have used a slow start up algorithm to minimize the startup
566 shock. However the learning curve to estimate the proper value for D
567 was probably quicker.
568
569 A large part of the perceived RTT is due to the delay getting off the
570 TCP2IP (TCP transitional) queue when we used large windows. If IP
571 would invoke some back-pressure to TCP in a real implementation this
572 can be significantly reduced. Reducing the window would do this for
573 us at the expense of throughput.
574
575 After an SQ burst which tosses datagrams the sender gets in a mode
576 where TCP may only send one or two datagrams per RTT until the queued
577 but not acked segments fall into sequence and are acked. This
578 assumes only the head of the retransmission queue is retransmitted on
579 a timeout. We can send one datagram upon timeout. When the ack for
580 the retransmission is received the window opens allowing sending a
581 second. We then wait for the next lost datagram to time out.
582
583 If we stop sending data for a while but allow D to be decreased, our
584 algorithm causes the introduced delay to dwindle away. We would thus
585 go through a new startup learning curve and network oscillation
586 sequence.
587
588 One thing not observed often was TCP timing out a segment before the
589 source IP even sent the datagram the first time. As discussed above
590 the first datagram on the queue of a large burst is delayed minimally
591 and succeeding datagrams have linearly increasing delays. The
592 smoothed round trip delay algorithm has a chance to adapt to the
593 perceived increasing round trip times.
594
595 Unstructured Thoughts and Comments
596
597 The further down a route a datagram traverses before being clobbered
598 the greater the waste of network resources. SQs which do not destroy
599 the datagram referred to are better than ones that do if return path
600 resources are available.
601
602 Any fix must be implementable piecemeal. A fix can not be installed
603 in all or most nodes at one time. The SQuID algorithm fulfills this
604 requirement. It could be implemented, installed in one location, and
605 used effectively.
606
607 If it can be shown that by using the new algorithm effective
608 throughput can be increased over implementations which do not
609
610
611
612 <span class="grey">Prue &amp; Postel [Page 11]</span></pre>
613 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
614 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
615
616
617 implement it that may well be effective impetus to get vendors to
618 implement it.
619
620 Once a source host has an established average minimum inter-datagram
621 delay to a destination (see <a href="#appendix-A">Appendix A</a>), this information should be
622 stored across system restarts. This value might be used each time
623 data is sent to the given host as a minimum inter-datagram delay
624 value.
625
626 Window closing algorithms reduce the average inter-datagram delay and
627 the burst size but do not affect the minimum inter-datagram spacing
628 by TCP.
629
630 Currently an IP gateway node can know if it is in a critical path
631 because its queues stay high or keep building up. Its optimum queue
632 size is one because it always has something to do and the through
633 node delay is at a minimum. It is very important that the gateway at
634 the critical path not so discourage data flow that its queue size
635 drops to zero. If the gateway tosses datagrams this stops data flow
636 for TCP for a while (as described in Observed Results above). This
637 argues for the gateway algorithm described above which SQs but does
638 not toss datagrams unless necessary. Optimally we should try to have
639 a queue size somewhat larger than 1 but less than say 50% of the max
640 queue size. Large queues lead to large delay.
641
642 TCP's SRTT is made artificially large by introducing delay at IP but
643 the perceived round trip time variance is probably smaller allowing a
644 smaller Beta value for the timeout value.
645
646 So that a decrease timer is not needed for the "D" decrease function,
647 upon the next sent datagram to a delayed destination just decrease
648 the delay by the amount of time since we last did this divided by the
649 decrease timer interval. An alternate algorithm would be to decrease
650 it by only one decrease unit amount if more than the timer interval
651 has gone by. This eliminates the problem caused by the delay, "D",
652 dwindling away if we stop sending for a while. The longer we send
653 using this "D", the more likely it is that it is too large a delay
654 and the more we should decrease it.
655
656 It is better for the network and the sender for our introduced delay
657 to be a little on the high side. It minimizes the chances of getting
658 a datagram clobbered by sending it into a congested gateway. A lost
659 datagram scenario described above showed that one lost datagram can
660 reduce our effective delay by one to two orders of magnitude
661 temporarily. Also if the delay is a little high, the net is less
662 stressed and the queues get smaller, reducing through network delay.
663
664 The RTT experienced at a given time verses the minimum RTT possible
665
666
667
668 <span class="grey">Prue &amp; Postel [Page 12]</span></pre>
669 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
670 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
671
672
673 for the given route does give a good measure of congestion. If we
674 ever get congestion control working RTT may have little to do with
675 the amount of congestion. Effective throughput when compared with
676 the possible throughput (or some other measure) is the only real
677 measure of congestion.
678
679 Slow startup of TCP is a good thing and should be encouraged as an
680 additional mechanism for alleviating network overload.
681
682 The network dynamics tends to bunch datagrams. If we properly space
683 data instead of bunching it like windowing techniques to control
684 overflow of queues then greater throughput is accomplished because
685 the absolute rate we can send is pacing our sending not the RTT. We
686 eliminate "stochastic bunching" [<a href="#ref-6" title="&quot;Re: Appropriate measures of gateway performance&quot;">6</a>].
687
688 The longer the RTT the more network resources the data takes to
689 traverse the net.
690
691 Should "fair queuing" say that a longer route data transfer should
692 get less band width than a shorter one (since it consumes more of the
693 net)? Being fair locally on each node may be unfair overall to
694 datagrams traversing many nodes.
695
696 If we solve congestion problems today, we will start loading up the
697 net with more data tomorrow. When this causes congestion in a year
698 will that type of congestion be harder to solve than todays or is it
699 not our problem? John Nagle suggests "In a large net, we may well
700 try to force congestion out to the fringes and keep the interior of
701 the net uncongested by controlling entry to the net. The IMP-based
702 systems work that way, or at least used to. This has the effect of
703 concentrating congestion at the entrance to the long-haul system.
704 That's where we want it; the Source Quench / congestion window / fair
705 queuing set of strategies are able to handle congestion at the LAN to
706 WAN bottleneck [<a href="#ref-7" title="&quot;Source quench, and congestion generally&quot;">7</a>]. Our algorithm should try to push the network
707 congestion out to the extremities and keep the interior network
708 congestion free.
709
710 Use of the algorithm is aesthetically appealing because the data is
711 sitting in our local queue instead of consuming resources inside the
712 net. We give data to the network only when it is ready to accept it.
713
714 An averaged minimum inter-datagram arrival value will give a measure
715 of the network bottleneck speed at the receiver. If the receiver
716 does not defer or batch together acks the same would be learned from
717 the inter-datagram arrival time of the acks. A problem is that IP
718 doesn't have knowledge of the datagram contents. However IP does
719 know from which host a datagram comes.
720
721
722
723
724 <span class="grey">Prue &amp; Postel [Page 13]</span></pre>
725 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span>
726 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
727
728
729 If SQuID limits the size of its pre-net buffering properly (causes
730 back-pressure to TCP) then artificially high RTT measurements would
731 not occur.
732
733 TCP might, in the future, get a way to query IP for the current
734 introduced delay, D, for a given destination and if the value is too
735 excessive abort or not start a session.
736
737 With the new algorithm TCP could have an arbitrarily large window to
738 send into without fear of over running queue sizes in intermediate
739 nodes (not that any TCP ever considered having this fear before).
740 Thus it could have a window size which would allow it to always be
741 sending; keeping the pipe full and seldom getting in the stop-and-
742 wait mode of sending. This presupposes that the local IP is able to
743 cause some sort of back pressure so that the local IPs queues are not
744 over run. TCP would still be operating in the burst mode of sending
745 but the local IP would be sending a datagram for the TCP as often as
746 the network could accept it keeping the data flow continuous though
747 potentially slow.
748
749 Experience implementing protocols suggests avoiding timers in
750 protocols whenever possible. IP, as currently defined, does not use
751 timers. The SQuID algorithm uses two at the IP level. A way to
752 eliminate the introduced delay decrease timer is to decrease the D
753 value when we check the send queue for data to send. We would
754 decrease "D" by one "J" unit if "S" time, or more, has elapsed. The
755 other timer is not so easily eliminated. If the IP implementation is
756 periodically awakened to check for work to do, it could check the
757 time stamps of the head of the queues to see if any datagrams have
758 waited long enough. This would mean we would necessarily wait too
759 long before sending, but it may not be too large of a variance from
760 our desired rates. The additional delay would help congestion and
761 reduce our chances of SQ. Another option is setting a real timer
762 which is say 25-50% too large and hope that our periodic work in IP
763 will allow us to notice a datagram is delayed enough, and send it.
764 Upon sending the datagram we would cancel the timer, avoiding the
765 timer interrupt and environment swap. In other implementations the
766 communications interface or the link level protocol may be able to
767 provide the timing needed without interrupts to the main processor.
768
769 Background tasks like some file transfers could query IP for the
770 latest delay characteristics for a given destination to determine if
771 it is appropriate to consume network resources now or if it would be
772 better to wait until later.
773
774 We should consider what would happen if IP, using the SQuID
775 algorithm, and TCP both introduced delay between the datagrams. If
776 TCPs delay was greater than IP's, then when IP got the datagrams it
777
778
779
780 <span class="grey">Prue &amp; Postel [Page 14]</span></pre>
781 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span>
782 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
783
784
785 would forward them immediately as described in the algorithm above.
786 This is because when the IP send queue is empty and it has been at
787 least as long as IP wants the higher level protocol, TCP, gets one
788 free (no delay) send. Note also that IP will be decreasing the
789 amount of delay it wants introduced because of the successful
790 transmissions without SQs. This would affect other protocols who
791 might also send to the same destination. If TCP sends too quickly
792 then IP will protect the network from its indiscretion as described
793 in the basic algorithm however TCPs round trip time estimates will be
794 much closer to reality. A lost datagram will thus be detected more
795 quickly. If TCP also uses windowing to limit its sending rate, it
796 might, because of its success with a smaller window, increase the
797 window size increasing TCPs efficiency.
798
799 As this algorithm is implemented everywhere, the SQ Keep (SQK) and SQ
800 Low Water (SQLW) queue level percentages should be dropped to reduce
801 queue sizes and thus the through net delay. The percentage we lower
802 SQK and SQLW to should be adjusted based upon the percentage of time
803 the queue is empty. The more the queue is empty the more likely it
804 is that the node is discouraging data flow too much. The more time
805 the queue is not empty but not too full, the more likely it is the
806 node is not excessively discouraging data flow. How uniform the
807 queue size is, is a measure of how well the network citizens are
808 behaved.
809
810 As the congestion is pushed to the sources, gateways which are
811 bottlenecks can more easily detect someone not playing by the rules
812 (sending datagrams in bursts) and deal with the offender.
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836 <span class="grey">Prue &amp; Postel [Page 15]</span></pre>
837 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span>
838 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
839
840
841 Appendix A -- Determination of the Value for the Parameter "I"
842
843 To get to the correct value for the delay needed quickly, when an
844 event occurred and the currently used delay was minimal, the
845 transmission time for an average sized datagram across the slowest
846 communications link was used for a first value. How a real IP node
847 is to guess this value is discussed below. In our example the
848 transition between node 2 and node 3 is the bottleneck. Using the 56
849 kb/s line, a 512 byte datagram would take 73 msec with no queuing or
850 processing time is considered. This value is defined to be the
851 minimum inter-datagram arrival time (MIAT). Assuming a perfect
852 network, ignoring factors other than transmission speed, this is the
853 minimum time one could expect between receipt of datagrams at the
854 destination, because of the slowed data rate through the bottleneck.
855 This won't hold true if the datagrams do not follow the same path.
856
857 The MIAT, minimum inter-datagram arrival time, may be guessed at by
858 comparing the arrival timestamps of consecutive datagrams from a
859 source of data. Each value to be considered needs to be adjusted up
860 or down based upon the size between the second datagram received and
861 the typical datagram size. More simply stated, a datagram which is
862 half the size of the average datagram can be transmitted across a
863 line in half the time. Therefore, double its IAT before considering
864 it for an MIAT. If the timestamp of a datagrams is taken based upon
865 an event caused by the start of the datagram arriving, not the
866 completion of the datagram arriving, then the first datagram's size
867 is the limiting length and should be used to adjust its IAT. In
868 order to keep the algorithm simple, arrival times for short datagram
869 could be ignored as could IATs which were orders of magnitude too
870 large (see below).
871
872 Once a minimal value is found based upon looking for small values
873 over a minute or more, the value might be time averaged with a value
874 kept like TCP's SRTT in order to reduce the effects of a false MIAT.
875 We could assume the limiting facility would be a 9.6 kb/s line, a
876 56-64 kb/s line, or a 1.5 Mb/s line. These facilities would provide
877 a MIAT of 427 msec, 73-64 msec, or 3 msec respectively, for a
878 datagram 512 bytes long. These are almost orders of magnitude in
879 differences. If the MIAT a node measures is not in this range but
880 close, the value it is closest to may be used for its MIAT from that
881 source.
882
883 One of the good things about this measurement is that it is an
884 entirely passive measurement. No additional traffic is needed to
885 measure it. If a source is not sending data continuously then the
886 longer measured values won't be validated as minimal values. The
887 assumption is that at least sometimes the source will send multiple
888 datagrams at a time.
889
890
891
892 <span class="grey">Prue &amp; Postel [Page 16]</span></pre>
893 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span>
894 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
895
896
897 The MIAT measurement is totally unaffected by satellite delay
898 characteristics of any intervening facilities. The chance of getting
899 a valid minimal reading is affected by the number of nodes traversed,
900 but the value measured if it is valid will not be affected by the
901 number of nodes traversed. Stated another way, when a pair of
902 datagrams traverse from one node to the next the datagrams are
903 susceptible to being separated by a datagram from another source.
904 Both of these factors affect SRTT. The value obtained requires no
905 topological knowledge of the route.
906
907 A potential problem with the measurement is, it will not be the
908 proper value for some forms of alternate routes. If a T1 link is the
909 bottleneck route some times and other times it is a 56 kb/s link our
910 first guess for inter-datagram delay would be too small for the 56
911 kb/s line route. Another problem is that if one datagram goes via
912 one route and the next goes via another, their inter-datagram arrival
913 difference could lead to a small false measurement. If intervening
914 networks fragment datagrams then the measured IAT between segments
915 could be misleading. A solution to this problem is to ignore
916 fragmented datagram IATs.
917
918 This number represents the minimum inter-datagram delay the sending
919 IP should use to send to us, the measuring site, for the given
920 datagram size. If we assume that the return path will be through the
921 same facilities or the same type, then as described above this value
922 can be the first guess for inter-datagram introduced delay, "D" (in
923 the algorithm). It represents the "I" parameter.
924
925 These MIATs may be cached on a host, subnet, or network basis. The
926 last "n" hosts MIATs could be kept. For infrequent destinations an
927 entry per destination network would be applicable to many
928 destinations. If the local net is in fact a subnet, then the other
929 local subnet MIATs could be kept.
930
931 If a good algorithm is found for MIAT, comparing it to the average
932 IAT (during data transfer) would give a good measure of the amount of
933 network traffic load. Since IP has no idea when the source of data
934 is sending as fast as possible, to get a valid average, upper layer
935 protocols would have to figure this out for themselves. IP could
936 however provide an interface to get the current MIAT for a given
937 destination.
938
939
940
941
942
943
944
945
946
947
948 <span class="grey">Prue &amp; Postel [Page 17]</span></pre>
949 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span>
950 <span class="grey"><a href="./rfc1016">RFC 1016</a> Source Quench Introduced Delay -- SQuID July 1987</span>
951
952
953 References
954
955 [<a id="ref-1">1</a>] Postel, Jon, "Internet Protocol - DARPA Internet Program
956 Protocol Specification", <a href="./rfc791">RFC 791</a>, ISI, September 1981.
957
958 [<a id="ref-2">2</a>] Postel, Jon, "Internet Control Message Protocol - DARPA Internet
959 Program Protocol Specification", <a href="./rfc792">RFC 792</a>, ISI, September 1981.
960
961 [<a id="ref-3">3</a>] Karels, M., "Re: Source Quench", electronic mail message to J.
962 Postel and INENG-INTEREST, Tue, 24 Feb 87.
963
964 [<a id="ref-4">4</a>] Nagle, John B., "On Packet Switches With Infinite Storage", <a href="./rfc970">RFC</a>
965 <a href="./rfc970">970</a>, FACC Palo Alto, December 1985.
966
967 [<a id="ref-5">5</a>] Jacobson, Van, "Re: interpacket arrival variance and mean",
968 electronic mail message to TCP-IP, Mon, 15 Jun 87 06:08:01 PDT
969
970 [<a id="ref-6">6</a>] Jacobson, Van, "Re: Appropriate measures of gateway performance"
971 electronic mail message to J. Noel Chiappa and INENG-INTEREST, Sun,
972 22 Mar 87 15:04:44 PST.
973
974 [<a id="ref-7">7</a>] Nagle, John B., "Source quench, and congestion generally",
975 electronic mail message to B. Braden and INENG-INTEREST, Thu, 5 Mar
976 87 11:08:49 PST.
977
978 [<a id="ref-8">8</a>] Nagle, John B., "Congestion Control in IP/TCP Internetworks", <a href="./rfc896">RFC</a>
979 <a href="./rfc896">896</a>, FACC Palo Alto, 6 January 1984.
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004 Prue &amp; Postel [Page 18]
1005 </pre>