One document matched: draft-irtf-tmrg-metrics-00.txt
Internet Engineering Task Force Sally Floyd
INTERNET-DRAFT Editor
draft-irtf-tmrg-metrics-00.txt 17 August 2005
Expires: February 2006
Metrics for the Evaluation of Congestion Control Mechanisms
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of section 3 of RFC 3667. 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 February 2006.
Copyright Notice
Copyright (C) The Internet Society (2005). All Rights Reserved.
Floyd [Page 1]
INTERNET-DRAFT Expires: February 2006 August 2005
Abstract
This document discusses the metrics to be considered in an
evaluation of new or modified congestion control mechanisms for the
Internet. This document is intended to be the first in a series of
documents aimed at improving the models that we use in the
evaluation of transport protocols.
Floyd [Page 2]
INTERNET-DRAFT Expires: February 2006 August 2005
Table of Contents
1. Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1. Throughput, Delay, and Drop Rates. . . . . . . . . . . . 5
3.1.1. Throughput. . . . . . . . . . . . . . . . . . . . . 5
3.1.2. Delay . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.3. Packet Drop Rates . . . . . . . . . . . . . . . . . 6
3.2. Response Times and Minimizing Oscillations . . . . . . . 6
3.2.1. Response to Changes . . . . . . . . . . . . . . . . 6
3.2.2. Minimizing Oscillations . . . . . . . . . . . . . . 7
3.3. Fairness and Convergence . . . . . . . . . . . . . . . . 7
3.4. Robustness for Challenging Environments. . . . . . . . . 10
3.5. Robustness to Failures and to Misbehaving
Users . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.6. Deployability. . . . . . . . . . . . . . . . . . . . . . 10
3.7. Metrics for Specific Types of Transport. . . . . . . . . 10
4. Comments on Methodology . . . . . . . . . . . . . . . . . . . 11
5. Security Considerations . . . . . . . . . . . . . . . . . . . 11
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
7. Acknowledgements. . . . . . . . . . . . . . . . . . . . . . . 11
Informative References . . . . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14
Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 14
Intellectual Property. . . . . . . . . . . . . . . . . . . . . . 14
Floyd [Page 3]
INTERNET-DRAFT Expires: February 2006 August 2005
1. Conventions
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].
TO BE DELETED BY THE RFC EDITOR UPON PUBLICATION:
Changes from draft-floyd-transport-metrics-00.txt:
* Added metrics for:
- robustness in challenging environments,
- deployability,
- robustness to failures and to misbehaving users
* Added a discussion of fairness and packet size.
2. Introduction
As a step towards improving our methodologies for evaluating
congestion control mechanisms, in this document we discuss some of
the metrics to be considered. We also consider the relationship
between metrics, e.g., the well-known tradeoff between throughput
and delay.
Subsequent documents will discuss the models that are used in
analysis, simulations, or experiments for the evaluation of
transport protocols in general, and of congestion control mechanisms
in particular. These are intended to become documents in the newly-
chartered Transport Modeling Research Group (TMRG) in the IRTF
(Internet Research Task Force).
3. Metrics
The metrics that we discuss are the following:
o Throughput;
o Delay;
o Packet drop rates;
o Response to sudden changes or to transient events;
o Minimizing oscillations in throughput or in delay;
Floyd Section 3. [Page 4]
INTERNET-DRAFT Expires: February 2006 August 2005
o Fairness and convergence times;
o Robustness for challenging environments;
o Robustness to failures and to misbehaving users;
o Deployability;
o Metrics for specific types of transport.
We consider each of these below. Many of the metrics have both
network-based and user-based interpretations. For some of the
metrics, such as fairness between flows, there is not a clear
agreement in the network community about the desired goals.
3.1. Throughput, Delay, and Drop Rates
Because of the clear tradeoffs between throughput, delay, and drop
rates, it can be useful to consider the three metrics together.
An alternative would be to consider a separate metric such as power,
defined in this context as throughput over delay, that combines
throughput and delay. However, we do not propose in this document a
clear target in terms of the tradeoffs between throughput and delay;
we are simply proposing that the evaluation of transport protocols
include an exploration of the competing metrics.
3.1.1. Throughput
Throughput can be measured both as a router-based metric of
aggregate link throughput, and as a user metric of per-connection
transfer times. It is a clear goal of most congestion control
mechanisms to maximize throughput, subject to application demand and
to the constraints of the other metrics. We note that maximizing
throughput is of concern in a wide range of environments, from
highly-congested networks to under-utilized ones.
In some contexts, it might be sufficient to consider the aggregate
throughput or the mean per-flow throughput, while in other contexts
it might be necessary to consider the distribution of per-flow
throughput. Some researchers evaluate transport protocols in terms
of maximizing the aggregate user utility, where a user's utility is
generally defined as a function of the user's throughput [KMT98].
Individual applications can have application-specific needs in terms
of throughput. For example, real-time video traffic can have highly
variable bandwidth demands; VoIP traffic is sensitive to the amount
of bandwidth received immediately after idle periods. Thus, user
Floyd Section 3.1.1. [Page 5]
INTERNET-DRAFT Expires: February 2006 August 2005
metrics for throughput can be more complex than simply the per-
connection transfer time.
3.1.2. Delay
Like throughput, delay can be measured as a router-based metric of
queueing delay over time, or in terms of per-packet transfer times.
For reliable transfer, the per-packet transfer time includes the
possible delay of retransmitting a dropped packet.
Users of bulk data transfer applications might care about per-packet
transfer times only in so far as they affect the per-connection
transfer time. On the other end of the spectrum, for users of
streaming media, per-packet delay can be a significant concern.
Note that in some cases the average delay might not capture the
metric of interest to the users; for example, some users might care
about the worst-case delay, or about the tail of the delay
distribution.
3.1.3. Packet Drop Rates
Packet drop rates can be measured as a network-based or as a user-
based metric.
Some users might care about packet drop rates only in so far as they
affect per-connection transfer times, while other users might care
about packet drop rates directly. One network-related reason to
avoid high steady-state packet drop rates is to avoid congestion
collapse in environments containing paths with multiple congested
links. In such environments, high packet drop rates could result in
congested links wasting scarce bandwidth by carrying packets that
will only be dropped downstream, before being delivered to the
receiver.
3.2. Response Times and Minimizing Oscillations
In this section we consider response times and oscillations
together, as there are well-known tradeoffs between improving
response times and minimizing oscillations. In addition, the
scenarios that illustrate the dangers of poor response times are
often quite different from the scenarios that illustrate the dangers
of unnecessary oscillations.
3.2.1. Response to Changes
One of the key concerns in the design of congestion control
mechanisms has been the response times to sudden congestion in the
network. On the one hand, congestion control mechanisms should
Floyd Section 3.2.1. [Page 6]
INTERNET-DRAFT Expires: February 2006 August 2005
respond reasonably promptly to sudden congestion from routing or
bandwidth changes, or from a burst of competing traffic. At the
same time, congestion control mechanisms should not respond too
severely to transient changes, e.g., to a sudden increase in delay
that will dissipate in less than the connection's round-trip time.
Evaluating the response to sudden or transient changes can be of
particular concern for slowly-responding congestion control
mechanisms such as equation-based congestion control [RFC 3448], and
for AIMD (Additive Increase Multiplicative Decrease) or related
mechanisms using parameters that make them more slowly-responding
that TCP [BB01, BBFS01].
In addition to the responsiveness and smoothness of aggregate
traffic, one can consider the tradeoffs between responsiveness,
smoothness, and aggressiveness for an individual connection [FHP00].
In this case smoothness can be defined by the largest reduction in
the sending rate in one round-trip time, in a deterministic
environment with a packet drop exactly every 1/p packets. The
responsiveness is defined as the number of round-trip times of
sustained congested required for the sender to halve the sending
rate, and the aggressiveness is defined as the maximum increase in
the sending rate in one round-trip time, in packets per second, in
the absence of congestion.
3.2.2. Minimizing Oscillations
One goal is that of stability, in terms of minimizing oscillations
of queueing delay or of throughput. Scenarios illustrating
oscillations are often dominated by long-lived connections, perhaps
with a small number of changes in the level of congestion.
An orthogonal goal for some congestion control mechanisms, e.g., for
equation-based congestion control, is to minimize the oscillations
in the sending rate for an individual connection, given an
environment with a fixed, steady-state packet drop rate. (As is
well known, TCP congestion control is characterized by a pronounced
oscillation in the sending rate, with the sender halving the sending
rate in response to congestion.) One metric for the level of
oscillations is the smoothness metric given above.
3.3. Fairness and Convergence
Another set of metrics are those of fairness and of convergence
times. Fairness can be considered between flows of the same
protocol, and between flows using different protocols (e.g.,
fairness between TCP and a new transport protocol).
Floyd Section 3.3. [Page 7]
INTERNET-DRAFT Expires: February 2006 August 2005
There are a number of different fairness measures. These include
max-min fairness [HG86], proportional fairness [KMT98, K01], the
fairness index proposed in [JCH84], and the product measure, a
variant of network power [BJ81].
Max-min fairness: In order to satisfy the max-min fairness criteria,
the smallest throughput rate must be as large as possible. Given
this condition, the next-smallest throughput rate must be as large
as possible, and so on. Thus, the max-min fairness gives absolute
priority to the smallest flows.
Epsilon-fairness: A metric related to max-min fairness is epsilon-
fairness, where a rate allocation is defined as epsilon-fair if
min_i x_i / max_i x_i >= 1 - epsilon.
where x_i is the resource allocation to the i-th user. Epsilon-
fairness measures the worst-case ratio between any two throughput
rates [ZKL04].
Proportional fairness: In contrast, an allocation x is defined as
proportionally fair if for any other feasible allocation x*, the
aggregate of proportional changes is zero or negative:
sum_i (x*_i - x_i)/x_i <= 0.
"This criterion favours smaller flows, but less emphatically than
max-min fairness" [K01].
Jain's fairness index: The fairness index in [JCH84] is
(( sum_i x_i )^2) / (n * sum_i (x_i)^2 ) ,
where there are n users. This fairness index ranges from 0 to 1,
and is maximum when all users receive the same allocation. This
index is k/n when k users equally share the resource, and the other
n-k users receive zero allocation.
The product measure: The product measure
product_i x_i ,
the product of the throughput of the individual connections, is also
used as a measure of fairness. For our purposes, let x_i be the
throughput for the i-th connection. (In other contexts x_i is taken
as the power of the i-th connection, and the product measure is
referred to as network power.) The product measure is particularly
sensitive to segregation; the product measure is zero if any
Floyd Section 3.3. [Page 8]
INTERNET-DRAFT Expires: February 2006 August 2005
connection receives zero throughput. In [MS90] it is shown that for
a network with many connections and one shared gateway, the product
measure is maximized when all connections receive the same
throughput.
Fairness and the number of congested links: Some of these fairness
metrics are discussed in more detail in [F91]. We note that there
is not a clear consensus for the fairness goals, in particular for
fairness between flows that traverse different numbers of congested
links [F91].
Fairness and round-trip times: One goal cited in a number of new
transport protocols has been that of fairness between flows with
different round-trip times [KHR02, XHR04]. We note that there is not
a consensus in the networking community about the desirability of
this goal, or about the implications and interactions between this
goal and other metrics [FJ92] (Section 3.3).
Fairness and packet size: One fairness issue is that of the relative
fairness for flows with different packet sizes. Many file transfer
applications will use the maximum packet size possible; in
contrast, low-bandwidth VoIP flows are likely to send small packets,
sending a new packet every 10 to 40 ms., to limit delay. Should a
small-packet VoIP connection receive the same sending rate in bytes
per second as a large-packet TCP connection in the same environment,
or should it receive the same sending rate in *packets* per second?
This fairness issue has been discussed in more detail in [FK04],
with [FK05] also describing the ways that packet size can effect the
packet drop rate experienced by a flow.
Convergence times: Convergence times concern the time for
convergence to fairness between an existing flow and a newly-
starting one, and are a special concern for environments with high-
bandwidth flows. As with fairness, convergence times can matter
both between flows of the same protocol, and between flows using
different protocols [SLFK03].
One metric used for convergence times is the delta-fair convergence
time, defined as the time taken for two flows with the same round-
trip time to go from shares of 100/101-th and 1/101-th of the link
bandwidth, to having close to fair sharing with shares of
(1+delta)/2 and (1-delta)/2 of the link bandwidth [BBFS01]. A
similar metric for convergence times measures the convergence time
as the number of round-trip times for two flows to reach epsilon-
fairness, when starting from a maximally-unfair state [ZKL04]. '
Floyd Section 3.3. [Page 9]
INTERNET-DRAFT Expires: February 2006 August 2005
3.4. Robustness for Challenging Environments
While congestion control mechanisms are generally evaluated first
over environments with static routing in a network of two-way point-
to-point links, some environments bring up more challenging problems
(e.g., corrupted packets, variable bandwidth, mobility) as well as
new metrics to be considered (e.g., energy consumption).
Robustness for challenging environments: Robustness needs to be
explored for paths with reordering, corruption, variable bandwidth,
asymmetric routing, router configuration changes, mobility, and the
like. In general, Internet architecture has valued robustness over
efficiency, e.g., when there are tradeoffs between robustness and
the throughput, delay, and fairness metrics described above.
Energy consumption: In mobile environments the energy consumption
for the mobile end-node can be a key metric that is affected by the
transport protocol [TM02].
Goodput: For wireless networks, goodput can be a useful metric,
where goodput is defined as the fraction of useful data from all of
the data delivered. High goodput indicates an efficient use of the
radio spectrum and lower interference to other users [GF04].
3.5. Robustness to Failures and to Misbehaving Users
One goal is for congestion control mechanisms to be robust to
misbehaving users, such as receivers that `lie' to data senders
about the congestion experienced along the path or otherwise attempt
to bypass the congestion control mechanisms of the sender [SCWA99].
Another goal is for congestion control mechanisms to be as robust as
possible to failures, such as failures of routers in using explicit
feedback to end-nodes or failures of end-nodes to follow the
prescribed protocols,
3.6. Deployability
One metric for congestion control mechanisms is their deployability
in the current Internet. Metrics related to deployability include
the ease of failure diagnosis, and the overhead in terms of packet
header size or added complexity at end-nodes or routers.
3.7. Metrics for Specific Types of Transport
In some cases modified metrics are needed for evaluting transport
protocols intended for QoS-enabled environments or for below-best-
Floyd Section 3.7. [Page 10]
INTERNET-DRAFT Expires: February 2006 August 2005
effort traffic [VKD02, KK03].
4. Comments on Methodology
The types of scenarios that are used to test specific metrics, and
the range of parameters that it is useful to consider, will be
discussed in separate documents, e.g., along with specific scenarios
for use in evaluating congestion control mechanisms.
We note that it can be important to evaluate metrics over a wide
range of environments, with a range of link bandwidths, congestion
levels, and levels of statistical multiplexing. It is also
important to evaluate congestion control mechanisms in a range of
scenarios, including typical ranges of connection sizes and round-
trip times [FK02]. It is also useful to compare metrics for new or
modified transport protocols with those of the current standards for
TCP.
More general references on methodology include [J91].
5. Security Considerations
There are no security considerations in this document.
6. IANA Considerations
There are no IANA considerations in this document.
7. Acknowledgements
Thanks to Doug Leith for feedback.
Informative References
[BB01] D. Bansal and H. Balakrishnan, Binomial Congestion Control
Algorithms, IEEE Infocom, April 2001.
[BBFS01] D. Bansal, H. Balakrishnan, S. Floyd, and S. Shenker,
Dynamic Behavior of Slowly-Responsive Congestion Control
Algorithms, SIGCOMM 2001.
[BJ81] K. Bharath-Kumar and J. Jeffrey, A New Approach to
Performance-Oriented Flow Control, IEEE Transactions on
Communications, Vol.COM-29 N.4, April 1981.
[F91] S. Floyd, Connections with Multiple Congested Gateways in
Packet-Switched Networks Part 1: One-way Traffic, Computer
Communication Review, Vol.21, No.5, October 1991, p. 30-47.
Floyd [Page 11]
INTERNET-DRAFT Expires: February 2006 August 2005
[FK05] S. Floyd and E. Kohler, TFRC for Voice: the VoIP Variant,
draft-ietf-dccp-tfrc-voip-02.txt, internet draft, work in
progress, July 2005.
[FHP00] S. Floyd, M. Handley, and J. Padhye, A Comparison of
Equation-Based and AIMD Congestion Control, May 2000. URL
"http://www.icir.org/tfrc/".
[FJ92] S. Floyd and V. Jacobson, On Traffic Phase Effects in Packet-
Switched Gateways, Internetworking: Research and Experience, V.3
N.3, September 1992, p.115-156.
[FK04] S. Floyd and J. Kempf, IAB Concerns Regarding Congestion
Control for Voice Traffic in the Internet, RFC 3714, March 2004.
[FK02] S. Floyd and E. Kohler, Internet Research Needs Better
Models, Hotnets-I. October 2002.
[GF04] A. Gurtov and S. Floyd, Modeling Wireless Links for Transport
Protocols, ACM CCR, 34(2):85-96, April 2004.
[HG86] E. Hahne and R. Gallager, Round Robin Scheduling for Fair
Flow Control in Data Communications Networks, IEEE International
Conference on Communications, June 1986.
[J91] R. Jain, The Art of Computer Systems Performance Analysis:
Techniques for Experimental Design, Measurement, Simulation, and
Modeling, John Wiley & Sons, 1991.
[JCH84] R. Jain, D.M. Chiu, and W. Hawe, A Quantitative Measure of
Fairness and Discrimination for Resource Allocation in Shared
Systems, DEC TR-301, Littleton, MA: Digital Equipment
Corporation, 1984.
[K01] F. Kelly, Mathematical Modelling of the Internet, "Mathematics
Unlimited - 2001 and Beyond" (Editors B. Engquist and W.
Schmid), Springer-Verlag, Berlin, pp. 685-702, 2001.
[KHR02] D. Katabi, M. Handley, and C. Rohrs, Congestion Control for
High Bandwidth-Delay Product Networks, ACM Sigcomm, 2002.
[KK03] A. Kuzmanovic and E. W. Knightly, TCP-LP: A Distributed
Algorithm for Low Priority Data Transfer, IEEE INFOCOM 2003,
April 2003.
[KMT98] F. Kelly, A. Maulloo and D. Tan, Rate Control in
Communication Networks: Shadow Prices, Proportional Fairness and
Stability. Journal of the Operational Research Society 49, pp.
Floyd [Page 12]
INTERNET-DRAFT Expires: February 2006 August 2005
237-252, 1998.
[MS90] D. Mitra and J. Seery, Dynamic Adaptive Windows for High
Speed Data Networks: Theory and Simulations, ATT Bell
Laboratories report, April 1990.
[RFC 2119] S. Bradner. Key Words For Use in RFCs to Indicate
Requirement Levels. RFC 2119.
[RFC 2434] T. Narten and H. Alvestrand. Guidelines for Writing an
IANA Considerations Section in RFCs. RFC 2434.
[RFC 2581] M. Allman, V. Paxson, and W. Stevens. TCP Congestion
Control. RFC 2581.
[RFC 3448] M. Handley, S. Floyd, J. Padhye, and J. Widmer, TCP
Friendly Rate Control (TFRC): Protocol Specification, RFC 3448,
Proposed Standard, January 2003.
[SLFK03] R.N. Shorten, D.J. Leith, J. Foy, and R. Kilduff, Analysis
and Design of Congestion Control in Synchronised Communication
Networks. Proc. 12th Yale Workshop on Adaptive & Learning
Systems, May 2003.
[SCWA99] TCP Congestion Control with a Misbehaving Receiver, ACM
Computer Communications Review, October 1999.
[TM02] V. Tsaoussidis and I. Matta, Open Issues of TCP for Mobile
Computing, Journal of Wireless Communications and Mobile
Computing: Special Issue on Reliable Transport Protocols for
Mobile Computing, February 2002.
[VKD02] A. Venkataramani, R. Kokku, and M. Dahlin, TCP Nice: A
Mechanism for Background Transfers, Fifth USENIX Symposium on
Operating System Design and Implementation (OSDI), 2002.
[XHR04] L. Xu, K. Harfoush, and I. Rhee, Binary Increase Congestion
Control for Fast, Long Distance Networks, Infocom 2004.
[YL00] Y. R. Yang and S. S. Lam, General AIMD Congestion Control,
Technical Report TR-00-09, Department of Computer Sciences, UT
Austin, May 2000.
[ZKL04] Y. Zhang, S.-R. Kang, and D. Loguinov, Delayed Stability and
Performance of Distributed Congestion Control, ACM SIGCOMM,
August 2004.
Floyd [Page 13]
INTERNET-DRAFT Expires: February 2006 August 2005
Authors' Addresses
Sally Floyd <floyd@icir.org>
ICSI Center for Internet Research
1947 Center Street, Suite 600
Berkeley, CA 94704
USA
Full 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.
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.
Intellectual Property
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.
Floyd [Page 14]
| PAFTECH AB 2003-2026 | 2026-04-23 06:11:13 |