Network slicing has been proposed as a paradigm for 5G+ networks. The operators slice physical resources from the edge all the way to the datacenter, and are responsible to micro-manage the allocation of these resources among tenants bound by predefined Service Level Agreements (SLAs). A key task, for which recent works have advocated the use of Deep Neural Networks (DNNs), is tracking the tenant demand and scaling its resources. Nevertheless, for the edge resources (e.g., RAN), a question arises on whether operators can: (a) scale them fast enough (often in the order of ms) and (b) afford to transmit huge amounts of data towards a remote cloud where such a DNN model might operate. We propose a Distributed DNN (DDNN) architecture for a class of such problems: a small subset of the DNN layers at the edge attempt to act as fast, standalone resource allocator; this is complemented by a mechanism to intelligently offload a percentage of (harder) decisions to additional DNN layers running at a remote cloud. To implement the offloading, we propose: (i) a Bayes-inspired method, using dropout during inference, to estimate the confidence in the local prediction; (ii) a learnable function which automatically classifies samples as “remote” (to be offloaded) or “local”. Using the public Milano dataset, we investigate how such a DDNN should be trained and operated to address (a) and (b). In some cases, our offloading methods are near-optimal, resolving up to 50% of decisions locally with little or no penalty on the allocation cost.

In this paper we investigate the problem of uplink scheduling in a multicell system in order to minimize the total queuing delay at the mobile devices. The proposed setting introduces an environment with multiple interacting decision makers: Base Stations are considered as agents who have partial view of the system and interact with each other through interference generated by their scheduled devices for uplink transmissions. In addition, since traffic and channel processes are unknown, finding the optimal global scheduling policy can be modeled as a multiagent reinforcement learning problem. In this work, we propose distributed learning algorithms based on policy gradient to tackle this problem and investigate the impact of information exchange between Base Stations. Our results illustrate that the proposed algorithm outperforms standard schedulers, such as Proportional Fair and MaxWeight and that information exchange is crucial for challenging problem instances, such as topologies with many devices on the cell edge and/or high traffic demands.

This paper presents a new framework to deal with the unpredictable nature of demands in Edge Computing. We formulate the edge resource reservation problem as a constrained Online Convex Optimization (OCO) problem with time-varying cost and constraint functions and introduce a new metric, termed Outage Fit, to capture the fact that constraint violation by even a small amount can lead to service outages. Based on this notion, an online algorithm which provably learns to avoid service outages and constraint violations while resulting in a good latency cost is proposed and numerical results, based on real data traces showcase the improvement with respect to the state of the art algorithms.

This paper considers the Multiple Access problem where$N$Internet of Things (IoT) devices share a common wireless medium towards a central Base Station (BS). We propose a Reinforcement Learning (RL) method where the BS is the agent and the devices are part of the environment. A device is allowed to transmit only when the BS decides to schedule it. Besides the information packets, devices send additional messages like the delay or the number of discarded packets since their last transmission. This information is used to design the RL reward function and constitutes the next observation that the agent can use to schedule the next device. Leveraging RL allows us to learn the sporadic and heterogeneous traffic patterns of the IoT devices and an optimal scheduling policy that maximizes the channel throughput. We adapt the Proximal Policy Optimization (PPO) algorithm with a Recurrent Neural Network (RNN) to handle the partial observability of our problem and exploit the temporal correlations of the users' traffic. We demonstrate the performance of our model through simulations on different number of heterogeneous devices with periodic traffic and individual latency constraints. We show that our RL algorithm outperforms traditional scheduling schemes and distributed medium access algorithms.

We learn optimal user association policies for traffic from different locations to Access Points(APs), in the presence of unknown dynamic traffic demand. We aim at minimizing a broad family of α-fair cost functions that express various objectives in load assignment in the wireless downlink, such as total load or total delay minimization. Finding an optimal user association policy in dynamic environments is challenging because traffic demand fluctuations over time are non-stationary and difficult to characterize statistically, which obstructs the computation of cost-efficient associations. Assuming arbitrary traffic patterns over time, we formulate the problem of online learning of optimal user association policies using the Online Convex Optimization (OCO) framework. We introduce a periodic benchmark for OCO problems that generalizes state-of-the-art benchmarks. We exploit inherent properties of the online user association problem and propose PerOnE, a simple online learning scheme that dynamically adapts the association policy to arbitrary traffic demand variations. We compare PerOnE against our periodic benchmark and prove that it enjoys the no-regret property, with additional sublinear dependence of the network size. To the best of our knowledge, this is the first work that introduces a periodic benchmark for OCO problems and a no-regret algorithm for the online user association problem. Our theoretical findings are validated through results on a real-trace dataset.

Reconfigurable intelligent surfaces (RIS) technology, as the name implies, is a grid of many small intelligent surfaces that can be reconfigured. It is a new and promising concept in wireless communications, expected to help realize the requirements of the future cellular generations. Numerous studies have been done to prove its added advantages and to control these surfaces in beneficial ways. However, these control schemes come with difficulties related to efficient and practical implementation. In this paper, we propose to control multiple RISs in a multi-user scheme with an algorithm that leads to a simple implementation. We formulate a stochastic optimization problem and we propose a new method using a distributed stochastic algorithm that allows the optimization to be done locally at each RIS with low computational requirements and without the need for instantaneous channel knowledge at the RIS. Also, the signaling between the base station (BS) and each RIS is limited to the exchange of a scalar only. Simulation results prove the success and efficiency of this algorithm.

We consider the dynamic spectrum access (DSA) problem where K Internet of Things (IoT) devices compete for T time slots constituting a frame. Devices collectively monitor M events where each event could be monitored by multiple IoT devices. Each device, when at least one of its monitored events is active, picks an event and a time slot to transmit the corresponding active event information. In the case where multiple devices select the same time slot, a collision occurs and all transmitted packets are discarded. In order to capture the fact that devices observing the same event may transmit redundant information, we consider the maximization of the average sum event rate of the system instead of the classical frame throughput. We propose a multi-agent reinforcement learning approach based on a stochastic version of Multi-Agent Deep Deterministic Policy Gradient (MADDPG) to access the frame by exploiting device-level correlation and time correlation of events. Through numerical simulations, we show that the proposed approach is able to efficiently exploit the aforementioned correlations and outperforms benchmark solutions such as standard multiple access protocols and the widely used Independent Deep Q-Network (IDQN) algorithm.

The performance of existing coded caching schemes is sensitive to the worst channel quality, a problem which is exacerbated when communicating over fading channels. In this paper, we address this limitation in the following manner: in short-term, we allow transmissions to subsets of users with good channel quality, avoiding users with fades, while in long-term we ensure fairness among users. Our online scheme combines (i) the classical decentralized coded caching scheme with (ii) joint scheduling and power control for the fading broadcast channel, as well as (iii) congestion control for ensuring the optimal long-term average performance. We prove that our online delivery scheme maximizes the alpha-fair utility among all schemes restricted to decentralized placement. By tuning the value of alpha, the proposed scheme can achieve different operating points on the average delivery rate region and tune performance according to an operator's choice. We demonstrate via simulations that our scheme outperforms two baseline schemes: (a) standard coded caching with multicast transmission, limited by the worst channel user yet exploiting the global caching gain; (b) opportunistic scheduling with unicast transmissions exploiting the fading diversity but limited to local caching gain.

We study the problem of wireless edge caching when file popularity is unknown and possibly non-stationary. A bank of J caches receives file requests and a utility is accrued for each request depending on the serving cache. The network decides dynamically which files to store at each cache and how to route them, in order to maximize total utility. The request sequence is assumed to be drawn from an arbitrary distribution, capturing time-variance, temporal and spatial locality of requests. For this challenging setting, we propose the Bipartite Supergradient Caching Algorithm (BSCA) which provably exhibits no regret (RT/T → 0). That is, as the time horizon T increases, BSCA achieves (at least) the same utility with the cache configuration that we would have chosen knowing all future requests. The learning rate of the algorithm is characterized by its regret expression RT= O( √JT ), which is independent of the file library size. For the single-cache case, we prove that this is the lowest attainable bound. BSCA requires at each step J projections on intersections of boxes and simplices, for which we propose a tailored algorithm. Our model is the first that draws a connection between the network caching problem and Online Convex Optimization, and we demonstrate its generality by discussing various practical extensions and presenting a tracedriven comparison with state-of-the-art competitors.

We study a class of online convex optimization problems with long-term budget constraints that arise naturally as reliability guarantees or total consumption constraints. In this general setting, prior work by Mannor et al. (2009) has shown that achieving no regret is impossible if the functions defining the agent’s budget are chosen by an adversary. To overcome this obstacle, we refine the agent’s regret metric by introducing the notion of a "K-benchmark", i.e., a comparator which meets the problem’s allotted budget over any window of length K. The impossibility analysis of Mannor et al. (2009) is recovered when K=T; however, for K=o(T), we show that it is possible to minimize regret while still meeting the problem’s long-term budget constraints. We achieve this via an online learning policy based on Cautious Online Lagrangiant Descent (COLD) for which we derive explicit bounds, in terms of both the incurred regret and the residual budget violations.

This paper introduces a novel caching analysis that, contrary to prior work, makes no modeling assumptions for the file request sequence. We cast the caching problem in the framework of Online Linear optimization (OLO), and introduce a class of minimum regret caching policies, which minimize the losses with respect to the best static configuration in hindsight when the request model is unknown. These policies are very important since they are robust to popularity deviations in the sense that they learn to adjust their caching decisions when the popularity model changes. We first prove a novel lower bound for the regret of any caching policy, improving existing OLO bounds for our setting. Then we show that the Online Gradient Ascent (OGA) policy guarantees a regret that matches the lower bound, hence it is universally optimal. Finally, we shift our attention to a network of caches arranged to form a bipartite graph, and show that the Bipartite Subgradient Algorithm (BSA) has no regret.

In this paper we address the problem of joint admission control and resource scheduling for Ultra Reliable Low Latency Communications (URLLC). We examine two models: (i) the continuous, where all allocated resource blocks contribute to the success probability, and (ii) a binary, where only resource blocks with strong signal are “active” for each user, and user$k$needs dkactive resource blocks for a successful URLLC transmission. In situations of congestion, we are interested in finding a subset of users that can be scheduled simultaneously. We show that finding a feasible schedule for at least$m$URLLC users is NP-complete in the (easier) binary SNR model, hence also in the continuous. Maximizing the reward obtained from a feasible set of URLLC users is NP-hard and inapproximable to within (log2d)2/d of the optimal, where$d$≐ maxkdk. On the other hand, we prove that checking a candidate set of users for feasibility and finding the corresponding schedule (when feasible) can be done in polynomial time, which we exploit to design an efficient heuristic algorithm for the general continuous SNR model. We complement our theoretical contributions with a numerical evaluation of our proposed schemes.

This paper addresses a major challenge in traffic engineering: the selection of a set of paths that minimizes routing cost for a random traffic matrix. We introduce the concept of pathbook: a small set of paths to which we restrict routing. The use of pathbook accelerates centralized traffic engineering algorithms, and therefore is appealing for instantiating, configuring, and optimizing large software-based networks. However, restricting routing to a few paths may lead to higher cost or infeasibility. To this end, we introduce the problem of pathbook design, wherein we search for a pathbook of constrained size that minimizes the expected routing cost of the random traffic matrix, which represents a prediction of the future traffic. The pathbook design problem is of combinatorial nature, and we show that it is NP-hard. We then study its convex relaxation for which we propose an optimal algorithm based on the projected subgradient method. For large networks, the subgradient vector is of prohibitive dimensions, hence we propose a coordinate-descent method using the Gauss-Southwell rule, which prescribes a move along the direction of largest subgradient element. We test the performance of our solution on dynamic traffic matrices from GEANT and find that our Gauss-Southwell pathbooks can accelerate standard methods by two orders of magnitude.

This paper studies Ultra-Reliable Low-Latency Communications (URLLC), an important service class of emerging 5G networks. In this class, multiple unreliable transmissions must be combined to achieve reliable latency: a user experiences a frame success when the entire L bits are received correctly within a deadline, and its latency performance is reliable when the frame success rate is above a threshold. When jointly serving multiple users, a natural URLLC scheduling question arises: given the uncertainty of the wireless channel, can we find a scheduling policy that allows all users to meet a target reliable latency objective? This is called the URLLC SLA Satisfaction (USS) problem. The USS problem is an infinite horizon constrained Markov Decision Process, for which, after establishing a convenient property, we are able to derive an optimal policy based on dynamic programming. Our policy suffers from the curse of dimensionality, hence for large instances we propose a class of knapsack-inspired computationally efficient - but not necessarily optimal - policies. We prove that every policy in that class becomes optimal in a fluid regime, where both the deadline and L scale to infinity, while our simulations show that the policies perform well even in small practical instances of the USS problem.

Imposing fairness in resource allocation incurs a loss of system throughput, known as the Price of Fairness (PoF). In wireless scheduling, PoF increases when serving users with very poor channel quality because the scheduler wastes resources trying to be fair. This paper proposes a novel resource allocation framework to rigorously address this issue. We introduce selective fairness: being fair only to selected users, and improving PoF by momentarily blocking the rest. We study the associated admission control problem of finding the user selection that minimizes PoF subject to selective fairness, and show that this combinatorial problem can be solved efficiently if the feasibility set satisfies a condition; in our model it suffices that the wireless channels are stochastically dominated. Using selective fairness, we formulate the PoF minimization subject to an SLA, which ensures that an ergodic subscriber is served frequently enough. In this context, we propose an online policy that combines the DriftPlus-Penalty technique with Gradient-Based Scheduling experts, and we prove it achieves the optimal PoF. Simulations show that our intelligent blocking outperforms by 40% in throughput the baseline approach which satisfies the SLA by blocking low-SNR users without considering the overall PoF minimization.

We investigate a pilot allocation problem in wireless networks over Markovian fading channels. In wireless systems, the channel state information (CSI) is collected at the base station, in particular, this paper considers a pilot-aided channel estimation method (TDD mode). Typically, there are less available pilots than users, hence at each slot the scheduler needs to decide an allocation of pilots to users with the goal of maximizing the long-term average throughput. There is an inherent tradeoff in how the limited pilots are used: assign a pilot to a user with up-to-date CSI and good channel condition for exploitation, or assign a pilot to a user with outdated CSI for exploration. As we show, the arising pilot allocation problem is a restless bandit problem and thus its optimal solution is out of reach. In this paper, we propose an approximation based on the Lagrangian relaxation method, which provides a low-complexity Whittle index policy. We prove this policy to be asymptotically optimal in the many users regime (when the number of users in the system and the available pilots for channel sensing grow large). We evaluate the performance of Whittle's index policy in various scenarios and illustrate its remarkably good performance for small number of users, where it is not guaranteed to be optimal.

The performance of existing coded caching schemes is sensitive to the worst channel quality, when applied to wireless channels. In this paper, we address this limitation in the following manner: in short-term, we allow transmissions to subsets of users with good channel quality, avoiding users with fades, while in long-term we ensure fairness across the different users. Our online delivery scheme combines (i) joint scheduling and power control for the fading broadcast channel, and (ii) congestion control for ensuring the optimal long-term average performance. By restricting the caching operations to decentralized coded caching proposed in the literature, we prove that our proposed scheme has near-optimal overall performance with respect to the long-term alpha fairness performance. By tuning the coefficient alpha, the operator can differentiate the user performance in terms of video delivery rates achievable by coded caching. We demonstrate via simulations that our scheme outperforms standard coded caching and unicast opportunistic scheduling, which are identified as special cases of our general framework.

We study network response to a stream of queries that require computations on remotely located data, and we seek to characterize the network performance limits in terms of maximum sustainable query rate that can be satisfied. The available network setup consists of (i) a communication network graph with finite-bandwidth links over which data is routed, (ii) computation nodes with certain computation capacity, over which computation load is balanced, and (iii) network nodes that need to schedule raw and processed data transmissions. Our aim is to design a universal methodology and distributed algorithm to adaptively allocate resources in order to support maximum query rate. The proposed algorithms extend in a nontrivial way the backpressure (BP) algorithm to take into account computations carried out in the presence of query streams. They contribute to the fundamental understanding of network computation performance limits when the query rate is limited by both the communication bandwidth and the computation capacity, a classical setting that arises in streaming big data applications in network clouds and fogs.

Software-Defined Network (SDN) controllers include mechanisms to globally reconfigure the network in order to respond to a changing environment. While iterative methods are employed to solve flow optimization problems, demands arrive or leave the system changing the optimization instance and requiring further iterations. In this paper, we focus on the general class of iterative solvers considering an exponential decrease over time in the optimality gap. Assuming dynamic arrivals and departures of demands, the computed optimality gap at each iteration Q(t) is described by an auto-regressive stochastic process. At each time slot the controller may choose to apply the current iteration to the network or not. Applying the current iteration improves the optimality gap but requires flow reconfiguration which hurts QoS and system stability. To limit the reconfigurations, we propose two control policies that minimize the flow allocation cost while respecting a network reconfiguration budget. We validate our model by experimenting with a realistic network setting and using standard Linear Programming tools used in the SDN industry. We show that our policies provide a practical means of keeping the optimally gap small within a given reconfiguration constraint.

We study a service provisioning system where arriving jobs are routed in an online fashion to any of the available servers; typical applications include datacenters, Internet switches, and cloud computing infrastructures. A common goal in these scenarios is to balance the load across the servers and achieve maximum throughput. For example, the classical online policy Join-the-Shortest-Queue (JSQ) routes an arriving job to the server with the shortest instantaneous queue length. Although JSQ has desirable properties, it requires coordination between the routers and the servers in the form of queue length reports, which prohibits its practical usability in many scenarios. In this paper we study the practical case of “routing with blinkers”, where no coordination is allowed between the routers and the service provisioning system, and the routers act in an individual manner with limited view of the system state. Every router keeps a log of delays of all jobs it has routed in the past; these are delayed estimates of the actual server queue length. Although easy to acquire, such information is a highly inaccurate depiction of the system state and hence it is unclear whether it is enough to achieve maximum performance. Motivated by the fact that a reasonable policy such as Join-the-Shortest-Delay fails to achieve maximum throughput, we propose a novel routing policy that “samples” the servers periodically and achieves maximum throughput, subject to a condition for the service discipline of the server.

We investigate a pilot allocation problem in wireless networks over Markovian fading channels. In wireless systems, the Channel State Information (CSI) is collected at the Base Station (BS) through either a feedback channel (FDD mode) or a pilot-aided channel estimation method (TDD mode). This paper focuses on the latter. Typically, there are less available pilots than users, hence at each slot the scheduler needs to decide an allocation of pilots to users with the goal of maximizing the long-term average throughput. A trade-off emerges between exploiting users with up-to-date CSI for immediate gains or, exploring users with outdated CSI for a potential larger future gain. As we show, the arising pilot allocation problem is a restless bandit problem and thus its optimal solution is out of reach. In this paper, we propose a Lagrangian relaxation approach to obtain a Whittle index policy, which represents a low-complexity heuristic solution with remarkably good performance.

In this paper, we target a massive multiple-input/multiple-output (MIMO) system operating in frequency-division duplexing (FDD) mode, assuming the adoption of a two-level linear precoding strategy at the BS. We propose a novel strategy to effectively acquire the channel state information (CSI) at the base station (BS). In particular, we devise a cross-layer dynamic algorithm for user grouping, CSI acquisition and user scheduling that takes into account fairness considerations, application characteristics and quality of service (QoS) constraints of the users. We assess the merit of the proposed algorithm for a proportional fairness objective by comparing its performance with what is achieved by a relevant baseline algorithm in which user grouping is static and based only on the second order statistics, i.e., joint space division and multiplexing (JSDM). Our numerical findings illustrate that the proposed algorithm outperforms the baseline in terms of both fairness and speed of convergence to a steady state, and for different network topologies.

In this paper we study the downlink of a TDD (Time Division Duplex) single cell system where the Base Station (BS) employs multiple antennas to serve the users taking into account the traffic patterns. The BS chooses each slot the users to be active, and serves them using Zero Forcing (ZF) precoding. This requires the knowledge of the users' channels which is assumed to be performed e.g. via uplink training. Due to the channel acquisition overhead, only a subset of users must be active at each timeslot (depending on traffic patterns and channel states). In this paper, we develop an active user selection strategy where the base station sets a given threshold for the channel gain of the users. Then, only the users that have their channel gain higher than the threshold send their training sequence and are then considered to be served. The base station estimates the channel states of these users and, due to channel reciprocity, uses these channel states to transmit data via ZF precoding. With appropriate signaling and threshold selection, which adapt to the queuing behavior of the users, we prove that our proposed method achieves a larger stability region than the baseline centralized policy where the BS selects the users based on channel statistics and queue lengths. The performance of the threshold-based method is illustrated via simulations, where we can observe a tradeoff between the expansion of the stability region and delay performance.

In this paper, the problem of feedback and active user selection in multiple-input single-output (MISO) wireless systems such that the system's stability region is as big as possible is examined. The focus is on a system in a Rayleigh fading environment where zero forcing precoding is used to serve all active users in every slot. Acquisition of the channel states is done via uplink training in time division duplexing mode by the active users. Clearly, only a subset of users can perform uplink training and the selection of this subset is a challenging and interesting problem especially in MISO systems. The stability regions of a baseline centralized scheme and two novel decentralized policies are examined analytically. In the decentralized schemes, the transmitter broadcasts periodically the queue state information and the users contend for the channel in a carrier sense multiple access-based manner with parameters based on the outdated queue state information and real-time channel state information. We show that, using infrequent signaling between the base station and the users, the decentralized policies outperform the centralized policy. In addition, a threshold-based user selection and training scheme for discrete-time contention is proposed. The results of this paper imply that, as far as stability is concerned, the users must be involved in the active user selection and feedback/training decision. This should be leveraged in future communication systems.

In this paper we study the stability region of the 2-user MISO broadcast channel where the transmitter employs Zero Forcing precoding when both users are scheduled, taking into account the time overheads needed for uplink channel training. We show that, with proper signalling design, combining a decentralized policy with the baseline centralized one for user selection can increase the stability region of the system.

In this work, we address the problem of power allocation for interfering transmitter-receiver pairs so that the probability that each queue length exceeds a specified threshold is fixed at a desired value. One application is satisfying QoS requirements in a dense cellular network. We deal with this problem using heavy traffic approximation techniques which lead to an asymptotic model of a (controlled) stochastic differential equation. The proposed power control strategy consists of allocating most of the power according to the states of the channel and a smaller fraction according to the queue lengths, for which we find a closed-form expression. We first consider a scenario where all channel realizations and queue lengths are known instantaneously to every transmitter. Then, the algorithm is extended to the case where only local SINR feedback is available and when queue length information is shared with delays among the transmitters. These models and results are also extended to the case where the transmitters are equipped with multiple antennas. Finally, the applicability in practical system settings are discussed and simulation results are provided to illustrate the performance of the proposed method.

In this work we address the problem of channel probing in a multicarrier downlink wireless network where in order to collect CSI feedback from each user at a channel, a fraction of the available time for transmission is used. This means that the time left to transmit is getting smaller. We study the aspect of stability of such a system and we find a randomized algorithm which can guarantee an expansion of the stability region with respect to full probing and prior works. In addition, we investigate a special case of a probing scheme that does not require knowledge of the statistics of the channels and can still enlarge the stability region of the system. Simulations show the performance of the proposed scheme.

In this work we study the problem of channel state feedback and user scheduling in a single cell downlink wireless network employing multiple orthogonal parallel channels. The aspect of the system we are focusing on is stability. For user scheduling for stability as a performance measure, both the queue and channel states need to be known by the base station. However channel states can be known only via feedback from the receivers. In order to collect CQI feedback from each user at one channel, a fraction of the available time for transmission is used. This means that the time left to transmit is getting smaller. We present a joint feedback and scheduling algorithm which can guarantee an expansion of the stability region with respect to prior works. We also provide expressions regarding the distribution of the time needed to be devoted for feedback at each channel in some special cases. The proposed algorithm does not need knowledge of the statistics of the channels and traffic patterns. Simulations illustrate the operation of the proposed scheme.