Note: Descriptions are shown in the official language in which they were submitted.
CA 02344738 2001-04-20
Motivation
Multimedia traffic, comprising voice, video, images and text, is becoming
increasingly common on internets and is expected to account for a large
portion of
future Internet use. Entertainment (movies, television and games) and
videoconferences (meetings, classes) are two of the important applications.
Multimedia traffic, unlike e-mail or file transfers, requires strict
guarantees of the
Quality of Service (QoS) provided by the Internet, mostly relating to the data
rate
(transmission speed), error rate and latency (delay) provided to the customer.
Video,
for example, must be transmitted at the correct rate and with few errors, or
users will
see jerky or distorted images. Interactive voice conversations must suffer
network
delays of less than a few hundred milliseconds or participants will become
disoriented,
unsure of who's speaking. A network which guarantees the promised level of QoS
to
each customer is called a QoS-enabled network.
Given that any network has finite resources -- the capacities of its
transmission
links (measured in bits/sec) and routers or switches (often measured in
packets/sec) --
the allocation of enough link and switch capacity to each user to guarantee
QoS means
that not all applicants can be admitted to a QoS-enabled network. (To do so
would
2
CA 02344738 2001-04-20
invite overbooking of resources and hence the violation of QoS guarantees.) If
there is not enough free capacity to serve a new applicant, it must be
rejected. The
entity which scrutinizes applicants and admits or rejects them is called a
network
admission controller. An admission controller which keeps track of committed
network resources, and only admits a new applicant if sufficient uncommitted
or free
resources are available to meet its QoS needs, is called an admission
controller with
Quality of Service Guarantees. If these guarantees are absolute they are
called hard; if
they can be broken occasionally without penalty they are soft. Finally, an
admission
controller which is able to select among all of the customers on offer, so as
to admit
the subset which yields the highest possible revenue, is revenue-optimal.
Description of the Invention
We claim to have invented and built the first revenue-optimal admission
controller
with QoS guarantees for internets. (In previously disclosed work, we described
a
revenue-optimal admission controller for a multimedia server computer.)
Customers'
requests for admission are expressed as Service Level Agreements; we describe
these
first.
1. SLA request
The Service Level Agreement or SLA specifies
3
CA 02344738 2001-04-20
1. the data rate requested
2. the maximum acceptable latency
3. the offered price, and
4. start and end times
5. whether the service is recurnng (e.g. every Tuesday)
for each of one or more levels of QoS.
The admission controller must then admit the customer at one of the specified
levels
of QoS. (By convention, QoS Level 0 means zero data rate, infinite latency,
and no
charge, i.e. rejection of the SLA.) If a rejected customer chooses, she may
revise her
offered price upwards and bid again to be admitted; hence the admission
process
incorporates an auction.
As SLAs may arrive randomly in time, and as the controller selects a subset of
those on offer to be admitted, we collect or batch SLAs for an interval of
time called
an epoch. At the end of each epoch ( a few seconds to a few minutes in
practice) the
controller selects SLAs for admission from the accumulated batch, and
concurrently
the next epoch begins.
4
CA 02344738 2001-04-20
2. Mathematical Formulation of the Controller's Functioning
For each session, a QoS level must be selected. This level determines the
session
revenue and the session resource requirements, where a session is the flow of
datagrams ( for example, a telephone call or the viewing of a movie) requested
and
permitted by an SLA.
In order to guarantee service at the level of QoS selected, we must bind the
necessary resources to the session before it begins, and for the duration of
its
existence. In this manner we can avoid allocating the same resource to two
competing
sessions (analogous to allocating an airline seat to two competing
passengers), and
thus violating QoS guarantees.
The system revenue is the arithmetic sum of all session revenues. Figure 1
shows
the relations between system and session revenues, and between resource
mappings
and constraints, established via the choice of session QoS.
CA 02344738 2001-04-20
' session i
bronze silver gold
Quality Q;
session utility function , ~ \ , resource mapping
session utility u~(Q;)~ ( session resources r
system utility ~ \ system resource constraints
U= E u,(Q~ ~ ~ E r (Q~) 5 R
Figure 1: Relations among qualities, utility and resources.
Our goal, then, is to maximize the revenue U while respecting the system
resource
constraints R. This problem is called the Adaptive Multimedia Problem, or AMP.
We believe we are the first to realize that the problem of selecting SLAs for
admission
from an offered batch so as to maximize revenue, while observing all QoS
guarantees,
can be expressed as a variant of the famous Knapsack Problem of combinatorial
mathematics.
2.1 Knapsack Problem
6
CA 02344738 2001-04-20
In its simplest form, we have a pile of stones, each of which has a weight and
a
l~
r
J
w
Pick items to maximize weight (utility) U=Eu,
sub ject to volume constraint (resource constraint): Eps39
Fig 2- Knapsack Problem
Volume (please see Fig 2), and a knapsack which has a volume. The problem is
to
pick a subset of the stones which maximizes the weight of the knapsack while
remaining within its volume constraint, i.e. not overfilling it.
2.2 Multidimensional Multiple Choice Knapsack Problem (MMKP)
In this little-studied variant of the Knapsack Problem, we have piles of
stones, and
we must select exactly one stone per pile, so as to maximize weight while
respecting
the volume constraint. And, volumes are allowed to be vectors rather than
single
7
CA 02344738 2001-04-20
numbers, so the volume constraint is multidimensional. Please see Figure 3,
where the
volume is 2-dimensional with components p and m. This means that the sum of p-
values of the stones chosen must not exceed the p-value of the knapsack, and
the sum
of m-values of stones chosen must not exceed the m-value of the knapsack.
Revenues
are u-values, as before.
Figure 3: Multidimensional Multiple Choice Knapsack Problem (MMKP)
2.3 Mapping
The key to solving our admission control problem is to convert it into a
known,
well-understood problem - the MMKP. We do this by letting
8
CA 02344738 2001-04-20
~ a stone represent a SLA at a particular level of QoS
~ a pile of stones represent a SLA ( all levels of QoS)
~ the knapsack represent the data network
~ each volume constraint of a stone represent a requirement for one of
the network's resources, i.e. data rate or latency of one link of the
network.
~ the weight of a stone be the price offered for this SLA at this level of
QoS
Thus the act of selecting a set of stones to maximize weight becomes the act
of
selecting a set of SLAs at particular QoS levels which maximizes revenue. To
refrain
from overfilling the knapsack is to refrain from oversubscribing any of the
network's
resources - the data rates or latencies which its links can sustain - and thus
QoS is
assured.
2.4 Routing
However, we must know which links of the network a given SLA will use, in
order to
know the links whose data rate or bandwidth resource will be (partially or
completely )
consumed by the SLA. In order to determine this, we must select a path or
route through
the network from source to destination. As figure 4 shows, a route is a
sequence or chain
9
CA 02344738 2001-04-20
of links connected by switches, along which datagrams flow from source to
destination.
We must find a route which has adequate spare (free, uncommitted) capacity or
bandwidth on each of its links. We do this by deleting all links with
insufficient spare
capacity from the network and applying a well-known, standard network routing
algorithm to the remainder.
CA 02344738 2001-04-20
Figure 4 - A Route through a network from S to D.
2.5 Solving the MMKP
We have now completely converted our problem to a mathematical one, an MMKP.
To solve the MMKP we invented two new algorithms, described in the Appendices.
The first, BBLP, (Branch & Bound with Linear Programming) yields an exact
solution. However, as the problem grows (bigger networks or more SLAs) the
time
and cost for a solution grows very rapidly (as the problem is NP-hard) so BBLP
is
impractical for large networks. The second solution algorithm, NHEU, is
inexact.
However, it is much faster and usually yields solutions which are within 10 or
20
of the exact, i.e. truly optimal or best solution.
2.6 Building the Admission Controller
The admission controller has been constructed as software running on a
standard
Pentium-based computer running Windows 9~. We implemented the NHEU solution
11
CA 02344738 2001-04-20
algorithm for the MMKP, a routing algorithm (OSPF), and procedures to accept a
set
of SLAs and a description of the subject network's topology and link
capacities.
2.7 Using the Admission Controller
In our demonstrations of the controller, we make up SLAs manually and put them
in
an input file. The controller reads the network topology and capacity files
and builds
an internal description of the subject network. It then reads the SLAB.
Procedure
NHEU is invoked to solve the resulting MMKP, and the SLAs admitted are
displayed
on the computer's screen, together with the revenue earned and the states of
all
network links.
To use the controller to regulate admissions to a real network, we pass SLAs
to the
controller, which batches them and selects the admitted ones by solving the
MMKP. It
then asks the local switch of the network, to which it has a direct
connection, to build
MPLS (Multi Path Label Switching) paths corresponding to the routes chosen by
the
controller for the admitted SLAB. It then passes the resulting MPLS path id to
the
customer, who labels every datagram with this label. The usual MPLS procedures
of
the switch then ensure that all datagrams of this SLA are routed along this
MPLS path.
12
CA 02344738 2001-04-20
2.8 Performance
The controller must run fast enough to allow real-time admissions; that is,
the
decisions to admit SLAs, and if so at which level of QoS, must be taken as the
SLAs
arrive in real time. Admission of a batch can be done concurrently with the
collecting
of SLAs for the next batch, so the controller need only complete an admission
in less
than the epoch time inter~.-al: We have suggested that a few seconds to a few
minutes
are realistic values for the epoch interval.
Using a controller built in Java running on a Pentium 3 microprocessor, we are
able
to admit 100 SLAs to a 30-node network in less than 2 seconds. As a re-
implementation of the controller in C would yield about a factor of 10
speedup, a
controller to do this task in 200 msec is feasible. Hence the controller using
current
technology is fast enough for real time admission to enterprise networks
(usually
defined as networks of less than 100 switches or nodes).
of the patent application
1. A method for admission control of service reque's'ts-i~ QoS-guaranteed data
network to provide dynamically optimal system revenue, by using a technique
13
