The online advertising market, with its thousands of auctions run per second, presents a daunting challenge for advertisers who wish to optimize their spend under a budget constraint. Thus, advertising platforms typically provide automated agents to their customers, which act on their behalf to bid for impression opportunities in real time at scale. Because these proxy agents are owned by the platform but use advertiser funds to operate, there is a strong practical need to balance reliability and explainability of the agent with optimizing power. We propose a generalizable approach to optimizing bidding policies in production environments by learning from real data using offline reinforcement learning. This approach can be used to optimize any differentiable base policy (practically, a heuristic policy based on principles which the advertiser can easily understand), and only requires data generated by the base policy itself. We use a hybrid agent architecture that combines arbitrary base policies with deep neural networks, where only the optimized base policy parameters are eventually deployed, and the neural network part is discarded after training. We demonstrate that such an architecture achieves statistically significant performance gains in both simulated and at-scale production bidding environments compared to the default production bidding policy. Our approach does not incur additional infrastructure, safety, or explainability costs, as it directly optimizes the parameters of existing production routines without necessarily replacing them with black box-style models like neural networks.

Network function virtualization (NFV), with its potential to facilitate network service provisioning, has drawn growing interest from both academia and industry. One essential challenge is to allocate efficiently the bandwidth and computational resources to the service requests. In an online context, service chain requests may arrive, depart or evolve in an arbitrary fashion, adding more difficulty to the problem. Service chain reconfiguration may help improve the performance by individually rerouting a subset of the service chain requests. In this paper, we propose a new service chain reconfiguration framework to achieve load balancing in an NFV environment under varying levels of support from the underlying infrastructure. We show that our framework can achieve an approximation ratio of O(lnm/ln lnm) with high probability for the service chain request rerouting problem.

Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem. We route the service chain with the goal of jointly minimizing the maximum network congestion and the number of hops from the source to the destination. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(log m)-competitive in terms of congestion minimization, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.

Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem with the goal of minimizing the maximum network congestion. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(log m)-competitive, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.

Efficient allocation of resources is an essential yet challenging problem in a virtual network environment, especially in an online setting whereby virtual network requests may arrive, depart, or be modified in real time. Virtual network reconfiguration may help to improve network performance by remapping a subset of virtual nodes or links to better align the allocation of resources to current network conditions. In this paper, we develop a virtual network reconfiguration scheme that aims to balance the load on the substrate network by dynamically reconfiguring the embedding of both virtual nodes and links. Our solution consists of decomposing the problem into two subproblems: i) virtual node selection, for which we present a linear programming-based fully polynomial time approximation scheme to select the virtual nodes to be migrated, and ii) virtual node remapping, for which we make use of random walk on a Markov chain to select new substrate nodes for the migrated virtual nodes.

Virtual request partitioning is an essential subproblem of two common problems in virtual networks, namely, virtual network embedding (VNE) and virtual machine placement (VMP). In this study, we consider a network-aware variant of the problem where the objective is to partition a virtual request so as to minimize the total amount of inter-cluster traffic. This problem is equivalent to the (k,v)-balanced partitioning problem, an NP-complete problem. To handle the inherent complexity of this problem, we develop a spectral clustering-based partitioning scheme that produces good solutions in a reasonable amount of time. Our solution consists of several components: (a) spectral clustering, (b) a constrained k-means partitioning algorithm that ensures that capacity limits for clusters are met, and for which we present a polynomial-time greedy algorithm, and (c) a greedy refinement algorithm using simulated annealing to further improve the clustering solution. Simulation results indicate that our algorithm outperforms existing partitioning schemes in terms of inter-cluster traffic minimization.