home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / email / reno.apr90 < prev    next >
Text File  |  1995-08-22  |  14KB  |  345 lines

  1. >From van@helios.ee.lbl.gov Mon Apr 30 01:44:05 1990
  2. To: end2end-interest@ISI.EDU
  3. Subject: modified TCP congestion avoidance algorithm
  4. Date: Mon, 30 Apr 90 01:40:59 PDT
  5. From: Van Jacobson <van@helios.ee.lbl.gov>
  6. Status: RO
  7. Content-Length: 12896
  8. X-Lines: 297
  9.  
  10. This is a description of the modified TCP congestion avoidance
  11. algorithm that I promised at the teleconference.
  12.  
  13. BTW, on re-reading, I noticed there were several errors in
  14. Lixia's note besides the problem I noted at the teleconference.
  15. I don't know whether that's because I mis-communicated the
  16. algorithm at dinner (as I recall, I'd had some wine) or because
  17. she's convinced that TCP is ultimately irrelevant :).  Either
  18. way, you will probably be disappointed if you experiment with
  19. what's in that note.
  20.  
  21. First, I should point out once again that there are two
  22. completely independent window adjustment algorithms running in
  23. the sender:  Slow-start is run when the pipe is empty (i.e.,
  24. when first starting or re-starting after a timeout).  Its goal
  25. is to get the "ack clock" started so packets will be metered
  26. into the network at a reasonable rate.  The other algorithm,
  27. congestion avoidance, is run any time *but* when (re-)starting
  28. and is responsible for estimating the (dynamically varying)
  29. pipesize.  You will cause yourself, or me, no end of confusion
  30. if you lump these separate algorithms (as Lixia's message did).
  31.  
  32. The modifications described here are only to the congestion
  33. avoidance algorithm, not to slow-start, and they are intended to
  34. apply to large bandwidth-delay product paths (though they don't
  35. do any harm on other paths).  Remember that with regular TCP (or
  36. with slow-start/c-a TCP), throughput really starts to go to hell
  37. when the probability of packet loss is on the order of the
  38. bandwidth-delay product.  E.g., you might expect a 1% packet
  39. loss rate to translate into a 1% lower throughput but for, say,
  40. a TCP connection with a 100 packet b-d p. (= window), it results
  41. in a 50-75% throughput loss.  To make TCP effective on fat
  42. pipes, it would be nice if throughput degraded only as function
  43. of loss probability rather than as the product of the loss
  44. probabilty and the b-d p.  (Assuming, of course, that we can do
  45. this without sacrificing congestion avoidance.)
  46.  
  47. These mods do two things: (1) prevent the pipe from going empty
  48. after a loss (if the pipe doesn't go empty, you won't have to
  49. waste round-trip times re-filling it) and (2) correctly account
  50. for the amount of data actually in the pipe (since that's what
  51. congestion avoidance is supposed to be estimating and adapting to).
  52.  
  53. For (1), remember that we use a packet loss as a signal that the
  54. pipe is overfull (congested) and that packet loss can be
  55. detected one of two different ways:  (a) via a retransmit
  56. timeout or (b) when some small number (3-4) of consecutive
  57. duplicate acks has been received (the "fast retransmit"
  58. algorithm).  In case (a), the pipe is guaranteed to be empty so
  59. we must slow-start.  In case (b), if the duplicate ack
  60. threshhold is small compared to the bandwidth-delay product, we
  61. will detect the loss with the pipe almost full.  I.e., given a
  62. threshhold of 3 packets and an LBL-MIT bandwidth-delay of around
  63. 24KB or 16 packets (assuming 1500 byte MTUs), the pipe is 75%
  64. full when fast-retransmit detects a loss (actually, until
  65. gateways start doing some sort of congestion control, the pipe
  66. is overfull when the loss is detected so *at least* 75% of the
  67. packets needed for ack clocking are in transit when
  68. fast-retransmit happens).  Since the pipe is full, there's no
  69. need to slow-start after a fast-retransmit.
  70.  
  71. For (2), consider what a duplicate ack means:  either the
  72. network duplicated a packet (i.e., the NSFNet braindead IBM
  73. token ring adapters) or the receiver got an out-of-order packet.
  74. The usual cause of out-of-order packets at the receiver is a
  75. missing packet.  I.e., if there are W packets in transit and one
  76. is dropped, the receiver will get W-1 out-of-order and
  77. (4.3-tahoe TCP will) generate W-1 duplicate acks.  If the
  78. `consecutive duplicates' threshhold is set high enough, we can
  79. reasonably assume that duplicate acks mean dropped packets.
  80.  
  81. But there's more information in the ack:  The receiver can only
  82. generate one in response to a packet arrival.  I.e., a duplicate
  83. ack means that a packet has left the network (it is now cached
  84. at the receiver).  If the sender is limitted by the congestion
  85. window, a packet can now be sent.  (The congestion window is a
  86. count of how many packets will fit in the pipe.  The ack says a
  87. packet has left the pipe so a new one can be added to take its
  88. place.)  To put this another way, say the current congestion
  89. window is C (i.e, C packets will fit in the pipe) and D
  90. duplicate acks have been received.  Then only C-D packets are
  91. actually in the pipe and the sender wants to use a window of C+D
  92. packets to fill the pipe to its estimated capacity (C+D sent -
  93. D received = C in pipe).
  94.  
  95. So, conceptually, the slow-start/cong.avoid/fast-rexmit changes
  96. are:
  97.  
  98.   - The sender's input routine is changed to set `cwnd' to `ssthresh'
  99.     when the dup ack threshhold is reached.  [It used to set cwnd to
  100.     mss to force a slow-start.]  Everything else stays the same.
  101.  
  102.   - The sender's output routine is changed to use an effective window
  103.     of min(snd_wnd, cwnd + dupacks*mss)  [the change is the addition
  104.     of the `dupacks*mss' term.]  `Dupacks' is zero until the rexmit
  105.     threshhold is reached and zero except when receiving a sequence
  106.     of duplicate acks.
  107.  
  108. The actual implementation is slightly different than the above
  109. because I wanted to avoid the multiply in the output routine
  110. (multiplies are expensive on some risc machines).  A diff of the
  111. old and new fastrexmit code is attached (your line numbers will
  112. vary).
  113.  
  114. Note that we still do congestion avoidance (i.e., the window is
  115. reduced by 50% when we detect the packet loss).  But, as long as
  116. the receiver's offered window is large enough (it needs to be at
  117. most twice the bandwidth-delay product), we continue sending
  118. packets (at exactly half the rate we were sending before the
  119. loss) even after the loss is detected so the pipe stays full at
  120. exactly the level we want and a slow-start isn't necessary.
  121.  
  122. Some algebra might make this last clear:  Say U is the sequence
  123. number of the first un-acked packet and we are using a window
  124. size of W when packet U is dropped.  Packets [U..U+W) are in
  125. transit.  When the loss is detected, we send packet U and pull
  126. the window back to W/2.  But in the round-trip time it takes
  127. the U retransmit to fill the receiver's hole and an ack to get
  128. back, W-1 dup acks will arrive (one for each packet in transit).
  129. The window is effectively inflated by one packet for each of
  130. these acks so packets [U..U+W/2+W-1) are sent.  But we don't
  131. re-send packets unless we know they've been lost so the amount
  132. actually sent between the loss detection and the recovery ack is
  133. U+W/2+W-1 - U+W = W/2-1 which is exactly the amount congestion
  134. avoidance allows us to send (if we add in the rexmit of U).  The
  135. recovery ack is for packet U+W so when the effective window is
  136. pulled back from W/2+W-1 to W/2 (which happens because the
  137. recovery ack is `new' and sets dupack to zero), we are allowed
  138. to send up to packet U+W+W/2 which is exactly the first packet
  139. we haven't yet sent.  (I.e., there is no sudden burst of packets
  140. as the `hole' is filled.)  Also, when sending packets between
  141. the loss detection and the recovery ack, we do nothing for the
  142. first W/2 dup acks (because they only allow us to send packets
  143. we've already sent) and the bottleneck gateway is given W/2
  144. packet times to clean out its backlog.  Thus when we start
  145. sending our W/2-1 new packets, the bottleneck queue is as empty
  146. as it can be.
  147.  
  148. [I don't know if you can get the flavor of what happens from
  149. this description -- it's hard to see without a picture.  But I
  150. was delighted by how beautifully it worked -- it was like
  151. watching the innards of an engine when all the separate motions
  152. of crank, pistons and valves suddenly fit together and
  153. everything appears in exactly the right place at just the right
  154. time.]
  155.  
  156. Also note that this algorithm interoperates with old tcp's:  Most
  157. pre-tahoe tcp's don't generate the dup acks on out-of-order packets.
  158. If we don't get the dup acks, fast retransmit never fires and the
  159. window is never inflated so everything happens in the old way (via
  160. timeouts).  Everything works just as it did without the new algorithm
  161. (and just as slow).
  162.  
  163. If you want to simulate this, the intended environment is:
  164.  
  165.     - large bandwidth-delay product (say 20 or more packets)
  166.  
  167.     - receiver advertising window of two b-d p (or, equivalently,
  168.       advertised window of the unloaded b-d p but two or more
  169.       connections simultaneously sharing the path).
  170.  
  171.     - average loss rate (from congestion or other source) less than
  172.       one lost packet per round-trip-time per active connection.
  173.       (The algorithm works at higher loss rate but the TCP selective
  174.       ack option has to be implemented otherwise the pipe will go empty
  175.       waiting to fill the second hole and throughput will once again
  176.       degrade at the product of the loss rate and b-d p.  With selective
  177.       ack, throughput is insensitive to b-d p at any loss rate.)
  178.  
  179. And, of course, we should always remember that good engineering
  180. practise suggests a b-d p worth of buffer at each bottleneck --
  181. less buffer and your simulation will exhibit the interesting
  182. pathologies of a poorly engineered network but will probably
  183. tell you little about the workings of the algorithm (unless the
  184. algorithm misbehaves badly under these conditions but my
  185. simulations and measurements say that it doesn't).  In these
  186. days of $100/megabyte memory, I dearly hope that this particular
  187. example of bad engineering is of historical interest only.
  188.  
  189.  - Van
  190.  
  191. -----------------
  192. *** /tmp/,RCSt1a26717    Mon Apr 30 01:35:17 1990
  193. --- tcp_input.c    Mon Apr 30 01:33:30 1990
  194. ***************
  195. *** 834,850 ****
  196.                    * Kludge snd_nxt & the congestion
  197.                    * window so we send only this one
  198. !                  * packet.  If this packet fills the
  199. !                  * only hole in the receiver's seq.
  200. !                  * space, the next real ack will fully
  201. !                  * open our window.  This means we
  202. !                  * have to do the usual slow-start to
  203. !                  * not overwhelm an intermediate gateway
  204. !                  * with a burst of packets.  Leave
  205. !                  * here with the congestion window set
  206. !                  * to allow 2 packets on the next real
  207. !                  * ack and the exp-to-linear thresh
  208. !                  * set for half the current window
  209. !                  * size (since we know we're losing at
  210. !                  * the current window size).
  211.                    */
  212.                   if (tp->t_timer[TCPT_REXMT] == 0 ||
  213. --- 834,850 ----
  214.                    * Kludge snd_nxt & the congestion
  215.                    * window so we send only this one
  216. !                  * packet.
  217. !                  *
  218. !                  * We know we're losing at the current
  219. !                  * window size so do congestion avoidance
  220. !                  * (set ssthresh to half the current window
  221. !                  * and pull our congestion window back to
  222. !                  * the new ssthresh).
  223. !                  *
  224. !                  * Dup acks mean that packets have left the
  225. !                  * network (they're now cached at the receiver) 
  226. !                  * so bump cwnd by the amount in the receiver
  227. !                  * to keep a constant cwnd packets in the
  228. !                  * network.
  229.                    */
  230.                   if (tp->t_timer[TCPT_REXMT] == 0 ||
  231. ***************
  232. *** 853,864 ****
  233.                   else if (++tp->t_dupacks == tcprexmtthresh) {
  234.                       tcp_seq onxt = tp->snd_nxt;
  235. !                     u_int win =
  236. !                         MIN(tp->snd_wnd, tp->snd_cwnd) / 2 /
  237. !                         tp->t_maxseg;
  238.   
  239.                       if (win < 2)
  240.                           win = 2;
  241.                       tp->snd_ssthresh = win * tp->t_maxseg;
  242.                       tp->t_timer[TCPT_REXMT] = 0;
  243.                       tp->t_rtt = 0;
  244. --- 853,864 ----
  245.                   else if (++tp->t_dupacks == tcprexmtthresh) {
  246.                       tcp_seq onxt = tp->snd_nxt;
  247. !                     u_int win = MIN(tp->snd_wnd,
  248. !                             tp->snd_cwnd);
  249.   
  250. +                     win /= tp->t_maxseg;
  251. +                     win >>= 1;
  252.                       if (win < 2)
  253.                           win = 2;
  254.                       tp->snd_ssthresh = win * tp->t_maxseg;
  255.                       tp->t_timer[TCPT_REXMT] = 0;
  256.                       tp->t_rtt = 0;
  257. ***************
  258. *** 866,873 ****
  259.                       tp->snd_cwnd = tp->t_maxseg;
  260.                       (void) tcp_output(tp);
  261.                       if (SEQ_GT(onxt, tp->snd_nxt))
  262.                           tp->snd_nxt = onxt;
  263.                       goto drop;
  264.                   }
  265.               } else
  266. --- 866,879 ----
  267.                       tp->snd_cwnd = tp->t_maxseg;
  268.                       (void) tcp_output(tp);
  269. !                     tp->snd_cwnd = tp->snd_ssthresh +
  270. !                                tp->t_maxseg *
  271. !                                tp->t_dupacks;
  272.                       if (SEQ_GT(onxt, tp->snd_nxt))
  273.                           tp->snd_nxt = onxt;
  274.                       goto drop;
  275. +                 } else if (tp->t_dupacks > tcprexmtthresh) {
  276. +                     tp->snd_cwnd += tp->t_maxseg;
  277. +                     (void) tcp_output(tp);
  278. +                     goto drop;
  279.                   }
  280.               } else
  281. ***************
  282. *** 874,877 ****
  283. --- 880,890 ----
  284.                   tp->t_dupacks = 0;
  285.               break;
  286. +         }
  287. +         if (tp->t_dupacks) {
  288. +             /*
  289. +              * the congestion window was inflated to account for
  290. +              * the other side's cached packets - retract it.
  291. +              */
  292. +             tp->snd_cwnd = tp->snd_ssthresh;
  293.           }
  294.           tp->t_dupacks = 0;
  295. *** /tmp/,RCSt1a26725    Mon Apr 30 01:35:23 1990
  296. --- tcp_timer.c    Mon Apr 30 00:36:29 1990
  297. ***************
  298. *** 223,226 ****
  299. --- 223,227 ----
  300.           tp->snd_cwnd = tp->t_maxseg;
  301.           tp->snd_ssthresh = win * tp->t_maxseg;
  302. +         tp->t_dupacks = 0;
  303.           }
  304.           (void) tcp_output(tp);
  305.  
  306. >From van@helios.ee.lbl.gov Mon Apr 30 10:37:36 1990
  307. To: end2end-interest@ISI.EDU
  308. Subject: modified TCP congestion avoidance algorithm (correction)
  309. Date: Mon, 30 Apr 90 10:36:12 PDT
  310. From: Van Jacobson <van@helios.ee.lbl.gov>
  311. Status: RO
  312. Content-Length: 838
  313. X-Lines: 27
  314.  
  315. I shouldn't make last minute 'fixes'.  The code I sent out last
  316. night had a small error:
  317.  
  318. *** t.c    Mon Apr 30 10:28:52 1990
  319. --- tcp_input.c    Mon Apr 30 10:30:41 1990
  320. ***************
  321. *** 885,893 ****
  322.                * the congestion window was inflated to account for
  323.                * the other side's cached packets - retract it.
  324.                */
  325. !             tp->snd_cwnd = tp->snd_ssthresh;
  326.           }
  327. -         tp->t_dupacks = 0;
  328.           if (SEQ_GT(ti->ti_ack, tp->snd_max)) {
  329.               tcpstat.tcps_rcvacktoomuch++;
  330.               goto dropafterack;
  331. --- 885,894 ----
  332.                * the congestion window was inflated to account for
  333.                * the other side's cached packets - retract it.
  334.                */
  335. !             if (tp->snd_cwnd > tp->snd_ssthresh)
  336. !                 tp->snd_cwnd = tp->snd_ssthresh;
  337. !             tp->t_dupacks = 0;
  338.           }
  339.           if (SEQ_GT(ti->ti_ack, tp->snd_max)) {
  340.               tcpstat.tcps_rcvacktoomuch++;
  341.               goto dropafterack;
  342.  
  343.