Effective procedures for performance analysis and pricing are
important for controlling the use and dimensioning of broadband
networks. These procedures must be accurate, efficient, and take into
account the technological characteristics of broadband networks.
In this dissertation we apply and evaluate, for real traffic, the many
sources asymptotic and the related effective bandwidth definition, and
show how they can be used to clarify the effects on the
link's performance of the time scales of traffic burstiness, of the
traffic mix, of the link parameters (capacity and buffer), and of
traffic control mechanisms, such as traffic smoothing. Furthermore,
we use the many sources asymptotic to simultaneously capture the cell
scale and burst scale effects on the buffer overflow probability at an
ATM (Asynchronous Transfer Mode) link with a small buffer that
multiplexes a large number of periodic on-off sources.
In addition to giving the
correct expression of the overflow probability for very small
buffers,
we give a new qualitative description of how overflow occurs for
such buffers.
We investigate usage-based pricing schemes for services with open loop
control that are based on bounds of the effective bandwidth. These
include time-volume schemes that involve two measurements (the
duration of a connection and the total volume transferred), and two
schemes that involve measurements in distinct time intervals, smaller
than the duration of a connection: pricing with renegotiation and the
virtual bucket scheme. Finally, we present an approach to pricing and
resource sharing for ABR services with the following three features:
(i) prices are adjusted according to the demand, (ii) users declare
the price per unit of time according to which they will be charged,
and (iii) resource sharing is based on effective bandwidths.
Our experiments are
performed for link capacities and buffer sizes that will be used
in broadband networks, and
involve MPEG-1 compressed video with various contents,
Internet Wide Area Network (WAN) traffic, and modeled voice traffic.
[Contents],
My defense
was held on November 27, 1997.
For those
curious, here is my
thesis writing
progress.
Operators of multi-service networks require simple charging
schemes with which they can fairly recover costs from their users
and effectively allocate network resources. This paper studies an
approach for computing such charges from simple measurements (time
and volume), and relating these to bounds of the effective
bandwidth. A requirement for usage-based charging schemes is that
they capture the relative amount of resources used by connections.
Based on this criteria, we evaluate our approach for real traffic
consisting of Internet Wide Area Network traces and MPEG-1
compressed video. Its incentive compatibility is displayed with an
example involving deterministic multiplexing, and the effect of
pricing on a network's equilibrium is investigated for
deterministic and statistical multiplexing. Finally, we
investigate the incentives for traffic shaping provided by the
approach.
We present a web-based
tool for advanced statistical analysis of network traffic measurements.
The tool consists of an interface and software modules implementing
advanced statistical analysis procedures.
The interface provides a flexible environment through which a
user, using a Java enabled web browser, can create, modify, save, and
execute experiments.
The experiments are executed by software modules
implementing analysis procedures based on a theory of statistical
multiplexing a large number of bursty traffic streams while
guaranteeing some Quality of Service (QoS); the input to the
software modules are
traces that contain measurements of actual network traffic.
Questions that can be investigated using the tool
include the maximum link utilization when some QoS
is guaranteed, how this utilization is affected by the link buffer
and traffic shaping, the acceptance region when some QoS
is guaranteed, and the token
bucket parameters for a traffic stream.
We present a platform for collecting and analyzing measurements
of real network traffic. The measurements are collected by a high
performance PC-based monitor, which can collect detailed traffic
statistics on a high speed (155 Mbps) link, without disrupting the
operation or affecting the performance of the network. The
analysis is performed by a set of tools that use results from a
recent theory of statistical multiplexing, and have the objective
of answering important questions related to the management and
dimensioning of networks carrying bursty traffic and guaranteeing
some level of performance. Finally, we present case studies
demonstrating the application of our analysis tools.
We present an approach to manage and price service level agreements
(SLAs) for differentiated services that uses a simple upper bound for
the effective bandwidth of the conforming traffic as a proxy for
resource usage. The bound depends on the user's traffic profile
(peak rate and token bucket descriptor). Usage charges for a specific
time period are proportional to this proxy, and their calculation
requires only measurements of volume. We discuss and present
experimental results regarding the incentives and fairness of the
proxy, which is required in order to achieve economic efficiency. An
important feature of our approach is the simplicity of the user's
procedure for selecting optimal token bucket parameters. Our
approach is quite generic and can be applied to scheduling
disciplines that enable the provision of multiple service classes with
different levels of performance. Finally, we present a case study for
two service classes, a real-time and a non-real-time service, with
actual Internet traces.
This paper studies an approach that uses the effective bandwidth as a
measure of resource usage for creating time-only (flat rate) and time-
and volume-based tariffs for ATM services with guaranteed QoS. We
first argue that it is advantageous for a network operator to charge
according to effective bandwidths since this would lead to higher
aggregate utility and to competitive gains related to the long term
impact of pricing. Next, we present numerical investigations
involving real broadband traffic, showing how this tariffing approach
can accurately and consistently take into account the effects of link
and traffic contract parameters on resource usage. Finally, we
compare the tariffs derived under the studied approach with real
tariffs published by a particular network operator.
Accurate yet simple methods for traffic engineering are important
for efficient management of resources in broadband networks. The
goal of this paper is to apply and evaluate large deviation techniques
for traffic engineering. In particular, we employ the recently
developed theory of effective bandwidths, where the effective
bandwidth depends not only on the statistical characteristics of the
traffic stream, but also on a link's operating point through two
parameters, the space and time parameters, which can be
computed using the many sources asymptotic. We show that this
effective bandwidth definition can accurately quantify resource
usage. Furthermore, we estimate and interpret values of the space and
time parameters for various mixes of real traffic demonstrating how
these values can be used to clarify the effects on the link
performance of the time scales
of traffic burstiness, of the link resources (capacity and buffer),
and of traffic control mechanisms such as traffic shaping.
Our experiments involve a large set of MPEG-1 compressed video and
Internet Wide Area Network (WAN) traces, as well as modeled voice
traffic.
Traditional ABR flow control mechanisms share, in a fair way, the
available bandwidth according to the instantaneous peak rate
requirements of active traffic streams. Such an approach does not
allow bursty users, who besides the peak rate value additional
measures of burstiness (e.g., the mean rate), to express their true
preferences for network usage. Furthermore, fair sharing is achieved
at the short time scales of the duration of the bursts, and cannot
express fairness properties defined over longer time scales, such as
average throughput. We describe an approach where resource sharing
is done according to effective usage. Users bid for some amount of
effective bandwidth, and the network controls the effective bandwidth
of their traffic by adjusting the explicit rate ER (maximum rate the
user is allowed to send traffic) in order to achieve economically
fair resource sharing. The feedback loop operates in much longer time
scales than the round trip delays, and its performance relies on the
heavy multiplexing anticipated due to the large capacity of the
broadband links. Experiments demonstrate how our approach can
differentiate connections with different mean rates, and show that for
anticipated link capacities and traffic burstiness, the approach
yields adequate bandwidth utilization.
There has been extensive research on the application of the effective
bandwidth concept for quantifying resource usage in order to create
simple yet effective usage-based charging schemes with desirable
incentive properties.
This research has shown that simple charging
schemes which involve two measurements, time and volume, can serve
their purpose well by producing adequate approximations of the
effective usage of a bursty traffic stream.
An issue that has not been addressed
in detail is the relation between the type of admission
control mechanism the network uses and the definition of effective usage.
In particular, the above charging schemes assume
"static" Connection Admission Control (CAC).
In contrast to static CAC, "dynamic" CAC strategies
utilize on-line measurements
of the actual load, hence can achieve much higher utilization. We argue that
under such dynamic strategies the effective usage concept must be
redefined, and that when control actions occur at faster time scales
than the burstiness of the sources, the effective usage approaches the
mean rate of the sources.
In addition to
justifying the potential use of simple volume-based tariffs,
the above justifies
the deployment of sophisticated dynamic admission control mechanisms
since these result in more competitive prices.
Accurate yet simple methods for traffic engineering are
important for efficient dimensioning of broadband networks. The goal
of this paper is to apply and evaluate large deviation techniques for
traffic engineering. In particular, we employ the recently developed
theory of effective bandwidths , where the effective bandwidth
depends not only on the statistical characteristics of the traffic
stream, but also on a link's operating point through two
parameters, the space and time parameters,
which are computed using the many sources asymptotic . We
show that this effective bandwidth definition can accurately quantify
resource usage. Furthermore, we estimate and interpret values of the
space and time parameters for various mixes of real traffic
demonstrating how these values can be used to clarify the effects on
the link performance of the time scales of burstiness of the traffic
input, of the link parameters (capacity and buffer), and of traffic
control mechanisms, such as traffic shaping. Our approach relies on
off-line analysis of traffic traces, the granularity of which is
determined by the time parameter of the link, and our experiments
involve a large set of MPEG-1 compressed video and Internet Wide
Area Network (WAN) traces, as well as modeled voice traffic.
We evaluate usage-based pricing schemes that are based on bounds of
the effective bandwidth. The schemes include ones that require
simple measurements (time and volume) for the whole duration of a
call, and two schemes that require measurements in distinct time
intervals, smaller than the duration of a call: pricing with
renegotiation and the virtual bucket scheme. Using MPEG-1 compressed
video, the schemes are compared for different link capacities and
buffer sizes in terms of their fairness, i.e., the ability to capture
the relative amount of resources used by connections.
Operators of high-speed networks are interested in implementing simple
charging schemes with which they can fairly recover costs from their
customers and effectively allocate network resources. This paper
describes an approach for computing such charges from simple
measurements (the duration and transferred volume of a connection),
and relating these to bounds of the effective bandwidth. A
requirement for usage-based charging schemes is that they capture the
relative amount of resources used by connections. Based on this
criteria, we evaluate our approach for Internet Wide Area Network
traffic. Furthermore, its incentive compatibility is displayed with
an example involving deterministic multiplexing, and the effect of
pricing on a network's equilibrium is investigated for deterministic
and statistical multiplexing.
Tariff structures where charges depend on resource usage allow network
operators to fairly recover costs from their customers. The notion of
effective bandwidth is an important mathematical abstraction to the
complex problem of quantifying resource usage. We consider
usage-based pricing schemes which are based on some bound of
the effective bandwidth and involve two measurements:
the duration of a connection and the total volume transferred.
The schemes are compared according to their fairness, i.e., their
ability to capture the relative amount of resources used by connections.
Our experiments involve a large set of MPEG-1 compressed video
with different contents, and show that for links with a high degree
of multiplexing, simple approximations can yield good performance.
Considerable research activity has been directed towards estimating
the Cell Loss Probability (CLP) at the buffer of an ATM switch and
understanding the ways in which it can occur. Much of this activity
has been conducted by modeling the cells which enter the buffer as a
continuous fluid. This model can capture the variability of a source
at a burst level, but it ignores the fact that the workload actually
arrives in discrete cells. Nonetheless the fluid model can give
accurate estimates of the cell loss probability when the buffer size
is not very small. If the switch has a very small amount of buffer
per source then cell level effects can not be ignored. We consider
both Constant Bit Rate (CBR) and periodic on/off Variable Bit Rate
(VBR) sources, and apply large asymptotic techniques to a cell level
model of an ATM output link. Our analysis simultaneously captures both
the cell scale and burst scale effects, enabling us to study the
boundary between regions in the parameter space where cell level
effects are or are not significant. In addition to accurately
computing the CLP, we are able to give an insightful qualitative
description of how cell loss occurs in very small buffers.
The success of the Available Bit Rate (ABR) service will depend not
only on pure technological issues, but also on whether its pricing
structure provides the right incentives for users to efficiently use
network resources, thus minimizing the negative effects of congestion.
We describe a testbed for experimenting with various pricing
schemes. The testbed attempts to be as realistic as possible, and
allows real end-users to visually experience the effects of pricing
and network congestion.
We present a theoretically justified pricing scheme for ABR services
which utilizes mechanisms provided by rate-based flow control as
defined by the ATM Forum. As a result, the scheme imposes no
additional communication overhead, while the added complexity at the
switches and end-systems is minimal. Our approach complements ABR's
rate-based flow control and leads to economically efficient
utilization of network resources. According to the scheme, a
connection is charged based on the sum of the price per unit of
bandwidth on all links along its route. Prices depend on the demand
for bandwidth and are adjusted in a decentralized and iterative
manner. Simulation results show that prices converge reasonably fast
and do not have a negative effect on the convergence properties of
flow control.
The ability to quantify and accurately
measure resource usage in broadband networks
is important in areas such as network dimensioning, call
acceptance control, and charging for network services. Closely related
is the ability to identify and
measure quantities such as the relevant space and time scales.
This is important for accurate and efficient traffic modeling.
The many sources asymptotic, based
on the theory of large deviations, is an approach
for estimating the overflow probability and identifying the relevant
time scales at a buffered ATM output link
which multiplexes a large number of sources.
In addition,
the effective bandwidth formula based on this asymptotic appears to be
a promising approach for quantifying resource usage.
We investigate the accuracy of approximations
based on the many sources asymptotic,
and evaluate the effective bandwidth formula for real MPEG traffic.
Tariff structures where charges depend on resource usage allow network
operators to fairly recover costs from their customers. The notion of
effective bandwidth is an important mathematical abstraction to the
complex problem of quantifying resource usage. We consider
usage-based pricing schemes which are based on some approximation of
the effective bandwidth. The schemes involve few parameters and
simple measurements, hence are easily understood by customers.
Charging and accounting in modern high-speed networks are
extremely vital for their successful operation and growth. Tariffs
and pricing schemes are needed for the network to recover its
costs in a fair way from the diverse population of users, and to effectively
allocate network resources. Economists have developed simple
models for pricing network services, while neglecting the important
constraints imposed by the technology of such networks
such as the provision of quality-of-service, and the recommendations
by various standardization bodies. We discuss the above issues
and propose a unifying and consistent framework for the usage-based
pricing of network services. Finally, we investigate implementation
issues and directions for possible extensions.
We present a platform for collecting and analyzing measurements
of real network traffic. The measurements are collected by a high
performance PC-based monitor, which can collect detailed traffic
statistics on a high speed (155 Mbps) link, without disrupting the
operation or affecting the performance of the network. The
analysis is performed by a set of tools that use results from a
recent theory of statistical multiplexing, and have the objective
of answering important questions related to the management and
dimensioning of networks carrying bursty traffic and guaranteeing
some level of performance. Finally, we present case studies
demonstrating the application of our analysis tools.
This paper studies an approach that uses the effective bandwidth as a
measure of resource usage for creating time-only (flat rate) and time-
and volume-based tariffs for ATM services with guaranteed QoS. We
first argue that it is advantageous for a network operator to charge
according to effective bandwidths since this would lead to higher
aggregate utility and to competitive gains related to the long term
impact of pricing. Next, we present numerical investigations
involving real broadband traffic, showing how this tariffing approach
can accurately and consistently take into account the effects of link
and traffic contract parameters on resource usage. Finally, we
compare the tariffs derived under the studied approach with real
tariffs published by a particular network operator.
Describes a unifying approach for charging
services in ATM networks with guarantees
(CBR, VBR) and without guarantees (ABR, UBR).
Discusses issues regarding interconnection
charging.
The approach was developed and tested within project CA$hMAN.
Back to
Vasilis' Home Page
Ph.D. Dissertation
``Performance Analysis and Pricing in Broadband Networks''. Ph.D. Dissertation,
Dept. of Computer Science, University of Crete, December 1997.
Advisor: Prof. Costas Courcoubetis
Whole thesis:
[
.ps.gz (530 Kbytes)],
[or
here, .ps.gz (530 Kbytes)]
Publications
Revised version of [CSS98] containing a desciption of how to efficiently implement
the optimization procedures for the many sources asymptotic.
Extended version in
TR-212
Extended version in
TR-214
Other Workshops and Invited Papers
See [CSS99]
We discuss two properties that are important for usage-based pricing:
fairness and robustness. Fairness refers to whether a scheme captures
the relative amount of resources used by different users. Robustness
refers to whether a pricing scheme is equally fair for different
values of network resources (bandwidth and buffers) and different
types of traffic. We define a measure of fairness and compare
various usage-based pricing schemes based on this measure. Our
experiments involve a large number of MPEG-1 traces with different
content such as news, action movies, and talk shows. Our objectives
are to assess usage-based pricing schemes in terms of fairness and
robustness, to investigate the effects of traffic shaping on prices,
and to present these results in a form which allows easy extraction of
meaningful conclusions.
Technical Reports
Invited Talks
presentation
Work in progress
Compiled by Vasilios Siris - vsiris@ics.forth.gr
Last Modification: April 1999