| 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=""Internet Protocol - DARPA Internet Program Protocol Specification"">1</a>,<a href="#ref-2" title=""Internet Control Message Protocol - DARPA Internet Program Protocol Specification"">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 & 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 <-- maximum (D + K, I) |
| 69 |
(where K = .020 second, |
| 70 |
I = .075 second) |
| 71 |
|
| 72 |
on decrease event: |
| 73 |
|
| 74 |
D <-- 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 & 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=""Re: Source Quench"">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=""On Packet Switches With Infinite Storage"">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 & 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 & 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 |
| |> datagrams tossed & SQed (but not ICMP msgs.) |
| 245 |
+--------------+ SQT level (95%) |
| 246 |
| |\ |
| 247 |
| | > datagrams SQed but forwarded |
| 248 |
| |/ |
| 249 |
+--------------+ SQK level (70%) |
| 250 |
| |\ |
| 251 |
| | \ datagrams SQed but forwarded if SQK level |
| 252 |
| | / exceeded & 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 & 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 & 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 & 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=""Re: interpacket arrival variance and mean"">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 & 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 & 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 & 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 & 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 & 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=""Re: Appropriate measures of gateway performance"">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=""Source quench, and congestion generally"">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 & 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 & 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 & 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 & 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 & 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 & Postel [Page 18] |
| 1005 |
</pre> |