Resource Allocation and Pricing for QoS Management in Computer Networks
Errin W. Fulp
1999
Doctor of Philosophy
Computer Engineering
North Carolina State University

Computer networks must accommodate a wide variety of applications,
ranging from simple file transfer programs to complex multimedia
applications. Many of these applications require certain Quality of
Service (QoS) guarantees for their proper operation. QoS guarantees
include bounds on the packet delay, delay variation and loss rate. These
guarantees can be provided through the allocation of network resources
such as, processor time, buffer space and link bandwidth. Properly
allocating network resources remains a challenging problem due to the
number of users, diversity of network applications and the finite supply
of resources. Furthermore, these resources are expected to have costs
associated with their usage (amount and renegotiation). Given this
environment, two important resource allocation issues are addressed in
this thesis. First, methods are needed to reduce the amount of resources
and renegotiations required to provide a desired QoS (thereby reducing
the cost and increasing the utilization). Second, network administrators
are interested in allocating and managing resources to all users in an
efficient and fair manner. 

Determining an efficient amount of network resources that will result in
a desired QoS is difficult for certain sources, due to their
unpredictable behavior and limited a priori source information. Such
applications include the transmission of, MPEG-compressed video, live
video and interactive multimedia. In this thesis, an allocation method
called Dynamic Search Algorithm (DSA+) is introduced. DSA+ is an on-line
algorithm that dynamically adjusts the resource allocation based upon
the measured QoS. Advantages of DSA+ include efficient use of resources,
few renegotiations, reasonable implementation cost, and stringent QoS
control. The ability of DSA+ to allocate bandwidth to meet a desired
cell loss probability is investigated and analyzed via simulation using
generated (MMBP) and actual MPEG-compressed videos. Advantages of DSA+
over other allocation methods, the robustness to initial parameter
selection and the ability to allocate for multiple hop connections are
presented.

Network managers seek to allocate resources, to all users, in an
efficient and fair manner. In this thesis, microeconomic-based
allocation techniques are introduced that model the network as an
economy, consisting of separate and independent competitive markets. In
these markets, switches price their link bandwidth based on supply and
demand, and users purchase bandwidth to maximize their individual QoS.
Two different types of markets are used to allocate resources: the spot
market and the reservation market. The reservation market provides users
the advantage of bandwidth ownership over a period of time, while the
bandwidth sold in the spot market has the advantage of immediate
availability (no reservation overhead). These decentralized state-less
allocation methods can provide efficient and fair allocations of
bandwidth as well as guarantees of resource availability. Proofs of
important microeconomic and standard computer network measures of
fairness are presented, as well as price stability. The performance of
these resource allocation methods are also investigated and analyzed
using simulations with various network configurations and actual
MPEG-compressed videos. Results indicate that these microeconomic-based
resource allocation methods achieve high utilization, optimal
allocations and provide better QoS than other allocation techniques.