In this paper, we propose a novel algorithm for video bitrate adaptation in HTTP Adaptive Streaming (HAS), based on online learning. The proposed algorithm, named Learn2Adapt (L2A) , is shown to provide a robust bitrate adaptation strategy which, unlike most of the state-of-the-art techniques, does not require parameter tuning, channel model assumptions, or application-specific adjustments. These properties make it very suitable for mobile users, who typically experience fast variations in channel characteristics. Experimental results, over real 4G traffic traces, show that L2A improves on the overall Quality of Experience (QoE) and in particular the average streaming bitrate, a result obtained independently of the channel and application scenarios.

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.

The advent of elastic Content Delivery Networks (CDNs) enable Content Providers (CPs) to lease cache capacity on demand and at different cloud and edge locations in order to enhance the quality of their services. This article addresses key challenges in this context, namely how to invest an available budget in cache space in order to match spatio-temporal fluctuations of demand, wireless environment and storage prices. Specifically, we jointly consider dynamic cache rental, content placement, and request-cache association in wireless scenarios in order to provide just-in-time CDN services. The goal is to maximize the an aggregate utility metric for the CP that captures both service benefits due to caching and fairness in servicing different end users. We leverage the Lyapunov drift-minus-benefit technique and Jensen's inequality to transform our infinite horizon problem into hour-by-hour subproblems which can be solved without knowledge of future file popularity and transmission rates. For the case of non-overlapping small cells, we provide an optimal subproblem solution. However, in the general overlapping case, the subproblem becomes a mixed integer non-linear program (MINLP). In this case, we employ a randomized cache lease method to derive a scalable solution. We show that the proposed algorithm guarantees the theoretical performance bound by exploiting the submodularity property of the objective function and pick-and-compare property of the randomized cache lease method. Finally, via real dataset driven simulations, we find that the proposed algorithm achieves 154% utility compared to similar static cache storage-based algorithms in a representative urban topology.

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 addresses a fundamental challenge in cloud computing, that of learning an economical yet robust reservation, i.e. reserve just enough resources to avoid both violations and expensive over provisioning. Prediction tools are often inadequate due to observed high variability in CPU and memory workload. We propose a novel model-free approach that has its root in online learning. Specifically, we allow the workload profile to be engineered by an adversary who aims to harm our decisions, and we investigate a class of policies that aim to minimize regret (minimize losses with respect to a baseline static policy that knows the workload sample path). Then we propose a combination of the Lyapunov optimization theory [1] and a linear prediction of the future based on the recent past, used in learning and online optimization problems, see [2]. This enables us to come up with a no regret policy, i.e., a policy whose cost difference to the benchmark and violation constraint residual both grow sublinearly in time, and hence become amortized over the horizon. Our policy has then “no regret and eventually learns the minimum cost reservation subject to a time-average constraint for 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.

Network utility maximization (NUM) is an iconic problem in network traffic management which is at the core of many current and emerging network design paradigms - and, in particular, software-defined networks (SDNs). Thus, given the exponential growth of modern-day networks (in both size and complexity), it is crucial to develop scalable algorithmic tools that are capable of providing efficient solutions in time which is dimension-free, i.e., independent-or nearly-independent-on the size of the system. To do so, we leverage a suite of modified gradient methods known as “mirror descent” and we derive a scalable and efficient algorithm for the NUM problem based on gradient exponentiation. We show that the convergence speed of the proposed algorithm only carries a logarithmic dependence on the size of the network, so it can be implemented reliably and efficiently in massively large networks where traditional gradient methods are prohibitively slow. These theoretical results are sub-sequently validated by extensive numerical simulations showing an improvement of several order of magnitudes over standard gradient methods in large-scale networks.

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.

We study the user association problem in the context of dense networks, where standard adaptive algorithms become ineffective. This paper proposes a novel data-driven technique leveraging the theory of robust optimization. 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. We propose a generalized iterative algorithm, referred to as GRMA, which is shown to converge to the optimal robust map. 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 and find that we can reduce violations from 25% (inflicted by a baseline adaptive algorithm) down to almost zero.

We study the problem of user association in Ultra Dense Networks (UDNs) for two network services; 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 this way, our framework uses the fundamental problem of user association to show that both isolation and statistical multiplexing can be achieved in the context of UDNs, when different services or slices must share BS resources, as envisioned in 5G networks. We demonstrate no violations of the VIP flow constraint on real data traces for mobile network traffic, while a baseline best effort distributed policy applied to this setup inflicts up to 46.5% violations.

The massive scale of future wireless networks will cause computational bottlenecks in performance optimization. In this paper, we study the problem of connecting mobile traffic to Cloud RAN (C-RAN) stations. To balance station load, we steer the traffic by designing device association rules. The baseline association rule connects each device to the station with the strongest signal, which does not account for interference or traffic hot spots, and leads to load imbalances and performance deterioration. Instead, we can formulate an optimization problem to decide centrally the best association rule at each time instance. However, in practice this optimization has such high dimensions, that even linear programming solvers fail to solve. To address the challenge of massive connectivity, we propose an approach based on the theory of optimal transport, which studies the economical transfer of probability between two distributions. Our proposed methodology can further inspire scalable algorithms for massive optimization problems in wireless networks.

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.

Telecommunication networks are converging to a massively distributed cloud infrastructure interconnected with software defined networks. In the envisioned architecture, services will be deployed flexibly and quickly as network slices. Our paper addresses a major bottleneck in this context, namely the challenge of computing the best resource provisioning for network slices in a robust and efficient manner. With tractability in mind, we propose a novel optimization framework which allows fine-grained resource allocation for slices both in terms of network bandwidth and cloud processing. The slices can be further provisioned and auto-scaled optimally based on a large class of utility functions in real-time. Furthermore, by tuning a slice-specific parameter, system designers can trade off traffic-fairness with computing-fairness to provide a mixed fairness strategy. We also propose an iterative algorithm based on the alternating direction method of multipliers (ADMM) that provably converges to the optimal resource allocation and we demonstrate the method's fast convergence in a wide range of quasi-stationary and dynamic settings.

We study the user association problem in the context of dense networks, where standard adaptive algorithms become ineffective. The paper proposes a novel data-driven technique leveraging the theory of robust optimization. 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 allows to accurately balance base station loads. We propose a generic iterative algorithm, referred to as GRMA, which is shown to converge to the optimal robust map. 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 and find that we can reduce violations from 25% (achieved by an adaptive algorithm) down to almost zero.

Allocating resources to network slices can be achieved by means of solving virtual network embedding problems, whereby virtual nodes are used to reserve computing resources on cloud nodes, and virtual links are used to reserve bandwidth resources on network paths. Since the associated optimization problem is also NP-hard to approximate, in this paper we focus on a natural simplified setting of interest: the case where the tunnels can be embedded with splittable flows. For this problem, we provide a simple proof that it is NP-hard by a reduction from the 3-SAT problem. Further, using the idea of the multipartite graph, we propose a poly-time heuristic for the loose capacity constraint case, based on linear relaxation and randomized rounding. This heuristic is shown to have small optimality gaps in extensive simulations.

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.

With elastic CDNs, content providers can rent cache space on demand at different cloud locations in order to enhance their offered quality of service (QoS). This paper addresses a key challenge in this context, namely how to invest an available budget in cache space in order to match spatio-temporal fluctuations of file demand and storage price. Specifically, we consider jointly dynamic cache rental, file placement, and request-cache association in a wireless scenario in order to provide a just-in-time CDN service. The objective is to maximize the benefit in average download delay obtained by the rented caches, while ensuring that the time-average rental cost is less than a fixed budget. We leverage a Lyapunov drift-minus-benefit technique to transform our infinite horizon problem into day-by-day subproblems which can be solved without knowledge of distant future file popularity and transmission rates. For the case of non-overlapping small cells (also wired case) we provide an efficient subproblem solution, referred to as JCC. However, in the general overlapping case, the subproblem becomes a mixed integer non-linear program (MINLP). In this case, we employ a dual decomposition method to derive a scalable solution, namely the JCCA algorithm. Finally, via extensive simulations, we reveal that the proposed JCCA algorithm attains 82.66 % higher delay benefit than existing static cache storage-based algorithms when available average cache budget is 20% of entire file library; moreover, the benefit becomes higher as the average cache budget gets tighter.

This paper has the following ambitious goal: to convince the reader that content caching is an exciting research topic for the future communication systems and networks. Caching has been studied for more than 40 years, and has recently received increased attention from industry and academia. Novel caching techniques promise to push the network performance to unprecedented limits, but also pose significant technical challenges. This tutorial provides a brief overview of existing caching solutions, discusses seminal papers that open new directions in caching, and presents the contributions of this special issue. We analyze the challenges that caching needs to address today, also considering an industry perspective, and identify bottleneck issues that must be resolved to unleash the full potential of this promising technique.

Welcome to the second part of the IEEE JSAC special issue on Caching for Communication Systems and Networks. The goal of this special issue is to present the multiple facets of caching, from information theory to networking and services, and explore the role of memory in communications. This is a very timely topic due to recent technological and theoretical advances summarized in the tutorial paper that appears in the first part of the issue[1].

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.

End-to-end encryption seemingly signifies the death of caching, because current methods ensure that no two sessions are alike. In this paper, we show that servers can reuse encrypted content between sessions, thereby rejuvenating caching. The main idea of our technique is to allow interim nodes to cache content based on pseudo-identifiers instead of real file identities. This enables caching of reusable pseudo-identifiers, whilst maintaining content confidentiality, i.e., ensuring that only the client and the server know the actual identity of the requested file. Furthermore, we provide an extension that prevents client linkability, i.e., ensuring it is impossible to tell if two clients are viewing the same content. Finally, we formally analyse the balance between security and the hit probability performance of the cache.

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.

Legacy networks are often designed to operate with simple single-path routing, like the shortest path, which is known to be throughput suboptimal. On the other hand, previously proposed throughput optimal policies (i.e., backpressure) require every device in the network to make dynamic routing decisions. In this paper, we study an overlay architecture for dynamic routing, such that only a subset of devices (overlay nodes) need to make the dynamic routing decisions. We determine the essential collection of nodes that must bifurcate traffic for achieving the maximum multi-commodity network throughput. We apply our optimal node placement algorithm to several graphs and the results show that a small fraction of overlay nodes is sufficient for achieving maximum throughput. Finally, we propose a threshold-based policy (BP-T) and a heuristic policy (OBP), which dynamically control traffic bifurcations at overlay nodes. Policy BP-T is proved to maximize throughput for the case when underlay paths do no overlap. In all studied simulation scenarios, OBP not only achieves full throughput but also reduces delay in comparison to the throughput optimal backpressure routing.

The backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand. For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and backpressure routing policy, called the loop free backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm and via simulation show that its delay performance is better than that of backpressure.

We study the problem of efficiently disseminating packets in multi-hop wireless networks. At each time slot, the network controller activates a set of non-interfering links and forward selected copies of packets on each activated link. The maximum rate of commonly received packets is referred to as the broadcast capacity of the network. Existing policies achieve the broadcast capacity by balancing traffic over a set of spanning trees, which are difficult to maintain in a large and time-varying wireless network. In this paper, we propose a new dynamic algorithm that achieves the broadcast capacity when the underlying network topology is a directed acyclic graph (DAG). This algorithm is decentralized, utilizes local information only, and does not require the use of spanning trees. The principal methodological challenge inherent in this problem is the absence of work-conservation principle due to the duplication of packets, which renders usual queuing modeling inapplicable. We overcome this difficulty by studying relative packet deficits and imposing in-order delivery constraints to every node in the network. We show that in-order delivery is throughput-optimal in DAGs and can be exploited to simplify the design and analysis of optimal algorithms. Our capacity characterization also leads to a polynomial time algorithm for computing the broadcast capacity of any wireless DAG under the primary interference constraints. In addition, we propose a multiclass extension of our algorithm, which can be effectively used for broadcasting in any network with arbitrary topology. Simulation results show that the our algorithm has a superior delay performance as compared with the traditional tree-based approaches.

In this paper we design throughput-optimal dynamic broadcast algorithms for multi-hop networks with arbitrary topologies. Most of the previous broadcast algorithms route packets along spanning trees, rooted at the source node. For large time-varying networks, computing and maintaining a set of spanning trees is not efficient, as the network-topology may change frequently. In this paper we design a class of dynamic algorithms which make packet-by-packet scheduling and routing decisions and hence, obviate the need for maintaining any global topological structures, such as spanning trees. Our algorithms may be conveniently understood as a non-trivial generalization of the familiar back-pressure algorithm, which makes unicast packet routing and scheduling decisions, based on local queue-length information and does not require to maintain end-to-end paths. However, in the broadcast setting, due to packet duplications, it is hard to define appropriate queuing structures. We design and prove the optimality of a virtual-queue based algorithm, where virtual-queues are defined for subsets of nodes. We then propose a multi-class broadcast policy which combines the above scheduling algorithm with in-class-in-order packet forwarding, resulting in significant reduction in complexity. Finally, we evaluate performance of the proposed algorithms via extensive numerical simulations.

This paper proposes distributed load shedding policies for regulating excessive network load. Data packets are inserted into the network to be delivered to intended destinations. The intermediate network nodes may decide to forward or shed some packets depending on temporally available resources. It is possible for some packets to traverse several nodes in the network until they are finally dropped before reaching the destination, which exacerbates energy consumption. We define a multi-objective optimization problem where we aim to minimize the used energy subject to providing maximum sum throughput. For the case of single-path unicast sessions, we show that Energy-efficient Distributed Load Shedding (E-DLS), a simple shedding mechanism combined with pushback routing, solves this load di shedding optimization. We implement E-DLS in a testbed and use the experiments to select policy parameter values that strike a good balance between energy and delay performance. We then propose a heuristic extension of E-DLS for multirate multicast routing, and showcase via testbed experiments its optimal performance.

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.

This paper addresses a fundamental limitation for the adoption of caching for wireless access networks due to small population sizes. This shortcoming is due to two main challenges: making timely estimates of varying content popularity and inferring popular content from small samples. We propose a framework which alleviates such limitations. To timely estimate varying popularity in a context of a single cache we propose an Age-Based Threshold (ABT) policy which caches all contents requested more times than a threshold N (τ), where τ is the content age. We show that ABT is asymptotically hit rate optimal in the many contents regime, which allows us to obtain the first characterization of the optimal performance of a caching system in a dynamic context. We then address small sample sizes focusing on L local caches and one global cache. On the one hand we show that the global cache learns L times faster by aggregating all requests from local caches, which improves hit rates. On the other hand, aggregation washes out local characteristics of correlated traffic which penalizes hit rate. This motivates coordination mechanisms which combine global learning of popularity scores in clusters and Least-Recently-Used (LRU) policy with prefetching.

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.

We present a novel control scheme that dynamically optimizes multirate multicast. By computing the differential backlog at every node, our scheme adaptively allocates transmission rates per session/user pair in order to maximize throughput. An important feature of the proposed scheme is that it does not require source cooperation or centralized calculations. This methodology leads to efficient and distributed algorithms that scale gracefully and can be embraced by low-cost wireless devices. Additionally, it is shown that maximization of sum utility is possible by the addition of a virtual queue at each destination node of the multicast groups. The virtual queue captures the desire of the individual user and helps in making the correct resource allocation to optimize total utility. Under the operation of the proposed schemes backlog sizes are deterministically bounded, which provides delay guarantees on delivered packets. To illustrate its practicality, we present a prototype implementation in the NITOS wireless testbed. The experimental results verify that the proposed schemes achieve maximum performance while maintaining low complexity.

We study the problem of broadcasting packets in wireless networks. At each time slot, a network controller activates non-interfering links and forwards packets to all nodes at a common rate; the maximum rate is referred to as the broadcast capacity of the wireless network. Existing policies achieve the broadcast capacity by balancing traffic over a set of spanning trees, which are difficult to maintain in a large and time-varying wireless network. We propose a new dynamic algorithm that achieves the broadcast capacity when the underlying network topology is a directed acyclic graph (DAG). This algorithm utilizes local queue-length information, does not use any global topological structures such as spanning trees, and uses the idea of in-order packet delivery to all network nodes. Although the in-order packet delivery constraint leads to degraded throughput in cyclic graphs, we show that it is throughput optimal in DAGs and can be exploited to simplify the design and analysis of optimal algorithms. Our simulation results show that the proposed algorithm has superior delay performance as compared to tree-based approaches.

The backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand.

We study a one-hop broadcast channel with two receivers. The receivers have side information obtained by overhearing wireless channels. The relay takes control decisions by coding transmissions based on its knowledge of side information in the receivers. We consider two control mechanisms. In the ACK system, the relay has definite knowledge of side information announced via overhearing reports. In the NACK system, the relay has statistical knowledge of side information and receives feedback after every decoding failure. Our contribution is as follows. We provide the minimal evacuation times for the two systems and obtain analytical expressions of the throughput region for the ACK and the code-constrained region for the NACK system. When the transmission rates are the same (r1= r2) or when the receiver with the highest transmission rate has perfect side information (pf=1), we show that the two regions are equal. We then provide simple joint xor coding and scheduling policies that achieve those regions and, thus, are throughput optimal. Subsequently, we evaluate the report overhead performance for both mechanisms and reflect on the involved tradeoff with throughput. Ultimately, we demonstrate by simulations that the proposed throughput optimal policies can be appropriately enhanced to have good delay properties, particularly for protocols that utilize sequenced packet delivery.

This work focuses on the design, analysis and evaluation of Dynamic Weighted Round Robin (DWRR) algorithms that can guarantee CPU service shares in clusters of servers. Our motivation comes from the need to provision multiple server CPUs in cloud-based data center environments. Using stochastic control theory we show that a class of DWRR policies provide the service differentiation objectives, without requiring any knowledge about the arrival and the service process statistics. The member policies provide the data center administrator with trade-off options, so that the communication and computation overhead of the policy can be adjusted. We further evaluate the proposed policies via simulations, using both synthetic and real traces obtained from a medium scale mobile computing application.

We consider a system where packets (jobs) arrive for processing using one of the policies in a given class. We study the connection between the minimal evacuation time and the stability region of the system and show that evacuation time optimal policies can be used for stabilizing the system (and for characterizing its stability region) under broad assumptions. Conversely, we show that while a stabilizing policy can be suboptimal in terms of evacuation time, one can always design a randomized version of any stabilizing policy that achieves an optimal evacuation time in the asymptotic regime when the number of evacuated packets scales to infinity.

Multirate multicast improves user quality but complicates network optimization. This paper introduces a novel control scheme to dynamically optimize multirate multicast. We present MMT, an adaptive policy which combines differential backlog scheduling and intelligent packet dropping, both based on local information. MMT is shown to maximize network throughput by adapting to changing conditions such as channel quality, network congestion, and device capabilities. Then, we study the problem of per-receiver network utility maximization. To maximize sum utility we propose the MMU policy, an extension of MMT with receiver-end flow control. Under the operation of both policies backlog sizes are deterministically bounded, which provides delay guarantees on delivered packets. An important feature of the proposed scheme is that it does not require source cooperation or centralized calculations. To illustrate its practicality, we present a prototype implementation in the NITOS wireless testbed. Experimental results verify the optimality of the scheme and its low complexity.

Legacy networks are often designed to operate with simple single-path routing, like shortest-path, which is known to be throughput suboptimal. On the other hand, previously proposed throughput optimal policies (i.e., backpressure) require every device in the network to make dynamic routing decisions. In this work, we study an overlay architecture for dynamic routing such that only a subset of devices (overlay nodes) need to make dynamic routing decisions. We determine the essential collection of nodes that must bifurcate traffic for achieving the maximum multicommodity network throughput. We apply our optimal node placement algorithm to several graphs and the results show that a small fraction of overlay nodes is sufficient for achieving maximum throughput. Finally, we propose a heuristic policy (OBP), which dynamically controls traffic bifurcations at overlay nodes. In all studied simulation scenarios, OBP not only achieves full throughput, but also reduces delay in comparison to the throughput optimal backpressure routing.

We consider the problem of optimal load balancing in a server farm under overload conditions. A convex penalty minimization problem is studied to optimize queue overflow rates at the servers. We introduce a new class of α-fair penalty functions, and show that the cases of α = 0, 1, ∞ correspond to minimum sum penalty, penalty proportional fairness, and min-max fairness, respectively. These functions are useful to maximize the time to first buffer overflow and minimize the recovery time from temporary overload. In addition, we show that any policy that solves an overload minimization problem with strictly increasing penalty functions must be throughput optimal. A dynamic control policy is developed to solve the overload minimization problem in a stochastic setting. This policy generalizes the well-known join-the-shortest-queue (JSQ) policy and uses intelligent job tagging to optimize queue overflow rates without the knowledge of traffic arrival rates.

In this paper, we study the problem of resource allocation in the setting of multitier data centers. Our main motivation and objective is to provide applications hosted in the data center with different service levels. In such centers, there are several mechanisms the designer can use to achieve such objectives. We restrict our attention to CPU time at the service tier as the resource; the objective we consider is service differentiation, expressed as allocating prespecified percentages of this resource to applications. Then, mechanisms at the designer's disposal to provide desired service differentiation include the triplet of load balancing through the switch fabric, enqueueing at a server and scheduling at a server. We focus on the enqueueing component of control mechanisms. We provide, through analysis and simulations “rules of thumb” for situations where simple enqueueing policies can provide service differentiation.

We study an 1-hop broadcast channel with two receivers. Due to overhearing channels, the receivers have side information which can be leveraged by interflow network coding techniques to provide throughput increase. In this setup, we consider two different control mechanisms, the deterministic system, where the contents of the receivers' buffers are announced to the coding node via overhearing reports and the stochastic system, where the coding node makes stochastic control decisions based on statistics and the performance is improved via NACK messages. We study the minimal evacuation times for the two systems and obtain analytical expressions of the throughput region for the deterministic and the code-constrained region for the stochastic. We show that maximum performance is achieved by simple XOR policies. For equal transmission rates r1= r2, the two regions are equal. If r1≠ r2, we showcase the tradeoff between throughput and overhead.

We propose a resource allocation model that captures the interaction between legitimate users of a distributed service provisioning system with malicious intruders attempting to disrupt its operation. The system consists of a bank of servers providing service to incoming requests. Malicious intruders generate fake traffic to the servers attempting to degrade service provisioning. Legitimate traffic may be balanced using available mechanisms in order to mitigate the damage from the attack. We characterize the guaranteed region, i.e. the set of legitimate traffic intensities that are sustainable given specific intensities of the fake traffic, under the assumption that the fake traffic is routed using static policies. This assumption will be relaxed, allowing arbitrary routing policies, in the full version of this work.

We investigate the scalability of multihop wireless communications, a major concern in networking, for the case that users access content replicated across the nodes. In contrast to the standard paradigm of randomly selected communicating pairs, content replication is efficient for certain regimes of file popularity, cache, and network size. Our study begins with the detailed joint content replication and delivery problem on a 2-D square grid, a hard combinatorial optimization. This is reduced to a simpler problem based on replication density, whose performance is of the same order as the original. Assuming a Zipf popularity law, and letting the size of content and network both go to infinity, we identify the scaling laws and regimes of the required link capacity, ranging from$O\!\left(\!\sqrt {N}\right)$down to$O(1)$.

A key consideration in novel communication paradigms in multihop wireless networks regards the scalability of the network. We investigate the case of nodes making random requests on content stored in multiple replicas over the wireless network. We show that, in contrast to the conventional paradigm of random communicating pairs, multihop communication is a sustainable scheme for certain values of file popularity, cache and network size. In particular, we formulate the joint problem of replication and routing and compute an order optimal solution. Assuming a Zipf file popularity distribution, we vary the number of files M in the system as a function of the nodes N, let both go to infinity and identify the scaling regimes of the required link capacity, from O(√N) down to O(1).

We consider a system where jobs (packets) arrive for processing using one of the policies in a given class. We study the connection between the minimal evacuation times and the stability region of the system under the given class of policies. The result is used to establish the equality of information theoretic capacity region and system stability region for the multiuser broadcast erasure channel with feedback.

We consider a mobile connected to a base station, and study how to optimally schedule shutting off its transceiver. First, we study the model from optimal control perspective. We consider off-times (periods of inactivity) of (controlled) duration. We study the question of scheduling "waking up" instants in which the mobile communicates with the base station and checks whether the inactivity period is over. There is a cost proportional to the delay from the moment the off-time ends until the mobile discovers it, a (small) running cost while the mobile is sleeping and a cost for waking up. We present conditions for optimal sleep periods to be constant and derive the optimal period. For the case that the conditions do not hold, we obtain suboptimal solutions which perform strictly better than the optimal constant one. We then investigate optimality restricted to classes of policies with specific constraints. We adopt the parametric optimization approach which entails cost minimization for a given parameterized policy and selection of the best policy among a class. We then compare the performance of optimal policies, of the proposed suboptimal policies as well as that of standard policies like IEEE 802.16e.

The beamforming capacity optimization problem in MISO systems, when the transmitter has both mean and covariance feedback of the channel, has been tackled only with the SNR maximization approach, which is known to give a sub-optimal solution. Numerical solutions of the full rank input covariance matrix, presented in the literature, are capable of tracking the beamforming vector only if it is the optimal capacity achieving solution. In this paper, we solve the beamforming capacity optimization problem by following an analytical approach that projects the beamforming vector on an orthonormal basis defined by the eigenvectors of the channel covariance matrix. The proposed formulation reduces the complexity of calculating the solution and provides intuition into the problem itself. In particular, we express the necessary conditions for beamforming capacity maximization as a system of two equations, which can be solved numerically very efficiently using the secant method. Surprisingly, our indicative numerical results for the 2 x 1 and 10 x 1 MISO systems, showed that for some cases the performance gain through beamforming capacity optimization compared to the SNR maximization approach can reach 0.4 bps/Hz. This means that the SNR maximization solution deviates considerably from the optimal beamforming vector. Finally, the optimality of the SNR maximization solution is also examined.

In a publish/subscribe (pub/sub) network, message delivery is guaranteed for all connected subscribers at publish time. However, in a dynamic mobile scenario where users join and leave the network, it is important that content published at the time they are disconnected is still delivered when they reconnect from a different point. In this paper, we enhance the caching mechanisms in pub/sub networks to enable client mobility. We build our mobility support with minor changes in the caching scheme while preserving the main principles of loose coupled and asynchronous communication of the pub/sub communication model. We also present a new proactive mechanism to reduce the overhead of duplicate responses. The evaluation of our proposed scheme is performed via simulations and testbed measurements.

In current publish/subscribe networks messages are not stored and only active subscribers receive published messages. However, in a dynamic scenario a user may be interested in content published before the subscription time. In this paper, we introduce a mechanism that enables storing in such networks, while maintaining the main principle of loose-coupled and asynchronous communication. Furthermore, we propose a new storage placement and replication algorithm which differentiates classes of content and minimize the clients response latency. The performance of our proposed placement and replication algorithm and the proposed storing mechanism is evaluated via simulations and insights are given for future work.

We consider the sleep mode algorithm of IEEE 802.16e mobile networks where a mobile station may switch off the transceiver and go into sleep mode in order to save power. Depending on the underlying application, different algorithms are defined in the standard. In practice, a hybrid combination of the sleep mode algorithms will be used in a mobile. In this paper, we build a novel performance model that captures the behavior of a single sleep mode algorithm. Moreover, we provide an accurate approximation for the hybrid case. Finally, the model is used to select the standard-compliant sleep window strategy which satisfies a given (approximative) delay constraint and minimizes the energy usage.

In a publish/subscribe network, message delivery is guaranteed for all active subscribers at publish time. However, in a dynamic scenario where users join and leave the network, a user may be interested in content published before the subscription time. In this paper, we introduce mechanisms that enable caching in such networks, while maintaining the main principle of loose-coupled and asynchronous communication. Furthermore we investigate two caching policies; caching in all candidate brokers (basic caching) which yields high survivability and low delay and caching in leaf brokers (leaf caching) which maintains low overhead and querying complexity. The comparison is performed via simulations and testbed measurements and insights are given for future work.

In this paper we underline the importance of utilizing unequal powers in wireless ad hoc networks. Recent results from percolation theory indicate that a threshold exists after which a very large randomly positioned ad hoc network becomes disconnected almost surely for a given communication configuration. In this paper we prove that it is possible to extend the region of connectivity by allocating the transmit power of each node in an intelligent manner.

This paper analyzes a two-hop extension to the coverage of an IEEE 802.16 cell. There is natural degradation in cell capacity due to multihop communications which can be mitigated by spatial reuse, adaptive modulation and coding. We estimate the available capacity by analyzing the random geometry related to the locations of the base station, the sponsor nodes and the mesh subscriber stations situated two hops away from the base station. The results show the trade-offs of extending the coverage area and the decrease of the capacity.

In this paper we compare and enhance the three prevailing approaches of IEEE 802.11e performance analysis. Specifically, the first model utilizes a Markov Chain to describe the state of the Backoff Counter, the second is based on a general probabilistic explanation of the standard and the third forms a queuing network. We have injected, in the proposed models, new ideas to cover the latest update of the QoS-enabled 802.11e standard, and compared all the models showing results regarding the accuracy of each approach. Throughput performance is given for various parameters of the medium while including Gaussian error-prone channel in 802.11b/e. Results are also provided regarding the effect of the Block-ACK feature. The comparison is performed both in terms of accuracy and structural possibilities and finally the results are validated via simulations with Opnet Modeler. The proposed comparison mathematical analysis can also be extended to other applications and wireless protocols.

A number of different approaches have been recently presented for image retrieval using color features. Most of these methods use the color histogram or some variation of it. If the extracted information is to be stored for each image, such methods may require a significant amount of space for storing the histogram, depending on a given image's size and content. In the method proposed, only a small number of features, called chromaticity moments, are required to capture the spectral content (chrominance) of an image. The proposed method is based on the concept of the chromaticity diagram and extracts a set of two-dimensional moments from it to characterize the shape and distribution of chromaticities of the given image. This representation is compact (only a few chromaticity moments per image are required) and constant (independent of image size and content), while its retrieval effectiveness is comparable to using the full chromaticity histogram.

RGB, a nonuniform color space, is almost universally accepted by the image processing community as the means for representing color. On the other hand, perceptually uniform spaces, such as L*a*b*, as well as approximately-uniform color spaces, such as HSV, exist, in which measured color differences are proportional to the human perception of such differences. This paper compares RGB with L*a*b* and HSV in terms of their effectiveness in color texture analysis. There has been a limited but increasing amount of work on the color aspects of textured images. The results have shown that incorporating color into a texture analysis and recognition scheme can be very important and beneficial. The presented methodology uses a family of Gabor filters specially tuned to measure specific orientations and sizes within each color texture. Effectiveness is measured by the classification performance of each color space, as well as by classifier-independent measures. Experimental results are obtained with a variety of color texture Images. Perceptually uniform spaces are shown to outperform RGB in many cases.

Describes a visual monitoring system that performs scene segmentation based on color and texture information. Color information is combined with texture, and corresponding segmentation algorithms are developed to detect and measure changes (loss/gain) in a given scene or environment over a period of time. The xyY color space is used to represent the color information. The two chromaticity coordinates (x, y) are combined into one, thus providing the chrominance (spectral) part of the image, while Y describes the luminance (intensity) information. The proposed color/texture segmentation system processes luminance and chrominance separately. Luminance is processed in three stages: filtering, smoothing and boundary detection. Chrominance is processed in two stages: histogram multi-thresholding and region growing. Two or more images may be combined at the end in order to detect scene changes, using logical pixel operators. As a case study, the methodology is used to determine wetland loss/gain. For comparison purposes, results in both the xyY and HIS (hue, intensity, saturation) color spaces are presented.