Internet DRAFT - draft-anjali-ippm-avail-band-measurement
draft-anjali-ippm-avail-band-measurement
IP Performance Metrics Working Group T. Anjali
Internet Draft C. Scoglio
Expiration Date: April 2003 I. F. Akyildiz
Georgia Institute of Technology
G. Uhl
A. Sciuto
Swales Aerospace
J. A. Smith
NASA Goddard
Available Bandwidth Measurement in IP Networks
draft-anjali-ippm-avail-band-measurement-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
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 made obsolete 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.
Abstract
Available bandwidth along a path is an important metric that can be
useful to provide insight into the state and performance of the
network. Some methods have been proposed in literature for
measurement of available bandwidth but they face the problems of
scalability and high intrusiveness. In this draft, we propose a
method to measure path available bandwidth using an active approach
that probes the path. The probing mechanism used is based on TCP
New Reno. Once the samples for the available bandwidth measurement
are obtained, more accurate results are calculated using a
prediction filter.
Anjali et al Expires April 2003 Page 1
Available Bandwidth Measurement October 2002
Table of Contents
Abstract
1. Introduction 2
1.1 Overview of available bandwidth measurement 3
1.2 Available tools 3
2. Description 4
2.1 TCP measurement phase 4
2.2 Estimation and prediction phase 5
3. Enhancements and Evaluations 6
4. References 7
5. Authors' Addresses 7
1. Introduction
The efficiency of the QoS provided by an IP network depends on
effective traffic management, performed at both small and large
time-scales. Traffic management encompasses the need for dynamic
configuration of network devices to adjust to the evolving
traffic. This feedback loop is based on measurement of network
characteristics. But observability of Internet traffic is difficult
because of the network size, large traffic volumes, and distributed
administration.
Some QoS metrics can be measured in the core of the network and
others at the edges. Some have local significance at each router
while others are end-to-end metrics. They can be obtained by
measurements from the various network elements. To obtain measured
statistics from each network element is possible if individual
users can monitor each such device. Due to security reasons, this
is not possible in a network. Thus, common users can only measure
the end-to-end metrics.
The approaches to monitor a network are active or passive. The
active approach has the advantage of measuring the desired
quantities at the desired time. Passive measurements are carried
out by observing normal network traffic, without the extra load.
But the amount of data accumulated can be substantial because the
network will be polled often for information.
Available bandwidth in a network is an important metric that can be
indicative of the network performance. The available bandwidth of
a link can be defined as the unused portion of the link capacity.
Then, the available bandwidth along a path is defined as the
minimum of the available bandwidths of the links in the path. Based
on the bandwidth available in various segments of the network, the
network operator can obtain information about the congestion in the
network, perform the admission control, routing, capacity
provisioning etc.
Anjali et al Expires April 2003 Page 2
Available Bandwidth Measurement October 2002
1.1 Overview of available bandwidth measurement
Most approaches to available bandwidth measurement are active.
However, SNMP based approaches are passive since they obtain router
statistics from the router and do not observe the treatment
received by the injected pseudo traffic. The active approaches have
the advantage of being faster and they operate independently of any
network support. SNMP based approaches need cooperation from the
network as they need access to the network element MIBs.
The available bandwidth can be measured for individual links of the
network. The end-to-end performance of the network is what the
users and network operators are really interested in. The
end-to-end available bandwidth information can be obtained by a
concatenation of the available bandwidth measurements of the
individual links comprising the path. However, this approach can be
very inefficient as the amount of data collected grows as the path
size increases and a central data analysis station will be
required. Thus, tools have to be devised that can measure the
end-to-end available bandwidth directly and accurately from the
path.
1.2 Available tools
Currently, various tools and products are available that can be
used to measure the total capacity in the links of a path in the
network. They can be split into two families: pathchar-based and
packet pair-based. Examples include Nettimer [1], Network Weather
Service approach [2] etc.
Among the tools to measure the available bandwidth of a path is an
active approach given in [3]. It is based on transmission of
self-loading periodic measurement streams. This scheme sends
traffic at increasing rates from the source to the destination
until the rate finally reaches the available bandwidth of the tight
link after which the packets start experiencing increasing amounts
of delay. Thus this scheme can be highly intrusive. Also, it takes
a long time to converge to a measurement estimate. Another active
approach to measure the throughput of a path is Iperf from NLANR
that sends streams of TCP/UDP flows. It is another highly intrusive
approach that sends traffic at high speeds and displays the
throughput achieved. Cisco has introduced the NetFlow technology
that provides IP flow information for a network. NetFlow provides
detailed data collection with minimal impact on the performance on
the routing device and no external probing device. But in a
DiffServ environment, the core of a network is interested in
aggregate rather than per-flow statistics, due to the scalability
issues. MRTG is a tool, based on SNMP, that gives periodic
measurements of the utilization of a particular link along the
path. To obtain statistics of a link via MRTG, the SNMP query needs
access to the router. Also, MRTG obtains available bandwidth
estimates over periods of length 5 minutes.
Anjali et al Expires April 2003 Page 3
Available Bandwidth Measurement October 2002
Most of the current bandwidth measurement techniques face the
problems of poor accuracy, scalability, statistical robustness,
agility in adapting to bandwidth changes and flexibility.
In this draft, we propose a method to measure the available
bandwidth along a path that is accurate, scalable, easy to
implement and does not need any network support. The method can be
enhanced under scenarios where network support is available to a
highly accurate measurement procedure.
2. Description
Our proposed method for available bandwidth measurement can be
spilt into two phases. In the first phase, a TCP application is
deployed to obtain rough estimates of the available bandwidth along
the path. We call this the TCP measurement phase. The second phase
analyzes the gathered estimates of the available bandwidth to
obtain a more accurate and reliable measurement value. This is
called the prediction phase. Next, we explain the individual phases
in detail.
2.1 TCP measurement phase
Our method employs a TCP application to detect and estimate the
congestion level in the network. The basic functioning of TCP is
described in [4] with modifications in [5]. TCP starts in slow
start where the congestion window size is increased by one segment
for each ACK for a successful packet delivery. The sender can
transmit segments upto the congestion window size. Once the sender
observes a packet loss (from a missing acknowledgement), the sender
enters congestion avoidance state. A fast retransmit of the missing
segment is performed if triple duplicate ACKs are received in a row
and then the sender enters fast recovery (and not slow start). TCP
NewReno suggests a modification to the fast recovery algorithm to
incorporate a response to partial acknowledgements received during
fast recovery.
Thus, TCP constantly probes the network to find out the available
capacity, and when it encounters congestion, it backs off. We use
this feature of TCP in our proposed available bandwidth measurement
method.
If the TCP session is allowed to run for long durations, it fully
occupies the unused portion of the path bandwidth, thus changing
the network state. Thus, we define a time interval T for which the
TCP session is run and then terminated. During this time interval,
we gather various samples of bandwidth, which are then fed to the
prediction phase. The bandwidth samples are calculated as follows.
When the TCP session is started, it starts with the slow start
algorithm. When the first signs of congestion are discovered, the
TCP session goes into congestion avoidance. We note the value of
congestion window just before it is reduced. That determines the
rate at which the sender was transmitting and constitutes the first
Anjali et al Expires April 2003 Page 4
Available Bandwidth Measurement October 2002
sample of available bandwidth estimate. Then the sender goes into
congestion avoidance and reduces its transmission rate. The
transmission rate increases again, faster due to the NewReno
modifications to fast retransmit and fast recovery algorithms, till
the next sign of congestion. At this point, the value of the
congestion window parameter is noted again, along with the
timestamp at which this happens. Continuing like this, we gather
multiple samples during the time T of the TCP session. These
samples provide an insight into the unused capacity on the path
that is available to be used by new applications. These samples
will be input to the prediction phase where we try to derive
accurate measurements of the path available bandwidth.
Note that this TCP measurement phase relies only on information
readily available at the sender, using the current TCP header, and
does not require any support from receivers or any network
component.
2.2 Estimation and prediction phase
Once the bandwidth estimates are obtained by the TCP measurement
phase, we have to obtain more accurate values for the bandwidth
samples. For this purpose, we propose to use a filter. Note that
the samples gathered during the TCP measurement phase are not
uniformly spaced in time. This is because the samples were gathered
whenever the congestion was detected by the TCP sender. Assume that
we obtained N samples of bandwidth estimates from the first
phase. To use these samples in our filter, we interpolate them to
obtain a sample distribution of M samples that is uniform in
time. We denote by T_s the desired time between bandwidth
samples. The first sample is assumed to be at time 0 and the
successive (interpolated) samples at time i*T_s are obtained by
linear interpolation between the two actual samples around the
timestamp i*T_s, i = 1, ..., M. For example, suppose that we have a
bandwidth estimate of x at timestamp 3*T_s - 5 and another estimate
of y at timestamp 3*T_s + 10. Then the sample at 3*T_s will be
interpolated as x + 5*(y-x)/15. The number of samples M after this
interpolation will be less than or equal to N depending on the
timestamps of the actual samples collected during the TCP
measurement phase. These M samples will correspond to timestamps 0
to (M-1)*T_s and are denoted by U(i), i = 1 to M,
respectively. Once we have these uniformly distributed samples, we
apply a linear filter to them to forecast the next M samples. They
are given as follows. U(M+i) is given as the sum of U(M-n)*c_i(n)
for n from 0 to M-1, for i = 1 to M. We find the filter
coefficients c_i(n) by using the covariance equations method. The
covariance of the sequence U(i), i = 1 to M can be estimated from
the samples. The covariance equations can be solved by Gaussian
elimination or some other faster methods such as triangular
decomposition etc. Substituting the c_i's back into the linear
prediction, we find the next M samples, U(M+i), i = 1 to M. From
these samples, we can obtain the estimate of the available
bandwidth on the path. The estimate depends on the conservativeness
Anjali et al Expires April 2003 Page 5
Available Bandwidth Measurement October 2002
requirements of the application needing the measurement. If the
application is highly conservative, it needs an upper bound on the
available bandwidth and then we estimate the available bandwidth as
the minimum among U(M+i), i = 1 to M. On the other hand, if the
application is not very conservative, we estimate the available
bandwidth as the mean of U(M+i), i = 1 to M. This single value is
the final measurement provided by our scheme. It is not just a
measurement but also incorporates a prediction and this value will
be valid for sometime in the future. An extended version of this
prediction method based on MRTG measurements is given in [6].
3. Enhancements and Evaluations
Our proposed method, detailed in the previous section, does not
need any support from the receiver and the network. It probes the
network on its own. On the other hand, if network support is
available for a path, we can modify our method to obtain more
accurate measurements. The method can become less intrusive and
more fast and accurate. If network support is available, we replace
the TCP measurement phase with a network probe phase. In this
phase, we send measurement packets from the source of the path to
the destination that collect hop information along the path. More
specifically, they collect the counter information about the number
of octets that have crossed that hop till then, for each hop. This
information can be obtained from the MIBs stored in the routers on
the path. In future networks, information sharing seems desirable
as the networks can provide the QoS support that users request by
cooperation. We need to send a small number of such packets to
obtain repeated samples to calculate the path available
bandwidth. These samples can then be input to the prediction
phase. Only modification is that the samples represent the
utilization of the bottleneck link in the path, unlike the
available bandwidth samples in the original proposal. Thus, for a
conservative application, we estimate the available bandwidth of
the path as the minimum among the set of link available
bandwidths. The link available bandwidths can be calculated as the
difference between the link capacity and the maximum among the
predicted utilization samples for that link.
The measurement samples can be obtained by utilizing MRTG instead
of probing the network. But MRTG has the problem that it obtains a
utilization sample every 5 minutes. This can be too long an
averaging interval for some applications. For such cases, we have
developed MRTG++ [6], our own enhanced version of MRTG. MRTG++
obtains utilization estimates by averaging over intervals of length
anytime above 10 seconds.
The proposed method is accurate, scalable, easy to implement and
does not need any network support. It is accurate as it obtains
measurements from the network using a TCP session. If the
application desiring the measurement needs highly accurate
information, the TCP measurement phase can be repeated a few times
Anjali et al Expires April 2003 Page 6
Available Bandwidth Measurement October 2002
to obtain more samples. Our approach is scalable as the measurement
samples are obtained by a simple TCP session between the
end-points. The overhead will not be different if the number of
hops in the path is increased. Our scheme is easy to implement as
it involves a simple TCP session initiation, followed by the linear
prediction. Also, our scheme does not require any network support
for its operation.
It has to be noted that our scheme will have difficulty in
measuring bandwidth for paths with high capacity links. This is
because of the limitations in TCP operation like buffer size,
segment size etc. For paths with high capacity links, our method
can be extended to include multiple TCP sessions to be initiated in
parallel. These multiple sessions can probe the network and obtain
fair share estimates of the path available bandwidth. These
sub-estimates can then be added to obtain proper estimates for the
path.
4. References
[1] Lai, K. and Baker, M., "Nettimer: a tool for measuring
bottleneck link bandwidth," USENIX symposium on Internet
technologies and systems, 2001.
[2] Wolski, R., "Dynamically forecasting network performance using
the network weather service," Journal of cluster computing,
January 1998.
[3] Jain, M. and Dovrolis, C., "End-to-end available bandwidth:
measurement methodology, dynamics and relation with TCP
throughput," ACM Sigcomm, 2002.
[4] Stevens, W., "TCP slow start, congestion avoidance, fast
retransmit, and fast recovery algorithms," RFC 2001, January
1997.
[5] Allman, M., Paxson, V. and Stevens, W., "TCP congestion
control," RFC 2581, April 1999.
[6] Anjali, T., Scoglio, C., Chen, L. C., Akyildiz, I. F. and Uhl,
G., "ABEst: an available bandwidth estimator within an
autonomous system," IEEE Globecom 2002.
5. Author's Addresses
Tricha Anjali
Georgia Institute of Technology
250 14th Street, Suite 556
Atlanta, GA 30318 USA
Phone: +1 404 894 6616
<tricha@ece.gatech.edu>
Anjali et al Expires April 2003 Page 7
Available Bandwidth Measurement October 2002
Caterina Scoglio
Georgia Institute of Technology
250 14th Street, Suite 556
Atlanta, GA 30318 USA
Phone: +1 404 894 6616
<caterina@ece.gatech.edu>
Ian F. Akyildiz
Georgia Institute of Technology
250 14th Street, Suite 568
Atlanta, GA 30318 USA
Phone: +1 404 894 5141
<ian@ece.gatech.edu>
George Uhl
Swales Aerospace
Phone: +1 301 614 5155
<uhl@rattler.gsfc.nasa.gov>
Agatino Sciuto
Swales Aerospace
Phone: +1 301 614 5155
<asciuto@rattler.gsfc.nasa.gov>
Jeffrey A. Smith
NASA Goddard Space Flight Center
Phone: +1 301 614 5155
<jsmith@rattler.gsfc.nasa.gov>
Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain
it or assist in its implementation may be prepared, copied,
published and distributed, in whole or in part, without restriction
of any kind, provided that the above copyright notice and this
paragraph are included on all such copies and derivative
works. However, this document itself may not be modified in any
way, such as by removing the copyright notice or references to the
Internet Society or other Internet organizations, except as needed
for the purpose of developing Internet standards in which case the
procedures for copyrights defined in the Internet Standards process
must be followed, or as required to translate it into languages
other than English. The limited permissions granted above are
perpetual and will not be revoked by the Internet Society or its
successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS 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.
Anjali et al Expires April 2003 Page 8
