Traditionally, network optimization is used to provide good configurations in real network system problems based on mathematical models and statistical assumptions. Recently, this paradigm is evolving, fueled by an explosion of availability of data. The modern trend in networking problems is to tap into the power of data to extract models and deal with uncertainty. This thesis is targeting on augmenting the arsenal of algorithms against specific network problems, by proposing algorithmic frameworks for wireless networks, based both on classical or data-driven optimization and machine learning.
In wireless networks, application of optimization is gaining momentum both in practice and research, following the wireless communication proliferation and the need for greatly enhanced resource utilization efficiency. Demand for wireless data is increasing exponentially, networks are becoming extremely dense in devices and cells, services come with extreme and diverse QoS requirements. Current network architecture which is based on one-type-fits-all services and spectrum re-use is already becoming unprofitable.
As a consequence, resource provisioning in wireless networks is evolving in a very challenging problem. This can be briefly accounted to the following: i) high spatiotemporal variation of demand, ii) high dimension of optimization and iii) coupling of decisions. The challenge is to come up with optimization methods that are fast, scalable and quickly adapting to input changes; while being robust against fluctuations to guarantee the service requirements. We target two use cases, user association and cloud resource reservation.
The baseline approach for user association, connecting wireless devices to the base station that provides the strongest signal, leads to very inefficient configurations in current and future wireless networks. We focus on tailoring user association based on resource efficiency and service requirement satisfaction (QoS guarantees), depending on the underlying network demand.
First, we study the user association problem for two network services (chapter 2); one requiring QoS guarantees to VIP flows, and one best effort service. The goal is to take advantage of statistical multiplexing in order to optimize the use of resources, while ensuring that the VIP flows enjoy active performance guarantees. We formulate this as an optimization problem, show that the problem is convex, and finally demonstrate that the optimum point can in fact be realized by distributed user association rules.
In chapter 3 we tackle user association focusing on developing a central scalable algorithm. We steer wireless traffic to Cloud-Radio Access Networks (C-RANs) by designing device association rules, in order to load balance the network. To address the challenge of massive connectivity and the resulting computational bottleneck, we propose an approach based on the theory of optimal transport, which studies the economical transfer of probability between two distributions.
Further, we propose a data-driven framework for user association leveraging the theory of robust optimization, see in chapter 4. The main idea is to predict future traffic fluctuations, and use the predictions to design association maps before the actual arrival of traffic. Although the actual playout of the map is random due to prediction error, the maps are robustly designed to handle uncertainty, preventing constraint violations, and maximizing the expectation of a convex utility function, which is used to accurately balance base station loads. The optimal maps have the intriguing property that they jointly optimize the predicted load and the variance of the prediction error. We validate our robust maps in Milano-area traces with dense coverage.
Moving to the topic of cloud resource reservation, we develop a novel framework to handle resource reservation in worst-case scenaria, where the demand is engineered by an adversary aiming to harm our performance. We provide policies that have "no regret" and guarantee asymptotic feasibility in budget constraints, under such workloads, complementing the results of recent literature in cloud computing and more importantly in Online Convex Optimization (OCO).
In chapter 5 we propose a policy for cloud resource reservations that eventually learns the minimum cost reservation, while satisfying a time-average constraint for violations. This uses a combination of the Lyapunov optimization theory and a linear prediction of the future based on the recent past. We validate our policy on real cloud system traces.
Next, we generalize in chapter 6, creating a framework for online convex optimization problems with long-term budget constraints. Problems like this arise naturally in networks as reliability guarantees or total consumption constraints. Our proposition is cautious online Lagrangian descent (COLD) for which we derive explicit bounds, in terms of both the incurred regret and the residual budget violations.
Finally, chapter 7 contains the conclusions of our work and our future goals and some preliminary results on the comparison of the proposed methods.
