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]