home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_a_c / draft-ietf-bmwg-ippm-treno-btc-01.txt < prev    next >
Text File  |  1997-08-05  |  17KB  |  351 lines
  1.   Network Working Group                                    Matt Mathis
  2.   INTERNET-DRAFT                      Pittsburgh Supercomputing Center
  3.   Expiration Date:  Jan 1998                                 July 1997
  4.  
  5.  
  6.         Empirical Bulk Transfer Capacity
  7.         < draft-ietf-bmwg-ippm-treno-btc-01.txt >
  8.  
  9.  
  10. Status of this Document
  11.  
  12. This document is an Internet-Draft.  Internet-Drafts are working documents 
  13. of the Internet Engineering Task Force (IETF), its areas, and its working 
  14. groups.  Note that other groups may also distribute working documents as  
  15.  Internet-Drafts.
  16.  
  17. Internet-Drafts are draft documents valid for a maximum of six months and 
  18. may be updated, replaced, or obsoleted by other documents at any time.  It 
  19. is inappropriate to use Internet-Drafts as reference material or to cite 
  20. them other than as "work in progress."
  21.  
  22. To learn the current status of any Internet-Draft, please check the 
  23. "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 
  24. Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au 
  25. (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West 
  26. Coast).
  27.  
  28. Abstract:
  29.  
  30. Bulk Transport Capacity (BTC) is a measure of a network's ability to 
  31. transfer significant quantities of data with a single congestion-aware 
  32. transport connection (e.g. state-of-the-art TCP).  For many applications 
  33. the BTC of the underlying network dominates the overall elapsed time for 
  34. the application, and thus dominates the performance as perceived by a user.
  35. The BTC is a property of an IP cloud (links, routers, switches, etc.) 
  36. between a pair of hosts.  It does not include the hosts themselves (or 
  37. their transport-layer software).  However, congestion control is crucial to 
  38. the BTC metric because the Internet depends on the end systems to fairly 
  39. divide the available bandwidth on the basis of common congestion behavior. 
  40.  The BTC metric is based on the performance of a reference congestion 
  41. control algorithm that has particularly uniform and stable behavior.
  42.  
  43. Introduction:
  44.  
  45. Bulk Transport Capacity (BTC) is a measure of a network's ability to 
  46. transfer significant quantities of data with a single congestion-aware 
  47. transport connection (e.g. state-of-the-art TCP).  For many applications 
  48. the BTC of the underlying network dominates the overall elapsed time for 
  49. the application, and thus dominates the performance as perceived by a user. 
  50.  Examples of such applications include FTP and other network copy 
  51. utilities.
  52.  
  53. The BTC is a property of an IP cloud (links, routers, switches, etc.) 
  54. between a pair of hosts.  It does not include the hosts themselves (or 
  55. their transport-layer software).  However, congestion control is crucial to 
  56. the BTC metric because the Internet depends on the end systems to fairly 
  57. divide the available bandwidth on the basis of common congestion behavior.
  58.  
  59. Four standard control congestion algorithms are described in RFC2001: 
  60. Slow-start, Congestion Avoidance, Fast Retransmit and Fast Recovery.  Of 
  61. these algorithms, Congestion Avoidance drives the steady-state bulk 
  62. transfer behavior of TCP.  It calls for opening the congestion window by 1 
  63. segment size on each round trip time, and closing it by 1/2 on congestion, 
  64. as signaled by lost segments.
  65.  
  66. Slow-start is part of TCP's transient behavior.  It is used to quickly 
  67. bring new or recently timed out connections up to an appropriate congestion 
  68. window.
  69.  
  70. In Reno TCP, Fast Retransmit and Fast Recovery are used to support the 
  71. Congestion Avoidance algorithm during recovery from lost segments.  During 
  72. the recovery interval the data receiver sends duplicate acknowledgements, 
  73. which the data sender must use to identify missing segments as well as to 
  74. estimate the quantity of outstanding data in the network.  The research 
  75. community has observed unpredictable or unstable TCP performance caused by 
  76. errors and uncertainties in the estimation of outstanding data [Lakshman94, 
  77. Floyd95, Hoe95].  Simulations of reference TCP implementations have 
  78. uncovered situations where incidental changes in other parts of the network 
  79. have a large effect on performance [Mathis96].  Other simulations have 
  80. shown that under some conditions, slightly better networks (higher 
  81. bandwidth or lower delay) yield lower throughput [This is easy to 
  82. construct, but has it been published?].  As a consequence, even reference 
  83. TCP implementations do not make good metrics.
  84.  
  85. Furthermore, many TCP implementations in use in the Internet today have 
  86. outright bugs which can have arbitrary and unpredictable effects on 
  87. performance [Comer94, Brakmo95, Paxson97a, Paxson97b].
  88.  
  89. The difficulties with using TCP for measurement can be overcome by using 
  90. the Congestion Avoidance algorithm by itself, in isolation from other 
  91. algorithms.  In [Mathis97] it is shown that the performance of the 
  92. Congestion Avoidance algorithm can be predicted by a simple analytical 
  93. model.  The model was derived in [Ott96a, Ott96b].  The model predicts the 
  94. performance of the Congestion Avoidance algorithm as a function of the 
  95. round trip time, and the TCP segment size and the probability of receiving 
  96. a congestion signal (i.e. packet loss).  The paper shows that the model 
  97. accurately predicts the performance of TCP using the SACK option [RFC2018] 
  98. under a wide range of conditions.  If losses are isolated (no more than one 
  99. per round trip) then Fast Recovery successfully estimates the actual 
  100. congestion window during recovery, and Reno TCP also fits the model.
  101.  
  102. This version of the BTC metric is based on the TReno ("tree-no") 
  103. diagnostic, which implements a protocol-independent version of the 
  104. Congestion Avoidance algorithm.  TReno's internal protocol is designed to 
  105. accurately implement the Congestion Avoidance algorithm under a very wide 
  106. range of conditions, and to diagnose timeouts when they interrupt 
  107. Congestion Avoidance.  In [Mathis97] it is observed that TReno fits the 
  108. same performance model as SACK and Reno TCPs.   [Although the paper was 
  109. written using an older version of TReno, which has less accurate internal 
  110. measurements.]
  111.  
  112. Implementing the Congestion Avoidance algorithm within a diagnostic tool 
  113. eliminates calibration problems associated with the non-uniformity of 
  114. current TCP implementations.  However, like all empirical metrics it 
  115. introduces new problems, most notably the need to certify the correctness 
  116. of the implementation and to verify that there are not systematic errors 
  117. due to limitations of the tester.
  118.  
  119. Many of the calibration checks can be included in the measurement process 
  120. itself.  The TReno program includes error and warning messages for many 
  121. conditions that indicate either problems with the infrastructure or in some 
  122. cases problems with the measurement process.  Other checks need to be 
  123. performed manually.
  124.  
  125. Metric Name: TReno-Type-P-Bulk-Transfer-Capacity
  126. (e.g. TReno-UDP-BTC)
  127.  
  128. Metric Parameters: A pair of IP addresses, Src (aka "tester")
  129. and Dst (aka "target"), a start time T and initial MTU.
  130.  
  131. Definition: The average data rate attained by the Congestion
  132. Avoidance algorithm, while using type-P packets to probe the forward (Src 
  133. to Dst) path.  In the case of ICMP ping, these messages also probe the 
  134. return path.
  135.  
  136. Metric Units: bits per second
  137.  
  138. Ancillary results:
  139. * Statistics over the entire test
  140. (data transferred, duration and average rate)
  141. * Statistics over the Congestion Avoidance portion of the test (data 
  142. transferred, duration and average rate)
  143. * Path property statistics (MTU, Min RTT, max cwnd during Congestion 
  144. Avoidance and max cwnd during Slow-start)
  145. * Direct measures of the analytic model parameters (Number of congestion 
  146. signals, average RTT)
  147. * Indications of which TCP algorithms must be present to attain the same 
  148. performance.
  149. * The estimated load/BW/buffering used on the return path
  150. * Warnings about data transmission abnormalities.
  151. (e.g. packets out-of-order, events that cause timeouts)
  152. * Warnings about conditions which may affect metric accuracy. (e.g. 
  153. insufficient tester buffering)
  154. * Alarms about serious data transmission abnormalities.
  155. (e.g. data duplicated in the network)
  156. * Alarms about internal inconsistencies of the tester and events which 
  157. might invalidate the results.
  158. * IP address/name of the responding target.
  159. * TReno version.
  160.  
  161. Method: Run the TReno program on the tester with the chosen packet type 
  162. addressed to the target.  Record both the BTC and the ancillary results.
  163. Manual calibration checks:  (See detailed explanations below).
  164.  
  165. * Verify that the tester and target have sufficient raw bandwidth to 
  166. sustain the test.
  167. * Verify that the tester and target have sufficient buffering to support 
  168. the window needed by the test.
  169. * Verify that there is not any other system activity on the tester or 
  170. target.
  171. * Verify that the return path is not a bottleneck at the load needed to 
  172. sustain the test.
  173. * Verify that the IP address reported in the replies is an appropriate 
  174. interface of the selected target.
  175.  
  176. Version control:
  177.  
  178. * Record the precise TReno version (-V switch)
  179. * Record the precise tester OS version, CPU version and speed, interface 
  180. type and version.
  181.  
  182. Discussion:
  183.  
  184. Note that the BTC metric is defined specifically to be the average data 
  185. rate between the source and destination hosts.  The ancillary results are 
  186. designed to detect possible measurement problems, and to help diagnose the 
  187. network.  The ancillary results should not be used as metrics in their own 
  188. right.
  189.  
  190. The current version of TReno does not include an accurate model for TCP 
  191. timeouts or their effect on average throughput.  TReno takes the view that 
  192. timeouts reflect an abnormality in the network, and should be diagnosed as 
  193. such.
  194.  
  195. There are many possible reasons why a TReno measurement might not agree 
  196. with the performance obtained by a TCP-based application.  Some key ones 
  197. include: older TCPs missing key algorithms such as MTU discovery, support 
  198. for large windows or SACK, or mis-tuning of either the data source or sink. 
  199.  
  200. Some network conditions which require the newer TCP algorithms are 
  201. detected by TReno and reported in the ancillary results.  Other documents 
  202. will cover methods to diagnose the difference between TReno and TCP 
  203. performance.
  204.  
  205. It would raise the accuracy of TReno's traceroute mode if the ICMP "TTL 
  206. exceeded" messages were generated at the target and transmitted along the 
  207. return path with elevated priority (reduced losses and queuing delays).
  208. People using the TReno metric as part of procurement documents should be 
  209. aware that in many circumstances MTU has an intrinsic and large impact on 
  210. overall path performance.  Under some conditions the difficulty in meeting 
  211. a given performance specifications is inversely proportional to the square 
  212. of the path MTU.  (e.g. Halving the specified MTU makes meeting the 
  213. bandwidth specification 4 times harder.)
  214.  
  215. When used as an end-to-end metric TReno presents exactly the same load to 
  216. the network as a properly tuned state-of-the-art bulk TCP stream between 
  217. the same pair of hosts.  Although the connection is not transferring useful 
  218. data, it is no more wasteful than fetching an unwanted web page with the 
  219. same transfer time.
  220.  
  221. Calibration checks:
  222.  
  223. The following discussion assumes that the TReno diagnostic is implemented 
  224. as a user mode program running under a standard operating system.  Other 
  225. implementations, such as thoes in dedicated measurement instruments, can 
  226. have stronger built-in calibration checks.
  227.  
  228. The raw performance (bandwidth) limitations of both the tester
  229. and target should be measured by running TReno in a controlled
  230. environment (e.g. a bench test).  Ideally the observed
  231. performance limits should be validated by diagnosing the nature
  232. of the bottleneck and verifying that it agrees with other
  233. benchmarks of the tester and target (e.g. That TReno performance
  234. agrees with direct measures of backplane or memory bandwidth or
  235. other bottleneck as appropriate).  These raw performance
  236. limitations may be obtained in advance and recorded for later
  237. reference.  Currently no routers are reliable targets, although
  238. under some conditions they can be used for meaningful measurements.  When 
  239. testing between a pair of modern computer systems at a few megabits per 
  240. second or less, the tester and target are unlikely to be the bottleneck.
  241. TReno may not be accurate, and should not be used as a formal metric, at 
  242. rates above half of the known tester or target limits.  This is because 
  243. during the initial Slow-start TReno needs to be able to send bursts which 
  244. are twice the average data rate.
  245.  
  246. Likewise, if the link to the first hop is not more than twice as fast as 
  247. the entire path, some of the path properties such as max cwnd during 
  248. Slow-start may reflect the testers link interface, and not the path itself.
  249. Verifying that the tester and target have sufficient buffering is 
  250. difficult.  If they do not have sufficient buffer space, then losses at 
  251. their own queues may contribute to the apparent losses along the path. 
  252. There are several difficulties in verifying the tester and target buffer 
  253. capacity.  First, there are no good tests of the target's buffer capacity 
  254. at all.  Second, all validation of the testers buffering depends in some 
  255. way on the accuracy of reports by the tester's own operating system. 
  256. Third, there is the confusing result that in many circumstances 
  257. (particularly when there is much more than sufficient average tester 
  258. performance) insufficient buffering in the tester does not adversely impact 
  259. measured performance.
  260.  
  261. TReno reports (as calibration alarms) any events in which transmit packets 
  262. were refused due to insufficient buffer space.  It reports a warning if the 
  263. maximum measured congestion window is larger than the reported buffer 
  264. space.  Although these checks are likely to be sufficient in most cases 
  265. they are probably not sufficient in all cases, and will be the subject of 
  266. future research.
  267.  
  268. Note that on a timesharing or multi-tasking system, other activity on the 
  269. tester introduces burstiness due to operating system scheduler latency. 
  270. Since some queuing disciplines discriminate against bursty sources, it is 
  271. important that there be no other system activity during a test.  This 
  272. should be confirmed with other operating system specific tools.
  273.  
  274. In ICMP mode TReno measures the net effect of both the forward and return 
  275. paths on a single data stream.  Bottlenecks and packet losses in the 
  276. forward and return paths are treated equally.
  277.  
  278. In traceroute mode, TReno computes and reports the load it contributes to 
  279. the return path.  Unlike real TCP, TReno can not distinguish between losses 
  280. on the forward and return paths, so ideally we want the return path to 
  281. introduce as little loss as possible.  A good way to test to see if the 
  282. return path has a large effect on a measurement is to reduce the forward 
  283. path messages down to ACK size (40 bytes), and verify that the measured 
  284. packet rate is improved by at least factor of two.  [More research is 
  285. needed.]
  286.  
  287. References
  288.  
  289. [Brakmo95], Brakmo, S., Peterson, L., "Performance problems in BSD4.4 TCP", 
  290. Proceedings of ACM SIGCOMM '95, October 1995.
  291.  
  292. [Comer94], Comer, C., Lin, J., "Probing TCP Implementations", USENIX Summer 
  293. 1994, June 1994.
  294.  
  295. [Floyd95] Floyd, S., "TCP and successive fast retransmits", February 1995, 
  296. Obtain via ftp://ftp.ee.lbl.gov/papers/fastretrans.ps.
  297.  
  298. [Hoe95] Hoe, J., "Startup dynamics of TCP's congestion control and 
  299. avoidance schemes".  Master's thesis, Massachusetts Institute of 
  300. Technology, June 1995.
  301.  
  302. [Jacobson88] Jacobson, V., "Congestion Avoidance and Control", Proceedings 
  303. of SIGCOMM '88, Stanford, CA., August 1988.
  304.  
  305. [mathis96] Mathis, M. and Mahdavi, J. "Forward acknowledgment:
  306. Refining TCP congestion control",  Proceedings of ACM SIGCOMM '96, 
  307. Stanford, CA., August 1996.
  308.  
  309. [RFC2018] Mathis, M., Mahdavi, J. Floyd, S., Romanow, A., "TCP Selective 
  310. Acknowledgment Options", 1996 Obtain via:
  311. ftp://ds.internic.net/rfc/rfc2018.txt
  312.  
  313. [Mathis97] Mathis, M., Semke, J., Mahdavi, J., Ott, T., "The Macroscopic 
  314. Behavior of the TCP Congestion Avoidance Algorithm", Computer 
  315. Communications Review, 27(3), July 1997.
  316.  
  317. [Ott96a], Ott, T., Kemperman, J., Mathis, M., "The Stationary
  318. Behavior of Ideal TCP Congestion Avoidance", In progress, August
  319. 1996. Obtain via pub/tjo/TCPwindow.ps using anonymous ftp to
  320. ftp.bellcore.com
  321.  
  322. [Ott96b], Ott, T., Kemperman, J., Mathis, M., "Window Size Behavior in 
  323. TCP/IP with Constant Loss Probability", DIMACS Special Year on Networks, 
  324. Workshop on Performance of Real-Time Applications on the Internet, Nov 
  325. 1996.
  326.  
  327. [Paxson97a] Paxson, V "Automated Packet Trace Analysis of TCP 
  328. Implementations", Proceedings of ACM SIGCOMM '97, August 1997.
  329.  
  330. [Paxson97b] Paxson, V, editor "Known TCP Implementation Problems",
  331. Work in progress: http://reality.sgi.com/sca/tcp-impl/prob-01.txt
  332.  
  333. [Stevens94] Stevens, W., "TCP/IP Illustrated, Volume 1: The Protocols", 
  334. Addison-Wesley, 1994.
  335.  
  336. [RFC2001] Stevens, W., "TCP Slow Start, Congestion Avoidance,
  337. Fast Retransmit, and Fast Recovery Algorithms",
  338. ftp://ds.internic.net/rfc/rfc2001.txt
  339.  
  340.  
  341.  
  342.  
  343. Author's Address
  344.      Matt Mathis
  345.      email: mathis@psc.edu
  346.      Pittsburgh Supercomputing Center
  347.      4400 Fifth Ave.
  348.      Pittsburgh PA 15213
  349.  
  350.  
  351.