Control of Network Resources over Multiple Time-Scales
by Matthias Grossglauser
Networked multimedia applications require resource allocation
because of their quality of service (QoS) requirements. On the
other hand, network efficiency depends crucially on the degree
of resource overbooking inside the network. A key problem in concurrently
achieving both goals is caused by the fluctuation over multiple
time-scales of the traffic load emitted by multimedia applications,
because it makes it hard to predict resource requirements with
sufficient accuracy. This in turn requires a careful design of
control mechanisms so that they cover all time-scales.
In our work, we examine resource control over three natural time-scales.
On the packet time-scale, we evaluate the performance of traffic
smoothing as a mechanism to accommodate bandwidth fluctuation.
Our interest stems from the mounting experimental evidence that
packet arrival processes exhibit ubiquitous properties of self-similarity
and long range dependence (LRD). A random process exhibits long-range
dependence if it has a non-summable autocorrelation function.
Intuitively, this means that the process exhibits fluctuations
over a wide range of time-scales. This property is of importance
because it cannot be captured by Markovian traffic models, which
have traditionally been the analytical tool of choice in the teletraffic
community. However, we show that in the case of traffic smoothing,
there exists a correlation horizon that separates relevant from
irrelevant fluctuation time-scales for the purpose of performance
prediction. This illustrates the general principle that the traffic,
system, and performance metric time-scales together determine
the set of candidate traffic models.
Per-flow smoothing is not effective in removing the longer-term
traffic fluctuations. To achieve high utilization, we therefore
need a mechanism to share the link bandwidth among multiple flows.
We advocate renegotiation as an efficient mechanism to accommodate
fluctuations over time-scales beyond the correlation horizon,
which we call the burst time-scale. A new network service model
called RCBR (Renegotiated Constant Bit Rate) combines network
simplicity with desirable quality of service guarantees, while
achieving much of the potential statistical multiplexing gain
of bursty traffic. With RCBR, the network guarantees a constant
bit rate to the application. The application can renegotiate this
bit rate, but there is a small probability of renegotiation blocking.
A network implementing RCBR is simple because there is no substantial
buffering in the network, and therefore no need for elaborate
buffer management and packet scheduling mechanisms. The quality
of service is determined by the renegotiation blocking probability,
which is kept small enough by limiting the number of flows in
the system. This is achieved through admission control.
On the flow time-scale, we discuss measurement-based admission
control (MBAC) as a means of relieving the application of the
burden of a-priori traffic specification. The traditional approach
to admission control requires an a priori traffic descriptor in
terms of the parameters of a deterministic or stochastic model.
However, it is generally hard or even impossible for the user
or the application to come up with a tight traffic descriptor
before establishing a flow. MBAC avoids this problem by shifting
the task of traffic characterization from the user to the network,
so that admission decisions are based on traffic measurements
instead of an explicit specification. This approach has several
important advantages. First, the user-specified traffic descriptor
can be trivially simple (eg, peak rate). Second, an overly conservative
specification does not result in an overallocation of resources
for the entire duration of the session.
Relying on measured quantities for admission control raises a
number of issues that have to be understood in order to develop
robust schemes.
Estimation Error
There is the possibility of making errors associated with any
estimation procedure. In the context of MBAC, the estimation errors
can translate into erroneous flow admission decisions. The effect
of these decision errors has to be carefully studied, because
they add another level of uncertainty to the system, the first
level being the stochastic nature of the traffic itself.
Dynamics and Separation of Time-scale
A MBAC is a dynamical system, with flow arrivals and departures,
and parameter estimates that vary with time. Since the estimation
process measures the in-flow burst statistics, while the admission
decisions are made for each arriving flow, MBAC inherently links
the flow and burst time-scale dynamics. Thus, the question of
impact of flow arrivals and departures on QoS arises. Intuitively,
each flow arrival carries the potential of making a wrong decision,
and each departing flow allows to recover from a past mistake.
Memory
The quality of the estimators can be improved by using more past
information about the flows present in the system. However, memory
in the estimation process adds another component to the dynamics
of a MBAC. Using too large a memory window will reduce the adaptability
of MBAC to non-stationarities in the statistics. A key issue is
therefore to determine an appropriate memory window size to use.
Using a simple model that captures the impact of measurement
uncertainty and the interplay of burst and flow time-scale dynamics,
we study all of the above issues in a unified analytical framework.
The goal is to shed insight on the design of robust MBAC schemes
which can make QoS guarantees in the presence of measurement uncertainty,
without requiring the tuning of external system parameters. The
figure illustrates how the traffic time-scales and control mechanisms
considered in our work relate to each other.
In our future work, we hope to address other problems that can
affect the quality of service experienced by the user. The Internet
grows rapidly in size and capacity, enabling more services such
as virtual private networks (VPN) and voice-over-IP, with more
vendors providing its elements, and with an increasing number
of operators competing for market share. The resulting system
is of very large scale and complexity, to such an extent that
one must assume that there is always something wrong somewhere.
The resulting flood of alarm information makes it difficult for
human network operators to detect, isolate, and repair faults
efficiently. This stresses the importance of network management.
Performance monitoring, fault identification and localization,
planning and resource provisioning, and configuration management
are important and challenging future research topics, encompassing
both architectural and performance issues.
More information about this project is available at: http://www.research.att.com/~mgross/
Please contact:
Matthias Grossglauser - AT&T Labs - Research
Tel: +1 973 360 7172
E-mail: mgross@research.att.com
 |
Matthias Grossglauser was the winner of the 1998 Cor Baayen Award
competition (see http://www.ercim.org/activity/cor-baayen.html). The work for which Grossglauser - an EPFL - graduate - received
the award was carried out at INRIA Sophia Antipolis under the
guidance of Jean Bolot where he was a member of the RODEO team.
He defended his thesis in spring 1998 on the topic 'Control of
Network Resources over Multiple Time-Scales'. Grossglauser recently
joined AT&T Laboratories in the US. |
