Network Working Group A. Saurin Internet-Draft C. Perkins Expires: January 6, 2006 University of Glasgow July 5, 2005 TFRC Testing Strategies draft-saurin-tsvwg-tfrc-testing-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on January 6, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This memo describes a possible testing strategy for TFRC implementations. Saurin & Perkins Expires January 6, 2006 [Page 1] Internet-Draft tfrc-testing July 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Glossary of Terms . . . . . . . . . . . . . . . . . . . . . . 3 3. Testing Overview . . . . . . . . . . . . . . . . . . . . . . . 3 3.1 Components Layout . . . . . . . . . . . . . . . . . . . . 3 3.2 Parts Tested . . . . . . . . . . . . . . . . . . . . . . . 4 4. Data Transport . . . . . . . . . . . . . . . . . . . . . . . . 4 4.1 System Initialization . . . . . . . . . . . . . . . . . . 4 4.2 Basic Behavior . . . . . . . . . . . . . . . . . . . . . . 5 5. Sender Behavior . . . . . . . . . . . . . . . . . . . . . . . 6 5.1 RTT Measurement . . . . . . . . . . . . . . . . . . . . . 6 5.2 Errors with Feedback Reports . . . . . . . . . . . . . . . 7 5.3 TFRC Sending Rate . . . . . . . . . . . . . . . . . . . . 8 5.4 Inter-Packet Interval Calculation . . . . . . . . . . . . 10 5.5 Slow-Start Algorithm . . . . . . . . . . . . . . . . . . . 10 5.6 Oscillation Prevention . . . . . . . . . . . . . . . . . . 10 6. Receiver Behavior . . . . . . . . . . . . . . . . . . . . . . 11 6.1 Feedback Mechanism . . . . . . . . . . . . . . . . . . . . 11 6.2 Loss Event Rate Estimation . . . . . . . . . . . . . . . . 12 7. Open Issues and Future Work . . . . . . . . . . . . . . . . . 14 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 11. Normative References . . . . . . . . . . . . . . . . . . . . 14 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 15 Intellectual Property and Copyright Statements . . . . . . . . 16 Saurin & Perkins Expires January 6, 2006 [Page 2] Internet-Draft tfrc-testing July 2005 1. Introduction TFRC is "a congestion control mechanism designed for unicast flows operating in an Internet environment and competing with TCP traffic" [2]. This memo describes a possible testing strategy for TFRC implementations. These tests are intended to help demonstrate correctness of implementations, and to illustrate common problems. However, they are not intended to be an exhaustive set of tests, and passing these tests does not necessarily imply conformance to the complete TFRC specification. 2. Glossary of Terms The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [1] 3. Testing Overview 3.1 Components Layout The architecture for testing TFRC requires three major components: two end systems, performing as communicating elements, and an interface system, acting as communication medium and testing instrument. +------------------+ +--------+ Interface System +-----+ | +------------------+ | | | +-------+--------+ +-------+--------+ | First TFRC | | Second TFRC | | implementation | | implementation | | (Sender) | | (Receiver) | +----------------+ +----------------+ The interface system must be capable of sending arbitrarily packets to both TFRC implementations, and of receiving packets sent by the sender implementation, parsing them, computing metrics based on those packets, and transmitting them to the receiver. This system should also be able to discard or reorder selected packets, or to introduce some delay in the transmission process. The testing framework is independant of the internal details of the TFRC implementation. Most of the tests have a zero knowledge of the system used, considering it as a black box and observing only the Saurin & Perkins Expires January 6, 2006 [Page 3] Internet-Draft tfrc-testing July 2005 interchanged information. However, some other tests have been proposed as optional, just in case there is enough information of the inner organization of the system. 3.2 Parts Tested For the testing of TFRC we must stress the following main parts of the protocol: o The basic interchage of information and interoperatibility (Section 4). o The RTT estimation (Section 5.1). o The TFRC sending rate calculation and inter-packet spacing (Section 5.3 and Section 5.4). o The feedback mechanism (Section 5.2 and Section 6.1). o The loss detection, loss history and associated loss rate estimation (Section 6.2). The following sections describe a series of tests for these parts of the TFRC protocol. 4. Data Transport The intention of these tests is to show that basic communication can be performed between the two TFRC implementations. In order to verify this, the system initialization must be tested as well as the basic operation of the system. 4.1 System Initialization In these tests, tested the correct initialization of both end points will be tested, in particular the initial values for the fundamental parameters. The sender initialization is tested first. There few specific tests for the sender, as the estimated RTT, R_i, and the RTO, t_RTO, have unspecified initial state. The sender initialization tests are limited to verifying that, for the first data packet sent, the sequence number is 0 (or an initial value chosen). The test continues with the receiver initialization. The receiver is initialized when the first packet from the sender arrives. When the Saurin & Perkins Expires January 6, 2006 [Page 4] Internet-Draft tfrc-testing July 2005 receiver receives an initial data packet at t_1, with sequence number 0, i=0, and associated timestamp, ts_0=0, and RTT, R_0=0, some checks must be performed: 1. Verify that the receiver sends a feedback report at t_2, t_2 = t_1 + t_delay. 2. Verify that the value reported for t_delay matches the time elapsed between t_1 and t_2. 3. Verify that the value reported for X_recv is equal to the packet size. 4. Verify that the value reported for t_recvdata is 0. 5. Verify that the value reported for p is 0. 6. Verify that the sender receives this feedback report. These tests demonstrate that the receiver correctly processes the first data packet, and is initialized with appropriate state. 4.2 Basic Behavior The purpose of these tests is to verify the basic correctness of the implementation of the TFRC transmission rules. These requirements can be verified at any point in a session. The sender application must be able to handle the following cases o Verify that the sequence number is incremented by one for each data packet sent. o Verify that the timestamp is incremented for each data packet sent. o Verify correct operation during sequence number wrap-around. o Verify correct operation during timestamp wrap-around. The receiver should also be verified to correctly handle the following edge cases: o Verify correct operation during sequence number wrap-around. o Verify correct operation during timestamp wrap-around. Saurin & Perkins Expires January 6, 2006 [Page 5] Internet-Draft tfrc-testing July 2005 5. Sender Behavior In this section, in addition to the basic communicacion requirements of Section 4, other features of the sender behavior must be verified. In particular, the RTT measurement, the feedback mechanism and the sending rate. 5.1 RTT Measurement It should be verified that the initial conditions regarding the RTT are correctly initialized in both systems. This process is described in Section 4.3 of [2]. As the RTT known by the receiver is provided by the sender, a correct measure by the sender is decisive. For the first test, we will tests how the receiver measures the RTT using the RTT sample provided in every feedback report. In order to do this, we will use a t_delay of 0 ms in the receiver, and the interface system will initially simulate a fixed 10ms delay between both systems that will not change depending on the queue length. The sender will initialize the system sending an initial data packet at t_0. 1. Verify that the first RTT reported by the sender is 0 (or null). 2. Verify that the first t_delay reported by the receiver is 0. 3. Verify that the first not-null RTT reported by the sender is equal to the RTT sample, 0.020. If this test succeeded, the process should be repeated for some time, keeping the network delay and send rate constant. 1. Verify that the RTT reported by the sender, R_i, is constant, R_i = 0.020, provided that the network delay is constant. If this test succeeds, the interface system will change the simulated delay to 20ms after the reception of a feedback report, at t_2. Next feedback report, received at t_3, t_3 = t_2 + 0.020, will provide a new R_sample. Next data packet, sent at t_4, t_4 > t_3, and with sequence number j, will include a different RTT measure: 1. Verify that the value reported for RTT in the data packet with sequence number j is 22ms. For subsequent data packet sent after a feedback report is received, Saurin & Perkins Expires January 6, 2006 [Page 6] Internet-Draft tfrc-testing July 2005 the RTT measure included must follow a known sequence: 1. Verify that the RTT included in the data packets evolves following the sequence 23.8ms, 25.42ms, 26.87ms, 28.19ms, 29.37ms, 30.43ms, 31.39ms, 32.25ms, 33.02ms... 2. Verify that, for every successive data packet sent after a feedback report, the RTT included, R_i, is equal to the new RTT estimation, R = 0,9*R + 0.1*(t_now - t_recvdata). 5.2 Errors with Feedback Reports The sender behavior should be verified for the absence of feedback reports. In order to verify this, the sender will be initialized, but the receiver will not send any feedback report. The sender has no knowledge of the RTT, so it must wait up to 2 seconds for a feedback report. o Verify that the sender sends one packet per second for two seconds. o Verify that the sender halves its sending rate every two seconds. o Verify that the sender reaches a minimum sending rate of one packet every 64 seconds. TIME: 0.000000 SEQ: 0 TIME: 1.000000 SEQ: 1 TIME: 2.000000 SEQ: 2 TIME: 4.000000 SEQ: 3 TIME: 6.000000 SEQ: 4 TIME: 10.000000 SEQ: 5 TIME: 14.000000 SEQ: 6 TIME: 22.000000 SEQ: 7 TIME: 30.000000 SEQ: 8 TIME: 46.000000 SEQ: 9 TIME: 62.000000 SEQ: 10 TIME: 94.000000 SEQ: 11 TIME: 126.000000 SEQ: 12 TIME: 190.000000 SEQ: 13 TIME: 254.000000 SEQ: 14 The behavior of the sender must change if no feedback information is received for some time, given by the current RTO. In order to verify this, the sender must begin sending packets and Saurin & Perkins Expires January 6, 2006 [Page 7] Internet-Draft tfrc-testing July 2005 the sender must respond with ACK packets, continuing with the normal operation until t=500ms, when all feedback reports must be suspended again. At this moment, we must take into account the last RTT, r, and sending rate, x, known by the sender when the last feedback report was received at the moment t. o Verify that, if the sender does not receive a feedback report in four RTT, at t+4r, it halves its sending rate, X=x/2. This situation must be kept for some time, discarding all feedback reports, verifying that the sender spaces packets accordingly. o Verify that the sender halves the sender rate every 4*r seconds . o Verify that the inter-packet interval is decreased until it reaches a minimum value of one packet every 64 seconds (as specified in Section 4.3 of [2]) 5.3 TFRC Sending Rate A TFRC implementation should be conformant to the throughput formula. For t_RTO = 4*R and b = 1, the throughput equation is: X= S/R*f(p) f(p) = sqrt(2*p/3) + (12*sqrt(3*p/8) * p * (1+32*p^2)) This formula depends on three parameters: the packet size (s), the loss event rate (p) and the RTT (R). Setting all three parameters to known values for a period of time should produce a known sending rate for the same period. Alternatively, if we set two parameters with known values but we change the last one, we should be able to observe a conforming variation in the sending rate of the sending system. To ensure this, some tests must be performed: o Fixing the packet size to S, the loss event rate to P and the RTT to R for a time T, verify that the calculated sending rate X corresponds to these values. Saurin & Perkins Expires January 6, 2006 [Page 8] Internet-Draft tfrc-testing July 2005 Varying p: s=1500 p=0.006 R=0.010 -> X=2.25006*10^6 s=1500 p=0.026 R=0.010 -> X=919512 s=1500 p=0.100 R=0.010 -> X=265515 Varying S: s=1500 p=0.010 R=0.010 -> X=1.68498*10^6 s=4800 p=0.006 R=0.010 -> X=7.20021*10^6 s=9000 p=0.006 R=0.010 -> X=1.35004*10^7 Varying RTT: s=1500 p=0.006 R=0.001 -> X=2.25006*10^7 s=1500 p=0.006 R=0.200 -> X=112503 s=1500 p=0.006 R=0.400 -> X=56251.6 o Fixing the packet size to S and the loss event rate to P for a time T, verify that a change of R in the RTT produces a change of X in the sending rate. o Fixing the packet size to S and the RTT to R for a time T, verify that a change of P in the loss event rate produces a change of X in the sending rate. We don't take into account a variation in the packet size, as it should be constant. It must also be verified that the real sending rate matches the amount of data sent in a RTT, R. This can be tested in the following manner. The interface system must measure the amount of data interchanged between two feedback reports, received at times t_1 and t_2, provided that the receiver is sending one report per RTT, t_2 - t_1=R. Taking into account the first data packet sent after t_1, at t_d, t_1 < t_d < t_2, and the sending rate, X_d, and RTT, R_d, included: o Verify that the amount of data send between t_d and t_2 matches the sending rate for that period, X_d*R_d. In addition, some tests should be performed to verify that the sender conforms to the data reported by the receiver. Some checks could be: o Verify that the sending rate is always less than twice the X_recv reported by the receiver. Saurin & Perkins Expires January 6, 2006 [Page 9] Internet-Draft tfrc-testing July 2005 5.4 Inter-Packet Interval Calculation It must be verified that the inter-packet interval matches the current sending rate reported by the sender (see Section 4.6 of [2]). In order to tests this, the sender must send packets to the receiver, and the interface system must log the times when these packets are sent. The packet size, S, is known, as it is the sending rate, X. o Verify that the average space between packets in one RTT is S/X. 5.5 Slow-Start Algorithm To perform this test, the system must be intialized. The sender will send packets and the reciever will answer with the corresponding feedback reports. The interface system must measure the amount of data sent between consecutive reports. o Verify that the sender doubles the sending rate once per RTT (see Section 4.3 of [2]). o Verify that the receiver reports a null value for the loss event rate, p=0. This situation can be sustained for some time, until t_1, where the last sending rate of the sender is X_1. After that, the receiver must report a loss event rate greater than 0, p_1 > 0, in order to test that the sender finishes the slow start phase. o Verify that the first data packet sent after t_1, at t_2, includes a sending rate, X_2, with X_2 < X_1. 5.6 Oscillation Prevention This is an OPTIONAL feature (specified in Section 4.5 of [2]). To prevent oscillations in the sending rate, the sender keeps an estimate of the long-term RTT and sets its sending rate depending on how much the last RTT differs from this mean value. For this testing scenario, the sender must be initialized and the receiver must send feedback reports on a regular basis. The RTT must be kept fixed at 20ms for at least two RTT (producing a internal value of 0.141421 for R_sqmean). This must must be kept for some time until a feedback reports arrives Saurin & Perkins Expires January 6, 2006 [Page 10] Internet-Draft tfrc-testing July 2005 at t_1. After this, the RTT must be halved, RTT = 10ms, and a new feedback report will arrive at t_2, providing an updated RTT sample. If the sending rate at t_1 was X_1, and the sending rate reported in the first data packet sent after t_2 is X_2: 1. If the internal value of R_sqmean is known, verify that R_sqmean is updated and its value is 0.137279. 2. Verify that the sending rate X_2 is X_1 * R_sqmean/sqrt(R_sample) = X_1 * 1.37279. This test must be performed again, but this time the RTT must be doubled after t_1, setting RTT=40ms. 1. If the internal value of R_sqmean is know, verify that R_sqmean is updated and its value is 0.147279. 2. Verify that the sending rate X_2 is X_1 * R_sqmean/sqrt(R_sample) = X_1 * 0.736396. These tests demonstrate that the receiver correctly calculates R_sqmean based on an expentially weighted moving average of the observed RTT values. 6. Receiver Behavior In this section, some advanced characteristics of the receiver will be verified. In particular, the feedback mechanism and some aspects of the loss event rate calculation. 6.1 Feedback Mechanism The receiver is expected to send a feedback report once per RTT. The following tests verify the accuracy of the information provided in a feedback report. The sender begins transmission, with the delay through the interface system kept constant for at least two RTTs. It must be known the RTT, R_1, when last feedback report arrived at the sender, at t_1. The interface system must then record all packets, since t_1 to t_2, t_2 - t_1 = R_1. 1. Verify that a feedback report is sent at t2. 2. Verify that the reported timestamp of last packet received, t_recvdata, matches the timestamp, t_last, of the last packet received, t_last < t_2. Saurin & Perkins Expires January 6, 2006 [Page 11] Internet-Draft tfrc-testing July 2005 The sending rate reported in the absence of losses must match the sending rate of the sender. Calculating the amount of data, d, sent in the interval between t_1 and t_2: o Verify that the reported sending rate as seen by the receiver, X_recv, matches the sending rate of the sender, X, in the previous RTT. o Verify that the sending rate as seen by the receiver, X_recv, matches the amount of data received since t_1, X_recv = d/RTT. Feedback reports must be sent only when some data has been received since the last one was sent. In order to test this, all data packets must be discarded after a feedback report arrrives at the sender, at t_1. If the last RTT known by the receiver was R_1, then a new feedback report would be expected at t_2 = t_1 + R_1. o Verify that there is no feedback report sent at t_2 o Verify that there is no feedback report sent while there are no data packets. 6.2 Loss Event Rate Estimation In the next test it will be tested some aspect of Section 5.1 of [2]. The receiver is required to keep a history of packets that have been successfully transmited in order to detect a lost packet. Using this facility, the loss detection system must register in a loss history any lost packet, and any change in this history will modify the current loss event rate reported. In these tests, the first implementation is made to transmit data packets, which are then received by the second implementation. The test instrument must discard some packets sent by the sender in order to simulate losses. An increment in the reported loss event rate will indicate that the loss has been detected. In the first test, a packet with sequence number i is discarded: o Verify that, after the receiver system receives three packets with sequence numbers i+1, i+2 and i+3, this is detected as a loss. o Verify that the receiver sends a feedback report immediately after it detects the loss. o Verify that the p reported has been increased. Saurin & Perkins Expires January 6, 2006 [Page 12] Internet-Draft tfrc-testing July 2005 If this tests succeded, the process should be repeated but with some packet reordering. In this case, no packet will be discarded, but some packets must be delayed by the test instrument, altering their natural sequence: o Verify that, after the receiver system receives three packets with sequence numbers i+2, i and i+1, this is not detected as a loss. o Verify that, after the receiver system receives four packets with sequence numbers i+3, i+2, i+1 and i, the last packet is detected as a lost packet. o Verify that the receiver sends a feedback report immediately after it detects the loss. o Verify that the p reported has been increased. In the next test it will be tested some aspect of loss computation (Section 5.2 of [2]). Like in the previous test, the testing instrument should discard some packets and verify the behavior of the receiver under such circumstances. However, it must be taken into account the state of the sender before the loss is produced. In particular, the RTT and p must be known. In this test, the interface system discards two packets in the same RTT, with sequence numbers i and i+1. o Verify that the receiver sends a feedback report after the packet with sequence number i+4 has been received. o Verify that there is an increment in the value of p reported by the receiver. o Verify that, discarding two packets in a RTT, it has the same effect as a single loss on the loss measurement. The test must be repeated with the same initial conditions. However, only one packet will be discarded this time: o Verify that a feedback report is sent by the receiver when the loss is detected. o Verify that the increment in the value of p is the same as in the previous measurement. Saurin & Perkins Expires January 6, 2006 [Page 13] Internet-Draft tfrc-testing July 2005 7. Open Issues and Future Work This draft could be conceived as a basic framework for testing TFRC. Future drafts should include more advanced testing of its features, as well as some scenarios where it would be tested the behavior of long term connections. For example, testing of the loss history is a difficult issue, and it would require some sort of scenario where patterns of losses could show how the loss event rate evolves. In the same way, more advanced features, like history discounting, would need long scenarios where the complete execution of the system could be tested. 8. Security Considerations Security considerations relating to the TFRC protocol are discussed in RFC 3448 [2]. The testing strategies outlined in this memo introduce no additional security considerations. 9. IANA Considerations No IANA actions are required. 10. Acknowledgements This work is supported by the National Science Foundation under grant No. 0230738. Thanks to Ladan Gharai for feedback on an early version of this memo. 11. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Handley, M., Floyd, S., Padhye, J., and J. Widmer, "TCP Friendly Rate Control (TFRC): Protocol Specification", RFC 3448, January 2003. Saurin & Perkins Expires January 6, 2006 [Page 14] Internet-Draft tfrc-testing July 2005 Authors' Addresses Alvaro Saurin University of Glasgow Department of Computing Science 17 Lilybank Gardens Glasgow G12 8QQ UK Email: saurin@dcs.gla.ac.uk Colin Perkins University of Glasgow Department of Computing Science 17 Lilybank Gardens Glasgow G12 8QQ UK Email: csp@csperkins.org Saurin & Perkins Expires January 6, 2006 [Page 15] Internet-Draft tfrc-testing July 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Saurin & Perkins Expires January 6, 2006 [Page 16]