Research interests
-
QoS management
-
distributed algorithms
-
convex optimization
-
wireless (sensor) networks
-
real-time systems
-
modeling and simulation of communication networks
My main research interest lies in the area of adaptive QoS management
for dynamic, open, and resource constrained systems, subject of
unpredictable overloads. A good example of dynamic, open, and
resource-constrained systems are wireless networks.
Background
Wireless networks, constrained resources
Wireless networks
will always be more resource constrained compared to their wireline
counterparts. This is a consequence of the limited communication
spectrum available, and of the embedded nature of the mobile
nodes. Moreover, transmission interference and fading, combined with
node mobility make it a highly unstable environment. Resource
availability can quickly change, leading to unpredictable overloads in
the network. Thus, frequent resource reallocation is needed in order
to mitigate overloads and keep the system performance as high as
possible. While nowadays multi-service wireless platforms (e.g. 3g,
wimax, and mesh networks) are still in their incipient roll-out
stages, it is expected that soon existing infrastructures could be
easily overloaded if a fraction of users would opt for data-intensive
services (such as Mobile TV).
Quality of Service (QoS)
Modern communication aim to
provide a wide range of services, where soft real-time, high priority
critical data, and best effort connections seamlessly integrate. Some
of these applications and services have firm resource requirements in
order to function properly (e.g. videoconferences), others are
flexible enough to adapt to whatever is available
(e.g. FTP). Different connections might have different importance
levels, and should be treated accordingly. Providing differentiation
and resource assurance is often referred to as providing quality of
service (QoS).
User specified utility, utility functions, optimisation
The goal of QoS management is to improve the performance of the system
with respect to the quality of service expected by users. Thus it is
important to capture the benefit of the particular users, in order to
know how resources in the system should be for optimal system
performance. This utility-resource relationship can be captured with
the help of utility functions.
Results
We have developed several algorithms aimed to optimize bandwidth
allocation in wireless networks. Major results are:
An adaptive utility-based bandwidth allocation and
reallocation scheme for cellular networks. The utility
functions of the connections are used to steer the allocation, with
the aim to optimise the overall system utility (the sum of the
utilities gained by all the connections). To keep the dynamic system
optimised we periodically reevaluate all allocations and perform
necessary reallocations. The novelty in our scheme is that we take
into account the effects that reallocations have on the accumulated
utility of the different connections. We have built algorithms for
modifying the initial utility functions at runtime, such that
connections become comparable regardless of their flexibility class or
age. Thus, adaptation and resource assurance are combined in a
consistent manner, and our system supports real-time applications
alongside best-effort ones. We have evaluated our new approach by
comparing it with a recent adaptive allocation scheme [TPDS'05].
A combined utility/price-based bandwidth allocation and
routing scheme for wireless ad hoc networks. In this case, we
study bandwidth allocation in a pure multi-hop environment. We first
show that the bandwidth allocation problem in a multi-hop wireless
network can be formulated as linear programming (LP) maximisation
problem. While centralised and infeasible for online allocation, the
LP solution provides an upper baseline for comparisons. Then we
propose a novel distributed allocation algorithm, where every flow
"bids" for resources on the end-to-end path of the connection,
depending on the resource "shadow price", and the flow's "utility
efficiency". Using the periodic (re)allocation, our scheme both adapts
to changes in the network, and also recalculates and improves our
estimation of the resource shadow prices. For deciding the routes we
use a new type of shortest path first algorithm, where the shadow
prices are used a natural distance metric. Experimental results show a
very good behaviour of our distributed allocation algorithm, that is
within 10% of the behaviour of the centralised, optimal LP solution
[SECON'05]. Moreover, experiments, show a better performance of
our algorithm compared to the state of the art price-based allocation
optimization algorithm [IPDPS´06].
Current directions
Our goal is to define and evaluate a utility-based allocation
framework for wireless communication networks. It will include
algorithms and utility models that we already developed, but several
other components are necessary. Thus active research directions are as
follows:
Suitable utility functions. A first step is to
derive suitable utility functions for different applications/services
and QoS combinations as related to the price the users are ready to
pay for the service and the constraints on the network
resources. Using techniques such as Multi-Attribute Utility Theory
might help us get the multi-dimensional utility functions represented
as a sum or as a multiplication of single-dimensional utility
functions.
Llightweight multidimensional optimization
algorithms. We also intend to devise novel distributed
resource allocation algorithms that can implement the optimisation
policy. To this end we intend to approximate the problem with a convex
problem and explore methods form convex optimisation theory. While not
aiming for optimality, formulating the problem in game theoretical
terms might provide robust allocation.
Cross-layer implementation. In order to evaluate
the feasibility and the advantages of an allocation scheme we need to
implement the allocation policy in the protocol stack of the
network. This will allow us to test important factors such as
generated overhead and allocation accuracy, under a number of
simulated test scenarios. The cross-layer approach, comes as a natural
choice, since the implemented protocols should be designed to support
the high level optimisation policy, and not to work independently.
The above price-allocation policy gets support also from the fact
that more and more consumers are ready to accept service models where
flexibility and congestion pricing are implemented, such as the the
low-fare airline model, micro-payments on the Internet, or fees for
congestion avoidance on public roads.
|
